102
5. Solution of Linear Equation Systems
Another incomplete lower-upper decomposition method, which has found
use in CFD, was proposed by Stone (1968). This method, also called the
strongly implicit procedure (SIP), is specifically designed for algebraic equations that are discretizations of partial differential equations and does not
apply to generic systems of equations.
We shall describe the SIP method for the five-point computational molecule,
i.e. a matrix with the structure shown in Fig. 3.5. The same principles can be
used to construct solvers for 7-point (in three-dimensions) and 9-point (for
two-dimensional non-orthogonal grids) computational molecules.
As in ILU, the L and U matrices have non-zero elements only on diagonals
on which A has non-zero elements. The product of lower and upper triangular
matrices with these structures has more non-zero diagonals than A. For the
standard five-point molecule there are two more diagonals (corresponding
to nodes NW and SE or NE and SW, depending on the ordering of the
nodes in the vector), and for seven-point molecules in 3D, there are six more
diagonals. For the ordering of nodes used in this book for 2D problems, the
extra two diagonals correspond to the nodes NW and SE (see Table 3.2 for
the correspondence of the grid indices (2, j ) and the one-dimensional storage
location index 1).
To make these matrices unique, every element on the main diagonal of U
is set to unity. Thus five sets of elements (three in L, two in U) need to be
determined. For matrices of the form shown in Fig. 5.1, the rules of matrix
multiplication give the elements of the product of L and U, M = LU:
We wish to select L and U, such that M is as good an approximation to
A as possible. At minimum, N must contain the two diagonals of M that
correspond to zero diagonals of A, see Eq. (5.36). An obvious choice is to let
N have non-zero elements on only these two diagonals, and force the other
diagonals of M to equal the corresponding diagonals of A. This is possible;
in fact, this is the standard ILU method mentioned earlier. Unfortunately,
this method converges slowly.
Stone (1968) recognized that convergence can be improved by allowing N
to have non-zero elements on the diagonals corresponding to all seven nonzero diagonals of LU. The method is most easily derived by considering the
5. Solution of Linear Equation Systems
Another incomplete lower-upper decomposition method, which has found
use in CFD, was proposed by Stone (1968). This method, also called the
strongly implicit procedure (SIP), is specifically designed for algebraic equations that are discretizations of partial differential equations and does not
apply to generic systems of equations.
We shall describe the SIP method for the five-point computational molecule,
i.e. a matrix with the structure shown in Fig. 3.5. The same principles can be
used to construct solvers for 7-point (in three-dimensions) and 9-point (for
two-dimensional non-orthogonal grids) computational molecules.
As in ILU, the L and U matrices have non-zero elements only on diagonals
on which A has non-zero elements. The product of lower and upper triangular
matrices with these structures has more non-zero diagonals than A. For the
standard five-point molecule there are two more diagonals (corresponding
to nodes NW and SE or NE and SW, depending on the ordering of the
nodes in the vector), and for seven-point molecules in 3D, there are six more
diagonals. For the ordering of nodes used in this book for 2D problems, the
extra two diagonals correspond to the nodes NW and SE (see Table 3.2 for
the correspondence of the grid indices (2, j ) and the one-dimensional storage
location index 1).
To make these matrices unique, every element on the main diagonal of U
is set to unity. Thus five sets of elements (three in L, two in U) need to be
determined. For matrices of the form shown in Fig. 5.1, the rules of matrix
multiplication give the elements of the product of L and U, M = LU:
We wish to select L and U, such that M is as good an approximation to
A as possible. At minimum, N must contain the two diagonals of M that
correspond to zero diagonals of A, see Eq. (5.36). An obvious choice is to let
N have non-zero elements on only these two diagonals, and force the other
diagonals of M to equal the corresponding diagonals of A. This is possible;
in fact, this is the standard ILU method mentioned earlier. Unfortunately,
this method converges slowly.
Stone (1968) recognized that convergence can be improved by allowing N
to have non-zero elements on the diagonals corresponding to all seven nonzero diagonals of LU. The method is most easily derived by considering the