Alternating-direction implicit method: Difference between revisions

Revision as of 16:57, 23 November 2021

Revision as of 20:34, 27 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 algorithm|Bartels-Stewart method]].<ref>{{Cite book|title=Matrix computations|last1=Golub|first1= G.|publisher=Johns Hopkins University|last2=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.