Previous: The use of fast solvers
Up: Preconditioners from properties of the differential equation
Previous Page: The use of fast solvers
Next Page: Related Issues

Alternating Direction Implicit methods

The Poisson differential operator can be split in a natural way as the sum of two operators:

Now let , be discretized representations of , . Based on the observation that , iterative schemes such as

with suitable choices of and have been proposed.

This alternating direction implicit, or ADI, method was first proposed as a solution method for parabolic equations. The are then approximations on subsequent time steps. However, it can also be used for the steady state, that is, for solving elliptic equations. In that case, the become subsequent iterates; see D'Yakonov [79], Fairweather, Gourlay and Mitchell [93], Hadjidimos [118], and Peaceman and Rachford [169]. Generalization of this scheme to variable coefficients or fourth order elliptic problems is relatively straightforward.

The above method is implicit since it requires systems solutions, and it alternates the and (and if necessary ) directions. It is attractive from a practical point of view (although mostly on tensor product grids), since solving a system with, for instance, a matrix entails only a number of uncoupled tridiagonal solutions. These need very little storage over that needed for the matrix, and they can be executed in parallel, or one can vectorize over them.

However, there is a problem of data distribution. For vector computers, either the system solution with or with will involve very large strides: if columns of variables in the grid are stored contiguously, only the solution with will involve contiguous data. For the the stride equals the number of variables in a column.

On parallel machines the same problem occurs, and it requires a global data transposition in between the and system solution.

A theoretical reason that ADI preconditioners are of interest is that they can be shown to be spectrally equivalent to the original coefficient matrix. Hence the number of iterations is bounded independent of the condition number.