On the complexity of bilinear computations

LAUR Repository

Show simple item record

dc.contributor.author Takche, Jean Halim
dc.date.accessioned 2018-04-17T09:22:21Z
dc.date.available 2018-04-17T09:22:21Z
dc.date.copyright 1984 en_US
dc.identifier.uri http://hdl.handle.net/10725/7391
dc.description.abstract Arithmetic complexity theory is the study of the minimum number of non-scalar multiplications required to compute a set of bilinear forms. One can show that we can restrict ourselves to bilinear algorithms. Brockett and Dobkin showed that the problem is equivalent to minimizing the number of rank one matrices that generate a given set of matrices. Strassen used another formulation and reduced the problem to finding the rank of a given three-tensor. One problem of interest in arithmetic complexity is the direct sum conjecture due to Strassen. Given two disjoint bilinear problems S(,1) and S(,2), Strassen conjectured that we can optimally compute their direct sum S(,1) (CRPLUS) S(,2) by optimally computing S(,1) and S(,2) separately. Our contribution is to prove the validity of the direct sum conjecture for a large class of bilinear computations. Assume that S(,1) and S(,2) correspond to r x m x n and s x p x q tensors respectively. We show that the direct sum conjecture is true if 2 (ELEM) r,m,n,s,p,q or r = mn - 2. Then we attack the matrix multiplication problem and improve the best known lower bound on the complexity of multiplying p x q by q x n matrices. We will establish our lower bounds over (,2), and these bounds will obviously hold over . The complexity of a set of bilinear forms is then studied as an invariant under the action of the tensor equivalence group. We find a complete set of invariants, which characterize the class of a pencil modulo the tensor equivalence group, and cannonical forms will be developed. Then we will introduce the notion of weak-equivalence, and find a complete set of invariants of irreducible triples under weak-equivalence. We will also consider special classes of three bilinear forms, and efficient algorithms will be developed, which are optimal in most cases. en_US
dc.language.iso en en_US
dc.title On the complexity of bilinear computations en_US
dc.type Thesis en_US
dc.author.degree PHD en_US
dc.author.school SAS en_US
dc.author.idnumber 198790400 en_US
dc.author.department Computer Science and Mathematics en_US
dc.description.embargo N/A en_US
dc.identifier.ctation Takche, J. H. (1984). On the complexity of bilinear computations. en_US
dc.author.email jtakshi@lau.edu.lb en_US
dc.identifier.tou http://libraries.lau.edu.lb/research/laur/terms-of-use/thesis.php en_US
dc.identifier.url https://dl.acm.org/citation.cfm?id=911876 en_US
dc.publisher.institution Pennsylvania State University en_US
dc.author.affiliation Lebanese American University en_US

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account