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?
Asked
Active
Viewed 250 times
1 Answers
6
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.
Tom Oldfield
- 13,034
- 1
- 39
- 77
-
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 09 '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 09 '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 09 '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 09 '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? – hmakholm left over Monica Dec 09 '12 at 17:57
-
@HenningMakholm The number of operations is equal to the length of the binary representation of the number plus the number of 1's in that binary representation. It's way more than a trillion technically – user51819 Dec 09 '12 at 17:59
-
@user51819: Okay, 150 billion decimal digits, then. Again, what do you need so large exponents for? How do you even store them? Half a trillion bits is about 64 gigabytes, just to store the value of the exponent. – hmakholm left over Monica Dec 09 '12 at 18:01
-
@HenningMakholm Technically I am taking the modulus of each step. I am trying to see if I can take advantage of different powers so I don't have to store the full number at any step. Powers of 2 are not going to suffice. – user51819 Dec 09 '12 at 18:06
-
@user51819: Why do you think powers of 2 will not suffice? I will now ask for the third time: How do you store your exponents now? – hmakholm left over Monica Dec 09 '12 at 18:08
-
I don't know yet. That's what I technically made this question for, since the answer will ultimately dictate how they are stored. Please do not be so condescending. – user51819 Dec 09 '12 at 18:08
-
@user51819: Where do you get your exponents from? How does the process that decides on the exponents you need to use deliver them to you? – hmakholm left over Monica Dec 09 '12 at 18:09
-
Because I can directly calculate the number of divisions for smaller powers (the binary method I mentioned earlier) and can extrapolate them for larger powers and therefore I know that past a certain point, it's no longer humanly possible to wait that long for so many divisions – user51819 Dec 09 '12 at 18:11
-
@user51819: Where do you get your exponents from? How does the process that decides on the exponents you need to use deliver them to you? – hmakholm left over Monica Dec 09 '12 at 18:12
-
I know how to handle matrices of very large size and small reasonable powers. I do not yet know how to handle small matrices with very large powers. I want to see if this can be circumvented by using different power structures. – user51819 Dec 09 '12 at 18:13
-
@user51819: Where do you get your exponents from? How does the process that decides on the exponents you need to use deliver them to you? (And what do you mean by "humanly possible"? If you're needing to handle exponents on the order of $2^{1.000.000.000.000}$, then certainly you're not planning to do it on paper). – hmakholm left over Monica Dec 09 '12 at 18:15
-
@HenningMakholm Pick a power, any power. It doesn't matter what it is; it just has to be too large to calculate in this lifetime by doing standard exponentiation by squaring. And no, I am doing this on the computer (not on paper). – user51819 Dec 09 '12 at 18:16
-
@user51819: If you can write down the exponent in any reasonable notation during your lifetime, then surely that lifetime will be enough to do exponentiation by squaring. The running time is linear in the length of the written representation of the exponent! (And you still have not answered where you're getting your exponents from). – hmakholm left over Monica Dec 09 '12 at 18:21
-
Also representing the result of $M^{2^{10^{12}}}$ is probably not possible even if you turn all the silicon in the earth into computers. (Except in pathological cases such as permutation matrices, which are best handled by specialized techniques for that case specifically). – hmakholm left over Monica Dec 09 '12 at 18:23
-
I have answered your question already, please stop asking it. Just pick any arbitrarily large power. I am really not appreciating your condescension. – user51819 Dec 09 '12 at 18:25
-
@user51819: No you haven't. I'm claiming that it is impossible to find any reasonable use for raising matrices to a power that has trillions of bits. You persist is claiming that you have a power you want to raise the matrix to that has trillions of bits, without revealing where you're getting such a large power from, or why you're interested in raising matrices to such ridiculous powers. I think you're laboring under a misapprehension about how many bits it takes to represent a large number. It allways takes less than four times the number of decimal digits ... – hmakholm left over Monica Dec 09 '12 at 18:28
-
... so if you can afford doing something for each decimal digit, there is absolutely no reason why you shouldn't be able to do something simpler once for each bit. If you want to say this is not true, you've got to come up with something else than bald assertions that your secret exponents has more bits than one could conceivably do something for in a lifetime. – hmakholm left over Monica Dec 09 '12 at 18:30
-
Alright then, thanks. – user51819 Dec 09 '12 at 18:30
-
@TomOldfield Would you be able to elaborate a bit more on Jordan normal form and how it is easier to operate on? – user51819 Dec 09 '12 at 18:38
-
No problem. It's essentially because $k^{th}$powers of any block diagonal matrix are just the matrices produced by taking the $k^{th}$ power of each block. Jordan form is especially nice because the blocks are mostly $0$s and $1$s, which interact in a nice way under matrix multiplication. Try computing powers of a few Jordan blocks by hand to see what I mean. – Tom Oldfield Dec 09 '12 at 18:41
-
@TomOldfield I guess my question is that since my exponent in this case would be too large to do powers-of-two because there would be too many divisions involved, does Jordan form reduce the number of total divisions needed? – user51819 Dec 09 '12 at 18:48
-
It doesn't reduce the number of divisions needed, but that problem is insurmountable, if you have an extremely large exponent powers will always take a very long time to compute. What it does is reduce the number of additions and multiplications required to compute each power with matrix multiplication. – Tom Oldfield Dec 09 '12 at 18:51
-
@TomOldfield So if my exponent is k^(k^m) then there's no way to take advantage of exponentiation by k'ing or anything similar to that to reduce the number of divisions by just using squares alone? Solving k^(k^m) in terms of k^(k^(m-1))... etc until it is something I can calculate? – user51819 Dec 09 '12 at 19:00
-
@user51819 No, not really. As I said earlier, squaring is easy, anything else is harder because you need to square first anyway. – Tom Oldfield Dec 09 '12 at 19:03