# Compute sparsity pattern of $A^2$

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

• have a look at this (more general) answer – GoHokies May 14 '16 at 8:25
• @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. – Carl Christian May 14 '16 at 21:45
• @CarlChristian can you elaborate? Or post an answer using lists?! I do not know what this means. – qtqt May 17 '16 at 5:31
• @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. – Carl Christian May 17 '16 at 8:38
• @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 – Carl Christian May 26 '16 at 8:49