On the complexity of bilinear computations
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 on...
Saved in:
| Main Author: | |
|---|---|
| Format: | masterThesis |
| Published: |
1984
|
| Online Access: | http://hdl.handle.net/10725/7391 http://libraries.lau.edu.lb/research/laur/terms-of-use/thesis.php https://dl.acm.org/citation.cfm?id=911876 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1864513482093756416 |
|---|---|
| author | Takche, Jean Halim |
| author_facet | Takche, Jean Halim |
| author_role | author |
| dc.creator.none.fl_str_mv | Takche, Jean Halim |
| dc.date.none.fl_str_mv | 1984 2018-04-17T09:22:21Z 2018-04-17T09:22:21Z 2018-04-17 |
| dc.identifier.none.fl_str_mv | http://hdl.handle.net/10725/7391 Takche, J. H. (1984). On the complexity of bilinear computations. http://libraries.lau.edu.lb/research/laur/terms-of-use/thesis.php https://dl.acm.org/citation.cfm?id=911876 |
| dc.language.none.fl_str_mv | en |
| dc.publisher.none.fl_str_mv | Pennsylvania State University |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.title.none.fl_str_mv | On the complexity of bilinear computations |
| dc.type.none.fl_str_mv | Thesis info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/masterThesis |
| description | 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. |
| eu_rights_str_mv | openAccess |
| format | masterThesis |
| id | LAURepo_ce58c2bbba99f2e22921c910869f1ce8 |
| identifier_str_mv | Takche, J. H. (1984). On the complexity of bilinear computations. |
| language_invalid_str_mv | en |
| network_acronym_str | LAURepo |
| network_name_str | Lebanese American University repository |
| oai_identifier_str | oai:laur.lau.edu.lb:10725/7391 |
| publishDate | 1984 |
| publisher.none.fl_str_mv | Pennsylvania State University |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | On the complexity of bilinear computationsTakche, Jean HalimArithmetic 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.N/APennsylvania State University2018-04-17T09:22:21Z2018-04-17T09:22:21Z19842018-04-17Thesisinfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/masterThesishttp://hdl.handle.net/10725/7391Takche, J. H. (1984). On the complexity of bilinear computations.http://libraries.lau.edu.lb/research/laur/terms-of-use/thesis.phphttps://dl.acm.org/citation.cfm?id=911876eninfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/73912021-03-19T10:43:12Z |
| spellingShingle | On the complexity of bilinear computations Takche, Jean Halim |
| status_str | publishedVersion |
| title | On the complexity of bilinear computations |
| title_full | On the complexity of bilinear computations |
| title_fullStr | On the complexity of bilinear computations |
| title_full_unstemmed | On the complexity of bilinear computations |
| title_short | On the complexity of bilinear computations |
| title_sort | On the complexity of bilinear computations |
| url | http://hdl.handle.net/10725/7391 http://libraries.lau.edu.lb/research/laur/terms-of-use/thesis.php https://dl.acm.org/citation.cfm?id=911876 |