116
5. Solution of Linear Equation Systems
this is achieved by passing a correction from each grid t o the next coarser
grid. One variant of the FAS scheme for the Navier-Stokes equations will be
presented in Chap. 11.
For a detailed analysis of multigrid methods, see books by Hackbusch
(1985) and Brandt (1984). A 2D multigrid solver that uses the Gauss-Seidel,
SIP, or ICCG methods as the smoother is available via Internet; see the
appendix for details.
5.3.9 Other Iterative Solvers
There are many other iterative solvers that cannot be described in detail here.
We mention the 'red-black' variation of the Gauss-Seidel solver which is often
used in conjunction with multigrid methods. On a structured grid, the nodes
are imagined to be 'colored' in the same way as a checkerboard. The method
consists of two Jacobi steps: black nodes are updated first, then the red nodes.
When the values a t black nodes are updated, only the 'old' red values are
used, see Eq. (5.33). On the next step, red values are recalculated using the
updated black values. This alternate application of the Jacobi method t o
the two sets of nodes gives an overall method with the same convergence
properties as the Gauss-Seidel method. The nice feature of the red-black
Gauss-Seidel solver is that it both vectorizes and parallelizes well, since there
are no data dependencies in either step.
Another practice often applied to multi-dimensional problems is the use
of iteration matrices which correspond to lower-dimensional problems. One
version of this is the AD1 method described above which reduces a 2D problem
to a sequence of 1D problems. The resulting tridiagonal problems are solved
line-by-line. The direction of solution is changed from iteration to iteration to
improve the rate of convergence. This method is usually used in the GaussSeidel fashion, i.e. new variable values from lines already visited are used.
A counterpart of the red-black Gauss-Seidel method is the 'zebra' lineby-line solver: first the solution is found on the even numbered lines, then
the odd numbered lines are treated. This gives better parallelization and
vectorization possibilities with no sacrifice in convergence properties.
It is also possible t o use the two-dimensional SIP method to solve threedimensional problems, applying it plane-by-plane and relegating the contributions from neighboring planes to the right hand side of the equations.
However, this method is neither cheaper nor faster than the three-dimensional
version of SIP. so it is not often used.
5.4 Coupled Equations and Their Solution
Most problems in fluid dynamics and heat transfer require solution of coupled systems of equations, i.e. the dominant variable of each equation occurs
5. Solution of Linear Equation Systems
this is achieved by passing a correction from each grid t o the next coarser
grid. One variant of the FAS scheme for the Navier-Stokes equations will be
presented in Chap. 11.
For a detailed analysis of multigrid methods, see books by Hackbusch
(1985) and Brandt (1984). A 2D multigrid solver that uses the Gauss-Seidel,
SIP, or ICCG methods as the smoother is available via Internet; see the
appendix for details.
5.3.9 Other Iterative Solvers
There are many other iterative solvers that cannot be described in detail here.
We mention the 'red-black' variation of the Gauss-Seidel solver which is often
used in conjunction with multigrid methods. On a structured grid, the nodes
are imagined to be 'colored' in the same way as a checkerboard. The method
consists of two Jacobi steps: black nodes are updated first, then the red nodes.
When the values a t black nodes are updated, only the 'old' red values are
used, see Eq. (5.33). On the next step, red values are recalculated using the
updated black values. This alternate application of the Jacobi method t o
the two sets of nodes gives an overall method with the same convergence
properties as the Gauss-Seidel method. The nice feature of the red-black
Gauss-Seidel solver is that it both vectorizes and parallelizes well, since there
are no data dependencies in either step.
Another practice often applied to multi-dimensional problems is the use
of iteration matrices which correspond to lower-dimensional problems. One
version of this is the AD1 method described above which reduces a 2D problem
to a sequence of 1D problems. The resulting tridiagonal problems are solved
line-by-line. The direction of solution is changed from iteration to iteration to
improve the rate of convergence. This method is usually used in the GaussSeidel fashion, i.e. new variable values from lines already visited are used.
A counterpart of the red-black Gauss-Seidel method is the 'zebra' lineby-line solver: first the solution is found on the even numbered lines, then
the odd numbered lines are treated. This gives better parallelization and
vectorization possibilities with no sacrifice in convergence properties.
It is also possible t o use the two-dimensional SIP method to solve threedimensional problems, applying it plane-by-plane and relegating the contributions from neighboring planes to the right hand side of the equations.
However, this method is neither cheaper nor faster than the three-dimensional
version of SIP. so it is not often used.
5.4 Coupled Equations and Their Solution
Most problems in fluid dynamics and heat transfer require solution of coupled systems of equations, i.e. the dominant variable of each equation occurs