| 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 |