Alternating-direction implicit method: Difference between revisions

Revision as of 08:33, 3 June 2020

Revision as of 15:42, 29 August 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}}</ref> and can be formulated to construct solutions in a memory-efficient, factored form.<ref name=":2">{{Cite journal|last1=Li|first1=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|last1=Benner|first1=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|doi-access=free}}</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 40:

==== Heuristic shift parameter strategies ====

When less is known about <math>\sigma(A)</math> and <math>\sigma(B)</math>, or when <math>A</math> or <math>B</math> 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,<ref>{{Cite journal|last=Starke|first=Gerhard|date=June 1993|title=Fejér-Walsh points for rational functions and their use in the ADI iterative method|journal=Journal of Computational and Applied Mathematics|volume=46|issue=1–2|pages=129–141|doi=10.1016/0377-0427(93)90291-i|issn=0377-0427|doi-access=free}}</ref> using the Ritz values of the matrices <math>A</math>, <math>A^{-1}</math>, <math>B</math>, and <math>B^{-1}</math> to formulate a greedy approach,<ref name=":7">{{Cite journal|last=Penzl|first=Thilo|date=January 1999|title=A Cyclic Low-Rank Smith Method for Large Sparse Lyapunov Equations|journal=SIAM Journal on Scientific Computing|language=en|volume=21|issue=4|pages=1401–1418|doi=10.1137/s1064827598347666|issn=1064-8275}}</ref> and cyclic methods, where the same small collection of shift parameters are reused until a convergence tolerance is met.<ref name=":7" /><ref name=":6" /> When the same shift parameter is used at every iteration, ADI is equivalent to an algorithm called Smith's method.<ref>{{Cite journal|last=Smith|first=R. A.|date=January 1968|title=Matrix Equation XA + BX = C|journal=SIAM Journal on Applied Mathematics|language=en|volume=16|issue=1|pages=198–201|doi=10.1137/0116017|issn=0036-1399}}</ref>

=== Factored ADI ===