Alternating-direction implicit method: Difference between revisions

Revision as of 04:47, 30 January 2023

Revision as of 22:18, 18 August 2023

Line 5:

=== 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|doi-access=free}}</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|last1=Lu|first1=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|doi-access=free}}</ref><ref name=":5">{{Cite journal|last1=Beckermann|first1=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|s2cid=3828461}}</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 ===