Alternating-direction implicit method: Difference between revisions

Revision as of 06:10, 16 April 2020

Revision as of 08:33, 3 June 2020

Line 1:

In [[numerical linear algebra]], the '''Alternating Direction Implicit (ADI) method''' is an iterative method used to solve [[Sylvester equation|Sylvester]] matrix equations. It is a popular method for solving the large matrix equations that arise in [[systems theory]] and [[Control theory|control]],<ref name=":1">{{Cite journal|last=Simoncini|first=V.|s2cid=17271167|date=2016|title=Computational Methods for Linear Matrix Equations|journal=SIAM Review|language=en|volume=58|issue=3|pages=377–441|doi=10.1137/130912839|issn=0036-1445|url=https://semanticscholar.org/paper/bf31e4aaa0f2f0cc1318d1742c60a409d68f12ce}}</ref> and can be formulated to construct solutions in a memory-efficient, factored form.<ref name=":2">{{Cite journal|lastlast1=Li|firstfirst1=Jing-Rebecca|author1-link=Jing-Rebecca Li|last2=White|first2=Jacob|date=2002|title=Low Rank Solution of Lyapunov Equations|journal=SIAM Journal on Matrix Analysis and Applications|language=en|volume=24|issue=1|pages=260–280|doi=10.1137/s0895479801384937|issn=0895-4798}}</ref><ref name=":3">{{Cite journal|lastlast1=Benner|firstfirst1=Peter|last2=Li|first2=Ren-Cang|last3=Truhar|first3=Ninoslav|date=2009|title=On the ADI method for Sylvester equations|journal=Journal of Computational and Applied Mathematics|volume=233|issue=4|pages=1035–1045|doi=10.1016/j.cam.2009.08.108|issn=0377-0427|bibcode=2009JCoAM.233.1035B}}</ref> It is also used to numerically solve [[Parabolic partial differential equation|parabolic]] and [[Elliptic partial differential equation|elliptic]] partial differential equations, and is a classic method used for modeling [[heat conduction]] and solving the [[diffusion equation]] in two or more dimensions.<ref name=":0">{{Citation|title=The numerical solution of parabolic and elliptic differential equations|year=1955|last1=Peaceman|last2=Rachford Jr.|first1=D. W.|first2=H. H.|journal=Journal of the Society for Industrial and Applied Mathematics|volume=3|issue=1|pages=28–41|doi=10.1137/0103003|mr=0071874|hdl=10338.dmlcz/135399|hdl-access=free}}.</ref> It is an example of an [[operator splitting]] method.<ref>*{{Cite book | last1=Press | first1=WH | last2=Teukolsky | first2=SA | last3=Vetterling | first3=WT | last4=Flannery | first4=BP | year=2007 | title=Numerical Recipes: The Art of Scientific Computing | edition=3rd | publisher=Cambridge University Press | ___location=New York | isbn=978-0-521-88068-8 | chapter=Section 20.3.3. Operator Splitting Methods Generally | chapter-url=http://apps.nrbook.com/empanel/index.html#pg=1052}}

</ref>

Line 6:

=== The method ===

The ADI method is a two step iteration process that alternately updates the column and row spaces of an approximate solution to <math>AX - XB = C</math>. One ADI iteration consists of the following steps:<ref>{{Cite journal|last=Wachspress|first=Eugene L.|date=2008|title=Trail to a Lyapunov equation solver|journal=Computers & Mathematics with Applications|volume=55|issue=8|pages=1653–1659|doi=10.1016/j.camwa.2007.04.048|issn=0898-1221}}</ref><blockquote>1. Solve for <math>X^{(j + 1/2)}</math>, where <math>\left( A - \beta_{j +1} I\right) X^{(j+1/2)} = X^{(j)}\left( B - \beta_{j + 1} I \right) + C.</math> </blockquote><blockquote>2. Solve for <math> X^{(j + 1)}</math>, where <math> X^{(j+1)}\left( B - \alpha_{j + 1} I \right) = \left( A - \alpha_{j+1} I\right) X^{(j+1/2)} - C</math>.</blockquote>

The numbers <math>(\alpha_{j+1}, \beta_{j+1})</math> are called shift parameters, and convergence depends strongly on the choice of these parameters.<ref name=":4">{{Cite journal|lastlast1=Lu|firstfirst1=An|last2=Wachspress|first2=E.L.|date=1991|title=Solution of Lyapunov equations by alternating direction implicit iteration|journal=Computers & Mathematics with Applications|volume=21|issue=9|pages=43–58|doi=10.1016/0898-1221(91)90124-m|issn=0898-1221}}</ref><ref name=":5">{{Cite journal|lastlast1=Beckermann|firstfirst1=Bernhard|last2=Townsend|first2=Alex|date=2017|title=On the Singular Values of Matrices with Displacement Structure|journal=SIAM Journal on Matrix Analysis and Applications|language=en|volume=38|issue=4|pages=1227–1248|doi=10.1137/16m1096426|issn=0895-4798|arxiv=1609.09494}}</ref> To perform <math>K</math> iterations of ADI, an initial guess <math>X^{(0)}</math> is required, as well as <math>K</math> shift parameters, <math>\{ (\alpha_{j}, \beta_{j})\}_{j = 1}^{K}</math>.

=== When to use ADI ===

Line 13:

The equation <math> AX-XB=C</math> has a unique solution if and only if <math> \sigma(A) \cap \sigma(B) = \emptyset</math>, where <math> \sigma(M) </math> is the [[Spectrum of a matrix|spectrum]] of <math>M</math>.<ref name=":1" /> However, the ADI method performs especially well when <math>\sigma(A)</math> and <math>\sigma(B)</math> are well-separated, and <math>A</math> and <math>B</math> are [[Normal matrix|normal matrices]]. These assumptions are met, for example, by the Lyapunov equation <math>AX + XA^* = C</math> when <math>A</math> is [[Positive-definite matrix|positive definite]]. Under these assumptions, near-optimal shift parameters are known for several choices of <math>A</math> and <math>B</math>.<ref name=":4" /><ref name=":5" /> Additionally, a priori error bounds can be computed, thereby eliminating the need to monitor the residual error in implementation.

The ADI method can still be applied when the above assumptions are not met. The use of suboptimal shift parameters may adversely affect convergence,<ref name=":1" /> and convergence is also affected by the non-normality of <math>A</math> or <math>B</math> (sometimes advantageously).<ref name=":6">{{Cite thesis|last=Sabino|first=J|date=2007|title=Solution of large-scale Lyapunov equations via the block modified Smith method|journal=PHD Diss., Rice Univ.|volume=|pages=|hdl=1911/20641|type=Thesis}}</ref> [[Krylov subspace]] methods, such as the Rational Krylov Subspace Method,<ref>{{Cite journal|lastlast1=Druskin|firstfirst1=V.|last2=Simoncini|first2=V.|date=2011|title=Adaptive rational Krylov subspaces for large-scale dynamical systems|journal=Systems & Control Letters|volume=60|issue=8|pages=546–560|doi=10.1016/j.sysconle.2011.04.013|issn=0167-6911}}</ref> are observed to typically converge more rapidly than ADI in this setting,<ref name=":1" /><ref name=":3" /> and this has led to the development of hybrid ADI-projection methods.<ref name=":3" />

=== Shift Parameter Selection and the ADI error equation ===

Line 105:

=== Relations to other implicit methods ===

Many classical implicit methods by Peachman-Rachford, Douglas-Gunn, D'Yakonov, Beam-Warming, Crank-Nicolson, etc., may be simplified to fundamental implicit schemes with operator-free right-hand sides.<ref name=":8" /> 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 <ref>{{Cite journal|last=Tan|first=E. L.|date=2007|title=Unconditionally Stable LOD-FDTD Method for 3-D Maxwell's Equations|url=https://www.ntu.edu.sg/home/eeltan/papers/2007%20Unconditionally%20Stable%20LOD-FDTD%20Method%20for%203-D%20Maxwell’s%20Equations.pdf|journal=IEEE Microwave and Wireless Components Letters|volume=17|issue=2|pages=85–87|doi=10.1109/LMWC.2006.890166|via=}}</ref><ref>{{Cite journal|lastlast1=Gan|firstfirst1=T. H.|last2=Tan|first2=E. L.|date=2013|title=Unconditionally Stable Fundamental LOD-FDTD Method with Second-Order Temporal Accuracy and Complying Divergence|url=https://www.ntu.edu.sg/home/eeltan/papers/2013%20Unconditionally%20Stable%20Fundamental%20LOD-FDTD%20Method%20With%20Second-Order%20Temporal%20Accuracy%20and%20Complying%20Divergence.pdf|journal=IEEE Transactions on Antennas and Propagation|volume=61|issue=5|pages=2630–2638|doi=10.1109/TAP.2013.2242036|via=}}</ref> 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. <ref>{{Cite journal|lastlast1=Tay|firstfirst1=W. C.|last2=Tan|first2=E. L.|last3=Heh|first3=D. Y.|date=2014|title=Fundamental Locally One-Dimensional Method for 3-D Thermal Simulation|url=|journal=IEICE Transactions on Electronics|volume=E-97-C|issue=7|pages=636–644|doi=10.1587/transele.E97.C.636}}</ref><ref>{{Cite journal|lastlast1=Heh|firstfirst1=D. Y.|last2=Tan|first2=E. L.|last3=Tay|first3=W. C.|date=2016|title=Fast Alternating Direction Implicit Method for Efficient Transient Thermal Simulation of Integrated Circuits|url=|journal=International Journal of Numerical Modelling: Electronic Networks, Devices and Fields|volume=29|issue=1|pages=93–108|doi=10.1002/jnm.2049}}</ref>

== References ==