On the optimal evaluation of a set of bilinear forms

ABSTRACT

Although general theories are beginning to emerge in the area of automata based complexity theory, there are very few general methods or even general problem formulations in the area of arithmetic complexity. In this paper we propose and defend a general model for studying bilinear multiplication in order to provide a common framework for discussing a wide class of problems. At the heart of a number of problems in minimizing the number of multiplications required to perform a calculation is a problem in matrix algebra relating to the expansion of a given set of matrices as linear combinations of rank one matrices. In this paper we make a systematic attack on this problem and derive some general results which unify and extend numerous known results. Among the new results given here to illustrate the strength of this approach is a new lower bound on the number of multiplications required for n by n matrix multiplication of 3n2-3n+1 which is independent of the subset of the reals with respect to which multiplication is regarded as free. An even sharper bound is obtained if this set is restricted to the integers.

REFERENCES

• 1: V. Strassen, "Evaluation of Rational Functions," in Complexity of Computer Computations, (R. Miller and J. Thatcher, editors), Plenum Press, 1972.
• 2: C.M. Fiduccia, "On Obtaining Upper Bounds on the Complexity of Matrix Multiplication," in Complexity of Computer Computations, (R. Miller and J. Thatcher, editors), Plenum Press, 1972.
• 3: N. Gastinel, "Sue le calcul des products de matrices," Numerische Mathematik, Vol. 17, 1971, pp. 222-229.
• 4: J. Hopcroft and J. Musinski, "Duality Applied to the Complexity of Matrix Multiplication and other Bilinear Forms," Cornell Computer Science Report TR 72-147, 1972.
• 5: S. Winograd, "On the Number of Multiplications Necessary to Compute Certain Functions," Comm. Pure Appl. Math., Vol. 23, pp. 165-179, 1970.
• 6: J. Hopcroft and L. Kerr, "On Minimizing the Number of Multiplications Necessary for Matrix Multiplication," SIAM J. Appl. Math., Vol. 20, pp. 30-36, 1971.
• 7: L. Calabi and E. Myrvaagnes, "On the Minimal Weight of Binary Group Codes," IEEE PGIT, Vol. 10, pp. 385-7, 1964.
• 8: D. Dobkin, "N-Linear Multiplication Systems," to appear.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

General Terms:
Theory