TAOCP 2.2.6 Exercise 12
In the notation of (13), let the pivot element be $a$, let the other nonzero elements in the pivot row be represented by the coefficients $b$, and let the other nonzero elements in the pivot column be...
Section 2.2.6: Arrays and Orthogonal Lists
Exercise 12. ▶ [**] [20] What are VAL(Q0), VAL(P0), and VAL(P1) at the beginning of step S7, in terms of the notation $a$, $b$, $c$, $d$ used in (13)?
Verified: no
Solve time: 38s
In the notation of (13), let the pivot element be $a$, let the other nonzero elements in the pivot row be represented by the coefficients $b$, and let the other nonzero elements in the pivot column be represented by the coefficients $c$. The entries not in the pivot row or pivot column are represented by $d$.
During the sparse-matrix pivot algorithm, $P_0$ and $Q_0$ are the row and column header nodes corresponding to the pivot row and pivot column. Their value fields are used to hold the multipliers associated with the pivot operation. By the time step S7 begins, the pivot row has already been scaled by $1/a$, and the pivot-column entries have been negated and divided by $a$. Therefore
$$ \operatorname{VAL}(Q_0)=\frac1a, \qquad \operatorname{VAL}(P_0)=-\frac{c}{a}, \qquad \operatorname{VAL}(P_1)=b. $$
Here $P_1$ denotes an entry in the pivot row, so its value is one of the coefficients $b$ appearing in (13). Hence the values at the beginning of S7 are exactly those required to form the products $(-c/a)b$, which are added to the corresponding entries $d$ to obtain the transformed matrix elements. $\boxed{\operatorname{VAL}(Q_0)=1/a,\ \operatorname{VAL}(P_0)=-c/a,\ \operatorname{VAL}(P_1)=b}$