... Methods¹

Work on this project was supported in part by National Science Foundation Grant MCS 79-19829 at The University of Texas at Austin.

... Austin²

Center for Numerical Analysis, RLM Bldg. 13.150, University of Texas, Austin, TX 78712

... Company³

Boeing Computer Services Company, 565 Andover Park West, Tukwila, WA 98067

... ``red-black"⁴

In this ordering, the components of the unknown vector u are considered as either ``red" or ``black". A ``red-black ordering" is any ordering such that every black unknown follows all of the red unknowns. This ordering of unknowns leads to a $2\times 2$ ``red-black partitioning" of the coefficient matrix, that is, a matrix of the form

$$\left[\begin{array}{cc} D_R & H \\ K & D_B \end{array} \right]$$

with diagonal submatrices D_R and D_B. The original linear system may require rearrangement in order to arrive at this form.

... workspace.⁵

For the red-black ordering, the Ith entry of a permutation array P(*) indicates the position J into which the Ith unknown of the original system is being mapped, that is, if ${\bf P(I)=J}$ then unknown I is mapped into position J. The Jth entry of an inverse permutation array IP(*) indicates the position I into which the Jth unknown of the permuted system must be mapped to regain the original ordering, that is, ${\bf IP(J)=I}$.

...).⁶

A matrix has Property A if and only if it is a diagonal matrix or else there exists a rearrangement of the rows and corresponding columns of the matrix which corresponds to a red-black partitioning.

... II).⁷

An L-matrix has positive diagonal elements and nonpositive off-diagonal elements.

... one.⁸

If the row and column corresponding to diagonal entry A_i,i are to be eliminated, then the right-hand side is adjusted to $b_i \leftarrow b_i/A_{i,i}$ and $b_j \leftarrow b_j-b_i A_{i,j}$ for $j \neq i$.

... matrix.⁹

IMSL (International Mathematical and Statistical Libraries, Inc.), Sixth Floor NBC Bldg., 7500 Bellaire Blvd., Houston, TX, 77036.

... procedure.¹⁰

Private communication.