
doi: 10.1137/0215071
handle: 10725/3520
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\).
bilinear computations, Analysis of algorithms and problem complexity, multiplicative complexity, algebraic complexity, direct sum conjecture, Symbolic computation and algebraic computation, bilinear forms
bilinear computations, Analysis of algorithms and problem complexity, multiplicative complexity, algebraic complexity, direct sum conjecture, Symbolic computation and algebraic computation, bilinear forms
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 19 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
