Previous: Block Iterative Methods
Up: Remaining topics
Next: Domain Decomposition Methods
Previous Page: Block Iterative Methods
Next Page: Domain Decomposition Methods

Reduced System Preconditioning

As we have seen earlier, a suitable preconditioner for CG is a matrix such that the system

requires fewer iterations to solve than does, and for which systems can be solved efficiently. The first property is independent of the machine used, while the second is highly machine dependent. Choosing the best preconditioner involves balancing those two criteria in a way that minimizes the overall computation time. One balancing approach used for matrices arising from 5-point finite difference discretization of second order elliptic partial differential equations (PDEs) with Dirichlet boundary conditions involves solving a reduced system. Specifically, for an grid, we can use a point red-black ordering of the nodes to get

where and are diagonal, and is a well-structured sparse matrix with 5 nonzero diagonals if n is even and 4 nonzero diagonals if n is odd. Applying one step of block Gaussian elimination (or computing the Schur complement; see Golub and Van Loan [108]) we have

which reduces to

With proper scaling (left and right multiplication by ), we obtain from the second block equation the reduced system

where , , and . The linear system () is of order for even n and of order for odd n. Once is determined, the solution is easily retrieved from . The values on the black points are those that would be obtained from a red/black ordered SSOR preconditioner on the full system, so we expect faster convergence.

The number of nonzero coefficients is reduced, although the coefficient matrix in () has nine nonzero diagonals. Therefore it has higher density and offers more data locality. Meier and Sameh [147] demonstrate that the reduced system approach on hierarchical memory machines such as the Alliant FX/8 is over 3 times faster than unpreconditioned CG for Poisson's equation on grids with .

For 3-dimensional elliptic PDEs, the reduced system approach yields a block tridiagonal matrix in () having diagonal blocks of the structure of from the 2-dimensional case and off-diagonal blocks that are diagonal matrices. Computing the reduced system explicitly leads to an unreasonable increase in the computational complexity of solving . The matrix products required to solve () would therefore be performed implicitly which could significantly decrease performance. However, as Meier and Sameh show [147], the reduced system approach can still be about 2-3 times as fast as the conjugate gradient method with Jacobi preconditioning for 3-dimensional problems.