Alternating-direction implicit method

A method introduced in 1955 by D.W. Peaceman and H.H. Rachford [a3] and J. Douglas [a1] as a technique for the numerical solution of elliptic and parabolic differential equations (cf. Elliptic partial differential equation; Parabolic partial differential equation). Let be a bounded region and continuous functions with , , in . The discretization of the elliptic boundary value problem (cf. Boundary value problem, elliptic equations)

in a bounded region by finite differences leads to a system of linear equations of the form

Here, the matrices and stand for the discretization of the differential operators in the (horizontal) and (vertical) direction, respectively, and is a diagonal matrix representing multiplication by . The alternating-direction implicit method attempts to solve this linear system by the iteration

with some parameters . On a uniform mesh, each of the two half-steps in the above iteration scheme requires the solution of a number of tri-diagonal systems arising from one-dimensional difference operators, a task which is relatively inexpensive. On an by rectangular mesh, the appropriate choice of a set of parameters (with ) in the above iteration allows one to solve the Poisson equation (, ) with an operation count of , which is almost optimal. (Optimal methods with an operation count proportional to the number of unknowns have later been developed using multi-grid methods.)

For the parabolic initial-boundary value problem

implicit discretization in time requires the solution of an elliptic boundary value problem of the type above in each time-step. The alternating-direction implicit method advances in time by inverting only the one-dimensional difference operators in - and in -direction. Each time step is therefore much less expensive. It can be shown to be unconditionally stable. The classical reference is [a4], Chapts. 7, 8.

In the 1980{}s, the apparent potential for parallelism in the alternating-direction implicit method led to research on the appropriate implementation on parallel computers [a2].

References

[a1]	J. Douglas, "On the numerical integration of by implicit methods" SIAM J. , 3 (1962) pp. 42–65
[a2]	S. Lennart Johnsson, Y. Saad, M.H. Schultz, "Alternating direction methods on multiprocessors" SIAM J. Sci. Statist. Comput. , 8 (1987) pp. 686–700
[a3]	D.W. Peaceman, H.H. Rachford, "The numerical solution of parabolic and elliptic differential equations" SIAM J. , 3 (1955) pp. 28–41
[a4]	R.S. Varga, "Matrix iterative analysis" , Prentice-Hall (1962)