DocumentCode :
2200188
Title :
Some techniques for proving certain simple programs optimal
Author :
Hopcroft, J.E. ; Kerr, L.R.
fYear :
1969
fDate :
15-17 Oct. 1969
Firstpage :
36
Lastpage :
45
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Switching and Automata Theory, 1969., IEEE Conference Record of 10th Annual Symposium on
Conference_Location :
Waterloo, ON, Canada
ISSN :
0272-4847
Type :
conf
DOI :
10.1109/SWAT.1969.21
Filename :
4569600
Link To Document :
بازگشت