What is the most efficient method to compute recuversively (sparse) matrix power?

Question

I have a sparse matrix $P$ and I want to take its $n$-th power.

more precisely my problem is "is it better to make

for k=1:n
   result(k)=result(k-1)+P^k;
end

or

temp=eye(size(P))
for k=1:n
   temp=temp*P
   result(k)=result(k-1)+temp;
end

?". The two methods should give the same results. If yes, then why?

(Note that I am not finding for the most efficient way to compute a sparse matrix but just to compare the two methods).

Answer 1

I assume that $P\in M_m$, $P$ has $km$ non zero entries (with $k/m$ small) and you want to calculate $I+P+\cdots +P^n$ (clearly both methods give the previous result when $result(0)=I_m$). Assume also that $n$ is a large number; the fact that $P^i$ is sparse or is not sparse, for $i<n$ large enough, depends on the choice of non-zero entries.

For example, if $P$ is a band matrix, then the $P^i$ 's quickly become non-sparse.

Another example: for $m=100,k=2$, in general, $P^{10}$ is non-sparse.

In the sequel, we assume that the $(P^i)$ are non-sparse. The complexity of the first method is

$\sim\sum_{i=1}^n \log(i)m^3\sim n\log(n)m^3$.

The complexity of the second method is $\sim nm^2k$ (each step has complexity $m^2k$ for $i$ large enough).

Then the best method is the second one.