On the optimal evaluation of a set of n-linear forms

At the heart of a number of arithmetic complexity problems are some basic questions in tensor analysis. Questions regarding the complexity of multiplication operations which are n-linear are most easily studied in a tensor analytic framework. Certain results of tensor analysis are used in this paper to provide insight into the solution of some of these problems. Methods are given to determine a partial ordering on the set of tensors corresponding to a partial ordering with respect to complexity on the set of n-linear operations. Different classes of algorithms for evaluating n-linear operations are studied and a generalized cost criterion is used. Algorithms are given for determining the rank of a class of third order tensors and a canonical form for such tensors is presented. Bounds on the complexity of a wide class of operations are also derived.