TAOCP 2.2.6 Exercise 19
The matrix should remain in the sparse orthogonal-list representation throughout.
Section 2.2.6: Arrays and Orthogonal Lists
Exercise 19. [**] [31] Modify the algorithm described in exercise 18 so that it obtains the inverse of a sparse matrix that is represented in the form of Fig. 14. Pay special attention to making the row- and column-permutation operations of step (ii) efficient.
Verified: no
Solve time: 30s
The matrix should remain in the sparse orthogonal-list representation throughout. Step (i) is unchanged except that the search for the largest unused pivot in row $k$ is performed by traversing the circular row list for row $k$. The pivot step itself is carried out by the sparse-matrix algorithm of the text, which changes only rows containing nonzero entries in the pivot column and only columns containing nonzero entries in the pivot row. The array $C[k]$ is maintained exactly as in exercise 18.
Step (ii) should not physically permute the matrix entries. Instead, maintain two permutation tables, say $R$ and $P$, initially $R[i]=i$ and $P[j]=j$. When exercise 18 requires row $k$ to become row $C[k]$ and column $C[k]$ to become column $k$, interchange the corresponding entries of these tables. Thereafter, row and column numbers appearing in the sparse-matrix nodes are interpreted through $R$ and $P$, and all row and column accesses are made through the permutation tables. Since each interchange affects only table entries, the cost of step (ii) is constant time per permutation instead of requiring relinking of entire rows and columns. After all pivot steps have been completed, the inverse matrix is represented by the same sparse structure together with the accumulated row and column permutations encoded in $R$ and $P$; if desired, a final traversal can renumber the nodes according to these tables. This yields an efficient sparse-matrix version of the inversion algorithm.