L. B ERGAMASCHI a , M. C ALIARI b , AND M. V IANELLO c

The Leja-Euler-Midpoint exponential integrator for parabolic equations

L. B ERGAMASCHI ^a , M. C ALIARI ^b , AND M. V IANELLO ^c

a

Department of Mathematical Methods and Models for Sci. Applic., University of Padova, ITALY

b

Department of Computer Science, University of Verona, ITALY

c

Department of Pure and Applied Mathematics, University of Padua, ITALY

Abstract We apply a second-order exponential integrator, constructed by coupling the exponential-like Euler and Midpoint integrators, to large and sparse systems of ODEs, generated by Finite Difference or Finite Ele- ment spatial discretizations of parabolic PDEs of the advection-diffusion- reaction type. The underlying exponential-like matrix function is approx- imated by polynomial interpolation at a sequence of real Leja points, re- lated to the spectrum of the Jacobian matrix of the discretization (ReLPM, Real Leja Points Method). Numerical tests on 2D models show the effi- ciency of the Leja-Euler-Midpoint (LEM) exponential integrator, which is up to 5 times faster than a classical second-order implicit solver.

1 Semi-discretization of ADR models

Problem: parabolic equation of the Advection-Diffusion-Reaction (ADR) type [8], with mixed Dirichlet and Neumann boundary conditions



 

 

 

 

 

 

∂c

∂t = div(D(x, t)∇c) − div(cv(x, t)) + f(c, x, t) x ∈ Ω, t > 0

c(x, t) = g

D

(x, t) x ∈ Γ

^D

, t > 0

hD∇c(x, t), νi = g

^N

(x, t) x ∈ Γ

^N

, t > 0

c(x, 0) = u

0

(x) x ∈ Ω

Semi-discretization by Finite Difference (FD) or Finite Element (FE) yields the N × N system of ODEs

( ˙c = φ(c, t) = P

L⁻¹

[H(t)c + f (c, t) + q(t)] , t > 0 c(0) = u

0

Key points:

• P

L

diagonal matrix (by mass-lumping of the mass matrix P for FE)

• Neumann boundary conditions absorbed in q

• Dirichlet boundary conditions absorbed in f and u

0

2 The Exponential Euler-Midpoint integrator

Exponential integrator

( c

_k+1

= c

k

+ ∆t

k

ϕ(∆t

k

J(c

k

, t

k+1/2

)) φ(c

k

, t

k+1/2

) , k = 0, 1, 2, . . . c

0

= u

0

where ϕ(z) is the entire function

ϕ(z) = e

^z

− 1

z if z 6= 0, ϕ(0) = 1 , and J(c, t) is the Jacobian matrix

J(c, t) = ∂

c

φ(c, t) = P

_L⁻¹

[H(t) + ∂

c

f(c, t)] . Key points:

• exponentially fitted Euler (cf. [6]) coupled with exponential Mid- point (cf. [7, 10])

• second-order accuracy (exact for linear autonomous systems)

• the Jacobian of the reaction can be taken diagonal

3 The Real Leja Point Method (ReLPM)

Computational problem: efficient approximation of the exponential prop- agator ϕ(∆tJ)v, v ∈ R

^N

.

• Krylov-like methods: projecting the propagator on a “small” Krylov subspace of J (drawback: long-term recurrences in the nonsymmet- ric case, time step splitting needed for efficiency; see [6]).

• Direct polynomial interpolation/approximation of ϕ(z) on a suitable compact subset containing the spectrum of ∆tJ; see [2, 5, 9, 10].

ReLPM (Real Leja Point Method) for computing ϕ(A)v, A large, sparse and nonsymmetric:

ϕ(A)v ≈ p

m

(A)v , p

m

(A) =

m

X

j=0

d

j j−1

Y

k=0

(A − ξ

k

I) , m = 1, 2, . . .

with p

m

(z) Newton interpolating polynomial of ϕ(z) at a sequence of Leja points {ξ

k

} (cf. [1]) in a complex compact containing the spectrum of A.

• Stable interpolant, maximally and superlinearly convergent.

• Estimating compact subset: a suitable ellipse E

ρ^∗

in a confocal family {E

ρ

}, with real focal interval [α, β]. The parameter ρ is the capacity (half-sum of semiaxes) of the ellipse.

• Due to maximal convergence, we can interpolate at real Leja points in the interval [α, β] (real arithmetic!).

• Superlinear convergence estimate:

kϕ(∆tJ)v − p

m

(∆tJ)vk

2

= O ((eρ

^∗

/m)

^m

) , m ≥ (1 + θ)ρ

^∗

, θ > 0 .

4 Implementation of the ReLPM

1. I

NPUT

: J, v, ∆t, tol

2. Estimate the “spectral” focal interval [α, β] for ∆tJ, by Gershgorin’s theorem

3. Compute a sequence of Fast Leja Points {ξ

j

} in [α, β] as in [1]

4. d

0

:= ϕ(ξ

0

), w

0

:= v, p

0

:= d

0

w

0

, m := 0 5.

WHILE

e

^Leja_m

:= |d

m

| · kw

m

k

2

> tol

a) z := Jw

m

b) w

