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$
  • 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
  • $\begingroup$ @CarlChristian can you elaborate? Or post an answer using lists?! I do not know what this means. $\endgroup$ – qtqt May 17 '16 at 5:31
  • 2
    $\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

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.