Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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.



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.

Based on that I deduced that Matrix Multiplication is O(n^2 lg n), 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:87­105, 1999. But that was proved to not be the case: T. Amdeberhan and G. Heinig - http://www-math.mit.edu/~tewodros/georgmemoriam.pdf




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: