Hacker News Reader

Comment by flourpower | Hacker News Reader

I couldn't find this by googling - if A is an n by n matrix, can you get A^k strictly faster than you can get a product of k arbitrary n by n matrices?

View on HN

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.

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.

Yes, see the Cayley-Hamilton Theorem[1], which changes matrix powering into the powering of scalers in the characteristic polynomial.

[1] - http://en.wikipedia.org/wiki/Cayley%E2%80%93Hamilton_theorem

Ah yes, one can compute P(x) a polynomial such that P(A) = 0. If you wish to compute A^n for n much bigger than the degree of P you can compute S(x) = x^n mod P(x) and then just compute S(A).

However, algorithms that do actually improve the complexity of powering when this technique isn't applicable do exist. Here is a paper on a recent one:

http://marco.bodrato.it/papers/Bodrato2010-StrassenLikeMatri...

Reply on news.ycombinator.com