On commutativity and approximation (Q799369)

The paper deals with lower and upper bounds on the algebraic complexity of bilinear forms based on the rank of the corresponding tensors. It defines the ''commutative border rank'' (cbrk) of a tensor, which is a modification of the definition of ''rank'' so that it can be applied to algorithms that a) only need to approximate the solution and b) make use of commutativity. The following upper and lower bounds on algebraic complexity are derived, using corresponding bounds on cbrk: (i) \(m(n+1)/2\) multiplications are necessary and sufficient for n,m-matrix-vector product. (ii) 6 multiplications are sufficient and 5 are necessary for 2,2-matrix multiplication. (iii) \((n/2)+2\) multiplications are sufficient for approximating the value of a polynomial of degree n at a given point. The last section of the paper gives possible bounds on the exponent of matrix multiplication complexity.