Some techniques for proving certain simple programs optimal
- 1 October 1969
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
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.Keywords
This publication has 3 references indexed in Scilit:
- ON THE NUMBER OF MULTIPLICATIONS REQUIRED TO COMPUTE CERTAIN FUNCTIONSProceedings of the National Academy of Sciences, 1967
- A Machine-Independent Theory of the Complexity of Recursive FunctionsJournal of the ACM, 1967
- METHODS OF COMPUTING VALUES OF POLYNOMIALSRussian Mathematical Surveys, 1966