Matrix power sum

Question

What is the best way to calculate the sum of matrices such as A ^ i + A ^ (i + 1) + A ^ i + 2 ........ A ^ n for very large n?

I thought of two possible ways:

1) Use the exponent of the logarithmic matrix (LME) for A ^ i, then calculate the subsequent matrices by multiplying by A.

Problem : Doesn't actually use the LME algorithm, since I only use it for the lowest power!

2) Use LME to find A ^ n and memoize intermediate calculations.

Problem: Too much space for large n.

Is there a third way?

Answer 1

Note:

A + A^2 = A(I + A) A + A^2 + A^3 = A(I + A) + A^3 A + A^2 + A^3 + A^4 = (A + A^2)(I + A^2) = A(I + A)(I + A^2) 

Let be

 B(n) = A + ... + A^n 

We have:

 B(1) = A B(n) = B(n / 2) * (I + A^(n / 2)) if n is even B(n) = B(n / 2) * (I + A^(n / 2)) + A^n if n is odd 

So, you will take a logarithmic number of steps and there is no need to calculate the inverse.

While a direct implementation will result in a factor of (log n)^2 , you can store it in log n by computing the credentials of A when computing B

Answer 2

You can use the fact that the sum in n geometric row of matrices is:

 S_n = (IA)^(-1) (IA^n) 

and since you are not starting at 0, you can simply calculate:

 result = S_n - S_i 

where i is your starting index.

Answer 3

Why not just diagonalize the matrix to make multiplication cheap.

edit:

While the matrix is ​​nonsingular, you should be able to find a diagonal representation D of the matrix A such that A = PDP ^ -1, where P is composed of eigenvectors A and D has eigenvalues ​​A along the diagonal. Getting D ^ m = D * D ^ (m-1) is cheap, because you only multiply it diagonally (i.e. as many times as many dimensions of the matrix)

Getting S (m) = S (m-1) + D ^ m is also cheap, because you add only diagonal elements.

Then you have

A ^ i + A ^ (i + 1) + A ^ i + 2 ........ A ^ n = P (D ^ i + D ^ (i + 1) + D ^ i + 2 .. ...... D ^ n) P ^ -1 = P (S (n) - S (i)) P ^ -1

The only difficult task is to find P and P ^ -1