Suppose we have a sparse matrix $A$. Is there any way to compute just the sparsity pattern of $A^2 = A \cdot A$ (I do not actually need to know what exactly the nonzero value are) faster than to compute the full sparse product $A \cdot A$?

  • 6
    $\begingroup$ have a look at this (more general) answer $\endgroup$
    – GoHokies
    Commented May 14, 2016 at 8:25
  • 5
    $\begingroup$ @ChristianClason. This is not an exact duplicate of an existing question. The new question deals with a special case. The top voted solution of the old questions recommends a solution which is quadratic in the matrix dimension! Moreover, it requires easy access to both rows and columns of the matrix. Unless, the matrix is structurally symmetric this is a nontrivial requirement. The new question can be solved rapidly using lists. $\endgroup$ Commented May 14, 2016 at 21:45
  • 3
    $\begingroup$ @qtqt Finding the sparsity pattern of $A^2$ is equivalent to finding all neighbors of degree at most 2 in the adjacency graph of $A$. Let $i$, $j$, and $k$ denote vertices. If there is an edge from $i$ to $j$ and from $j$ to $k$ in the adjacency graph of $A$, then there must be an edge from $i$ to $k$ in the adjacency graph of $A^2$. CSR format gives a compact representation of the adjacency lists. For each vertex in the graph of $A^2$ you record the neighbors in a sorted linked list/tree structure and then compress it to CSR form. This keeps memory consumption to a minimum. $\endgroup$ Commented May 17, 2016 at 8:38
  • 1
    $\begingroup$ @RichardZang: This question is not a duplicate of an existing question. The old question deals with the problem of determining the size of the memory needed to store $C = A \cdot B$. The new question deals with computing the sparsity pattern of $A^2$. The two questions are certainly related by they are not identical. As you can see from my comments, I believe that there is enough reason to lift the 'duplicate' tag. Regardless, I feel qtqt deserves a response. Kind regards $\endgroup$ Commented May 26, 2016 at 8:49
  • 1
    $\begingroup$ @CarlChristian Now that the question has finally been reopened, would you be so kind as to write the answer you had in mind? (This would also allow the comment thread to be cleaned up a bit.) $\endgroup$ Commented Jul 1, 2016 at 15:04


Your Answer

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

Browse other questions tagged or ask your own question.