patternMinor
Lower Bound of Matrix Multiplication
Viewed 0 times
lowermatrixboundmultiplication
Problem
I am reading the textbook algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani
The authors state in page $67$:
The preceding formula implies an $O(n^3)$ algorithm for matrix multiplication: there are $n^2$ entries to be computed, and each takes $O(n)$ time. For quite a while, this was widely believed to be the best running time possible, and it was even proved that in certain models of computation no algorithm could do better. It was therefore a source of great excitement when in $1969$, the German mathematician Volker Strassen announced a significantly more efficient
algorithm, based upon divide-and-conquer.
The statement that interests my more in this quotation, is:
it was even proved that in certain models of computation no algorithm could do better.
Could anyone support me with some references where I can find a proof of that kind?
The authors state in page $67$:
The preceding formula implies an $O(n^3)$ algorithm for matrix multiplication: there are $n^2$ entries to be computed, and each takes $O(n)$ time. For quite a while, this was widely believed to be the best running time possible, and it was even proved that in certain models of computation no algorithm could do better. It was therefore a source of great excitement when in $1969$, the German mathematician Volker Strassen announced a significantly more efficient
algorithm, based upon divide-and-conquer.
The statement that interests my more in this quotation, is:
it was even proved that in certain models of computation no algorithm could do better.
Could anyone support me with some references where I can find a proof of that kind?
Solution
Strassen, in his paper describing Strassen's algorithm (Gaussian elimination is not optimal) mentions
the result of Klyuyev and Kokovkin-Shcherbak [1] that Gaussian elimination for solving a system of linear equations is optimal if one restricts oneself to operations upon rows and columns as a whole.
The reference is to
The paper is available online.
In modern literature this result is virtually unknown, and I am not aware of any other lower bound on matrix multiplication beyond the $\Omega(n^2)$ lower bounds of Bshouty and Shpilka and the $\Omega(n^2\log n)$ lower bound of Raz.
the result of Klyuyev and Kokovkin-Shcherbak [1] that Gaussian elimination for solving a system of linear equations is optimal if one restricts oneself to operations upon rows and columns as a whole.
The reference is to
- Klyuyev, V. V., and N. I. Kokovkin-Shcherbak: On the minimizations of the number of arithmetic operations for the solution of linear algebraic systems of equations. Translation by G. I. Tee: Technical Report CS 24, June 14, 1965, Computer Science Dept., Stanford University.
The paper is available online.
In modern literature this result is virtually unknown, and I am not aware of any other lower bound on matrix multiplication beyond the $\Omega(n^2)$ lower bounds of Bshouty and Shpilka and the $\Omega(n^2\log n)$ lower bound of Raz.
Context
StackExchange Computer Science Q#80352, answer score: 6
Revisions (0)
No revisions yet.