Optimal Evaluation of Pairs of Bilinear Forms

Abstract

A large class of multiplication problems in arithmetic complexity can be viewed as the simultaneous evaluation of a set of bilinear forms. This class includes the multiplication of matrices, polynomials, quaternions, Cayley and complex numbers. Considering bilinear algorithms, the optimal number of nonscalar multiplications can be described as the rank of a three-tensor or as the smallest member of rank one matrices necessary to include a given set of matrices in their span. In this paper, we attack a rather large subclass of three-tensors, namely that of $(p,q,2)$-tensors, for arbitrary p and q, and solve it completely in the case where the field of constants contains the roots of a polynomial associated with the given tensor. In all other cases, we prove that, in general, our bounds cannot be improved. The complexity of a general pair of bilinear forms is determined explicitly in terms of parameters related to Kronecker’s theory of pencils and to the theory of invariant polynomials. This reveals unexpected results and shows explicitly the dependence on the algebraic structure of the constants; we display, for example, a pair of $3 \times 3$ bilinear forms whose complexity is 3 over the field $Z_7 $ and which, however, requires exactly 4 nonscalar multiplications over the fields $Z_5 $ or $Z_{11} $. Corresponding optimal algorithms are described and several applications are considered.