The power of commutativity
Author:
- Laurent HyafilLHLaurent Hyafil
- 1 September 1977
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 171-174
Abstract
In this paper we show that the computation of the determinant requires an exponential number of multiplications if the commutativity of indeterminates is not allowed. The determinant can be computed in polynomial time with the commutation of indeterminates. Hence the use of commutativity can reduce a computation of exponential complexity to a computation of polynomial complexity.Keywords
This publication has 5 references indexed in Scilit:
- On Obtaining Upper Bounds on the Complexity of Matrix Multiplication1972
- Evaluation of Rational Functions1972
- Sur le calcul des produits de matricesNumerische Mathematik, 1971
- On Minimizing the Number of Multiplications Necessary for Matrix MultiplicationSIAM Journal on Applied Mathematics, 1971
- On the number of multiplications necessary to compute certain functionsCommunications on Pure and Applied Mathematics, 1970