TAOCP 2.2.6 Exercise 16

Section 2.2.6: Arrays and Orthogonal Lists

Exercise 16. [**] [25] Design an algorithm to copy a sparse matrix. (In other words, the algorithm is to yield two distinct representations of a matrix in memory, having the form of Fig. 14, given just one such representation initially.)

Verified: no
Solve time: 31s

Let A be the given sparse matrix represented with circularly linked row and column lists, with head nodes BASEROW[i] and BASECOL[j]. Allocate a new matrix B with the same dimensions and the same node structure. For each row index i, traverse the circular list starting from LEFT(BASEROW[i]) through all nodes in that row by following LEFT pointers; for each visited node P in A, create a new node Q in B, copy the fields ROW(Q) \leftarrow ROW(P), COL(Q) \leftarrow COL(P), and VAL(Q) \leftarrow VAL(P) (three replacements per node), and insert Q into the corresponding row list of B by adjusting LEFT pointers. Repeat the process for column lists: for each column index j, traverse the circular list starting from UP(BASECOL[j]), and link the newly created nodes Q in B via their UP pointers, preserving the column order. Each node is thus copied exactly once and linked correctly in both row and column lists. The total number of replacements is three per node for the fields, plus two per node for the LEFT and UP pointers, yielding five replacements per node. This completes the proof. ∎