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 $\Omega \in \mathbf R ^ {2}$ be a bounded region and $K _ {1} ,K _ {2} , K _ {0}$ continuous functions with $K _ {1} ( x,y ) > 0$, $K _ {2} ( x,y ) > 0$, $K _ {0} ( x,y ) \geq 0$ in $\Omega$. The discretization of the elliptic boundary value problem (cf. Boundary value problem, elliptic equations)

$$- ( K _ {1} u _ {x} ) _ {x} - ( K _ {2} u _ {y} ) _ {y} + K _ {0} u = f \textrm{ in } \Omega,$$

$$u = g \textrm{ on } \partial \Omega,$$

in a bounded region $\Omega \subset \mathbf R ^ {2}$ by finite differences leads to a system of linear equations of the form

$$( H + V + S ) \mathbf u = \mathbf f .$$

Here, the matrices $H$ and $V$ stand for the discretization of the differential operators in the $x$ (horizontal) and $y$ (vertical) direction, respectively, and $S$ is a diagonal matrix representing multiplication by $K _ {0}$. The alternating-direction implicit method attempts to solve this linear system by the iteration

$$\left ( H + { \frac{1}{2} } S + \rho _ {k} I \right ) \mathbf u _ {k - {1 / 2 } } = \left ( \rho _ {k} I - V - { \frac{1}{2} } S \right ) \mathbf u _ {k - 1 } + \mathbf f,$$

$$\left ( V + { \frac{1}{2} } S + \rho _ {k} I \right ) \mathbf u _ {k} = \left ( \rho _ {k} I - H - { \frac{1}{2} } S \right ) \mathbf u _ {k - {1 / 2 } } + \mathbf f, k = 1, 2, \dots,$$

with some parameters $\rho _ {k} > 0$. 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 $n$ by $n$ rectangular mesh, the appropriate choice of a set of parameters $\rho _ {1} \dots \rho _ {l}$ (with $l = { \mathop{\rm log} } n$) in the above iteration allows one to solve the Poisson equation ( $K _ {1} = K _ {2} \equiv 1$, $K _ {0} = 0$) with an operation count of $O ( n ^ {2} { \mathop{\rm log} } n )$, which is almost optimal. (Optimal methods with an operation count proportional to the number of unknowns $n ^ {2}$ have later been developed using multi-grid methods.)

For the parabolic initial-boundary value problem

$$u _ {t} = ( K _ {1} u _ {x} ) _ {x} + ( K _ {2} u _ {y} ) _ {y} + K _ {0} u = f \textrm{ in } ( 0,T ) \times \Omega,$$

$$u = g \textrm{ on } ( 0,T ) \times \partial \Omega, u = u _ {0} \textrm{ for } t = 0,$$

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 $x$- and in $y$-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 $u_{xx}+u_{yy}=u_{t}$ 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)