2
$\begingroup$

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?

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.