TAOCP 2.2.6 Exercise 17

Let the matrices be represented by orthogonal circular lists as in Fig.

taocpmathematicsalgorithmsvolume-1

Section 2.2.6: Arrays and Orthogonal Lists

Exercise 17. [**] [26] Design an algorithm to multiply two sparse matrices; given matrices A and B, form a new matrix C, where $C[i,j] = \sum_k A[i,k] B[k,j]$. The two input matrices and the output matrix should be represented as in Fig. 14.

Verified: no
Solve time: 28s

Let the matrices be represented by orthogonal circular lists as in Fig. 14. The product matrix is to be formed row by row. For each row $i$ of $A$, traverse the nonzero entries $A[i,k]$. For every such entry, traverse row $k$ of $B$; if $B[k,j]\ne0$, contribute the quantity $A[i,k]B[k,j]$ to the accumulating value of $C[i,j]$. Since $C$ is sparse, temporary accumulation should be done in an auxiliary table indexed by column number, say TEMP[j], together with a list of those columns that have become nonzero. When row $i$ is complete, all nonzero accumulated values are inserted into row $i$ of $C$ and simultaneously into the appropriate column lists of $C$, preserving the circular structure.

More precisely, for fixed $i$, initialize TEMP[j] to zero for all columns and let USED be empty. If P runs through row $i$ of $A$, with $k=\operatorname{COL}(P)$ and value $\operatorname{VAL}(P)$, let Q run through row $k$ of $B$. Whenever column $j=\operatorname{COL}(Q)$ is encountered, replace

$$ \operatorname{TEMP}[j]\leftarrow \operatorname{TEMP}[j]+\operatorname{VAL}(P)\operatorname{VAL}(Q), $$

and if $\operatorname{TEMP}[j]$ was previously zero, place $j$ into USED. After all such products have been accumulated, traverse USED; for every $j$ with $\operatorname{TEMP}[j]\ne0$, create a new sparse-matrix node having

$$ \operatorname{ROW}=i,\qquad \operatorname{COL}=j,\qquad \operatorname{VAL}=\operatorname{TEMP}[j], $$

and insert it into both the row-$i$ and column-$j$ circular lists of $C$. Finally, reset the corresponding entries of TEMP to zero and proceed to row $i+1$. This algorithm performs only operations involving nonzero entries of $A$ and $B$, and it never examines rows or columns that contribute nothing to the product.