6
$\begingroup$

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$?

$\endgroup$
17
  • 5
    $\begingroup$ have a look at this (more general) answer $\endgroup$ – GoHokies May 14 '16 at 8:25
  • 4
    $\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$ – Carl Christian May 14 '16 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$ – Carl Christian May 17 '16 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$ – Carl Christian May 26 '16 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$ – Christian Clason Jul 1 '16 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.