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
.