Abstract
The localized exponential time differencing method based on overlapping domain decomposition has been recently introduced and successfully applied to parallel computations for extreme-scale numerical simulations of coarsening dynamics based on phase field models. In this paper, we focus on numerical solutions of a class of semilinear parabolic equations with the well-known Allen–Cahn equation as a special case. We first study the semi-discrete system under the standard central difference spatial discretization and prove the equivalence between the monodomain problem and the corresponding multidomain problem obtained by the Schwarz waveform relaxation iteration. Then we develop the fully discrete localized exponential time differencing schemes and, by establishing the maximum bound principle, prove the convergence of the fully discrete localized solutions to the exact semi-discrete solution and the convergence of the iterative solutions. Numerical experiments are carried out to verify the theoretical results in one-dimensional space and test the convergence and accuracy of the proposed algorithms with different numbers of subdomains in two-dimensional space.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Semilinear parabolic equations have been widely used in many mathematical models for various fields ranging from physics, chemistry, biology to materials and social sciences. Some examples of semilinear parabolic equations include the reaction–diffusion equations for chemical reactions and population dynamics [13], the Allen–Cahn and Cahn–Hilliard equations for modeling phase transitions [2, 3], the epitaxial growth models for simulating growth of thin films [28], the phase field crystal models for predicting crystal nucleation and growth [8], the time-dependent advection-diffusion and Navier–Stokes equations for fluids dynamics [31], the Ginzburg–Landau equations for modeling superconductivity [5] and so on. The analytic solutions of these models are usually not available, hence numerical methods play an important role in studying these models. Applying spatial discretizations, such as finite difference, finite element, or spectral collocation methods, to these semilinear parabolic equations will lead to a system of ordinary differential equations (ODEs) in time, which usually consists of highly stiff linear and/or nonlinear terms. When we consider time-marching approaches to the resulting ODE system, this stiffness leads to a severe constraint on the time step size for the sake of numerical stability. Therefore, traditional time-stepping schemes based on forward and backward differentiation formulas are not adequate for efficient numerical methods for the models mentioned above. In recent decades, numerous researches are devoted to efficient and stable time discretizations for highly stiff ODE systems, such as large stability domain ODE solvers [25, 29], strong stability preserving methods [12, 21, 30], and exponential integrator methods [18, 26].
Exponential time differencing (ETD) methods are efficient numerical methods for the temporal integration of ODE systems based on exponential integrators. Thorough reviews on ETD methods are given in [4, 17, 18]. The ETD methods are derived based on the variation-of-constants formula with the nonlinear terms in the system approximated by polynomial interpolations, followed by exact integration of the resulting integrals. Since the contribution of the linear part is evaluated exactly, the ETD methods provide desirable stability and accuracy by further combining with linear splitting techniques for stabilization of the nonlinear term, and hence, larger time step sizes are allowed while explicit methods often require a severe restriction on time step sizes. By using the special structure of the linear operator, the ETD methods often can be implemented via fast algorithms on regular domains, which leads to successful applications of these methods to efficient simulations of coarsening dynamics in materials science, see, e.g., [6, 22,23,24, 33] for the excellent numerical performance of ETD methods.
Applications of the ETD methods were limited initially due to the massive calculations for evaluating multiplications of matrix exponentials and vectors, especially when the size of the matrix is large. For the sake of practical implementation of the ETD methods, a large number of studies were devoted to the development of efficient algorithms for the action of matrix exponentials, see, e.g., [1, 16]. Alternatively, a localized compact ETD algorithm based on overlapping domain decomposition was first introduced in [32] for extreme-scale phase field simulations of three-dimensional coarsening dynamics on supercomputers. The key idea of this algorithm is that the ETD method is conducted locally in each subdomain in parallel and the data in the overlapping regions is transferred to the corresponding neighboring subdomains for time marching. The numerical results showed satisfactory computational efficiency and accuracy of the algorithm, though the theoretical analysis was not given there.
To our knowledge, the first literature on numerical analysis of localized ETD algorithms with overlapping domain decomposition was provided by [14] for the diffusion equation in one-dimensional space. For the continuous and space-discrete problems of the diffusion problem, the equivalence of the multidomain problem to the corresponding monodomain one was proven in [11] by showing the convergence of the iterative solutions generated by the Schwarz waveform relaxation algorithm. In the fully discrete version, however, the localized ETD scheme is not equivalent to the corresponding monodomain ETD scheme. In [14], the fully discrete first- and second-order localized ETD solutions were proven to converge to the exact solution of the space-discrete multidomain problem. Then, two types of iterative algorithms were proposed for practical calculations: one is based on the Schwarz iteration conducted at each time step and involves solving stationary problems in the subdomains in each iteration, while the other is based on the Schwarz waveform relaxation algorithm where the space-discrete problem is solved in the subdomains in each iteration. The iterative solutions were then proven to converge to the fully discrete localized ETD solutions at the same rate as the Schwarz iteration algorithm studied in [11] for the continuous and space-discrete problems. The analysis given in [14] is mainly based on the maximum principle of the diffusion equation and the corresponding discrete versions. The methods have also been extended to the case of nonoverlapping subdomains in [15], where the convergence of the localized ETD solutions is proven based on the variation-of-constants formula.
As a continuation of [14], we consider in this paper the numerical analysis of localized ETD methods with overlapping subdomains for semilinear parabolic equations. It should be noted that the equivalence between the semilinear parabolic problem and the corresponding multidomain problem was shown in [10] by considering the Schwarz waveform relaxation iteration for the continuous equations. The linear and superlinear convergence rates of the iterative solutions were also proven for the cases of unbounded and bounded time intervals, respectively. In this work, we first consider the semi-discrete problem and the corresponding multidomain problem by using the central difference approximation in space. We obtain the equivalence of both problems by proving rigorously the convergence of the iterative solutions generated by the Schwarz waveform relaxation algorithm. Then, we derive the fully discrete schemes by using the localized ETD approximation in time with first- and second-order accuracy and, similar to [14], propose two types of iterative algorithms for practical computations. Instead of the maximum principle for the diffusion problem, the semilinear parabolic equations with suitable nonlinear terms satisfy the “maximum bound principle” (see [7] and references cited therein), which says, there exists a constant such that if the absolute value of initial and boundary data is bounded by this constant, then the solution is also bounded by the same constant in the whole time and space. We show that such a maximum bound principle can be preserved by the semi-discrete multidomain problem and the fully discrete localized ETD schemes. The temporal convergence is proven by standard consistency and stability estimates using the maximum bound principle.
The rest of this paper is organized as follows. In Sect. 2, the model initial-boundary-value problem of semilinear parabolic equations is introduced along with the multidomain problem based on overlapping domain decomposition. For completeness, we present the convergence results of the Schwarz waveform relaxation methods studied in [10]. In Sect. 3, we consider the semi-discrete system of the original problem and prove the linear convergence of the overlapping Schwarz waveform relaxation algorithm for the semi-discrete multidomain problem. The fully discrete first- and second-order localized ETD schemes are presented in Sect. 4, as well as the iterative algorithms for solving the discrete coupled problems. In Sect. 5, the convergence of the iterative localized ETD solutions and the temporal convergence of the fully discrete solutions to the exact semi-discrete solutions are proven. In Sect. 6, numerical experiments are carried out in one- and two-dimensional cases to study the convergence behaviors of the proposed algorithms. Finally, some concluding remarks are given in Sect. 7.
2 Model problem and overlapping domain decomposition
In this section, we first introduce the model problem of semilinear parabolic equations, then we present the multidomain problem based on overlapping domain decomposition and recall the convergence results of the Schwarz waveform relaxation algorithm given in [10].
Let us consider the following semilinear parabolic equation in one-dimensional space:
where \(D>0\) is the diffusion coefficient and \(f\in C^1(\mathbb {R})\) satisfies (F1) there exists \(\rho >0\) such that \(f(\rho )\le 0\le f(-\rho )\);
(F2) the derivative \(f'(s)\) is bounded from above in \(\mathbb {R}\) and denote by \(\displaystyle R=\sup \nolimits _{s\in \mathbb {R}}f'(s)\).
It is shown in [7] that under condition (F1), problem (1) satisfies the maximum bound principle which will be stated later. Condition (F2) actually gives a restriction on the increasing rate of the nonlinear term and it will be used in the proofs of the convergence results (Theorems 3, 7, and 8) in later sections. A simple example of f could be \(f(s)=-s\) with \(R=-1\) and arbitrary positive \(\rho \). Another important example is given by \(f(s)=s-s^3\) with \(R=1\) and \(\rho \ge 1\), which corresponds to the Allen–Cahn equation. We assume that the given boundary and initial data \(g_1(t)\), \(g_2(t)\), and \(u_0(x)\) are piecewise continuous, so that the existence and uniqueness of a solution of (1) is guaranteed. We define the following norms for any function \(v\in C([0,L]\times [0,T])\):
The well-known maximum bound principle of problem (1) can be stated as follows (see, e.g., [7, 9]): for the constant \(\rho >0\) in (F1), if \(\max \{\Vert u_0\Vert _\infty ,\Vert g_1\Vert _T,\Vert g_2\Vert _T\}\le \rho \), then the solution u(x, t) of (1) satisfies \(\Vert u\Vert _{\infty ,T}\le \rho \).
Let us decompose the domain \(\Omega =(0,L)\) into two overlapping subdomains \(\Omega _1=(0,\beta L)\) and \(\Omega _2=(\alpha L,L)\) with \(0<\alpha<\beta <1\) as given in Fig. 1.
A decomposition into two overlapping subdomains [14]
The solution u(x, t) of (1) now can be obtained from the solutions v(x, t) on \(\overline{\Omega }_1\times [0,T]\) and w(x, t) on \(\overline{\Omega }_2\times [0,T]\) of the coupled problems:
and
Note that the pair (v, w) with \(v=u\) on \(\overline{\Omega }_1\times [0,T]\) and \(w=u\) on \(\overline{\Omega }_2\times [0,T]\) is the solution of (2). The uniqueness is obtained as a result of the convergence of the Schwarz waveform relaxation algorithm, which involves, at each iteration \(k=0,1,\dots \), the solution of
and
where \(v^{(0)}(\alpha L,t)\) and \(w^{(0)}(\beta L,t)\) are given initial guesses. The convergence of the Schwarz iteration (3) is guaranteed by the following theorem in [10].
Theorem 1
The Schwarz iterative solution \((v^{(k)},w^{(k)})\) of (3) converges to the solution (v, w) of (2) at the superlinear rate:
where \({{\,\mathrm{erfc}\,}}\) denotes the complementary error function.
3 Semi-discrete problems and maximum bound principles
In this section, we first consider the semi-discrete problem for (1) by finite difference discretizations and prove the semi-discrete maximum bound principle. Then, after presenting some useful lemmas, we show that the semi-discrete multidomain problem, by the Schwarz waveform relaxation iteration, is equivalent to the monodomain problem.
3.1 Monodomain problem
Let us consider the spatial discretization by using the standard second-order central difference with a uniform grid of size \(h=L/(N+1)\). Denote by \(\pmb {u}(t)=(u_1(t),u_2(t),\dots ,u_N(t))^T\) with \(u_j(t)\) representing the approximation of u(jh, t) for \(j=1,2, \dots , N\). We obtain the following ODE system for the semi-discrete problem of (1):
where the \(N\times N\) matrix \(A_{(N)}\), the vector-valued functions \(\pmb {f}(\pmb {u})\) and \(\pmb {B}(g_1(t),g_2(t))\) are given by
and \(\pmb {u}_{0}\) is the initial vector, \(\pmb {u}_0=(u_0(h),u_0(2h),\dots ,u_0(Nh))^T\). Define the following norms for each function \(\pmb {v}=(v_1,v_2,\dots ,v_N)^T\in C([0,T];\mathbb {R}^N)\):
We now establish the semi-discrete version of the maximum bound principle. It should be noted that the general framework proposed in [7] gives a systematic analysis on the maximum bound principle. In spite of this, we still present a brief statement for the special case here for completeness of this paper. By introducing a stabilizing constant \(S>0\), the semi-discrete problem (4) is equivalent to
where \(\pmb {f}^S(\pmb {u})=\pmb {f}(\pmb {u})+S\pmb {u}\). In the following, we impose a condition on the stabilizing constant S such that
Lemma 1
Under condition (6), we have
(i) \(|f^S(\xi )|\le S\rho \) for any \(\xi \in [-\rho ,\rho ]\);
(ii) \(|f^S(\xi _1)-f^S(\xi _2)|\le 2S|\xi _1-\xi _2|\) for any \(\xi _1,\xi _2\in [-\rho ,\rho ]\).
Proof
We have \(f^S(\xi )=f(\xi )+S\xi \) and \((f^S)'(\xi )=f'(\xi )+S\). To prove (i), as \((f^S)'(\xi )\ge 0\) for any \(\xi \in [-\rho ,\rho ]\) (deduced from (6)), we use condition (F1) and obtain
Again by (6), we have \(|(f^S)'(\xi )|\le 2S\) for any \(\xi \in [-\rho ,\rho ]\), which leads to (ii).
Theorem 2
Suppose that \(\max \{\Vert u_0\Vert _\infty ,\Vert g_1\Vert _T,\Vert g_2\Vert _T\}\le \rho \), then the semi-discrete system (4) admits a unique solution \(\pmb {u}\in C([0,T];\mathbb {R}^N)\) and \(\Vert \pmb {u}\Vert _{\infty ,T}\le \rho \).
Proof
Denote \(B_\rho =\{\pmb {\xi }\in \mathbb {R}^N:\Vert \pmb {\xi }\Vert _\infty \le \rho \}\) and \(X_t=C([0,t];B_\rho )\). Clearly, \(X_t\), equipped with the norm \(\Vert \cdot \Vert _{X_t}=\Vert \cdot \Vert _{\infty ,t}\), becomes a Banach space for each \(t\in [0,T]\). We need to show that there exists a unique solution \(\pmb {u}\in X_T\) of the system (4).
Given \(T_1\in (0,T]\) and \(\pmb {\phi }\in X_{T_1}\), we denote by \(\pmb {\psi }\) the solution of
Obviously, \(\pmb {\psi }\) is uniquely defined since \(A_{(N)}-SI_{(N)}\) (with \(I_{(N)}\) the \(N\times N\) identity matrix) is symmetric and negative definite. If \(\Vert \pmb {\psi }\Vert _{\infty ,T_1}\le \max \{\Vert \pmb {u}_0\Vert _\infty ,\Vert g_1\Vert _T,\Vert g_2\Vert _T\}\), then \(\pmb {\psi }\in X_{T_1}\). Otherwise, suppose that there exists \((j_0,t_0)\) with \(1\le j_0\le N\) and \(t_0\in (0,T_1]\) such that \(\psi _{j_0}(t_0)=\Vert \pmb {\psi }\Vert _{\infty ,T_1}\), then we have
which implies that
Since \(|\phi _{j_0}(t_0)|\le \rho \), by Lemma 1-(i), we deduce from (7) that \(\psi _{j_0}(t_0)\le \rho \), and thus, \(\Vert \pmb {\psi }\Vert _{\infty ,T_1}\le \rho \). Similarly, if there exists \((j_0',t_0')\) with \(1\le j_0'\le N\) and \(t_0'\in (0,T_1]\) such that \(\psi _{j_0'}(t_0')=-\Vert \pmb {\psi }\Vert _{\infty ,T_1}\), we can also show that \(\Vert \pmb {\psi }\Vert _{\infty ,T_1}\le \rho \). In any case, we obtain the unique solution \(\pmb {\psi }\in X_{T_1}\).
Denote by \(\mathcal {A}\) the mapping \(\pmb {\phi }\mapsto \pmb {\psi }\) from \(X_{T_1}\) to \(X_{T_1}\). Next we demonstrate that \(\mathcal {A}\) is a strict contraction if \(T_1\) is small sufficiently. To this end, we choose \(\pmb {\phi },\pmb {\widetilde{\phi }}\in X_{T_1}\) and define \(\pmb {\psi }=\mathcal {A}(\pmb {\phi }),\pmb {\widetilde{\psi }}=\mathcal {A}(\pmb {\widetilde{\phi }})\). The difference \(\varepsilon _{\pmb {\psi }}=\pmb {\psi }-\pmb {\widetilde{\psi }}\) satisfies
or equivalently,
Since \(A_{(N)}\) is strictly diagonally dominant with all negative diagonal entries, we know from [7] that the set of operators \(\{\mathrm {e}^{tA_{(N)}}\}_{t>0}\) becomes a contraction semigroup in the sense of matrix \(\infty \)-norm, namely, \(\Vert \mathrm {e}^{tA_{(N)}}\Vert _\infty \le 1\). Thus, using Lemma 1-(ii), we derive
and then,
Choose \(T_{1}\) small sufficiently such that \(T_1<S^{-1}\ln 2\), then \(2(1-\mathrm {e}^{-ST_1})<1\), which means \(\mathcal {A}\) is a strict contraction.
Since \(X_{T_1}\) is complete, we can apply the Banach’s fixed-point theorem to obtain a unique solution \(\pmb {u}\in X_{T_1}\) of the system (5) (or equivalently, of the system (4)) on the time interval \([0,T_1]\). Note that \(T_1\) depends only on the constant S, so we can repeat the same argument to extend the solution to the time interval \([T_1,2T_1]\). After finite steps, we obtain the unique solution \(\pmb {u}\in X_T\) on the time interval [0, T].
3.2 Preliminary lemmas
We now establish the semi-discrete analogue of the positivity lemma [10, Lemma 2.1]. For vectors \(\pmb {\phi },\pmb {\psi }\in \mathbb {R}^N\), we write \(\pmb {\phi }\ge \pmb {\psi }\) if \(\phi _j\ge \psi _j\) for all \(1\le j\le N\).
Lemma 2
Assume that \(C(t)={{\,\mathrm{diag}\,}}\{c_1(t),c_2(t),\dots ,c_N(t)\}\) and there exists a constant \(R_0\) such that \(c_j(t)\le R_0\) for all \(1\le j\le N\) and \(t\in [0,T]\). If a function \(\pmb {\psi }(t)\) satisfies the system
then \(\pmb {\psi }(t)\ge \pmb {0}\) for any \(t\in [0,T]\).
Proof
First, we consider the special case: \(c_j(t)<0\) for all \(1\le j\le N\) and \(t\in [0,T]\), namely, the diagonal entries of C(t) are negative. Assume that there exists \((j_0,t_0)\) with \(1\le j_0\le N\) and \(t_0\in (0,T]\) such that
We shall show \(\psi _{j_0}(t_0) \ge 0\) by contradiction. Suppose that \(\psi _{j_0}(t_0) < 0\), then it is implied that
In addition, as \(c_{j_0}(t_0)<0\), we obtain
which is contrary to the first inequality in (8). Hence, \(\psi _{j_0}(t_0)\ge 0\) and so \(\pmb {\psi }(t)\ge \pmb {0}\) for any \(t\in [0,T]\).
Next, we consider the general case. For any fixed \(\varepsilon >0\), let \(R_\varepsilon :=R_0+\varepsilon \) and \(\pmb {\phi }(t):=\mathrm {e}^{-R_\varepsilon t}\pmb {\psi }(t)\). Then \(\pmb {\psi }(t)=\mathrm {e}^{R_\varepsilon t}\pmb {\phi }(t)\) and we have
which means that the function \(\pmb {\phi }(t)\) satisfies the inequality
and \(\pmb {\phi }(0)=\pmb {\psi }(0)\ge \pmb {0}\). Since \(c_j(t)<R_\varepsilon \), namely, the diagonal entries of \(C(t)-R_\varepsilon I_{(N)}\) is negative, by the above argument, we have \(\pmb {\phi }(t)\ge \pmb {0}\), and consequently, \(\pmb {\psi }(t)\ge \pmb {0}\).
Corollary 1
Suppose that \(\pmb {\psi }(t)\) satisfies the system
where C(t) satisfies the assumption given in Lemma 2. Then it holds that
for any \(1\le j\le N\) and \(0\le t\le T\), where \((\cdot )_{j,k}\) denotes the (j, k)-entry of a matrix.
Proof
Let \(\pmb {\widetilde{\psi }}(t)\) be the solution of the following system:
or equivalently,
From Lemma 2 we have that \(\pmb {\widetilde{\psi }}(t)\ge \pmb {0}\) for \(0\le t\le T\). Note that
where \(\varepsilon _{\pmb {\psi }}(t):=\pmb {\widetilde{\psi }}(t)-\pmb {\psi }(t)\). By the definitions of \(\pmb {\psi }\), \(\pmb {\widetilde{\psi }}\) and using (9), we deduce that \(\varepsilon _{\pmb {\psi }}(t)\) satisfies the system:
According to Lemma 2, we have \(\pmb {\widetilde{\psi }}(t)-\pmb {\psi }(t)\ge \pmb {0}\). A similar result holds for the sum \(\pmb {\widetilde{\psi }}(t)+\pmb {\psi }(t)\ge \pmb {0}\). Hence, we obtain
that is,
which completes the proof.
The following lemma gives the estimates related to the entries of the matrix \(\mathrm {e}^{tA_{(N)}}\) and will be used in the analysis later.
Lemma 3
For the tridiagonal matrix \(A_{(N)}\) defined above, we have
for any \(1\le j\le N\) and \(t>0\).
Proof
Since \(A_{(N)}=\theta (-2I_{(N)}+J)\), where \(\theta =D/h^2\) and J contains only nonnegative entries, we have
which implies that the matrix \(\mathrm {e}^{\tau A_{(N)}}\) has only nonnegative entries. Thus, for any \(1\le j,k\le N\) and \(t>0\), we derive
Since \(A_{(N)}\) is symmetric and negative definite and
according to the property of matrix functions (see, e.g., [19, Theorem 6.2.9]), we have
The entries of the inversion of \(A_{(N)}\) is given by [20]
Combining (11)–(13), we obtain
Setting \(k=1\) and \(k=N\) lead to the inequalities (10a) and (10b), respectively.
3.3 Multidomain problem and Schwarz waveform relaxation method
For the overlapping domain decomposition as given in Fig. 1, we assume that \(\alpha L=N_\alpha h\) and \(\beta L=N_\beta h\) for some integers \(N_\alpha \) and \(N_\beta \) such that \(1<N_\alpha<N_\beta <N\). Denote by \(N_1=N_\beta -1\) and \(N_2=N-N_\alpha \) the numbers of interior grid points in \(\Omega _1\) and \(\Omega _2\), respectively. Set \(N_{\beta ,\alpha }=N_\beta -N_\alpha \). As in the continuous case, the solution \(\pmb {u}(t)\) of (4) can be obtained from the solutions \(\pmb {v}(t)=(v_j(t))_{1\le j\le N_1}\) on \(\overline{\Omega }_1\times [0,T]\) and \(\pmb {w}(t)=(w_j(t))_{1\le j\le N_2}\) on \(\overline{\Omega }_2\times [0,T]\) of the following two coupled problems:
and
where \(A_1=A_{(N_1)}\), \(A_2=A_{(N_2)}\), and
Applying the Schwarz waveform relaxation iteration to the coupled problems (14), we obtain
and
where \(v_{N_\alpha }^{(0)}(t)\) and \(w_{N_{\beta ,\alpha }}^{(0)}(t)\) are given initial guesses. The convergence of the semi-discrete Schwarz iteration (15) is guaranteed by the following theorem. Note that in [10], the Schwarz iteration was proven to converge only for continuous problems.
Theorem 3
The Schwarz iterative solution \((\pmb {v}^{(k)},\pmb {w}^{(k)})\) of (15) converges to the solution \((\pmb {v},\pmb {w})\) of (14) at a linear rate:
where \(\displaystyle 0<\kappa (\alpha ,\beta ):=\frac{\alpha (1-\beta )}{\beta (1-\alpha )}<1\).
Proof
Let \(\pmb {d}^{(k)}(t):=\pmb {v}^{(k)}(t)-\pmb {v}(t)\) and \(\pmb {e}^{(k)}(t):=\pmb {w}^{(k)}(t)-\pmb {w}(t)\), which satisfy the error equations
and
where \(\pmb {f}_\ell '\) denotes the Jacobian of \(\pmb {f}_\ell \), i.e.,
\(\pmb {\xi }^{(k+1)}(t)\) lies between \(\pmb {v}^{(k+1)}(t)\) and \(\pmb {v}(t)\) componentwisely for \(0<t\le T\), and \(\pmb {\eta }^{(k+1)}(t)\) lies between \(\pmb {w}^{(k+1)}(t)\) and \(\pmb {w}(t)\) componentwisely for \(0<t\le T\). Since \(f'(u)\le R\) for all \(u\in \mathbb {R}\) (condition (F2)), we apply Corollary 1 to the system (16) and obtain
and
Evaluating (17b) at \(j=N_{\beta ,\alpha }\) and combining with (17a), we deduce that
Setting \(j=N_\alpha \), by induction, we have
By using Lemma 3, we have
Thus, we obtain from (18) that
and consequently,
Similarly, we have
From (17a), we deduce that
in which, by Lemma 3, one finds that
Thus, combining (20) and (19) yields the following estimate:
Similarly,
which completes the proof.
We remark that Theorem 1 implies the superlinear convergence rate of the Schwarz iteration solution in the continuous case while we only obtain linear convergence rate in Theorem 3 due to some technical difficulties for the semi-discrete case. However, we still expect to observe the superlinear convergence rate in numerical experiments. Theorem 3 also guarantees the uniqueness of the solution \((\pmb {v},\pmb {w})\) of (14), and hence, implies the equivalence between the multidomain problem (14) and the monodomain one (4). Moreover, the maximum bound principle of the multidomain problem is a direct corollary.
Corollary 2
Suppose that \((\pmb {v},\pmb {w})\) is the solution of the multidomain problem (14). If
then we have \(\Vert \pmb {v}\Vert _{\infty ,T}\le \rho \) and \(\Vert \pmb {w}\Vert _{\infty ,T}\le \rho \).
4 Fully discrete localized ETD schemes
In this section, we study the fully discrete localized ETD schemes. For completeness, we first present the monodomain ETD schemes and the corresponding maximum bound principle. Then, we introduce the first- and second-order localized ETD schemes and show their unique solvability. Finally, two types of iterative algorithms for the localized ETD schemes are derived: the first one is based on the Schwarz iteration applied at each time step and involves solving stationary problems at each iteration, and the second one is based on the Schwarz waveform relaxation algorithm.
4.1 Monodomain ETD schemes
Consider a partition of the time interval [0, T] by \(\{t_m=m{\Delta t}:0\le m\le M\}\) with a uniform time step size \({\Delta t}=T/M\). The exact solution of the equivalent system (5) at each time level is given by the variation-of-constants formula:
for \(m=0,1,\dots ,M-1\), where \(A_{(N)}^S=A_{(N)}-SI_{(N)}\) and \(\pmb {B}(t)=\pmb {B}(g_1(t),g_2(t))\). Denote by \(\pmb {U}^m\) the approximation of \(\pmb {u}(t_m)\) by the ETD methods.
The first-order ETD (ETD1) scheme is obtained by approximating \(\pmb {f}^S(\pmb {u}(t))\) on \([t_m,t_{m+1}]\) by the constant \(\pmb {f}^S(\pmb {u}(t_m))\) and approximating \(\pmb {B}(t)\) by the constant \(\pmb {B}(t_{m+1})\):
The second-order ETD Runge–Kutta (ETDRK2) scheme is obtained by approximating \(\pmb {f}^S(\pmb {u}(t))+\pmb {B}(t)\) on \([t_m,t_{m+1}]\) with its linear interpolation polynomial:
where the predicted value \(\pmb {\widetilde{U}}^{m+1}\) is given by
We define the following norms for each function \(\pmb {V}=(V_j^m)_{1\le j\le N,\ 0\le m\le M}\):
Now we establish the fully discrete counterparts of the maximum bound principle for the ETD1 and ETDRK2 schemes. To this end, we always assume condition (6) for the rest of the paper.
Theorem 4
Suppose \(\{\pmb {U}^m\}_{0\le m\le M}\) is the solution of the ETD1 (21) or ETDRK2 scheme (22). If \(\max \{\Vert u_0\Vert _\infty ,\Vert g_1\Vert _T,\Vert g_2\Vert _T\}\le \rho \), then, for any \({\Delta t}>0\), we have \(\Vert \pmb {U}\Vert _{\infty ,T}\le \rho \).
Proof
We prove this theorem by induction. Obviously, \(\Vert \pmb {U}^0\Vert _\infty \le \Vert u_0\Vert _\infty \le \rho \). Now assume that the result holds for \(m=k\): \(\Vert \pmb {U}^k\Vert _\infty \le \rho \). We will show that it also holds for \(m=k+1\).
We note that the solution \(\pmb {U}^{k+1}\) is actually given by \(\pmb {U}^{k+1}=\pmb {\psi }({\Delta t})\) with the function \(\pmb {\psi }:[0,{\Delta t}]\rightarrow \mathbb {R}^N\) solving
where
and
Note that
Since \(\Vert \pmb {U}^{k+1}\Vert _\infty \le \Vert \pmb {\psi }\Vert _{\infty ,{\Delta t}}\), we just need to consider the case
and proceed as in the semi-discrete case (cf. Theorem 2). If there exists \((\widehat{j},\widehat{t})\) with \(1\le \widehat{j}\le N\) and \(\widehat{t}\in (0,{\Delta t}]\) such that \(\psi _{\widehat{j}}(\widehat{t})=\Vert \pmb {\psi }\Vert _{\infty ,{\Delta t}}\), then
which implies that
For the ETD1 scheme, since \(|U_{\widehat{j}}^k|\le \rho \), by using Lemma 1-(i), we deduce from (23) that
Therefore, \(\psi _{\widehat{j}}(\widehat{t})\le \rho \), and as a consequence, \(\Vert \pmb {U}^{k+1}\Vert _\infty \le \rho \). For the ETDRK2 scheme, since the predicted value \(\pmb {\widetilde{U}}^{k+1}\) is calculated by the ETD1 scheme, it holds that \(|\widetilde{U}_{\widehat{j}}^{k+1}|\le \rho \). Thus again, by using Lemma 1-(i), we obtain from the inequality (23) that
which yields \(\psi _{\widehat{j}}(\widehat{t})\le \rho \), and thus, \(\Vert \pmb {U}^{k+1}\Vert _\infty \le \rho \).
Similarly, if there exists \((\widehat{j}',\widehat{t}')\) with \(1\le \widehat{j}'\le N\) and \(\widehat{t}'\in (0,{\Delta t}]\) such that \(\psi _{\widehat{j}'}(\widehat{t}')=-\Vert \pmb {\psi }\Vert _{\infty ,{\Delta t}}\), one can show that \(\Vert \pmb {U}^{k+1}\Vert _\infty \le \rho \). This completes the proof.
4.2 Localized ETD schemes and iterative algorithms
We apply the ETD methods to the semi-discrete multidomain problem (14) (with overlapping subdomains as depicted in Fig. 1) to obtain the fully discrete localized ETD schemes. The exact solution of (14) at each time level is given by the variation-of-constants formula:
for \(m=0,1,\dots ,M-1\), where \(A_\ell ^S=A_\ell -SI_{(N_\ell )}\) and \(\pmb {f}_\ell ^S(\pmb {r})=\pmb {f}_\ell (\pmb {r})+S\pmb {r}\) with \(\ell =1,2\). Denote by \(\pmb {V}^m\) and \(\pmb {W}^m\) the approximations of \(\pmb {v}(t_m)\) and \(\pmb {w}(t_m)\).
The localized ETD1 scheme for solving the coupled problem (14) reads
for \(m=0,1,\dots ,M-1\), where \(I_1=I_{(N_1)}\), \(I_2=I_{(N_2)}\),
The localized ETDRK2 scheme for solving the coupled problem (14) reads
for \(m=0,1,\dots ,M-1\).
Theorem 5
The localized ETD schemes (24) and (25) are uniquely solvable.
Proof
We first show the case of the localized ETD1 scheme (24). For \(\ell =1,2\), denote by \(q^\ell _{i,j}\) the (i, j)-entry of the matrix \((A_\ell ^S)^{-1}(\mathrm {e}^{{\Delta t}A_\ell ^S}-I_\ell )\) and \(\pmb {q}^\ell _j=(q^\ell _{1,j},q^\ell _{2,j},\dots ,q^\ell _{N_\ell ,j})^T\). Note that
Thus, from Lemma 3 we find that
with \(\kappa (\alpha , \beta )\) as defined in Theorem 3. For given \(\pmb {V}^m\) and \(\pmb {W}^m\), the coupled problem (24) is indeed a linear system with respect to \(\pmb {V}^{m+1}\) and \(\pmb {W}^{m+1}\):
or equivalently,
Clearly, the \(N_{\beta ,\alpha }\)th column of \(P_1\in \mathbb {R}^{N_1\times N_2}\) is given by \(-\frac{D}{h^2}\pmb {q}^1_{N_1}\), the \(N_\alpha \)th column of \(P_2\in \mathbb {R}^{N_2\times N_1}\) is given by \(-\frac{D}{h^2}\pmb {q}^2_1\), and all other entries of \(P_1\) and \(P_2\) are zero. Thus, the \(N_{\beta ,\alpha }\)th column of \(P_2P_1\) is given by \((\frac{D}{h^2})^2q^1_{N_\alpha ,N_1}\pmb {q}^2_1\) and all other entries of \(P_2P_1\) are zero. Then, the determinant of the coefficient matrix of the system (26) is
which implies the unique solvability of (26), and thus, the localized ETD1 scheme.
For the localized ETDRK2 scheme (25), note that
Therefore, using a similar argument as above, we can obtain the unique solvability of (25).
We remark that, unlike the semi-discrete case, the localized ETD schemes (24) and (25) do not give exactly the same fully discrete solutions as those obtained by the corresponding monodomain ETD schemes (21) and (22). However, we shall show in Section 5.2 that the localized ETD solutions converge to the exact solution of the semi-discrete problem (14) as \({\Delta t}\) tends to zero. This property is specific to the ETD time integration, and was first discussed in [14] for the case of linear parabolic problems.
Since the localized ETD schemes (24) and (25) are both coupled systems with respect to \(\pmb {V}^{m+1}\) and \(\pmb {W}^{m+1}\), in the following, we construct two types of iterative methods to solve them.
S-LETD: Space localized ETD method Applying the Schwarz iteration to the localized ETD1 scheme (24) at each time step, we obtain the S-LETD1 method:
for \(k=0,1,\dots \), where \(V_{N_\alpha }^{m+1,(0)}\) and \(W_{N_{\beta ,\alpha }}^{m+1,(0)}\) are given initial guess. The iteration stops when
for a given tolerance \(\mathrm {tol}>0\). Applying the Schwarz iteration to the localized ETDRK2 scheme (25), we obtain the S-LETDRK2 method:
for \(k=0,1,\dots \), where \(V_{N_\alpha }^{m+1,(0)}=\widetilde{V}_{N_\alpha }^{m+1}\) and \(W_{N_{\beta ,\alpha }}^{m+1,(0)}=\widetilde{W}_{N_{\beta ,\alpha }}^{m+1}\). The iteration stopping criterion is still chosen as (28).
ST-LETD: Space-time localized ETD method Instead of the S-LETD methods (27) and (29), if we apply the ETD schemes to the Schwarz waveform relaxation iteration system (15), we can obtain the space-time localized ETD methods. For a given initial guess of \(V_{N_\alpha }^{m,(0)}\) and \(W_{N_{\beta ,\alpha }}^{m,(0)}\) for all \(0\le m\le M\), the ST-LETD1 method (for the \((k+1)\)-th iteration) reads
for \(m=0,1,\dots ,M-1\), where \(V_{N_\alpha }^{0,(k)}=u_0(\alpha )\) and \(W_{N_{\beta ,\alpha }}^{0,(k)}=u_0(\beta )\) for any k. The iteration stops when
for a given tolerance \(\mathrm {tol}>0\). The ST-LETDRK2 method (for the \((k+1)\)-th iteration) reads
for \(m=0,1,\dots ,M-1\), and the iteration stopping criterion is still chosen as (31). Note that the S-LETD algorithms (27) and (29) can be regarded as the ST-LETD methods (30) and (32), respectively, evolving for only one time step \(T={\Delta t}\).
5 Convergence analysis
This section is devoted to the convergence analysis at the theoretical level. In the first part, we prove the convergence of the localized ETD iterative algorithms when the number of iterations goes to infinity; then, as a direct corollary, we derive the maximum bound principle of the localized ETD schemes. In the second part, we show the convergence of the localized ETD solutions to the semi-discrete solution as the time step size goes to zero.
5.1 Convergence of the localized ETD iterative algorithms and the maximum bound principle
The following theorem suggests that the S-LETD methods (27) and (29) both converge at the linear rate.
Theorem 6
Given \((\pmb {V}^m,\pmb {W}^m)\), the iteration sequence \(\{(\pmb {V}^{m+1,(k)},\pmb {W}^{m+1,(k)})\}_{k\ge 0}\) generated by the S-LETD1 method (27) (resp., the S-LETDRK2 method (29)) converges to the solution \((\pmb {V}^{m+1},\pmb {W}^{m+1})\) of the localized ETD1 scheme (24) (resp., the localized ETDRK2 scheme (25)) as \(k\rightarrow \infty \). In particular, we have
Proof
Define the errors at each iteration by \(\pmb {e}_V^{m+1,(k)}=\pmb {V}^{m+1,(k)}-\pmb {V}^{m+1}\) and \(\pmb {e}_W^{m+1,(k)}=\pmb {W}^{m+1,(k)}-\pmb {W}^{m+1}\), which satisfy the following equations:
(i) if the localized ETD1 scheme is used, then
(ii) if the localized ETDRK2 scheme is used, then
For both cases, since \(\frac{\tau }{{\Delta t}}\le 1\) and \(\mathrm {e}^{-S({\Delta t}-\tau )}\le 1\), using Lemma 3, we have
Evaluating (33b) at \(j=N_{\beta ,\alpha }\) and (33a) at \(j=N_\alpha \), we obtain
from which we deduce that
and similarly,
Combining (33) with (34), we finally obtain
which completes the proof.
As a consequence of the convergence, we obtain the following maximum bound principle for the localized ETD schemes which will be used in the proof of temporal convergence in the next subsection.
Corollary 3
Suppose that \(\{(\pmb {V}^m,\pmb {W}^m)\}_{0\le m\le M}\) is the solution of the localized ETD1 scheme (24) or the localized ETDRK2 scheme (25). If \(\max \{\Vert u_0\Vert _\infty ,\Vert g_1\Vert _T,\Vert g_2\Vert _T\}\le \rho \), then, for any \({\Delta t}>0\), we have \(\Vert \pmb {V}\Vert _{\infty ,T}\le \rho \) and \(\Vert \pmb {W}\Vert _{\infty ,T}\le \rho \).
Proof
We prove this by induction. Clearly, \(\max \{\Vert \pmb {V}^0\Vert _\infty ,\Vert \pmb {W}^0\Vert _\infty \}\le \Vert u_0\Vert _\infty \le \rho \). Now we assume that \(\max \{\Vert \pmb {V}^m\Vert _\infty ,\Vert \pmb {W}^m\Vert _\infty \}\le \rho \) for some \(0\le m\le M-1\) and check the result for \(m+1\).
Consider the S-LETD methods (27) and (29), where the initial guess for (27) are chosen to satisfy \(|V_{N_\alpha }^{m+1,(0)}|\le \rho \) and \(|W_{N_{\beta ,\alpha }}^{m+1,(0)}|\le \rho \). For both first- and second-order cases, the subproblems are decoupled with respect to \(\pmb {V}^{m+1,(k+1)}\) and \(\pmb {W}^{m+1,(k+1)}\). Applying Theorem 4 to these two subproblems, we obtain
By passing the limit \(k\rightarrow \infty \), according to Theorem 6, we obtain
This completes the proof.
We recall that the ST-LETD algorithms (30) and (32) could be viewed as the monodomain ETD schemes applied to the semi-discrete Schwarz waveform relaxation problems (15a) and (15b). Therefore, the ST-LETD algorithms are expected to have similar convergence behaviors as stated in Theorem 3, that is, only linear convergence rate could be obtained theoretically while the superlinear convergence is again expected to be observed numerically. Furthermore, unlike the case of linear diffusion equations studied in [14], it is also necessary to require \(T<T^*\) for some \(T^*\) in the analysis (as done in the proofs of the following Theorems 7 and 8) due to some technical gaps, and we omit the details here.
5.2 Convergence of the localized ETD schemes to the semi-discrete problems
The following two theorems guarantee the convergence of the first- and second-order localized ETD solutions (24) and (25) to the exact solution of the semi-discrete multidomain problem (14) as \({\Delta t}\) tends to zero.
Theorem 7
For sufficiently smooth initial and boundary data, and for \(T<T^*\) with some \(T^*=T^*(h,D,R)>~0\), the localized ETD1 scheme (24) converges to the semi-discrete problem (14) as \({\Delta t}\rightarrow 0\). More precisely, we have the error estimates:
where C is a constant depending on T, R, S, h, \(g_1'(t)\), \(g_2'(t)\), \(\pmb {v}'(t)\) and \(\pmb {w}'(t)\).
Proof
Denote by \(\pmb {e}_v^m=\pmb {v}(t_m)-\pmb {V}^m\) and \(\pmb {e}_w^m=\pmb {w}(t_m)-\pmb {W}^m\), satisfying
and
for \(m=0,1,\dots ,M-1\) with \(\pmb {e}_v^0=\pmb {e}_w^0=\pmb {0}\), where \(\pmb {\xi }^m\) lies between \(\pmb {v}(t_m)\) and \(\pmb {V}^m\) componentwisely, \(\pmb {\eta }^m\) lies between \(\pmb {w}(t_m)\) and \(\pmb {W}^m\) componentwisely, and
Since \(A_1\) is strictly diagonally dominant with all negative diagonal entries, the set of operators \(\{\mathrm {e}^{tA_1}\}_{t>0}\) becomes a contraction semigroup in the sense of matrix \(\infty \)-norm, namely, \(\Vert \mathrm {e}^{tA_1}\Vert _\infty \le 1\), and thus, \(\Vert \mathrm {e}^{tA_1^S}\Vert _\infty \le \mathrm {e}^{-St}\) (see also [27, Theorem 2]). According to (6) and (F2), we find that \(|(f^S)'(\xi )|=f'(\xi )+S\le R+S\) for any \(\xi \in [-\rho ,\rho ]\). Therefore, we can bound \(\pmb {\gamma }_1^{m+1}\) and \(\pmb {\delta }_1^{m+1}\) by
and
According to Corollaries 2 and 3, we have \(\Vert \pmb {\xi }^m\Vert _\infty \le \rho \) and \(\Vert \pmb {\eta }^m\Vert _\infty \le \rho \). Hence, we obtain from (35) that
where \(\displaystyle C_1:=\frac{R+S}{2}\Vert \pmb {v}'\Vert _{\infty ,T}+\frac{D}{2h^2}\max \{\Vert g_1'\Vert _T,\Vert w_{N_{\beta ,\alpha }}'\Vert _T\}\). An application of the discrete Gronwall’s inequality leads to
Similarly, we have from (36) that
where \(\displaystyle C_2:=\frac{R+S}{2}\Vert \pmb {w}'\Vert _{\infty ,T}+\frac{D}{2h^2}\max \{\Vert v_{N_\alpha }'\Vert _T,\Vert g_2'\Vert _T\}\). Substituting (39) into (38), we obtain
If \(\displaystyle T<T^*:=\frac{1}{R}\ln \Big (1+\frac{Rh^2}{D}\Big )\), then \(\displaystyle \frac{(\mathrm {e}^{RT}-1)^2D^2}{R^2h^4} <1\) for any \({\Delta t}>0\). Consequently, we obtain
and similarly,
where \(C_3\) and \(C_4\) depend on T, R, S, h, \(\Vert g_1'\Vert _T\), \(\Vert g_2'\Vert _T\), \(\Vert \pmb {v}'\Vert _{\infty ,T}\) and \(\Vert \pmb {w}'\Vert _{\infty ,T}\).
Theorem 8
For sufficiently smooth initial and boundary data, and for \(T<T^*\) with some \(T^*=T^*(h,D,R,S)>0\), the localized ETDRK2 scheme (25) converges to the semi-discrete problem (14) as \({\Delta t}\rightarrow 0\). More precisely, we have the error estimates:
where C is a constant depending on T, R, \(F_2\), S, h, \(g_1''(t)\), \(g_2''(t)\), \(\pmb {v}''(t)\) and \(\pmb {w}''(t)\), where \(F_2\) is the supremum of \(|f''|\) on the interval \([-\rho ,\rho ]\).
Proof
Denote by \(\pmb {e}_v^m=\pmb {v}(t_m)-\pmb {V}^m\) and \(\pmb {e}_w^m=\pmb {w}(t_m)-\pmb {W}^m\), which satisfy
and
for \(m=0,1,\dots ,M-1\) with \(\pmb {e}_v^0=\pmb {e}_w^0=\pmb {0}\), where
\(\pmb {\xi }^m\) lies between \(\pmb {v}(t_m)\) and \(\pmb {V}^m\) componentwisely, \(\pmb {\widetilde{\xi }}^{m+1}\) lies between \(\pmb {v}(t_{m+1})\) and \(\pmb {\widetilde{V}}^{m+1}\) componentwisely, \(\pmb {\eta }^m\) lies between \(\pmb {w}(t_m)\) and \(\pmb {W}^m\) componentwisely, \(\pmb {\widetilde{\eta }}^{m+1}\) lies between \(\pmb {w}(t_{m+1})\) and \(\pmb {\widetilde{W}}^{m+1}\) componentwisely, and
Noting the fact that for any \(\varphi \in C^2(0,T)\),
then we can bound \(\pmb {\gamma }_1^{m+1}\) and \(\pmb {\delta }_1^{m+1}\) by
and
According to the last step in (37), we have
Using the maximum bound principle, we find that
Thus, it is deduced that
In addition, we have
Using the estimates (42)–(45), we obtain from (40) that
where \(\displaystyle C_5:=\frac{1}{6}(F_2\Vert \pmb {v}'\Vert _{\infty ,T}^2+(R+S)\Vert \pmb {v}''\Vert _{\infty ,T}) +\frac{D}{6h^2}\max \{\Vert g_1''\Vert _T,\Vert w_{N_{\beta ,\alpha }}''\Vert _T\}\). An application of the discrete Gronwall’s inequality leads to
Similarly, we have from (41) that
where \(\displaystyle C_6:=\frac{1}{6}(F_2\Vert \pmb {w}'\Vert _{\infty ,T}^2+(R+S)\Vert \pmb {w}''\Vert _{\infty ,T}) +\frac{D}{6h^2}\max \{\Vert v_{N_\alpha }''\Vert _T,\Vert g_2''\Vert _T\}\). Substituting (47) into (46), we obtain
When \(\displaystyle T<T^*:=\frac{1}{R}\ln \Big (1+\frac{R^2h^2}{(R+S)D}\Big )\), we have
for any \({\Delta t}>0\), and then, obtain
and similarly,
where \(C_7\) and \(C_8\) depend on T, R, \(F_2\), S, h, \(\Vert g_1''\Vert _T\), \(\Vert g_2''\Vert _T\), \(\Vert \pmb {v}''\Vert _{\infty ,T}\) and \(\Vert \pmb {w}''\Vert _{\infty ,T}\).
6 Numerical experiments
In this section, we will carry out numerical experiments to investigate the convergence behavior and the accuracy of the localized ETD schemes. In the first part, we consider the one-dimensional problem to verify the theoretical results on the convergence of the first- and second-order localized ETD schemes. In the second part, we focus on the two-dimensional problem to show the convergence behaviors of the iterative algorithms for the second-order localized ETD scheme.
6.1 One-dimensional examples
Let us consider the one-dimensional problem (1) with the spatial domain \(\Omega =(0,1)\), the reaction term \(f(u)=u-u^3\), and the parameter \(D=0.01\). Two subdomains are given by \(\Omega _1=(0,\beta )\) and \(\Omega _2=(\alpha ,1)\) with \(\frac{1}{2}<\beta <1\) and \(\alpha =1-\beta \). The spatial mesh size is set to be \(h=1/200\) and the overlap size is \(N_{\beta ,\alpha }h=\beta -\alpha \). The stabilizer is chosen to be \(S=2\) in all the experiments.
Example 1
Consider problem (1) with the initial and boundary conditions given by
Under this setting, we investigate numerically the temporal convergence of the localized ETD schemes with different overlap sizes.
We calculate the numerical solutions at time \(t=1\) by the localized ETD1 scheme (24) and the localized ETDRK2 scheme (25) with various time step sizes \({\Delta t}=\delta \times 2^{-K}\) (\(\delta =0.1\) and \(K=0,1,\dots ,6\)) and different overlap sizes \(N_{\beta ,\alpha }\in \{4,8,16,32\}\). To compute the numerical errors, we use the solution obtained by the ETDRK2 scheme (22) with \({\Delta t}=10^{-10}\) as the reference solution. Note that, once converged completely, the solutions of the localized ETD schemes computed by the S-LETD methods (27) and (29) are identical to those computed by the ST-LETD methods (30) and (32), respectively. Thus, we adopt the S-LETD methods (27) and (29) with the tolerance \(10^{-10}\). The maximum-norms of the numerical errors and corresponding convergence rates are given in Tables 1 and 2, where the expected convergence rates are obviously observed. In addition, the orders of the temporal accuracy of the localized ETD schemes are better preserved when larger overlap sizes are considered.
Example 2
We consider problem (1) with zero initial and boundary conditions so that it admits uniquely the zero solution. We will investigate the relation between the convergence of the S-LETD/ST-LETD methods and the overlap size \(N_{\beta ,\alpha }\), the time step size \(\Delta t\), and the final time T, respectively. All the components of the initial guess for the S-LETD/ST-LETD methods are chosen randomly in the interval \([-1,1]\).
First, we study the convergence of the S-LETD (27)–(29) and ST-LETD methods (30)–(32) with respect to the overlap size \(N_{\beta ,\alpha }\). For that purpose, we fix the time step size \({\Delta t}=0.1\) while varying \(N_{\beta ,\alpha }\in \{2,4,8,16,32\}\). Theoretically, since
the larger \(N_{\beta ,\alpha }\) means the larger \(\beta \) and the smaller \(\kappa (\alpha ,\beta )\), which implies the faster convergence. Figures 2 and 3 plot the iteration errors \(\Vert \pmb {V}^{(k)}\Vert _{\infty ,T}\) with respect to the number of iterations k with various overlap sizes for S-LETD with \(T={\Delta t}\) and ST-LETD with \(T=1\), respectively. Clearly, the larger overlap size leads to the faster convergence, which meets the theoretical prediction, and the linear and superlinear convergence rates are observed for S-LETD (Fig. 2) and ST-LETD (Fig. 3) methods, respectively. In addition, the second-order localized ETD schemes converge a little faster than the first-order ones.
(Example 2) Error curves of the S-LETD method with various overlap sizes: the localized ETD1 scheme (left) and the localized ETDRK2 scheme (right)
(Example 2) Error curves of the ST-LETD method with various overlap sizes: the localized ETD1 scheme (left) and the localized ETDRK2 scheme (right)
Next, we investigate the convergence of the S-LETD and ST-LETD methods with different the time step size by taking \(\Delta t\in \{1/10,1/20,1/40,1/80,1/160\}\) and fixing the overlap size \(N_{\beta ,\alpha }=4\). The curves of the iteration errors with different time step sizes are shown in Figs. 4 and 5 for the S-LETD method with \(T={\Delta t}\) and the ST-LETD method with \(T=1\), respectively. For S-LETD, it is observed that the linear convergence rate is sensitive to the time step size, that is, the smaller time step gives the faster convergence. However, for ST-LETD, we see that the superlinear convergence rate is quite independent of the time step size, especially if the second-order scheme is applied. This means that one could use larger time step sizes without yielding much more iterations. In addition, the second-order schemes gives smaller iteration errors than the first-order ones when conducting the same number of iterations.
(Example 2) Error curves of the S-LETD method with different time step sizes: the localized ETD1 scheme (left) and the localized ETDRK2 scheme (right)
(Example 2) Error curves of the ST-LETD method with different time step sizes: the localized ETD1 scheme (left) and the localized ETDRK2 scheme (right)
Finally, we study the convergence of the ST-LETD method with different final times by setting \(T\in \{1,2,4,8,16\}\) and fixing the overlap size \(N_{\beta ,\alpha }=32\) and the time step size \(\Delta t=0.1\). The discrete \(L^\infty (0,T;L^\infty (\Omega ))\) iteration errors are plotted in Fig. 6. We observe that the convergence is faster on the shorter time interval. Besides, the first- and second-order schemes have similar convergence rates.
(Example 2) Error curves of the ST-LETD method with different final times: the localized ETD1 scheme (left) and the localized ETDRK2 scheme (right)
6.2 Two-dimensional example
We now carry out numerical simulations for the two-dimensional problem to study the convergence of the localized ETD methods and compare their accuracy with the ETD methods. Again, we set the stabilizer \(S=2\).
Example 3
We consider the two-dimensional reaction-diffusion problem
where the initial and Dirichlet boundary conditions are determined by the exact solution
By setting \(D=0.01\), \(h=1/200\) and \({\Delta t}=0.01\), we will compare the accuracy of the ETD schemes on the whole domain and the localized ETD schemes based on the domain decomposition consisting of \(p\times p\) overlapping and congruent squares with a fixed overlap size \(N_{\beta ,\alpha }=20\).
Table 3 collects the relative \(L^\infty (\Omega )\) errors at time \(t=1\) between the exact solution and the localized ETDRK2 solutions, as well as the errors of the ETDRK2 solutions for comparison. The numbers in brackets are the numbers of iterations. We observe that S-LETD costs a few iterations to reach the accuracy of the ETDRK2 solution with the errors at the same order of magnitude. However, ST-LETD converges slower and needs more iterations to reach the desired accuracy. If one uses the same numbers of iterations as S-LETD, the numerical errors are much larger than the ETDRK2 solution by five orders of magnitude. Therefore, we see S-LETD is more efficient than ST-LETD, at least for this example.
7 Conclusion
In this paper, we focus on the development and analysis of the localized ETD methods based on overlapping domain decomposition for a class of semilinear parabolic equations. We first investigate the space-discrete multidomain problem and prove the linear convergence rate of the Schwarz waveform relaxation algorithm. For the fully discrete localized ETD schemes, we establish the corresponding discrete maximum bound principle and demonstrate the convergence of the solutions to the exact semi-discrete solution as well as the convergence of the iterative solutions. All the theoretical analyses are carried out in one-dimensional case. Numerical experiments for one- and two-dimensional problems confirm the expected convergence rates. In addition, we study numerically the relations between the convergence of the S-LETD/ST-LETD methods and the overlap size, the time step size and the final time, where the results show that larger overlap size and shorter time interval lead to faster convergence while the time step size has little effect on the convergence rate.
It should be noted that although the theoretical results for temporal convergence of the localized ETD schemes, as well as the convergence of the ST-LETD algorithms, hold only for the small enough final time T, the convergence behavior could be observed in numerical experiments for large T. Whether the restriction on T could be removed is still an open question at the theoretical level. Some novel technical skills may be necessary to remove such restriction in convergence analysis and we leave this problem as one of our important future works.
References
Al-Mohy, A.H., Higham, N.J.: Computing the action of the matrix exponential, with an application to exponential integrators. SIAM J. Sci. Comput. 33, 488–511 (2011)
Allen, S.M., Cahn, J.W.: A microscopic theory for antiphase boundary motion and its application to antiphase domain coarsening. Acta Metall. 27, 1085–1095 (1979)
Cahn, J.W., Hilliard, J.E.: Free energy of a nonuniform system. I. Interfacial free energy. J. Chem. Phys. 28, 258–267 (1958)
Cox, S.M., Matthews, P.C.: Exponential time differencing for stiff systems. J. Comput. Phys. 176, 430–455 (2002)
Du, Q., Gunzburger, M.D., Peterson, J.S.: Analysis and approximation of the Ginzburg–Landau model of superconductivity. SIAM Rev. 34, 54–81 (1992)
Du, Q., Ju, L., Li, X., Qiao, Z.: Maximum principle preserving exponential time differencing schemes for the nonlocal Allen–Cahn equation. SIAM J. Numer. Anal. 57, 875–898 (2019)
Du, Q., Ju, L., Li, X., Qiao, Z.: Maximum bound principles for a class of semilinear parabolic equations and exponential time differencing schemes. SIAM Rev. (2020, to appear)
Elder, K.R., Katakowski, M., Haataja, M., Grant, M.: Modeling elasticity in crystal growth. Phys. Rev. Lett. 88, 245–701 (2002)
Evans, L.C., Soner, H.M., Souganidis, P.E.: Phase transitions and generalized motion by mean curvature. Commun. Pure Appl. Math. 45, 1097–1123 (1992)
Gander, M.J.: A waveform relaxation algorithm with overlapping splitting for reaction diffusion equations. Numer. Linear Algebra Appl. 6, 125–145 (1999)
Gander, M.J., Stuart, A.M.: Space-time continuous analysis of waveform relaxation for the heat equation. SIAM J. Sci. Comput. 19, 2014–2031 (1998)
Gottlieb, S., Shu, C.W., Tadmor, E.: Strong stability-preserving high-order time discretization methods. SIAM Rev. 43, 89–112 (2001)
Gustafsson, B., Kreiss, H.O., Oliger, J.: Time-Dependent Problems and Difference Methods, 2nd edn. Wiley, Hoboken (2013)
Hoang, T.T.P., Ju, L., Wang, Z.: Overlapping localized exponential time differencing methods for diffusion problems. Commum. Math. Sci. 16, 1531–1555 (2018)
Hoang, T.T.P., Ju, L., Wang, Z.: Nonoverlapping localized exponential time differencing methods for diffusion problems. J. Sci. Comput. 82, 37 (2020)
Hochbruck, M., Lubich, C.: On Krylov subspace approximations to the matrix exponential operator. SIAM J. Numer. Anal. 34, 1911–1925 (1997)
Hochbruck, M., Ostermann, A.: Explicit exponential Runge—Kutta methods for semilinear parabolic problems. SIAM J. Numer. Anal. 43, 1069–1090 (2005)
Hochbruck, M., Ostermann, A.: Exponential integrators. Acta Numer. 19, 209–286 (2010)
Horn, R.A., Johnson, C.R.: Topics in Matrix Analysis. Cambridge University Press, Cambridge (1994)
Hu, G.Y., O’Connell, R.F.: Analytical inversion of symmetric tridiagonal matrices. J. Phys. A 29, 1511–1513 (1996)
Isherwood, L., Grant, Z.J., Gottlieb, S.: Strong stability preserving integrating factor Runge-Kutta methods. SIAM J. Numer. Anal. 56, 3276–3307 (2018)
Ju, L., Li, X., Qiao, Z., Zhang, H.: Energy stability and error estimates of exponential time differencing schemes for the epitaxial growth model without slope selection. Math. Comput. 87, 1859–1885 (2018)
Ju, L., Zhang, J., Du, Q.: Fast and accurate algorithms for simulating coarsening dynamics of Cahn–Hilliard equations. Comput. Mater. Sci. 108, 272–282 (2015)
Ju, L., Zhang, J., Zhu, L., Du, Q.: Fast explicit integration factor methods for semilinear parabolic equations. J. Sci. Comput. 62, 431–455 (2015)
Kleefeld, B., Martín-Vaquero, J.: SERK2v2: a new second-order stabilized explicit Runge–Kutta method for stiff problems. Numer. Methods Part. Differ. Equ. 29, 170–185 (2013)
Lawson, J.D.: Generalized Runge–Kutta processes for stable systems with large Lipschitz constants. SIAM J. Numer. Anal. 4, 372–380 (1967)
Lazer, A.C.: Characteristic exp nents and diagonally dominant linear differential systems. J. Math. Anal. Appl. 35, 215–229 (1971)
Li, B., Liu, J.G.: Thin film epitaxy with or without slope selection. Eur. J. Appl. Math. 14, 713–743 (2003)
Medovikov, A.A.: High order explicit methods for parabolic equations. BIT 38, 372–390 (1998)
Shu, C.W., Osher, S.: Efficient implementation of essentially nonoscillatory shock-capturing schemes. J. Comput. Phys. 77, 439–471 (1988)
Temam, R.: Navier–Stokes E quations: Theory and Numerical Analysis. North-Holland Publishing Co., New York (1977)
Zhang, J., Zhou, Z., Wang, Y., Ju, L., Du, Q., Chi, X., Xu, D., Chen, D., Liu, Y., Liu, Z.: Extreme-scale phase field simulations of coarsening dynamics on the Sunway Taihulight supercomputer. In: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC’16). IEEE Press, Piscataway (2016)
Zhu, L., Ju, L., Zhao, W.: Fast high-order compact exponential time differencing Runge–Kutta methods for second-order semilinear parabolic equations. J. Sci. Comput. 67, 1043–1065 (2016)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Christian Lubich.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
X. Li’s work is partially supported by National Natural Science Foundation of China grant 11801024. L. Ju’s work is partially supported by US National Science Foundation grant DMS-1818438 and US Department of Energy grants DE-SC0016540 and DE-SC0020270.
Rights and permissions
About this article
Cite this article
Li, X., Ju, L. & Hoang, TTP. Overlapping domain decomposition based exponential time differencing methods for semilinear parabolic equations. Bit Numer Math 61, 1–36 (2021). https://doi.org/10.1007/s10543-020-00817-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10543-020-00817-0
Keywords
- Semilinear parabolic equation
- Overlapping domain decomposition
- Localized exponential time differencing
- Parallel Schwarz iteration
- Waveform relaxation
- Convergence analysis