Algebras Having Linear Multiplicative Complexities
- 1 April 1977
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 24 (2) , 311-331
- https://doi.org/10.1145/322003.322014
Abstract
The foundations are laid for a theory of multiplicative complexity of algebras and it is shown how “multiplication problems” such as multiplication of matrices, polynomials, quaternions, etc., are instances of this theory. The usefulness of the theory is then demonstrated by utilizing algebraic ideas and results to derive complexity bounds. In particular linear upper and lower bounds for the complexity of certain types of algebras are established.Keywords
This publication has 14 references indexed in Scilit:
- On the complexity of quaternion multiplicationInformation Processing Letters, 1975
- Duality Applied to the Complexity of Matrix Multiplication and Other Bilinear FormsSIAM Journal on Computing, 1973
- Evaluation of Rational FunctionsPublished by Springer Nature ,1972
- Algebraic theory of finite fourier transformsJournal of Computer and System Sciences, 1971
- Linear Associative AlgebrasPublished by Elsevier ,1971
- Fast matrix multiplicationPublished by Association for Computing Machinery (ACM) ,1971
- Gaussian elimination is not optimalNumerische Mathematik, 1969
- An algorithm for the machine calculation of complex Fourier seriesMathematics of Computation, 1965
- Vectors and MatricesPublished by American Mathematical Society (AMS) ,1943
- Structure of AlgebrasPublished by American Mathematical Society (AMS) ,1939