Title :
Some techniques for proving certain simple programs optimal
Author :
Hopcroft, J.E. ; Kerr, L.R.
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 :
Commutation; Computational complexity; Computer aided instruction; Computer science; Digital arithmetic; Input variables; Modules (abstract algebra); Polynomials; Registers; Turing machines;
Conference_Titel :
Switching and Automata Theory, 1969., IEEE Conference Record of 10th Annual Symposium on
Conference_Location :
Waterloo, ON, Canada
DOI :
10.1109/SWAT.1969.21