Reduced system: Linear system obtained by eliminating certain variables from another linear system. Although the number of variables is smaller than for the original system, the matrix of a reduced system generally has more nonzero entries. If the original matrix was symmetric and positive definite, then the reduced system has a smaller condition number.

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 -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 nonzero diagonals if is even and nonzero diagonals if is odd. Applying one step of block Gaussian elimination (or computing the Schur complement; see Golub and Van Loan [109]) 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 and of order for odd . 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 [150] demonstrate that the reduced system approach on hierarchical memory machines such as the Alliant FX/8 is over times faster than unpreconditioned CG for Poisson's equation on grids with .

For -dimensional elliptic PDEs, the reduced system approach yields a block tridiagonal matrix in () having diagonal blocks of the structure of from the -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 [150], the reduced system approach can still be about - times as fast as the conjugate gradient method with Jacobi preconditioning for -dimensional problems.

Domain decomposition method: Solution method for
linear systems based on a partitioning of the physical domain
of the differential equation. Domain decomposition methods typically
involve (repeated) independent system solution on the subdomains,
and some way of combining data from the subdomains on the separator
part of the domain.

Mon Nov 20 08:52:54 EST 1995