Alternating-direction implicit method: Difference between revisions

Revision as of 09:20, 20 August 2023

Latest revision as of 09:33, 15 April 2025

(8 intermediate revisions by 4 users not shown)

Line 1:

In [[numerical linear algebra]], the '''alternating-direction implicit (ADI) method''' is an iterative method used to solve [[Sylvester equation|Sylvester matrix equations]]. It is a popular method for solving the large matrix equations that arise in [[systems theory]] and [[Control theory|control]],<ref name=":1">{{Cite journal |last=Simoncini |first=V. |s2cid=17271167 |date=2016 |title=Computational Methods for Linear Matrix Equations |journal=SIAM Review |language=en |volume=58 |issue=3 |pages=377–441 |doi=10.1137/130912839 |issn=0036-1445|hdl=11585/586011 |hdl-access=free }}</ref> and can be formulated to construct solutions in a memory-efficient, factored form.<ref name=":2">{{Cite journal |last1=Li |first1=Jing-Rebecca |author1-link=Jing-Rebecca Li |last2=White |first2=Jacob |date=2002 |title=Low Rank Solution of Lyapunov Equations |journal=SIAM Journal on Matrix Analysis and Applications |language=en |volume=24 |issue=1 |pages=260–280 |doi=10.1137/s0895479801384937 |issn=0895-4798}}</ref><ref name=":3">{{Cite journal |last1=Benner |first1=Peter |last2=Li |first2=Ren-Cang |last3=Truhar |first3=Ninoslav |date=2009 |title=On the ADI method for Sylvester equations |journal=Journal of Computational and Applied Mathematics |volume=233 |issue=4 |pages=1035–1045 |doi=10.1016/j.cam.2009.08.108 |issn=0377-0427 |bibcode=2009JCoAM.233.1035B |doi-access=free}}</ref> It is also used to numerically solve [[Parabolic partial differential equation|parabolic]] and [[Elliptic partial differential equation|elliptic]] partial differential equations, and is a classic method used for modeling [[heat conduction]] and solving the [[diffusion equation]] in two or more dimensions.<ref name=":0">{{Citation |title=The numerical solution of parabolic and elliptic differential equations |year=1955 |last1=Peaceman |last2=Rachford Jr. |first1=D. W. |first2=H. H. |journal=Journal of the Society for Industrial and Applied Mathematics |volume=3 |issue=1 |pages=28–41 |doi=10.1137/0103003 |mr=0071874 |hdl=10338.dmlcz/135399 |hdl-access=free}}.</ref> It is an example of an [[operator splitting]] method.<ref>*{{Cite book | last1=Press | first1=W. H. | last2=Teukolsky | first2=S. A. | last3=Vetterling | first3=W. T. | last4=Flannery | first4=B. P. | year=2007 | title=Numerical Recipes: The Art of Scientific Computing | edition=3rd | publisher=Cambridge University Press | ___location=New York | isbn=978-0-521-88068-8 | chapter=Section 20.3.3. Operator Splitting Methods Generally | chapter-url=http://apps.nrbook.com/empanel/index.html#pg=1052 | access-date=2011-08-18 | archive-date=2011-08-11 | archive-url=https://web.archive.org/web/20110811154417/http://apps.nrbook.com/empanel/index.html#pg=1052 | url-status=dead }}</ref>

The method was developed at [[Humble Oil]] in the mid-1950s by Jim Douglas Jr, Henry Rachford, and Don Peaceman.<ref name=PurdueObit-Douglas>{{cite web|accessdate=March 25, 2025

|url=https://www.math.purdue.edu/news/2016/douglas_obit.html

|publisher=Purdue University|title=Prof. Jim Douglas

|date=May 2, 2016}}</ref>

== ADI for matrix equations ==

Line 36 ⟶ 41:

</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|last1=Saff|first1=E.B.|last2=Totik|first2=V.|publisher= Springer Science & Business Media |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= Mathematics of the USSR-Sbornik|volume=7|issue=4|pages=623–635|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 ====

Line 73 ⟶ 78:

and <math>\delta_p^2</math> is the central second difference operator for the ''p''-th coordinate

: <math>\delta_p^2 u_{ij}=u_{ij+e_p}-2u_{ij}+u_{ij-e_p}</math>

with <math>e_p=10(1,0)</math> or <math>01(0,1)</math> for <math>p=x</math> or <math>y</math> respectively (and <math>ij</math> a shorthand for lattice points <math>(i,j)</math>).

After performing a [[Von Neumann stability analysis|stability analysis]], it can be shown that this method will be stable for any <math>\Delta t</math>.

Line 95 ⟶ 100:

The usage of the ADI method as an [[operator splitting]] scheme can be generalized. That is, we may consider general evolution equations

: <math> \dot u = F_1 u + F_2 u, </math>

where <math> F_1 </math> and <math> F_2 </math> are (possibly nonlinear) operators defined on a [[Banach space|Banach]] space.<ref>{{cite book|last2=Verwer|first2=Jan|first1=Willem|last1=Hundsdorfer|title=Numerical Solution of Time-Dependent Advection-Diffusion-Reaction Equations|date=2003|publisher=Springer Berlin Heidelberg|___location=Berlin, Heidelberg|isbn=978-3-662-09017-6}}</ref><ref>{{cite journal|last1=Lions|first1=P. L.|last2=Mercier|first2=B.|title=Splitting Algorithms for the Sum of Two Nonlinear Operators|journal=SIAM Journal on Numerical Analysis|date=December 1979|volume=16|issue=6|pages=964–979|doi=10.1137/0716071|bibcode=1979SJNA...16..964L}}</ref> In the diffusion example above we have <math> F_1 = {\partial^2 \over \partial x^2} </math> and <math> F_2 = {\partial^2 \over \partial y^2} </math>.

== Fundamental ADI (FADI) ==

Line 104 ⟶ 109:

=== 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 |hdl-access=free}}</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 |hdl-access=free}}</ref>

==Further reading==

*{{cite journal|accessdate=March 28, 2025

|url=https://www.researchgate.net/publication/265623760 |via=ResearchGate.net

|title=50 Years of ADI Methods: Celebrating the Contributions of Jim Douglas, Don Peaceman, and Henry Rachford

|first1=Adam |last1=Usadi |first2=Clint |last2=Dawson

|journal=SIAM News |volume=39|number=2|date=March 2006}} (Provides a review of the ADI methods and variants over the years.)

== References ==

Line 113 ⟶ 125:

[[Category:Partial differential equations]]

[[Category:Numerical differential equations]]

[[Category:Iterative methods]]