Alternating-direction implicit method: Difference between revisions

Revision as of 06:00, 5 October 2022

Revision as of 04:08, 23 October 2022

Line 39:

==== 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|bibcode=1999SJSC...21.1401P |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>

=== Factored ADI ===

Line 89:

The system of equations involved is [[symmetric matrix|symmetric]] and tridiagonal (banded with bandwidth 3), and is typically solved using [[tridiagonal matrix algorithm]].

It can be shown that this method is unconditionally stable and second order in time and space.<ref>{{Citation | last1=Douglas | first1=J. Jr.| title=On the numerical integration of u_xx+ u_yy= u_t by implicit methods | mr=0071875 | year=1955 | journal=Journal of the Society for Industrial and Applied Mathematics | volume=3 | pages=42–65}}.

</ref> There are more refined ADI methods such as the methods of Douglas,<ref>{{Citation | last1=Douglas | first1=Jim Jr.| title=Alternating direction methods for three space variables | doi=10.1007/BF01386295 | year=1962 | journal=Numerische Mathematik | issn=0029-599X | volume=4 | issue=1 | pages=41–63| s2cid=121455963 }}.</ref> or the f-factor method<ref>{{Citation | last1=Chang | first1=M. J. | last2=Chow | first2=L. C. | last3=Chang | first3=W. S. | title=Improved alternating-direction implicit method for solving transient three-dimensional heat diffusion problems | doi=10.1080/10407799108944957 | year=1991 | journal=Numerical Heat Transfer, Part B: Fundamentals | issn=1040-7790 | volume=19 | issue=1 | pages=69–84| bibcode=1991NHTB...19...69C | url=https://zenodo.org/record/1234469 }}.</ref> which can be used for three or more dimensions.

=== Generalizations ===

Line 100:

=== 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|hdl=10356/138245 |s2cid=29025478}}</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|arxiv=2011.14043|bibcode=2008ITAP...56..170T|hdl=10356/138249 |s2cid=37135325}}</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.

=== Relations to other implicit methods ===

Many classical implicit methods by Peaceman-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|hdl=10356/138296 |s2cid=22940993}}</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|bibcode=2013ITAP...61.2630G|s2cid=7578037}}</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|journal=IEICE Transactions on Electronics|volume=E-97-C|issue=7|pages=636–644|doi=10.1587/transele.E97.C.636|bibcode=2014IEITE..97..636T|hdl=10220/20410 }}</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|journal=International Journal of Numerical Modelling: Electronic Networks, Devices and Fields|volume=29|issue=1|pages=93–108|doi=10.1002/jnm.2049|hdl=10356/137201 |s2cid=61039449 }}</ref>

== References ==