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$?
$\begingroup$
$\endgroup$
17
-
6$\begingroup$ have a look at this (more general) answer $\endgroup$– GoHokiesMay 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$– Carl ChristianMay 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$– Carl ChristianMay 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$– Carl ChristianMay 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$– Christian ClasonJul 1, 2016 at 15:04
|
Show 12 more comments