3 ms·
With regards to matrix multiplication[1]: I think the hidden subtext here is that many people believe there exists a O(n^2) algorithm for matrix multiplication
by fractalsea 13y ago
With regards to matrix multiplication[1]:
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.
- amund 13y agoRan 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. Based on that I deduced that Matrix Multiplication is O(n^2 lg n), http://amundtveit.info/publications/2003/ComplexityOfMatrixInversion.pdf http://amundtveit.info/publications/2003/ComplexityOfMatrixI... 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 http://www-math.mit.edu/~tewodros/georgmemoriam.pdf