TAOCP 2.2.6 Exercise 14
In a sequential representation of a sparse matrix, the nonzero entries of each row may be stored consecutively, together with their column indices.
Section 2.2.6: Arrays and Orthogonal Lists
Exercise 14. [**] [22] Algorithm S actually saves pivoting time in a sparse matrix, since it avoids consideration of those columns in which the pivot row has a zero entry. Show that this savings in running time can be achieved in a large sparse matrix that is stored sequentially, with the help of an auxiliary table LINK[j], $1 \le j \le n$.
Verified: no
Solve time: 33s
In a sequential representation of a sparse matrix, the nonzero entries of each row may be stored consecutively, together with their column indices. The saving of Algorithm $S$ comes from scanning only those columns in which the pivot row has a nonzero entry. This can be achieved by maintaining an auxiliary table LINK[j], where LINK[j] points to the next nonzero column in row $j$, or is $0$ if no such column remains.
Suppose row $r$ is the pivot row. Before the pivot step, traverse the nonzero entries of row $r$ and construct a linked list through their column indices:
$$ j_1 \to j_2 \to \cdots \to j_t \to 0, $$
where $A[r,j_s]\ne0$ and every other entry in row $r$ is zero. Then, when another row $i$ with $A[i,p]\ne0$ is updated, the algorithm no longer scans all columns $1\le j\le n$; instead it follows the chain
$$ j\leftarrow j_1,\qquad j\leftarrow \operatorname{LINK}[j] $$
until $j=0$, performing the transformation only for those columns. Thus the running time depends on the number of nonzero entries in the pivot row, exactly as in Algorithm $S$, although the matrix itself is stored sequentially rather than by orthogonal lists.