2
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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

  1. 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.

$\endgroup$
  • $\begingroup$ I think, it is not bad to mention that latter lower bound is proved for matrices with real/complex numbers (which cannot be truly represented on computers) $\endgroup$ – rus9384 Aug 24 '17 at 1:15
  • $\begingroup$ Right, it's for the algebraic complexity model. $\endgroup$ – Yuval Filmus Aug 24 '17 at 6:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.