Some techniques for proving certain simple programs optimal

Authors:
  • JHJ. E. Hopcroft
    J. E. Hopcroft
  • LKL. R. Kerr
    L. R. Kerr

Abstract
This paper develops techniques for establishing a lower bound on the number of arithmetic operations necessary for sets of simple expressions. The techniques are applied to matrix multiplication. A modification of Strassen's algorithm is developed for multiplying n × p matrices by p × q matrices. The techniques are used to prove that this algorithm minimizes the number of multiplications for a few special cases. In so doing we establish that matrix multiplication with elements from a commutative ring requires fewer multiplications than with elements from a non-commutative ring.

This publication has 3 references indexed in Scilit: