Given a sparse matrix $A$ with $nnz(A)$ denoting the number of non-zero entries in it. What is the computational complexity of computing $A^k$, for some positive integer $k$? As $k$ gets larger, I understand that $A^k$ would no longer remain sparse, but I want to understand if there is an efficient algorithm that can handle this phenomenon?
$\begingroup$
$\endgroup$
Add a comment
|