Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a 4x4 matrix $M$ and a 4-length vector $V$, and I want to find $M^k\times V$ for very large $k$. Even if I did exponentiation by squaring, there would be way too many steps involved in terms of halving $k$ simply because it is so large. Is there a better way?

share|improve this question

1 Answer 1

up vote 5 down vote accepted

Write $M = PJP^{-1}$ where $J$ is in Jordan normal form. Then $M^k = PJ^kP^{-1}$, and powers of Jordan normal form matrices are much easier to compute.

share|improve this answer
    
Is there a way to do the exponentiation by powers of 10 instead of 2, by any chance? I'm not sure if Jordan form will let me do what I want. –  user51819 Dec 9 '12 at 17:35
1  
@user51819 Not really, exponentiation by squaring works because squares are easy to compute, $10^{th}$ powers aren't. What do you want to do that Jordan form won't let you do? I'm pretty sure it will let you do whatever you want. –  Tom Oldfield Dec 9 '12 at 17:41
    
@user51819 exponentiation by squares will still be helpful. Alternatively you could find $M^10 = N$ and then compute $N^{10^n}$ although I'd imagine squares would be faster. (I'm not totally sure though). Regardless, using Jordan form will also hugely reduce the number of computations required, especially if it's diagonal or nearly diagonal. –  Tom Oldfield Dec 9 '12 at 17:53
    
But with very large n, you can't exponentiate by squares because there would be many many trillions+ of divisions required –  user51819 Dec 9 '12 at 17:54
1  
@user51819: You only need a trillion divisions for exponentiation by squares if the decimal representation of the exponent has about 300 billion digits. What on earth do you need so large exponents for, and how do you represent them in the first place? –  Henning Makholm Dec 9 '12 at 17:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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