Optimum computation of p bilinear forms

AbstractWe wish to answer the following question: p matrices Bi, of the same dimension, being given, what is the minimum number of multiplications we have to perform to obtain the p values XtBiY, for arbitrary vectors X and Y? We will give first a precise definition of the class of algorithms we consider to evaluate these p bilinear forms, and of our optimization criteria. Then we will characterize an optimal algorithm of this class, and relate the minimum number of multiplications used to the tensorial rank of the p matrices Bi. Properties of this number are given. Finally, the paper will conclude with a proof of the optimality of Strassen's algorithm to perform the product of two 2×2 matrices