7

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

Rodrigo de Azevedo
  • 1
  • 4
  • 13
vainia
  • 121
  • 4
  • 6
    have a look at this (more general) answer – GoHokies May 14 '16 at 08:25
  • 5
    @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. – vainia May 17 '16 at 05:31
  • 3
    @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 08:38
  • @qtqt Have you resolved the problem? Otherwise we can put together a question which explains why the suggested solution of the more general question is too slow. – Carl Christian May 21 '16 at 15:47
  • @CarlChristian I have not resolved the problem. I believe I understand what to do (based on your May 17 comment), but my lack of programming skill is holding me back (learning about linked lists/hash table/binary trees). – vainia May 22 '16 at 23:28
  • @qtqt I have had time to think about the problem as well. I gave you the "standard" solution. I now realize that it can be expressed more clearly. Think about how you were taught to do $C= AB$ by hand. If $a_{11}, a_{13}$, and $a_{16}$ are the only nonzero entries in $A$, then the first row of $C$ is a linear combination of rows $1, 3$ and $6$ from $B$. The sparsity pattern of the first row of $C$ is therefore the union of the sparsity patterns of rows $1, 3$ and $6$. If both matrices are in CSR format, then this is the way to go. A similar approach works if both are in CSC format. – Carl Christian May 23 '16 at 08:21
  • @qtqt To be clear. If $b_{11}, b_{31}, b_{61}$ are the only nonzero entries in the first column of $B$, then the first column of $C$ is linear combination of columns $1, 3$ and $6$ from $A$. The sparsity pattern of the first column of $C$ is therefore the union of the sparsity patterns of columns $1$, $3$ and $6$ from $A$. This is the approach that I would use if the matrices were in CSC (compressed sparse column) format. Many new questions are possible and include: what other sparse formats are relevant and how do we do the operation in parallel :) – Carl Christian May 23 '16 at 08:27
  • @CarlChristian This makes a lot more sense. I've updated the question to hopefully lift the 'duplicate' tag. – vainia May 23 '16 at 16:32
  • @qtqt You problem continues to reside in the back of my mind. As we have discussed, the sparsity pattern of each row of $C$ is the union of the sparsity pattern of select rows of $B$, as dictated by the corresponding row of $A$. Equivalently, the adjacency list for a row of $C$ can be constructed by merging the adjacency lists for the appropriate rows of $A$. SImilarly, when $A$ and $B$ are in CSC format. Merging $k$ lists with at total of $N$ elements can be done in $O(N\log(k))$ time using a k-way merge using a heap. I will add a reference in the next comment. – Carl Christian May 26 '16 at 08:28
  • @qtqt Here is a reference to a k-way merge using a heap: http://cs.stackexchange.com/questions/12853/heap-give-an-on-lg-k-time-algorithm-to-merge-k-sorted-lists-into-one-so I suspect that it possible to capitalize on the fact that some mergers are performed more than once! Ex. if rows 1 and 2 of C both contain the sparsity pattern of rows 6 and 100 from $B$, then it might be worth while to merge those lists, before they are insert into the lists for rows 1 and 2. – Carl Christian May 26 '16 at 08:31
  • 1
    @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 08:49
  • @CarlChristian Thanks again! This is becoming more and more interesting! – vainia May 26 '16 at 22:47
  • @CarlChristian Notifications don't work for people who have not commented themselves. If you write an answer on how to handle this specific case with a better complexity than the general case, I'd be more than happy to nominate the question for reopening. (Comments are ephemeral and not the place for answers; neither is the question.) – Christian Clason Jun 03 '16 at 09:07
  • @ChristianClason Thank you for letting me know that the nofications didn't reach you. I have communicated with Wolfgang Bangerth who wrote the leading answer to the general question. We now agree on the complexity of the general case, but the details (implementation and analysis) are left to the reader. The complexity will not change in the special case of $C=A^2$. I can certainly write out the details, but where? qtqt asked for the complete pattern of $C=A^2$. The old question called for the size of the pattern of $C=A \cdot B$, so is it OK for me to write the answer there? – Carl Christian Jun 03 '16 at 10:05
  • @CarlChristian If this is not a duplicate of the other question, your answer belongs here, of course. – Christian Clason Jun 03 '16 at 10:35
  • 1
    @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.) – Christian Clason Jul 01 '16 at 15:04

0 Answers0