Matrix power sum

Question

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

I have thought of two possible ways:

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

Problem: Doesn't really take advantage of the LME algorithm as i am using it only for the lowest power!!

2)Use LME for finding A^n and memoize the intermediate calculations.

Problem: Too much space required for large n.

Is there a third way?

Answer 1

Notice that:

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

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 be doing a logarithmic number of steps and there is no need to compute inverses.

While a direct implementation will lead to a (log n)^2 factor, you can keep it at log n by computing the powers of A as you compute B.