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 ![]() |
[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) |
Alternating-direction implicit method. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Alternating-direction_implicit_method&oldid=14574