News for hackers. Stuff that matters.
Re:Matrix multiplication in O(n^2.373) by _mrc on Monday November 28, 2011 @08:35PM (#3288537)
The difference between n^2.373 and n^2.376 (i.e. n^0.003) is about 1.3% for n=100, 2% for n=1000, and keeps getting better for large n.

http://www.wolframalpha.com/input/?i=n%5E2.373%2Fn%5E2.376%2...

Re:Matrix multiplication in O(n^2.373) by LokiSnake on Monday November 28, 2011 @10:32PM (#3288896)
When you start applying real numbers to n, using O() doesn't make sense. When comparing the two in a slightly practical sense, the constant factor has to be taken into account.
Re:Matrix multiplication in O(n^2.373) by regularfry on Tuesday November 29, 2011 @05:06AM (#3289782)
If I understand correctly, in this case you can directly compare them - the algorithm is the same, so the constant factors are the same.

However, this is in so many ways not my field, so I could easily have completely misunderstood.

Re:Matrix multiplication in O(n^2.373) by dalke on Tuesday November 29, 2011 @07:58AM (#3290110)
You do not understand correctly. Compare the ratio of the quadratic f(n) = 1E100 + n2 to the linear g(n) = 1E100 + n. Using n=100 and n=1000 the ratio is effectively 1.0. You need to get to n=100000000000000000000000000000000000000000000000000 before the ratio is 2.
Re:Matrix multiplication in O(n^2.373) by regularfry on Tuesday November 29, 2011 @12:59PM (#3291343)
I see your point - we can compare the powers that n is raised to, but without knowing the constant factor we can't know the proportion of the result that it is responsible for.
Re:Matrix multiplication in O(n^2.373) by wbhart on Monday November 28, 2011 @09:15PM (#3288651)
Except that this algorithm can't be used for anything as small as n = 100. Essentially the analysis is asymptotic, meaning that you have matrices of dimension n = q^N and let N tend towards infinity to get your bound on omega.