On the Validity of the Direct Sum Conjecture
The direct sum conjecture states that the multiplicative complexity of disjoint sets of bilinear computations is the sum of their separate multiplicative complexities. This conjecture is known to hold for only a few specialized cases. In this paper, we establish its validity for large classes of com...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | article |
| Published: |
2016
|
| Online Access: | http://hdl.handle.net/10725/3520 http://dx.doi.org/10.1137/0215071 http://epubs.siam.org/doi/abs/10.1137/0215071 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | The direct sum conjecture states that the multiplicative complexity of disjoint sets of bilinear computations is the sum of their separate multiplicative complexities. This conjecture is known to hold for only a few specialized cases. In this paper, we establish its validity for large classes of computations. One such class can be defined as follows. Let $S_1 $ be a set of r$m \times n$ bilinear forms, and let $S_2 $ be a different set of s$p \times q$ bilinear forms. Then, if $2 \in \{ r,m,n,s,p,q\} $, we show that the direct sum conjecture holds over any field. The proof involves some nontrivial facts from linear algebra and relies on the theory of invariant polynomials. This result also settles the multiplicative complexity of pairs of bilinear forms over any field with large enough cardinality. It is also shown that the direct sum conjecture is true for the case when $r = mn - 2$. |
|---|