Alternating-direction implicit method: Difference between revisions

Revision as of 04:41, 9 August 2021

Revision as of 16:57, 23 November 2021

Line 8:

=== When to use ADI ===

If <math>A \in \mathbb{C}^{m \times m}</math> and <math>B \in \mathbb{C}^{n \times n}</math>, then <math> AX - XB = C</math> can be solved directly in <math> \mathcal{O}(m^3 + n^3)</math> using the Bartels-Stewart method.<ref>{{Cite book|title=Matrix computations|lastlast1=Golub,|first1= G.|publisher=Johns Hopkins University|otherslast2=Van Loan,|first2= C|year=1989|isbn=1421407949|edition=Fourth |___location=Baltimore|oclc=824733531}}</ref> It is therefore only beneficial to use ADI when matrix-vector multiplication and linear solves involving <math>A</math> and <math>B</math> can be applied cheaply.

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.

Line 36:

</math>

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|lastlast1=1944-Saff|firstfirst1=Saff, E. B.|otherslast2=Totik, |first2=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 ====