**Previous:** Block Iterative Methods

**Up:** Remaining topics

**Next:** Domain Decomposition Methods

**Previous Page:** Block Iterative Methods

**Next Page:** Domain Decomposition Methods

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.