Alternating-direction implicit method: Difference between revisions

Revision as of 18:20, 2 November 2020

Revision as of 17:30, 26 November 2020

Line 9:

=== 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|last=Golub, G.|publisher=Johns Hopkins University|others=Van Loan, C|year=1989|isbn=1421407949|edition=Fourth |___location=Baltimore|pages=|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.

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.|volume=|pages=|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 Selection and the ADI error equation ===

Line 37:

</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|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|url=|journal=Mat. Sb. (N.S.)|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|url=|journal=Zap. Imp. Akad. Nauk. St. Petersburg|volume=30|pages=1–59|via=}}</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 ====

Line 101:

=== Simplification of ADI to FADI ===

It is possible to simplify the conventional ADI method into Fundamental ADI method, which only has the similar operators at the left-hand sides while being operator-free at the right-hand sides. This may be regarded as the fundamental (basic) scheme of ADI method,<ref>{{Cite journal|last=Tan|first=E. L.|date=2007|title=Efficient Algorithm for the Unconditionally Stable 3-D ADI-FDTD Method|url=https://www.ntu.edu.sg/home/eeltan/papers/2007%20Efficient%20Algorithm%20for%20the%20Unconditionally%20Stable%203-D%20ADI–FDTD%20Method.pdf|journal=IEEE Microwave and Wireless Components Letters|volume=17|issue=1|pages=7–9|doi=10.1109/LMWC.2006.887239|via=}}</ref><ref name=":8">{{Cite journal|last=Tan|first=E. L.|date=2008|title=Fundamental Schemes for Efficient Unconditionally Stable Implicit Finite-Difference Time-Domain Methods|url=https://www.ntu.edu.sg/home/eeltan/papers/2008%20Fundamental%20Schemes%20for%20Efficient%20Unconditionally%20Stable%20Implicit%20Finite-Difference%20Time-Domain%20Methods.pdf|journal=IEEE Transactions on Antennas and Propagation|volume=56|issue=1|pages=170–177|doi=10.1109/TAP.2007.913089|via=}}</ref> with no more operator (to be reduced) at the right-hand sides, unlike most traditional implicit methods that usually consist of operators at both sides of equations. The FADI method leads to simpler, more concise and efficient update equations without degrading the accuracy of conventional ADI method.

<br />

=== Relations to other implicit methods ===

Many classical implicit methods by Peachman-Rachford, Douglas-Gunn, D'Yakonov, Beam-Warming, Crank-Nicolson, etc., may be simplified to fundamental implicit schemes with operator-free right-hand sides.<ref name=":8" /> In their fundamental forms, the FADI method of second-order temporal accuracy can be related closely to the fundamental locally one-dimensional (FLOD) method, which can be upgraded to second-order temporal accuracy, such as for three-dimensional Maxwell's equations <ref>{{Cite journal|last=Tan|first=E. L.|date=2007|title=Unconditionally Stable LOD-FDTD Method for 3-D Maxwell's Equations|url=https://www.ntu.edu.sg/home/eeltan/papers/2007%20Unconditionally%20Stable%20LOD-FDTD%20Method%20for%203-D%20Maxwell’s%20Equations.pdf|journal=IEEE Microwave and Wireless Components Letters|volume=17|issue=2|pages=85–87|doi=10.1109/LMWC.2006.890166|via=}}</ref><ref>{{Cite journal|last1=Gan|first1=T. H.|last2=Tan|first2=E. L.|date=2013|title=Unconditionally Stable Fundamental LOD-FDTD Method with Second-Order Temporal Accuracy and Complying Divergence|url=https://www.ntu.edu.sg/home/eeltan/papers/2013%20Unconditionally%20Stable%20Fundamental%20LOD-FDTD%20Method%20With%20Second-Order%20Temporal%20Accuracy%20and%20Complying%20Divergence.pdf|journal=IEEE Transactions on Antennas and Propagation|volume=61|issue=5|pages=2630–2638|doi=10.1109/TAP.2013.2242036|via=}}</ref> in [[computational electromagnetics]]. For two- and three-dimensional heat conduction and diffusion equations, both FADI and FLOD methods may be implemented in simpler, more efficient and stable manner compared to their conventional methods. <ref>{{Cite journal|last1=Tay|first1=W. C.|last2=Tan|first2=E. L.|last3=Heh|first3=D. Y.|date=2014|title=Fundamental Locally One-Dimensional Method for 3-D Thermal Simulation|url=|journal=IEICE Transactions on Electronics|volume=E-97-C|issue=7|pages=636–644|doi=10.1587/transele.E97.C.636}}</ref><ref>{{Cite journal|last1=Heh|first1=D. Y.|last2=Tan|first2=E. L.|last3=Tay|first3=W. C.|date=2016|title=Fast Alternating Direction Implicit Method for Efficient Transient Thermal Simulation of Integrated Circuits|url=|journal=International Journal of Numerical Modelling: Electronic Networks, Devices and Fields|volume=29|issue=1|pages=93–108|doi=10.1002/jnm.2049}}</ref>

== References ==