What is the fastest algorithm for multiplication of two n-digit numbers?
What is the fastest algorithm for matrix multiplication?
I think those "What is the fastest" questions are relative. In my opinion, they are not unsolved problem. There are already solutions for them. And in those current solutions, there is of course the fastest.
When a faster algorithm is formulated, a time will come where another algorithm will perform much better.
EDIT: Now I get it. That "fastest" is in terms of time complexity. Thanks guys. :)
An Algorithm with a lower time complexity will always take a shorter amount of time once the problem size grows large enough. You could run one algorithm on a modern cpu, utilizing Simd and tune for cache coherency and the other in QBASIC on an old 386 and the O(n log n) algorithm would still terminate earlier than the O(n^2) one past a certain n.
the problem is that while dropping from n^2 to n log n is a big deal, dropping from (n log n) to n won't help much if you end up increasing the constant costs at the same time.
It's talking about big O time complexity, which means you have to prove that there can be no faster algorithm. For example comparison sort (so no radix) can be no faster than O(nlogn).
I think the hidden subtext here is that many people believe there exists a O(n^2) algorithm for matrix multiplication, but it has not been discovered yet.
[1] Wouldn't be surprised if this is the case for the other problem too, although I don't know much about it.
Ran Raz proved that Matrix Inversion is O(n^2 lg n), ref: Ran Raz. On the Complexity of Matrix Product. SIAM Journal on Computing,
32(5):1356–1369, 2003.
Regarding even faster operations, it has been hypothetized that all matrices are Toeplitz or Hankel (which have O(n lg n) algorithms), ref: D. S. Mackey, N. Mackey, and S. Petrovic. Is Every Matrix Similar to a Toeplitz
Matrix. Linear Algebra & its Applications, 297:87105, 1999.
But that was proved to not be the case:
T. Amdeberhan and G. Heinig - http://www-math.mit.edu/~tewodros/georgmemoriam.pdf
What is the fastest algorithm for matrix multiplication?
I think those "What is the fastest" questions are relative. In my opinion, they are not unsolved problem. There are already solutions for them. And in those current solutions, there is of course the fastest.
When a faster algorithm is formulated, a time will come where another algorithm will perform much better.
EDIT: Now I get it. That "fastest" is in terms of time complexity. Thanks guys. :)