News for hackers. Stuff that matters.
Re:Matrix multiplication in O(n^2.373) by Rhapso on Monday November 28, 2011 @10:36PM (#3288913)
Just spending 30 seconds looking at it, think of it like the bit shifting solution to multiplication, do a related faster operation then correct.

You can reduce A^k to be a lot faster if you calculate A^2 then A^4 then A^8 .. A^N where N is 2^(Log(k)-1) (log base 2) then multiply A^N by A^(k-N) (which you can speedup using the same method if it is larger then 4)

That was a bit rough and quick, but the basic idea, is that doing (nxn)^k would likely be reduced to O(log(k)n^2.373) versus the more naive O(kn^2.373) which is a speedup of O(k/log(k)) (or it's inverse, I am not sure how it is best to represent the ratio) which is decent, I am sure there is a better solution out there.

Re:Matrix multiplication in O(n^2.373) by wbhart on Monday November 28, 2011 @11:32PM (#3289063)
Multiplying k arbitrary matrices can be done in less time than O(kn^omega). But certainly for k > 3 you wouldn't multiply naively k times as you've pointed out.