Is there any fast method of matrix exponentiation?

algorithm linear-algebra matrix-multiplication
Akashdeep Saluja picture Akashdeep Saluja · Sep 7, 2012 · Viewed 23.3k times · Source

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

Answer

Michael picture Michael · Sep 7, 2012

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.

Related questions

Efficient multiplication of very large matrices in MATLAB

I don't have enough memory to simply create a diagonal D-by-D matrix, since D is large. I keep getting an 'out of memory' error. Instead of performing M x D x D operations in the first multiplication, I do M …

Read More
Python Inverse of a Matrix

How do I get the inverse of a matrix in python? I've implemented it myself, but it's pure python, and I suspect there are faster modules out there to do it.

Read More
Algorithm for intersection of 2 lines?

I have 2 lines. Both lines containing their 2 points of X and Y. This means they both have length. I see 2 formulas, one using determinants and one using normal algebra. Which would be the most efficient to calculate and what does …

Read More