News for hackers. Stuff that matters.
Re:Matrix multiplication in O(n^2.373) by wbhart on Monday November 28, 2011 @09:56PM (#3288777)
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...

There are no comments on this comment yet.