|
|
| (One intermediate revision by one other user not shown) |
| Line 1: |
Line 1: |
| {{Distinguish2|[[exponential integral]] of [[exponential function]]s}}
| | [https://www.youtube.com/watch?v=zdvlRGr5pHg Best Man Wedding Speeches] |
| | |
| '''Exponential integrators''' are a class of [[numerical method]]s for the solution of [[partial differential equations|partial]] and
| |
| [[ordinary differential equations|ordinary]] differential equations. This large class of methods from [[numerical analysis]] is based on the exact integration of the [[Linear system|linear]] part of the initial value problem described later in this article.
| |
| Because the linear part is [[Integral|integrated]] exactly, this can help to mitigate the [[Stiff equation|stiffness]]
| |
| of a differential equation. Exponential integrators can be constructed to be [[Explicit and implicit methods|explicit or implicit]] for [[Numerical methods for ordinary differential equations|numerical ordinary differential equations]] or serve as the [[integrator|time integrator]] for [[numerical partial differential equations]].
| |
| | |
| == Background ==
| |
| Dating back to at least the 1960s, these methods were recognized by Certain<ref>Certain (1960)</ref> and Pope.<ref>Pope (1963)</ref> As of late [[exponential integrators]] have
| |
| become an active area of research. Originally developed for solving [[Stiff equation|stiff differential equations]], the methods have been used to solve [[partial differential equations]] including
| |
| [[Hyperbolic partial differential equations|hyperbolic]]
| |
| as well as
| |
| [[Parabolic partial differential equation|parabolic]]
| |
| problems<ref>Hochbruck & Ostermann, (2006)</ref> such as the [[heat equation]].
| |
| | |
| ==Introduction==
| |
| | |
| We consider [[initial value problem]]s of the form,
| |
| :<math>y'(t) = L y(t) + \mathcal{N}( y(t) ), \qquad y(t_0)=y_0, \qquad\qquad (1)</math>
| |
| where <math>L</math> is composed of [[Linear system|linear terms]],
| |
| and <math>\mathcal{N}</math> is composed of the [[Nonlinear system|non-linear]] terms.
| |
| These problems can come from a more typical [[initial value problem]]
| |
| :<math>y'(t) = f(y(t)), \qquad y(t_0)=y_0, </math>
| |
| after linearizing locally about a fixed or local state <math>y^*</math>:
| |
| :<math> L = \frac{\partial f}{\partial y}(y^*); \qquad \mathcal{N} = f(y) - L y.</math>
| |
| Here, <math>\frac{\partial f}{\partial y}</math> refers to the [[partial derivative]] of <math>f</math> with respect to <math>y</math>.
| |
| | |
| Exact integration of this problem from time 0 to a later time <math>t</math>
| |
| can be performed using [[matrix exponential]]s to define an integral equation for the exact solution:<ref name="Exponential integrators">Hochbruck & Ostermann, (2010)</ref>
| |
| :<math> y(t) = e^{L t } y_0 + \int_{0}^{t} e^{ L (t-\tau) } \mathcal{N}\left( y\left( \tau \right) \right)\, d\tau. \qquad (2) </math>
| |
| This is similar to the exact integral used in the [[Picard–Lindelöf theorem]]. In the case of <math>\mathcal{N}\equiv 0</math>, this formulation is the exact solution to the [[linear differential equation]].
| |
| | |
| Numerical methods require a [[discretization]] of equation (2). They can be based on
| |
| [[Runge-kutta method|Runge-Kutta]] discretizations,<ref>Cox and Mathews (2002)</ref><ref>Tokman (2006, 2011)</ref>
| |
| [[linear multistep method]]s or a variety of other options.
| |
| | |
| ==Examples==
| |
| | |
| See also: [[Numerical_ordinary_differential_equations#The first-order exponential integrator method|the first-order exponential integrator]] for more details.
| |
| | |
| === First-order forward Euler exponential integrator ===
| |
| | |
| The simplest method is based on a [[Euler method|forward Euler]] time discretization. It can be realized
| |
| by holding the term <math>\mathcal{N}( y(\tau) ) \approx \mathcal{N}( y(0) )</math> constant over the whole interval.
| |
| Exact integration of <math>e^{ L (t-\tau) }</math> then results in the
| |
| :<math>y(t) = e^{L t}y_0 + L^{-1} (e^{L t} - 1) \mathcal{N}( y( t_0 ) ).</math>
| |
| Of course, this process can be repeated over small intervals to serve as the basis of a single-step numerical method.
| |
| | |
| In general, one defines a sequence of functions,
| |
| :<math> \varphi_0( z ) = e^z; \qquad \varphi_1( z ) = \frac{e^z - 1}{z}, \qquad \varphi_2(z) = \frac{e^z - 1-z}{z^2}. </math>
| |
| that show up in these methods. Usually, these linear operators are not computed
| |
| exactly, but a [[Krylov subspace]] [[iterative method]] can be used to efficiently compute the multiplication of these operators times vectors efficiently.<ref>Tokman (2006, 2010)</ref>
| |
| See references for further details of where these functions come from.,<ref>Cox & Mathews (2002)</ref><ref>Hochbruck & Ostermann (2010)</ref>
| |
| | |
| === Fourth-order ETDRK4 method of Cox and Mathews ===
| |
| | |
| Cox and Mathews<ref>Cox and Mathews 2002</ref> describe a fourth-order method exponential time differencing (ETD) method that they used [[Maple (software)|Maple]] to derive.
| |
| | |
| We use their notation, and assume that the unknown function is <math>u</math>, and that we have a known solution <math>u_n</math> at time <math>t^n</math>.
| |
| Furthermore, we'll make explicit use of a possibly time dependent right hand side: <math>\mathcal{N} = \mathcal{N}( u, t )</math>.
| |
| | |
| Three stage values are first constructed:
| |
| :<math>
| |
| a_n = e^{ L h / 2 } u_n + L^{-1} \left( e^{Lh/2} - I \right) \mathcal{N}( u_n, t_n )
| |
| </math>
| |
| :<math>
| |
| b_n = e^{ L h / 2 } u_n + L^{-1} \left( e^{Lh/2} - I \right) \mathcal{N}( a_n, t_n + h/2 )
| |
| </math>
| |
| :<math>
| |
| c_n = e^{ L h / 2 } a_n + L^{-1} \left( e^{Lh/2} - I \right) \left( 2 \mathcal{N}( b_n, t_n + h/2 ) - \mathcal{N}(u_n,t_n) \right)
| |
| </math>
| |
| The final update is given by,
| |
| :<math>
| |
| u_{n+1} = e^{L h} u_n + h^{-2} L^{-3} \left\{
| |
| \left[ -4 - Lh + e^{Lh} \left( 4 - 3 L h + (L h)^2 \right) \right] \mathcal{N}( u_n, t_n ) +
| |
| 2 \left[ 2 + L h + e^{Lh} \left( -2 + L h \right) \right] \left( \mathcal{N}( a_n, t_n+h/2 ) + \mathcal{N}( b_n, t_n + h / 2 ) \right) +
| |
| \left[ -4 - 3L h - (Lh)^2 + e^{Lh} \left(4 - Lh \right) \right] \mathcal{N}( c_n, t_n + h )
| |
| \right\}.
| |
| </math>
| |
| | |
| If implemented naively, the above algorithm suffers from numerical instabilities due to [[floating point]] round-off errors.<ref>Kassam and Trefethen (2005)</ref> To see why, consider the first function,
| |
| :<math> \varphi_1( z ) = \frac{ 1 - e^z }{ z },</math>
| |
| which is present in the first-order Euler method, as well as all three stages of ETDRK4. For small values of <math>z</math>, this function suffers from numerical cancellation errors. However, these numerical issues can be avoided by evaluating the <math> \varphi_1 </math> function via a contour integral approach <ref>Kassam and Trefethen (2005)</ref> or by a Padé approximant. <ref>Berland and Skaflestad and Wright (2007)</ref>
| |
| | |
| == See also ==
| |
| *[[General linear methods]]
| |
| *[[Linear multistep method]]s
| |
| *[[Numerical analysis]]
| |
| *[[Numerical methods for ordinary differential equations]]
| |
| *[[Runge-Kutta methods]]
| |
| | |
| == Notes ==
| |
| <references/>
| |
| | |
| ==References==
| |
| {{reflist}}
| |
| | |
| * {{cite journal|title=B-series and Order Conditions for Exponential Integrators|
| |
| first1=Havard|last1=Berland|first2=Brynjulf|last2=Owren|first3=Bard|last3=Skaflestad|
| |
| journal=SIAM Journal of Numerical Analysis|volume=43|issue=4|pages=1715–1727|year=2005|
| |
| url=http://epubs.siam.org/doi/abs/10.1137/040612683}}
| |
| * {{cite book| last=Certaine | first=John|title=The solution of ordinary differential equations with large time constants|year=1960|pages=128–132|publisher=Wiley|booktitle=Mathematical methods for digital computers}}
| |
| * {{cite journal|last1=Cox|first1=S. M.|last2=Mathews|first2=P.C.|
| |
| title=Exponential time differencing for stiff systems|
| |
| doi=10.1006/jcph.2002.6995|journal=Journal of Computational Physics|volume=176|issue=2| date=March 2002 |pages=430–455|url=http://www.sciencedirect.com/science/article/pii/S0021999102969950}}
| |
| * {{cite journal|last1=Hochbruck|first1=Marlis|last2=Ostermann|first2=Alexander|title=Exponential integrators|journal=Acta Numer.| date=May 2010 |volume=19|pages=209–286|doi= 10.1017/S0962492910000048 |url=http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=7701740}}
| |
| * {{cite journal|last1=Hochbruck|first1=Marlis|last2=Ostermann|first2=Alexander|
| |
| title=Explicit exponential Runge-Kutta methods for semilinear parabolic problems|
| |
| journal=SIAM Journal of Numerical Analysis|volume=43|issue=3|pages=1069–1090|year=2005|doi=10.1137/040611434|url=http://epubs.siam.org/doi/abs/10.1137/040611434}}
| |
| * {{cite journal|last1=Hochbruck|first1=Marlis|last2=Ostermann|first2=Alexander|
| |
| title=Exponential Runge–Kutta methods for parabolic problems|
| |
| url=http://dx.doi.org/10.1016/j.apnum.2004.08.005|
| |
| doi=10.1016/j.apnum.2004.08.005|
| |
| journal=Applied Numerical Mathematics|
| |
| volume=53|issue=2-4| date=May 2005 |pages=323–339}}
| |
| * {{cite journal|last=Pope|first=David A|title=An exponential method of numerical integration of ordinary differential equations|journal=Communications of the ACM|volume=6|issue=8|pages=491–493|year=1963|doi=10.1145/366707.367592}}
| |
| * {{cite journal|
| |
| title=A new class of exponential propagation iterative methods of Runge–Kutta type (EPIRK)|
| |
| last=Tokman|first=Mayya|
| |
| doi=10.1016/j.jcp.2011.08.023|url=http://www.sciencedirect.com/science/article/pii/S0021999111005109|
| |
| journal=Journal of Computational Physics|
| |
| volume=230|issue=24| date=October 2011 |pages=8762–8778}}
| |
| * {{cite journal|title=Efficient integration of large stiff systems of ODEs with exponential propagation iterative (EPI) methods|
| |
| last=Tokman|first=Mayya| date=April 2006 |doi=10.1016/j.jcp.2005.08.032|
| |
| journal=Journal of Computational Physics|
| |
| volume=213|issue=2|pages=748–776|url=http://www.sciencedirect.com/science/article/pii/S0021999105004158}}
| |
| *{{cite journal|last=Trefethen|first=Lloyd N.|coauthors=Aly-Khan Kassam|title=Fourth-Order Time-Stepping for Stiff PDEs|journal=SIAM Journal of Scientific Computing|year=2005|volume=26|issue=4|pages=1214–1233|doi=10.1137/S1064827502410633|url=http://dx.doi.org/10.1137/S1064827502410633}}
| |
| * {{cite journal|last1=Berland|first1=Havard|last2=Skaflestad|first2=Bard|last3=Wright|first3=Will M.|title=EXPINT-A MATLAB Package for Exponential Integrators|journal=ACM Transactions on Mathematical Software|year=2007|volume=33|issue=1|doi=10.1145/1206040.1206044|url=http://doi.acm.org/10.1145/1206040.1206044}}
| |
| | |
| == External links ==
| |
| * [http://hgpu.org/?p=6901|Exponential integrators on GPGPUs]
| |
| * [http://www.mathworks.com/matlabcentral/fileexchange/40949-meshfree-exponential-integrator|MATLAB code for a meshfree exponential integrator]
| |
| | |
| {{Numerical integrators}}
| |
| | |
| {{DEFAULTSORT:Numerical Ordinary Differential Equations}}
| |
| [[Category:Numerical differential equations| ]]
| |
| [[Category:Ordinary differential equations]]
| |