7
$\begingroup$

Is there an algorithm to raise a matrix to the $n$th power in $O(\log n)$ time? I have been searching online, but have been unsuccessful thus far.

$\endgroup$
  • 1
    $\begingroup$ You mean you have a fixed size matrix? in fact if your matrix is of size $m$ you can't expect to find $O(log \ n)$ algorithm. $\endgroup$ – user742 Oct 10 '12 at 19:13
  • $\begingroup$ People usually refer to this problem as matrix powering. Matrix exponentiation means finding $e^X$ $\endgroup$ – Shitikanth Oct 10 '12 at 19:41
  • $\begingroup$ @Shitikanth Ok, thanks. I shall change that now. $\endgroup$ – Jack H Oct 10 '12 at 19:47
11
$\begingroup$

Here is the pseudocode for an $O(\lg n)$ matrix exponentiation algorithm. Note that the * operator denotes ordinary matrix multiplication.

MATHPOWER (M, n)
if n == 1
    then return M
else
    P = MATHPOWER (M, floor(n/2))
    if n mod 2 == 0
        then return P * P
    else
        return P * P * M
$\endgroup$
5
$\begingroup$

There are two other algorithms which may or may not be relevant. The first algorithm diagonalizes your matrix (which is usually possible), writing it as $M = PDP^{-1}$, where $M,D$ in general may be complex-valued. You then compute $M=PD^nP^{-1}$. Note it's very easy to raise a diagonal matrix to the $n$th power. If $M$ is not diagonalizable, you find its Jordan form and proceed as before (now you also have to calculate some binomial coefficients). This algorithm is probably not numerically stable.

Another algorithm uses the fact that $M$ satisfies its characteristic polynomial (or even its minimal polynomial). Suppose $P(M) = 0$ for some $P$, say the characteristic polynomial. Then we can compute $M^n$ over $\mathbb{R}[M]/(P(M))$, and then substitute $M$. That means that we calculate $M^n$ as a polynomial, using the fact that $P(M) = 0$, and only at the end substitute the values of $M$. We could even precompute all the necessary powers of $M$ and all the values of $M^k \pmod{P(M)}$ for $k < 2\deg P-1$, and then this algorithm could be faster than the algorithm is Massimo Cafaro's answer. It might be more numerically stable than the previous algorithm.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.