Alternating-direction implicit method: Difference between revisions

Revision as of 18:51, 30 March 2021

Revision as of 18:56, 30 March 2021

Line 1:

In [[numerical linear algebra]], the '''Alternating Directionalternating-direction Implicitimplicit (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=WHW. H. | last2=Teukolsky | first2=SAS. A. | last3=Vetterling | first3=WTW. T. | last4=Flannery | first4=BPB. P. | 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>

</ref>

== ADI for matrix equations ==

Line 15 ⟶ 14:

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.|hdl=1911/20641|type=Thesis}}</ref> [[Krylov subspace]] methods, such as the Rational Krylov Subspace Method,<ref>{{Cite journal|last1=Druskin|first1=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 Parameter Selectionselection and the ADI error equation ===

The problem of finding good shift parameters is nontrivial. This problem can be understood by examining the ADI error equation. After <math>K</math> iterations, the error is given by

Line 39 ⟶ 38:

where the infimum is taken over all rational functions of degree <math>(K, K)</math>.<ref name=":5" /> This approximation problem is related to several results in [[potential theory]],<ref>{{Cite book|title=Logarithmic potentials with external fields|last=1944-|first=Saff, E. B.|others=Totik, V.|isbn=9783662033296|___location=Berlin|oclc=883382758|date = 2013-11-11}}</ref><ref>{{Cite journal|last=Gonchar|first=A.A.|date=1969|title=Zolotarev problems connected with rational functions|journal=Mat. Sb. |series=New Series|volume=78 (120):4|issue=4|pages=640–654|bibcode=1969SbMat...7..623G|doi=10.1070/SM1969v007n04ABEH001107}}</ref> and was solved by [[Yegor Ivanovich Zolotarev|Zolotarev]] in 1877 for <math>E</math> = [a, b] and <math> F=-E.</math><ref>{{Cite journal|last=Zolotarev|first=D.I.|date=1877|title=Application of elliptic functions to questions of functions deviating least and most from zero|journal=Zap. Imp. Akad. Nauk. St. Petersburg|volume=30|pages=1–59}}</ref> The solution is also known when <math> E</math> and <math> F</math> are disjoint disks in the complex plane.<ref>{{Cite journal|last=Starke|first=Gerhard|date=July 1992|title=Near-circularity for the rational Zolotarev problem in the complex plane|journal=Journal of Approximation Theory|volume=70|issue=1|pages=115–130|doi=10.1016/0021-9045(92)90059-w|issn=0021-9045|doi-access=free}}</ref>

==== 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>