On The Complexity Of Symmetric Computations*
- 1 February 1974
- journal article
- research article
- Published by Taylor & Francis in INFOR: Information Systems and Operational Research
- Vol. 12 (1) , 71-86
- https://doi.org/10.1080/03155986.1974.11731565
Abstract
The paper demonstrates the equivalence of bilinear chains and matrix multiplication algorithms which do not assume commutativity of multiplication. This equivalence is exploited to obtain the main symmetry result, that the same lower bound on the number of multiplications required to compute each of the six matrix products of the form (m × n n × p n × m m × p p × m m × n m × p p × n n × p p × m) holds. An example is given to illustrate the technique of constructing algorithms for computing (m,n,p) and (p, m, n) niarix products from any given algorithm for computing an (m,n,p) matrix product. Finally, the main theorem is used to obtain a newj lower bound on the coniplexity of general matrix multiplication.Keywords
This publication has 7 references indexed in Scilit:
- On the optimal evaluation of a set of n-linear formsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1973
- Duality applied to the complexity of matrix multiplications and other bilinear formsPublished by Association for Computing Machinery (ACM) ,1973
- On Obtaining Upper Bounds on the Complexity of Matrix MultiplicationPublished by Springer Nature ,1972
- On multiplication of 2 × 2 matricesLinear Algebra and its Applications, 1971
- Fast matrix multiplicationPublished by Association for Computing Machinery (ACM) ,1971
- Gaussian elimination is not optimalNumerische Mathematik, 1969
- ON THE NUMBER OF MULTIPLICATIONS REQUIRED TO COMPUTE CERTAIN FUNCTIONSProceedings of the National Academy of Sciences, 1967