1
$\begingroup$

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?

1 Answers 1

5

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.

  • 0
    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.2012-12-09
  • 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.2012-12-09
  • 0
    @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.2012-12-09
  • 0
    But with very large n, you can't exponentiate by squares because there would be many many trillions+ of divisions required2012-12-09
  • 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?2012-12-09
  • 0
    @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 technically2012-12-09
  • 0
    @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.2012-12-09
  • 0
    @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.2012-12-09
  • 0
    @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_?2012-12-09
  • 0
    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.2012-12-09
  • 0
    @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?2012-12-09
  • 0
    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 divisions2012-12-09
  • 0
    @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?2012-12-09
  • 0
    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.2012-12-09
  • 0
    @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).2012-12-09
  • 0
    @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).2012-12-09
  • 0
    @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).2012-12-09
  • 0
    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).2012-12-09
  • 0
    I have answered your question already, please stop asking it. Just pick any arbitrarily large power. I am really not appreciating your condescension.2012-12-09
  • 0
    @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** ...2012-12-09
  • 0
    ... 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.2012-12-09
  • 0
    Alright then, thanks.2012-12-09
  • 0
    @TomOldfield Would you be able to elaborate a bit more on Jordan normal form and how it is easier to operate on?2012-12-09
  • 0
    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.2012-12-09
  • 0
    @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?2012-12-09
  • 0
    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.2012-12-09
  • 0
    @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?2012-12-09
  • 0
    @user51819 No, not really. As I said earlier, squaring is easy, anything else is harder because you need to square first anyway.2012-12-09