m+1

:= ∆t z − ξ

m

w

_m

c) m := m + 1

d) compute the next divided difference d

m

e) p

_m

:= p

_m−1

+ d

_m

w

_m

6. O

UTPUT

: the vector p

m

: kp

m

− ϕ(∆tJ)vk

2

≈ e

^Lejam

≤ tol

• Based on 2-term recurrence: 1 matrix-vector product and 2 DAXPYs per iteration.

• Low storage occupancy: 1 sparse matrix and 4 vectors.

• Good scalability: well structured for parallel implementation [4].

5 Numerical examples

Comparison of the Leja-Euler-Midpoint (LEM) exponential integrator, which is a second-order method, with a classical second-order method like Crank-Nicolson (CN), both with fixed time step ∆t.

• Implementation of CN: BiCGStab preconditioned by ILU(0) as linear solver (within Newton iterations for nonlinear instances).

• Fortran77 codes executed on an Alpha Station 600 with optimized linear algebra subroutines (optimized BLAS library).

5.1 FE discretization of an advection-dispersion model with linear reaction

• Equation:

∂c

∂t = div(D∇c) − div(cv) − kc, x = (x

1

, x

2

) ∈ Ω = {x

²1

+ x

²2

< 1}

where c is the solute concentration, D the hydrodynamic dispersion tensor, D

ij

= α

T

|v| δ

ij

+ (α

L

− α

^T

)v

i

v

j

/ |v|, v the velocity field, and k the reaction rate.

• Constant initial datum c(x, 0) ≡ 1 and Dirichlet boundary conditions c|

∂Ω

≡ 1; v = (1, 1), α

L

= α

T

= 0.00625.

• Spatial discretization by linear Finite Elements on a mesh of N = 35313 nodes and M = 70030 triangles (mesh parameter h = 0.0054).

FIGURE1.L2-norm of the solution with different values of the reaction rate k, computed by LEM with ∆t = h.

TABLE1. Comparison of the CN and LEM integrators for the equation above with k = 1000 at different time steps, up to steady-state (t = 2.7 10⁻²). BiCGS: average BiCGStab iterations per time step, Et=∆t: L2-error at time t = ∆t, ReLPM: average ReLPM iterations per time step, SU:

speed-up=(CPU of CN)/(CPU of LEM).

CN LEM

∆t BiCGS Et=∆t CPU s. ReLPM CPU s. SU

h 1.0 3E-1 8.3 10.2 8.0 1.0

h/4 1.0 6E-2 9.0 8.9 9.1 1.0

h/8 1.0 1E-2 18.1 7.8 11.7 1.6

h/16 1.0 2E-3 36.2 7.1 16.9 2.1

h/32 1.0 5E-4 72.3 6.7 26.9 2.7

h/64 1.0 4E-4 143.9 6.4 47.7 3.0

• Notice that CN with large time steps is inaccurate already at the first discrete time instant t = ∆t; see the third column in the table above, where the error E

