Alternating-direction implicit method

It is a popular method for solving the large matrix equations that arise in systems theory and control,[1] and can be formulated to construct solutions in a memory-efficient, factored form.

[2][3] It is also used to numerically solve parabolic and elliptic partial differential equations, and is a classic method used for modeling heat conduction and solving the diffusion equation in two or more dimensions.

The ADI method is a two step iteration process that alternately updates the column and row spaces of an approximate solution to

[9] It is therefore only beneficial to use ADI when matrix-vector multiplication and linear solves involving

[3] The problem of finding good shift parameters is nontrivial.

This problem can be understood by examining the ADI error equation.

In this case, the shift parameters can be expressed in closed form using elliptic integrals, and can easily be computed numerically.

, are known, the optimal shift parameter selection problem is approximately solved by finding an extremal rational function that attains the value

[8] This approximation problem is related to several results in potential theory,[12][13] and was solved by Zolotarev in 1877 for

are non-normal matrices, it may not be possible to find near-optimal shift parameters.

In this setting, a variety of strategies for generating good shift parameters can be used.

These include strategies based on asymptotic results in potential theory,[16] using the Ritz values of the matrices

to formulate a greedy approach,[17] and cyclic methods, where the same small collection of shift parameters are reused until a convergence tolerance is met.

[17][10] When the same shift parameter is used at every iteration, ADI is equivalent to an algorithm called Smith's method.

[1] In such a setting, it may not be feasible to store the potentially dense matrix

[10][8] Historically, the ADI method was developed to solve the 2D diffusion equation on a square domain using finite differences.

[4] Unlike ADI for matrix equations, ADI for parabolic equations does not require the selection of shift parameters, since the shift appearing in each iteration is determined by parameters such as the timestep, diffusion coefficient, and grid spacing.

This method results in a very complicated set of equations in multiple dimensions, which are costly to solve.

After performing a stability analysis, it can be shown that this method will be stable for any

This makes direct solution of the system of linear equations quite costly (although efficient approximate solutions exist, for example use of the conjugate gradient method preconditioned with incomplete Cholesky factorization).

The idea behind the ADI method is to split the finite difference equations into two, one with the x-derivative taken implicitly and the next with the y-derivative taken implicitly, The system of equations involved is symmetric and tridiagonal (banded with bandwidth 3), and is typically solved using tridiagonal matrix algorithm.

It can be shown that this method is unconditionally stable and second order in time and space.

The usage of the ADI method as an operator splitting scheme can be generalized.

are (possibly nonlinear) operators defined on a Banach space.

It is possible to simplify the conventional ADI method into Fundamental ADI method, which only has the similar operators at the left-hand sides while being operator-free at the right-hand sides.

This may be regarded as the fundamental (basic) scheme of ADI method,[24][25] with no more operator (to be reduced) at the right-hand sides, unlike most traditional implicit methods that usually consist of operators at both sides of equations.

The FADI method leads to simpler, more concise and efficient update equations without degrading the accuracy of conventional ADI method.

Many classical implicit methods by Peaceman-Rachford, Douglas-Gunn, D'Yakonov, Beam-Warming, Crank-Nicolson, etc., may be simplified to fundamental implicit schemes with operator-free right-hand sides.

[25] In their fundamental forms, the FADI method of second-order temporal accuracy can be related closely to the fundamental locally one-dimensional (FLOD) method, which can be upgraded to second-order temporal accuracy, such as for three-dimensional Maxwell's equations [26][27] in computational electromagnetics.

For two- and three-dimensional heat conduction and diffusion equations, both FADI and FLOD methods may be implemented in simpler, more efficient and stable manner compared to their conventional methods.