algorithm - Is there any fast method of matrix exponentiation?

Question

Is there any faster method of matrix exponentiation to calculate Mⁿ (where M is a matrix and n is an integer) than the simple divide and conquer algorithm?

Answer 1

You could factor the matrix into eigenvalues and eigenvectors. Then you get

M = V^-1 * D * V

Where V is the eigenvector matrix and D is a diagonal matrix. To raise this to the Nth power, you get something like:

M^n = (V^-1 * D * V) * (V^-1 * D * V) * ... * (V^-1 * D * V)
    = V^-1 * D^n * V

Because all the V and V^-1 terms cancel.

Since D is diagonal, you just have to raise a bunch of (real) numbers to the nth power, rather than full matrices. You can do that in logarithmic time in n.

Calculating eigenvalues and eigenvectors is r^3 (where r is the number of rows/columns of M). Depending on the relative sizes of r and n, this might be faster or not.