t=∆t

compares CN with LEM (which is here exact).

5.2 FD discretization of a 2D semilinear problem with a travelling wave solution

• Equation:

∂c

∂t = ε∇

²

c − α∇c + γc

²

(1 − c), x = (x

1

, x

2

) ∈ Ω = (0, 1)

²

• Initial (t = 0) and boundary conditions compatible with the exact

“travelling wave” solution

c(x

1

, x

2

, t) = (1 + exp(a(x

1

+ x

2

− bt) + c))

⁻¹

where a = pγ/4ε, b = 2α + √γε and c = a(b − 1), with α = −1, ε = 0.001 and γ = 100.

• Spatial discretization is obtained by third-order upwind-biased dif- ferences for the advection (cf. [8]) on a 160×160 grid (grid parameter h = 1/160 = 0.00625).

TABLE2.Comparison of the CN and LEM integrators for equation above at different time steps.

Newt: average Newton iterations per time step, BiCGS: average BiCGStab iterations per time step, Et=1: L2-error at final time, ReLPM: average ReLPM iterations per time step, SU: speed-up=(CPU of CN)/(CPU of LEM).

CN LEM

∆t Newt BiCGS CPU s. Et=1 ReLPM CPU s. Et=1 SU

h 2.8 4.0 103.5 8E-2 12.0 19.8 8E-2 5.2

h/2 2.2 2.2 150.3 3E-2 9.6 32.1 3E-2 4.7

h/4 2.2 1.9 270.5 2E-2 8.3 55.4 2E-2 4.9

h/8 2.2 1.9 477.9 2E-2 7.5 101.9 2E-2 4.7

FIGURE2.Computed eigenvalues (LAPACK) of the Jacobian matrices (40 × 40 spatial grid) in the Euler-Midpoint exponential integrator applied to the equation above, at t = 0, t = 0.5, t = 1.

FIGURE3.Plot of the computed solution (travelling wave) at t = 0.9.

References

[1] J. Baglama, D. Calvetti, and L. Reichel, Fast Leja points, Electron. Trans. Numer. Anal. 7 (1998), pp. 124–140.

[2] L. Bergamaschi, M. Caliari, and M. Vianello, Efficient approximation of the exponential op- erator for discrete 2D advection-diffusion problems, Numer. Linear Algebra Appl. 10 (2003), pp. 271–289.

[3] L. Bergamaschi, M. Caliari, and M. Vianello, The ReLPM exponential integrator for FE dis- cretizations of advection-diffusion equations, Springer LNCS vol. 3039, 2004, pp. 434–442.

[4] L. Bergamaschi, M. Caliari, A. Martinez and M. Vianello, A parallel exponential integrator for large-scale discretizations of advection-diffusion models, ParSim2005, submitted.

[5] M. Caliari, M. Vianello, and L. Bergamaschi, Interpolating discrete advection-diffusion prop- agators at Leja sequences, J. Comput. Appl. Math. 172 (2004), pp. 79–99.

[6] M. Hochbruck, C. Lubich, and H. Selhofer, Exponential integrators for large systems of dif- ferential equations, SIAM J. Sci. Comput. 19 (1998), pp. 1552–1574.

[7] M. Hochbruck, C. Lubich, On Magnus integrators for time-dependent Schr¨odinger equations, SIAM J. Numer. Anal. 41 (2003), pp. 945–963

[8] W. Hundsdorfer and J. G. Verwer, Numerical Solution of Time-Dependent Advection- Diffusion-Reaction equations, Springer, Berlin, 2003.

[9] I. Moret and P. Novati, An interpolatory approximation of the matrix exponential based on Faber polynomials, J. Comput. Appl. Math. 131 (2001), pp. 361–380.

[10] M. J. Schaefer, A polynomial based iterative method for linear parabolic equations, J. Comput.

Appl. Math. 29 (1990), pp. 35–50.

Work supported by the MIUR-PRIN2003 project “Dynamical systems on matrix manifolds: numerical methods and applications” (coordinator L. Lopez, Bari) and by the GNCS-INdAM.