1 Introduction

Porous media flows appear in many applications of societal relevance, such as groundwater remediation, environmental contamination, nuclear waste geological repositories, CO2 sequestration and enhanced oil recovery. Mathematical modeling and numerical simulation are key technologies for understanding the physical behavior of such systems, as they have the minimal environmental impact and cost. The problems are challenging for the numerical simulation since they involve coupled, nonlinear partial differential equations on a complex domain, which is actually a union of several subdomains with different hydrogeological properties or even with different models. Thus the time scales may vary significantly across various geological layers involved in the simulation. It is computationally inefficient to use a single time step in the whole domain and one should use a different time step in each subdomain. This can be achieved by using global-in-time domain decomposition (GT-DD) methods with nonmatching grids in time. The idea of GT-DD is to decouple the dynamic system into dynamic subsystems defined on the subdomains (resulting from a spatial decomposition), then solve time-dependent problems in each subdomain at each iteration and exchange the information over the space-time interfaces between subdomains. Note that GT-DD is different from classical DD methods applied to evolution problems where the model equations are first discretized implicitly in time, then DD iterations are performed at each time step as for the stationary case. Consequently, a uniform time step is usually considered in the classical approach.

GT-DD methods can be classified into two groups: Schur-type and Schwarz-type methods. The former is based on physical transmission conditions and the latter is based on more general transmission conditions such as Robin or Ventcel conditions. An important class of global-in-time Schwarz methods is the Optimized Schwarz Waveform Relaxation (OSWR) algorithm where additional coefficients involved in the transmission conditions are optimized to improve convergence rates [5, 6, 22]. Both global-in-time Schur and Schwarz methods have been extensively studied for linear flow and transport problems in porous media with different types of spatial discretizations and with nonmatching time grids in [12, 13, 22,23,24,25, 29, 30, 33,34,35, 41]. Instead, the literature for nonlinear problems using the GT-DD approach is less rich. In this context we refer to [26] for the rigorous convergence analysis of such problems. A nested iteration method based on OSWR and Newton linearization was proposed in [28] for the nonlinear reactive transport equation. Using a similar approach, though with physical transmission conditions, a global-in-time Schur method was developed in [36] for the coupled nonlinear Stokes-Darcy system. We also mention [16, 17, 27, 54, 55] where classical DD methods for nonlinear elliptic equations were developed.

In this work, we aim to derive nonlinear GT-DD methods with nonoverlapping subdomains for the Richards equation [4, 32, 49, 50] to model flow in partially saturated porous media. The Richards equation is a degenerate elliptic-parabolic nonlinear equation whose well-posedness and numerical solutions have been extensively analyzed in the literature (see, e.g., [2, 18, 44, 47, 52]). Due to the low regularity of the solution, this equation is often discretized in time by the backward Euler method (see, e.g., [45]) and in space by various schemes. In this sense, we refer to [3, 48, 51, 56, 57], where mixed finite elements are employed, or [19, 20, 38] for finite volume schemes, and to [43] for the a posteriori error analysis. To solve the nonlinear problem at each time step, different linearization strategies have been proposed such as Newton’s method [7, 14], Picard’s method [15, 40], the Jäger-Kačur method [37], the L-scheme [39, 46], or the scheme combining the L-scheme with Newton’s approach [42]. In addition, to reduce the size of the problem and perform parallel simulations, some DD methods have been studied for the stationary or time-discretized Richards equation. Nonlinear Dirichlet-Neumann and Robin algorithms were proposed and analyzed in [8, 9] for quasilinear elliptic problems and in [10, 11] for the semi-discrete Richards equation at each time step. In [53], a linear DD method was introduced by combining the L-scheme idea with Robin transmission conditions. The convergence of the scheme is proved under some mild restrictions on the time step size. These DD schemes for the Richards equation use pressure formulations and assume the same time steps in the subdomains.

Due to strong heterogeneity of the porous medium, it is desirable to use different time steps in different regions of the domain.

We develop in this work global-in-time Schur and Schwarz methods with mixed formulations as the conservation of mass is essential for flow in porous media. Based on either physical and Robin transmission conditions and by using substructuring techniques, we rewrite the original problem as a nonlinear space-time problem defined on the interfaces between the subdomains. Such an interface problem is linearized using Newton’s method and then solved iteratively by GMRES; each GMRES iteration involves parallel solution of time-dependent problems in the subdomains. Thus nonconforming time grids can be used to adapt to different time scales in the subdomains. To discretize the Richards equation in the subdomains at each Newton/GMRES iteration, we use the Euler implicit-mixed finite element (EI-MFE) scheme [3, 48, 51]. The proposed GT-DD methods are fully implicit, so that different and large time step sizes can be used for long-term simulations as often needed in some applications in geosciences. We shall validate numerically the convergence and accuracy of the proposed GT-DD methods with local time stepping on two test cases with continuous and discontinuous parameters and known exact solutions. The numerical effect of Robin parameters on the convergence of nonlinear and linear iterative schemes will also be discussed. Convergence analysis of the methods, theoretical optimized Robin parameters as well as further numerical experiments on more realistic problems will be investigated in a separate work. We remark that OSWR algorithms based on Robin or Ventcel transmission conditions were considered in [1] for two-phase flow discretized in space by finite volumes and in time by backward Euler. Such algorithms are a special case of the global-in-time Schwarz methods where one uses Jacobi iteration (instead of GMRES) to solve the linearized interface problem.

The rest of this paper is organized as follows. In Section 2, the model initial boundary value problem of Richards equation is introduced along with its numerical solution using the EI-MFE scheme and Newton linearization. An important part of the paper is Section 3 where two GT-DD methods are derived using either physical or equivalent Robin transmission conditions. For each method, a nonlinear space-time interface problem is formulated and is solved via a nested iterative algorithm. The fully discrete interface and subdomain problems are discussed in Section 4 with nonconforming time discretization. In Section 5, numerical experiments are presented to study the accuracy and convergence behaviors of the proposed algorithms. Finally, some concluding remarks are given in Section 6.

2 Model Problem and Its Numerical Solution

For a bounded domain Ω of \( \mathbb {R}^{d}\) (d ≥ 1) with Lipschitz continuous boundary ∂Ω and some fixed time T > 0, consider the Richards equation [32, 49, 50] to model flow in saturated-unsaturated porous media

$$ \partial_{t} {{\varTheta}} (\psi) - \nabla \cdot \left( K ({{\varTheta}} (\psi)) \nabla (\psi +z)\right) =f \quad \text{in} {{\varOmega}} \times (0,T ). $$
(2.1)

Here ψ is the pressure head, Θ the fluid saturation, K the hydraulic conductivity of the porous medium, z the vertical height (against the gravitational direction) and f the source term. The medium is assumed to be isotropic, i.e., K is a scalar function. We refer to [4] for different formulas for K(Θ) and Θ(ψ) based on laboratory experiments. It should be noted that Θ(ψ) is strictly increasing and bounded in unsaturated regions (where Θ is less than a maximal saturation ΘS), while it is constant in saturated regions (where Θ = ΘS). Thus, (2.1) is generally a degenerate elliptic-parabolic equation.

We rewrite (2.1) in an equivalent mixed form by introducing the vector field Q for the fluid flux

$$ \begin{array}{@{}rcl@{}} \partial_{t} {{\varTheta}} (\psi) + \nabla \cdot \boldsymbol{Q} &=& f \quad{\kern77pt} \text{in } {{\varOmega}} \times (0,T), \\ \boldsymbol{Q} &=& - K ({{\varTheta}} (\psi)) \nabla (\psi +z) \quad \text{in } {{\varOmega}} \times (0,T). \end{array} $$
(2.2)

Our model problem consists of (2.2) together with the following boundary and initial conditions

$$ \psi=0 \quad \text{on } \partial {{\varOmega}} \times (0,T ), \qquad \psi(t=0) = \psi_{0} \quad \text{in } {{\varOmega}}. $$
(2.3)

For simplicity, we have imposed homogeneous Dirichlet conditions on the boundary (for more general boundary conditions, see [10, 52]). Throughout the paper, the following assumptions are imposed(A1) The function Θ is monotonically increasing and Lipschitz continuous; there exist two constants ΘR and ΘS such that 0 < ΘR ≤Θ(x) ≤ΘS ≤ 1 for all \(x \in \mathbb {R}\).(A2) The function K is strictly monotonically increasing and Lipschitz continuous; there exist two constants K0 and K1 such that \(0 < K_{0} \leq K(x) \leq K_{1} < \infty \) for all \(x \in \mathbb {R}\).(A3) The source term f ∈ L2(0,T;L2(Ω)); the initial pressure head ψ0 is bounded and positive, and ψ0 ∈ L2(Ω).

To write the weak form of (2.2)–(2.3), we denote by (⋅,⋅) the inner product on L2(Ω), and for a measurable subset S ⊂Ω, we write (⋅,⋅)S (respectively, 〈⋅,⋅〉∂S) to indicate the inner product on S (respectively, ∂S). Let ez := ∇z be the constant gravitational vector. Due to the lacking regularity of the solution [2, 44], we consider the following mixed variational formulation of (2.2) as proposed in [3]:

Find \(\left (\psi , \boldsymbol {Q}\right ) \in L^{2}\left (0,T; L^{2}({{\varOmega }})\right ) \times L^{2}\left (0,T; (L^{2}({{\varOmega }}))^{d}\right )\) such that, for all t ∈ (0,T), \({\int \limits }_{{}0}^{t} \boldsymbol {Q}(\tau ) d\tau \in L^{2}\left (0,T; H(\text {div}, {{\varOmega }})\right )\) and

$$ \begin{array}{@{}rcl@{}} \left( {{\varTheta}} (\psi(t)) , \mu \right) + \left( \nabla \cdot {\int}_{{}0}^{t} \boldsymbol{Q}(\tau) d\tau, \mu\right) & = & \left( {\int}_{{}0}^{t} f(\tau) d\tau,\mu\right)+ \left( {{\varTheta}} (\psi_{0}) , \mu \right),\\ &&\forall \mu \in L^{2}({{\varOmega}}), \end{array} $$
(2.4a)
$$ \begin{array}{@{}rcl@{}} \left( K^{-1} \left( {{\varTheta}} (\psi)\right) \boldsymbol{Q}, \boldsymbol{v}\right) - \left( \psi, \nabla \cdot \boldsymbol{v}\right)+ \left( \boldsymbol{e}_{\boldsymbol{z}}, \boldsymbol{v}\right) & = & 0, \qquad \forall \boldsymbol{v} \in H(\text{div}, {{\varOmega}}). \end{array} $$
(2.4b)

Problem (??) is well-posed, i.e., there exists a unique solution to (??), as analyzed in detail in [2, 3, 44]. Our focus here is the numerical solutions of (??). We consider the EI-MFE scheme [3, 48, 51] for the discretization of problem (??); specifically, (??) is discretized in time by backward Euler and in space by mixed finite elements based on the lowest order Raviart-Thomas space. For completeness, we present the EI-MFE method as well as the linearization technique to find the numerical solution of the resulting nonlinear discrete problem iteratively. The algorithm will be used to solve the Richards equation in the subdomains as derived in the next sections.

Let \(\mathcal {T}\) be a partition of the time interval (0,T) into sub-intervals \(0= t_{0} < t_{1} < {\dots } < t_{N} = T\), with a time step size \({{\varDelta }} t ={{}^{T}/{}_{N}}\) for some integer N > 0. In space, assume that Ω is a polygon and let \( \mathcal {K}_{h} \) be a finite element partition of Ω into d-dimensional simplicial elements, where h is the mesh size. The discrete spaces for the scalar and vector variables are defined as

$$ \begin{array}{@{}rcl@{}} M_{h} &:=& \left\{ \mu \in L^{2}({{\varOmega}}): \mu_{\mid K} = \text{constant}, \forall K \in \mathcal{K}_{h} \right\}, \\ {{\varSigma}}_{h} &:=& \left\{ \boldsymbol{v} \in H(\text{div},{{\varOmega}}): \boldsymbol{v}\vert_{K} = \boldsymbol{a} + b \boldsymbol{x}, \forall K \in \mathcal{K}_{h}\right\}. \end{array} $$
(2.5)

The nonlinear fully discrete problem for (??) is given by (see [3]):

For each \(n=1, \dots , N\), find \(({\psi }_{h}^{n}, {\boldsymbol {Q}}_{h}^{n}) \in M_{h} \times {{\varSigma }}_{h}\), the approximation of (ψ(tn), Q(tn)), such that

$$ \begin{array}{@{}rcl@{}} \left( \frac{{{\varTheta}} ({\psi}_{h}^{n})-{{\varTheta}} ({\psi}_{h}^{n-1})}{{{\varDelta}} t} , \mu \right) + \left( \nabla \cdot {\boldsymbol{Q}}_{h}^{n}, \mu\right) = (f(t^{n}),\mu), && \quad\forall \mu \in M_{h}, \end{array} $$
(2.6a)
$$ \begin{array}{@{}rcl@{}} \left( K^{-1} \left( {{\varTheta}} ({\psi}_{h}^{n})\right) {\boldsymbol{Q}}_{h}^{n}, \boldsymbol{v}\right) - \left( {\psi}_{h}^{n}, \nabla \cdot \boldsymbol{v}\right) + \left( \boldsymbol{e}_{\boldsymbol{z}}, \boldsymbol{v}\right)=0, &&\quad \forall \boldsymbol{v} \in {{\varSigma}}_{h}. \end{array} $$
(2.6b)

Different linearization techniques have been studied for solving (??), the reader is referred to [39] and the references therein for further details. In this work, we use Newton’s method, which reads as: For each \(n=1,\dots , N\),

  1. (1)

    Set \({\psi }_{h}^{n,0} := {\psi }_{h}^{n-1}\) and \({\boldsymbol {Q}}_{h}^{n,0} := {\boldsymbol {Q}}_{h}^{n-1}\).

  2. (2)

    At each iteration \(l=1, 2, \dots ,\) find \(({\psi }_{h}^{n,l}, {\boldsymbol {Q}}_{h}^{n,l}) \in M_{h} \times {{\varSigma }}_{h}\) such that

    $$ \begin{array}{@{}rcl@{}} && \left( \frac{{{\varTheta}}^{\prime} ({\psi}_{h}^{n,l-1}) ({\psi}_{h}^{n,l}-{\psi}_{h}^{n,l-1})}{{{\varDelta}} t} , \mu \right) + \left( \nabla \cdot {\boldsymbol{Q}}_{h}^{n,l}, \mu\right) \\ && \quad = \left( f(t^{n}),\mu\right) - \left( \frac{{{\varTheta}} ({\psi}_{h}^{n,l-1}) - {{\varTheta}} ({\psi}_{h}^{n-1})}{{{\varDelta}} t} , \mu \right), \forall \mu \in M_{h}, \end{array} $$
    (2.7a)
    $$ \begin{array}{@{}rcl@{}} && \left( K^{-1} ({{\varTheta}} ({\psi}_{h}^{n,l-1})) {\boldsymbol{Q}}_{h}^{n,l}, \boldsymbol{v}\right) - \left( {\psi}_{h}^{n,l}, \nabla \cdot \boldsymbol{v}\right) + \left( \boldsymbol{e}_{\boldsymbol{z}}, \boldsymbol{v}\right) \\ && \qquad +\left( (K^{-1})^{\prime} ({{\varTheta}} ({\psi}_{h}^{n,l-1})) {{\varTheta}}^{\prime} ({\psi}_{h}^{n,l-1}) ({\psi}_{h}^{n,l}-{\psi}_{h}^{n,l-1}) {\boldsymbol{Q}}_{h}^{n,l-1}, \boldsymbol{v}\right) =0, \forall \boldsymbol{v} \in {{\varSigma}}_{h}.\\ \end{array} $$
    (2.7b)

The system (??) is solved with the same time step size on the whole spatial domain. In the next section, we consider a different approach based on nonoverlapping domain decomposition to reduce the size of the problem and to allow local time stepping, which is computationally efficient for problems with discontinuous physical coefficients.

3 Global-in-Time Domain Decomposition and Nested Iterative Methods

For the ease of presentation, we consider a decomposition of Ω into two nonoverlapping subdomains Ω1 and Ω2 separated by an interface Γ

$$ {{\varOmega}}_{1} \cap {{\varOmega}}_{2} = \emptyset;\quad {{\varGamma}} = \partial {{\varOmega}}_{1} \cap \partial {{\varOmega}}_{2} \cap {{\varOmega}}, \quad {{\varOmega}}= {{\varOmega}}_{1} \cup {{\varOmega}}_{2} \cup{{\varGamma}}. $$

The formulations given below can be generalized straightforwardly to the case of many subdomains. For i = 1,2, let ni denote the unit outward pointing normal vector field on ∂Ωi, and for any scalar or vector-valued function v defined on Ω, let vi be the restriction of v to Ωi. Solving problem (2.2)–(2.3) is equivalent to solve the corresponding problems in the subdomains

$$ \begin{array}{@{}rcl@{}} \partial_{t} {{\varTheta}}_{i} (\psi_{i}) + \nabla \cdot \boldsymbol{Q}_{i} &=& f_{i} {\kern90pt} \text{in } {{\varOmega}}_{i} \times (0,T), \\ \boldsymbol{Q}_{i} &=& - K_{i} ({{\varTheta}}_{i} (\psi_{i})) \nabla (\psi_{i} +z) {\kern5pt} \text{in } {{\varOmega}}_{i} \times (0,T), \\ \psi_{i} &=& 0 {\kern94pt} \text{on } \left( \partial {{\varOmega}}_{i} \cap \partial {{\varOmega}} \right) \times (0,T),\\ \psi_{i}(0) &=& \psi_{i,0} {\kern83pt} \text{in } {{\varOmega}}_{i}, \end{array} $$

for i = 1,2, together with the following transmission conditions on the space-time interface

$$ \begin{array}{c} \psi_{1} = \psi_{2} \\ \boldsymbol{Q}_{1} \cdot \boldsymbol{n}_{1} + \boldsymbol{Q}_{2} \cdot \boldsymbol{n}_{2} =0 \end{array} \quad \text{on } {{\varGamma}} \times (0,T). $$
(3.1)

Equivalently, one can also impose the Robin transmission conditions

$$ \begin{array}{c} -\boldsymbol{Q}_{1} \cdot \boldsymbol{n}_{1}+\alpha_{1,2} \psi_{1} = \boldsymbol{Q}_{2} \cdot \boldsymbol{n}_{2} +\alpha_{1,2} \psi_{2} \\ -\boldsymbol{Q}_{2} \cdot \boldsymbol{n}_{2} +\alpha_{2,1} \psi_{2} = \boldsymbol{Q}_{1} \cdot \boldsymbol{n}_{1} + \alpha_{2,1} \psi_{1} \end{array} \quad \text{on } {{\varGamma}} \times \left( 0,T\right), $$
(3.2)

where α1,2 and α2,1 are some positive numbers. Based on either the physical or Robin transmission conditions, we derive two methods, namely the global-in-time Schur (GT-Schur) and global-in-time Schwarz (GT-Schwarz) methods, in the following. Each method relies on a reformulation of the coupled subdomain problems as a space-time interface problem, through the use of trace operators.

3.1 Global-in-Time Schur (GT-Schur) Method

We first introduce the interface space \({{\varLambda }} := H^{{1/2}}_{00}({{\varGamma }})\) and its dual space \({{\varLambda }}^{\ast }:=(H^{{1/2}}_{00}({{\varGamma }}) )^{\prime }\). Denote by 〈⋅,⋅〉Γ the duality pairing between Λ∗ and Λ. The space-time interface operators associated with GT-Schur are time-dependent Dirichlet-to-Neumann or Steklov-Poincaré operators defined as

$$ \mathcal{S}^{\text{DtN}}_{i} : L^{2}(0,T; {{\varLambda}}) \longrightarrow L^{2}(0,T;{{\varLambda}}^{\ast}), \mathcal{S}^{\text{DtN}}_{i}(\lambda)=\boldsymbol{Q}_{i}(\lambda) \cdot \boldsymbol{n}_{i}{\mid_{{{\varGamma}}\times (0,T)}}, $$

for i = 1,2, where \(\left (\psi _{i}(\lambda ), \boldsymbol {Q}_{i}(\lambda )\right )\) is the solution to the following subdomain problem with Dirichlet boundary conditions on the space-time interface Γ × (0,T)

$$ \begin{array}{@{}rcl@{}} \partial_{t} {{\varTheta}}_{i} (\psi_{i}) + \nabla \cdot \boldsymbol{Q}_{i} &=& f_{i} {\kern90pt} \text{in } {{\varOmega}}_{i} \times (0,T), \\ \boldsymbol{Q}_{i} &=& - K_{i} ({{\varTheta}}_{i} (\psi_{i})) \nabla (\psi_{i} +z) {\kern5pt} \text{in } {{\varOmega}}_{i} \times (0,T), \\ \psi_{i} &=& \lambda {\kern93pt} \text{on } {{\varGamma}} \times (0,T), \\ \psi_{i} &=& 0 {\kern94pt}\text{on } \left( \partial {{\varOmega}}_{i} \cap \partial {{\varOmega}} \right) \times (0,T), \\ \psi_{i}(0) &=& \psi_{i,0} {\kern83pt}\text{in } {{\varOmega}}_{i}. \end{array} $$
(3.3)

The weak formulation of (3.3) is given by:

Find \(\left (\psi _{i}, \boldsymbol {Q}_{i}\right ) \in L^{2}\left (0,T; L^{2}({{\varOmega }}_{i})\right ) \times L^{2}\left (0,T; (L^{2}({{\varOmega }}_{i}))^{d}\right )\) such that, for all t ∈ (0,T), \( {{\int \limits }_{0}^{t}} \boldsymbol {Q}_{i}(\tau ) d\tau \in L^{2}\left (0,T; H(\text {div}, {{\varOmega }}_{i})\right )\) and

$$ \begin{array}{@{}rcl@{}} &&{}\left( {{\varTheta}}_{i} (\psi_{i}(t)) , \mu \right) + \left( \nabla \cdot {{\int}_{0}^{t}}\boldsymbol{Q}_{i}(\tau) d\tau, \mu\right) \\ && {}\quad = \left( {{\int}_{0}^{t}}f_{i}(\tau) d\tau,\mu \right) + \left( {{\varTheta}}_{i} (\psi_{i,0}) , \mu \right), \quad \forall \mu \in L^{2}({{\varOmega}}_{i}), \end{array} $$
(3.4)
$$ \begin{array}{@{}rcl@{}} && {}\quad\quad \left( {\kern-.5pt}K_{i}^{-1} {\kern-.5pt}\left( {{\varTheta}}_{i} (\psi_{i})\right){\kern-.5pt} \boldsymbol{Q}_{i}, \boldsymbol{v}{\kern-.5pt}\right) \! -\! \left( \psi_{i}, {\kern-.5pt}\nabla {\kern-.5pt}\cdot{\kern-.5pt} \boldsymbol{v}\right) + \left( \boldsymbol{e}_{\boldsymbol{z}}, \boldsymbol{v}\right) = - \langle \lambda, \boldsymbol{v} \cdot \boldsymbol{n}_{i}\rangle_{{{\varGamma}}},{\kern-.5pt} \forall \boldsymbol{v} \!\in\! H{\kern-.5pt}(\text{div}, {{\varOmega}}_{i}).~~~~~~~~~~~~ \end{array} $$
(3.5)

As the continuity of the pressure (3.1)1 is imposed via λ, there remains to enforce the normal flux continuity (3.1)2, which leads to the interface problem:

Find λ ∈ L2(0,T;Λ) such that

$$ {{\int}_{0}^{T}} \left\langle {{\varUpsilon}}(\lambda), \eta \right\rangle_{{{\varGamma}}} ds= 0, \quad \forall \eta \in L^{2}(0,T; {{\varLambda}}), $$
(3.6)

where \({{\varUpsilon }} (\lambda ) := S^{\text {DtN}}_{1}(\lambda )+ S^{\text {DtN}}_{2} (\lambda )\) is the jump of the normal fluxes across the space-time interface. Problem (3.6) is time-dependent and nonlinear, and will be solved by a nested iterative method. Applying Newton’s algorithm to (3.6) yields the following linear system at each iteration k

$$ {{\int}_{0}^{T}} \left\langle {{\varUpsilon}}^{\prime}(\lambda^{k})(\lambda^{k+1}-\lambda^{k}), \eta \right\rangle_{{{\varGamma}}} ds = {{\int}_{0}^{T}} \left\langle - {{\varUpsilon}}(\lambda^{k}), \eta \right\rangle_{{{\varGamma}}} ds, \quad \forall \eta \in L^{2}(0,T; {{\varLambda}}), $$
(3.7)

with

$$ {{\varUpsilon}}^{\prime}(\lambda)(g) = \mathcal{S}^{\text{DtN,lin}}_{1,\lambda}(g)+ \mathcal{S}^{\text{DtN,lin}}_{2, \lambda}(g), \text{ and} \quad \mathcal{S}^{\text{DtN,lin}}_{i,\lambda}(g) = \boldsymbol{w}_{i}(g) \cdot \boldsymbol{n}_{i} \vert_{{{\varGamma}} \times(0,T)}, $$

for i = 1,2, where \(\left (\xi _{i}(g), \boldsymbol {w}_{i}(g)\right ) \in L^{2}\left (0,T; L^{2}({{\varOmega }}_{i})\right ) \times L^{2} \left (0,T; (L^{2}({{\varOmega }}_{i}))^{d}\right )\), with \({{\int \limits }_{0}^{t}} \boldsymbol {w}_{i}(\tau ) d\tau \in L^{2}\left (0,T; H(\text {div}, {{\varOmega }}_{i})\right )\) for all t ∈ (0,T), is the solution to the linearized subdomain problem:

$$ \begin{array}{@{}rcl@{}} && \left( {{\varTheta}}_{i}^{\prime} (\psi_{i}(t)) \xi_{i}(t) , \mu \right) + \left( \nabla \cdot {{\int}_{0}^{t}}\boldsymbol{w}_{i}(\tau) d\tau, \mu\right)= 0, \qquad \forall \mu \in L^{2}({{\varOmega}}_{i}), \end{array} $$
(3.8)
$$ \begin{array}{@{}rcl@{}} && \left( K_{i}^{-1} \left( {{\varTheta}}_{i} (\psi_{i})\right) \boldsymbol{w}_{i}, \boldsymbol{v}\right) + ((K_{i}^{-1})^{\prime} ({{\varTheta}}_{i}(\psi_{i})){{\varTheta}}_{i}^{\prime}(\psi_{i}) \xi_{i} \boldsymbol{Q}_{i}, \boldsymbol{v})- \left( \xi_{i}, \nabla \cdot \boldsymbol{v}\right) \\ && \quad = - \langle g, \boldsymbol{v} \cdot \boldsymbol{n}_{i}\rangle_{{{\varGamma}}}-\left( \boldsymbol{e}_{\boldsymbol{z}}, \boldsymbol{v}\right), \quad \forall \boldsymbol{v} \in H(\text{div}, {{\varOmega}}_{i}). \end{array} $$
(3.9)

Note that \((\psi _{i}, \boldsymbol {Q}_{i}) = \left (\psi _{i}(\lambda ),\boldsymbol {Q}_{i}(\lambda )\right )\) is the solution of (3.4)–(3.5) for i = 1,2. The nested iteration algorithm for solving (3.6) is summarized in Algorithm 1.

Algorithm 1
figure a

Nested iteration for GT-Schur method.

Full size image

Remark 1

To accelerate the convergence of GMRES when solving the linearized interface problem (3.7), we use the time-dependent Neumann-Neumann preconditioner, \({\mathcal {P}}_{NN}^{-1}\), as proposed in [34] for the linear diffusion equation. Such a preconditioner involves solving the linearized subdomain problems (similarly to (3.8)–(3.9) but with Neumann boundary conditions on the space-time interface. Specifically, at each Newton iteration k and for 𝜗 ∈ L2(0,T;Λ∗), we have

$$ {\mathcal{P}}_{NN,\lambda^{k}}^{-1} (\vartheta) = {\mathcal{S}}_{1,\lambda^{k}}^{\text{NtD,lin}} (\vartheta) + {\mathcal{S}}_{2, \lambda^{k}}^{\text{NtD,lin}} (\vartheta), $$

where

$$ {\mathcal{S}}_{i,\lambda^{k}}^{\text{NtD,lin}} (\vartheta) = \xi_{i} (\vartheta) \vert_{{{\varGamma}} \times (0,T)}, i=1,2, $$

is the time-dependent Neumann-to-Dirichlet operator, and (ξi(𝜗),wi(𝜗)) ∈ L2(0,T;L2 \( ({{\varOmega }}_{i})) \times L^{2} (0,T; (L^{2}({{\varOmega }}_{i}))^{d})\) satisfiesi) \({{\int \limits }_{0}^{t}} \boldsymbol {w}_{i}(\tau ) d\tau \in L^{2}\left (0,T; H(\text {div}, {{\varOmega }}_{i})\right )\) for all t ∈ (0,T);ii) wi ⋅ni|Γ×(0,T) = 𝜗 and

$$ \begin{array}{@{}rcl@{}} && \left( {{\varTheta}}_{i}^{\prime} (\psi_{i}(t)) \xi_{i}(t) , \mu \right) + \left( \nabla \cdot {{\int}_{0}^{t}}\boldsymbol{w}_{i}(\tau) d\tau, \mu\right) = 0, \qquad \forall \mu \in L^{2}({{\varOmega}}_{i}), \\ && \left( K_{i}^{-1} \left( {{\varTheta}}_{i} (\psi_{i})\right) \boldsymbol{w}_{i}, \boldsymbol{v}\right) + \left( (K_{i}^{-1})^{\prime} ({{\varTheta}}_{i}(\psi_{i})) {{\varTheta}}_{i}^{\prime}(\psi_{i}) \xi_{i} \boldsymbol{Q}_{i}, \boldsymbol{v}\right)- \left( \xi_{i}, \nabla \cdot \boldsymbol{v}\right)\\ && \quad=-\left( \boldsymbol{e}_{\boldsymbol{z}}, \boldsymbol{v}\right), \quad \forall \boldsymbol{v} \in H^{{{\varGamma}}}_{0}(\text{div}, {{\varOmega}}_{i}), \end{array} $$

where \(H^{{{\varGamma }}}_{0}(\text {div}, {{\varOmega }}_{i}):=\left \{ \boldsymbol {v} \in H(\text {div}, {{\varOmega }}_{i}): \boldsymbol {v} \cdot \boldsymbol {n}_{i}\vert _{{{\varGamma }}}=0\right \}\).

3.2 Global-in-Time Schwarz (GT-Schwarz) Method

With Robin transmission conditions, the interface operators are of Robin-to-Robin type and are defined as

$$ \begin{array}{@{}rcl@{}} \mathcal{S}^{\text{RtR}}_{i} : L^{2}(0,T; L^{2}({{\varGamma}})) &\longrightarrow& L^{2}(0,T;L^{2}({{\varGamma}})), \\ \xi &\mapsto& \left( 1+\frac{\alpha_{j,i}}{\alpha_{i,j}}\right)\boldsymbol{Q}_{i}(\xi)\cdot \boldsymbol{n}_{i}{ \mid_{{{\varGamma}}\times (0,T)}}+\frac{\alpha_{j,i}}{\alpha_{i,j}}\xi, \end{array} $$

for i = 1,2, and j = 3 − i, where \(\left (\psi _{i}(\xi ), \boldsymbol {Q}_{i}(\xi )\right )\) is the solution to the subdomain problem with Robin boundary conditions on the space-time interface

$$ \begin{array}{@{}rcl@{}} \partial_{t} {{\varTheta}}_{i} (\psi_{i}) + \nabla \cdot \boldsymbol{Q}_{i} &=& f_{i} {\kern90pt} \text{ in } {{\varOmega}}_{i} \times (0,T), \\ \boldsymbol{Q}_{i} &=& - K_{i} ({{\varTheta}}_{i} (\psi_{i})) \nabla (\psi_{i} +z) {\kern5pt} \text{ in } {{\varOmega}}_{i} \times (0,T), \\ -\boldsymbol{Q}_{i}(\xi)\cdot \boldsymbol{n}_{i}+ \alpha_{i,j}\psi_{i} &=& \xi {\kern93pt} \text{ on } {{\varGamma}} \times (0,T), \\ \psi_{i} &=& 0 {\kern93.5pt} \text{ on } \left( \partial {{\varOmega}}_{i} \cap \partial {{\varOmega}} \right) \times (0,T), \\ \psi_{i}(0) &=& \psi_{i,0} {\kern83pt} \text{ in } {{\varOmega}}_{i}. \end{array} $$
(3.10)

The weak formulation of (3.10) is given by:

Find \(\left (\psi _{i}, \boldsymbol {Q}_{i}\right ) \in L^{2} \left (0,T; L^{2}({{\varOmega }}_{i})\right ) \times L^{2} \left (0,T; (L^{2} ({{\varOmega }}_{i}))^{d}\right )\) such that, for all t ∈ (0,T), \({{\int \limits }_{0}^{t}} \boldsymbol {Q}_{i}(\tau ) d\tau \in L^{2} \left (0,T; H(\text {div}, {{\varOmega }}_{i})\right )\) and

$$ \begin{array}{@{}rcl@{}} && \left( {{\varTheta}}_{i} (\psi_{i}(t)) , \mu \right) + \left( \nabla \cdot {{\int}_{0}^{t}} \boldsymbol{Q}_{i}(\tau) d\tau, \mu \right) \\ && \quad = \left( {{\int}_{0}^{t}}f_{i}(\tau) d\tau,\mu \right) + \left( {{\varTheta}}_{i} (\psi_{i,0}) , \mu \right), \quad \forall \mu \in L^{2}({{\varOmega}}_{i}), \end{array} $$
(3.11)
$$ \begin{array}{@{}rcl@{}} && \left( K_{i}^{-1} \left( {{\varTheta}}_{i} (\psi_{i})\right) \boldsymbol{Q}_{i}, \boldsymbol{v}\right) - \left( \psi_{i}, \nabla \cdot \boldsymbol{v}\right) + \left( \boldsymbol{e}_{\boldsymbol{z}}, \boldsymbol{v}\right) + \left\langle \frac{1}{\alpha_{i,j}} \boldsymbol{Q}_{i} \cdot \boldsymbol{n}_{i} , \boldsymbol{v} \cdot \boldsymbol{n}_{i} \right\rangle_{{{\varGamma}}} \\ && \quad = - \left\langle \frac{1}{\alpha_{i,j}} \xi, \boldsymbol{v} \cdot \boldsymbol{n}_{i} \right\rangle_{{{\varGamma}}}, \quad \forall \boldsymbol{v} \in H(\text{div}, {{\varOmega}}_{i}). \end{array} $$
(3.12)

The space-time interface problem is obtained by enforcing the Robin transmission conditions (3.2):

Find ξ = (ξ1,ξ2) ∈ L2(0,T;L2(Γ))2 such that

$$ {{\int}_{0}^{T}} \left\langle {{\varUpsilon}}_{R}(\boldsymbol{\xi}), \boldsymbol{\zeta} \right\rangle_{{{\varGamma}}} = 0 , \quad \forall \boldsymbol{\zeta}=(\zeta_{1},\zeta_{2})\in L^{2}(0,T;L^{2}({{\varGamma}}))^{2}, $$
(3.13)

where \({{\varUpsilon }}_{R}(\boldsymbol {\xi })=\left (\xi _{1} - \mathcal {S}^{\text {RtR}}_{2}(\xi _{2}), \xi _{2} - \mathcal {S}^{\text {RtR}}_{1}(\xi _{1})\right )\) represents the jumps of the Robin terms associated with each subdomain. To solve the nonlinear problem (3.13), we again apply Newton’s method and obtain the linearized interface problem

$$ \begin{array}{@{}rcl@{}} {{\int}_{0}^{T}} \left\langle \boldsymbol{J}_{{{\varUpsilon}}_{R}} (\boldsymbol{\xi}^{k}) (\boldsymbol{\xi}^{k+1}-\boldsymbol{\xi}^{k}), \boldsymbol{\zeta} \right\rangle_{{{\varGamma}}} ds &=& {{\int}_{0}^{T}}\left\langle -{{\varUpsilon}}_{R}(\boldsymbol{\xi}^{k}), \boldsymbol{\zeta} \right\rangle_{{{\varGamma}}} ds, \\ \forall \boldsymbol{\zeta} &\in& (L^{2}(0,T; L^{2}({{\varGamma}})))^{2}, \end{array} $$
(3.14)

with \( \boldsymbol {J}_{{{\varUpsilon }}_{R}}(\boldsymbol {\xi })(\boldsymbol {r}) =(r_{1} - \mathcal {S}^{\text {RtR,lin}}_{2,\xi _{2}}(r_{2}), r_{2}-\mathcal {S}^{\text {RtR,lin}}_{1,\xi _{1}}(r_{1}))\), and

$$ \mathcal{S}^{\text{RtR,lin}}_{i,\xi_{i}}(r) = \left( 1+\frac{\alpha_{j,i}}{\alpha_{i,j}}\right) \boldsymbol{w}_{i}(r)\cdot \boldsymbol{n}_{i}{ \mid_{{{\varGamma}}\times (0,T)}} + \frac{\alpha_{j,i}}{\alpha_{i,j}}r $$

for i = 1,2, where \((\xi _{i}(r), \boldsymbol {w}_{i}(r)) \in L^{2}(0,T; L^{2}({{\varOmega }}_{i})) \times L^{2}(0,T; (L^{2}({{\varOmega }}_{i}))^{d})\), with \({{\int \limits }_{0}^{t}} \boldsymbol {w}_{i}(\tau ) d\tau \in L^{2}(0,T; H(\text {div}, {{\varOmega }}_{i}))\) for all t ∈ (0,T), is the solution to the linearized subdomain problem

$$ \begin{array}{@{}rcl@{}} && \left( {{\varTheta}}_{i}^{\prime} (\psi_{i}(t)) \xi_{i}(t) , \mu \right) + \left( \nabla \cdot {{\int}_{0}^{t}} \boldsymbol{w}_{i}(\tau) d\tau, \mu\right) = 0, \forall \mu \in L^{2}({{\varOmega}}_{i}), \end{array} $$
(3.15)
$$ \begin{array}{@{}rcl@{}} && \left( {K}_{i}^{-1} \left( {{\varTheta}}_{i} (\psi_{i})\right) \boldsymbol{w}_{i}, \boldsymbol{v}\right) + \left( (K_{i}^{-1})^{\prime} ({{\varTheta}}_{i}(\psi_{i})) {{\varTheta}}_{i}^{\prime}(\psi_{i}) \xi_{i} \boldsymbol{Q}_{i}, \boldsymbol{v}\right) - \left( \xi_{i}, \nabla \cdot \boldsymbol{v}\right) \\ && \quad +\left\langle \frac{1}{\alpha_{i,j}} \boldsymbol{w}_{i} \cdot \boldsymbol{n}_{i} , \boldsymbol{v} \cdot \boldsymbol{n}_{i} \right\rangle_{{{\varGamma}}} = - \left\langle \frac{1}{\alpha_{i,j}} r, \boldsymbol{v} \cdot \boldsymbol{n}_{i} \right\rangle_{{{\varGamma}}} \!\!- \left( \boldsymbol{e}_{\boldsymbol{z}}, \boldsymbol{v}\right), \forall \boldsymbol{v} \in H(\text{div}, {{\varOmega}}_{i}).~~~~~~~~~~~~~~ \end{array} $$
(3.16)

Note that \((\psi _{i},\boldsymbol {Q}_{i}) = \left (\psi _{i}(\xi _{i}),\boldsymbol {Q}_{i}(\xi _{i})\right )\) is the solution to (3.11)–(3.12) for i = 1,2. The nested iteration algorithm for solving (3.13) is summarized in Algorithm 2.

Algorithm 2
figure b

Nested iteration for GT-Schwarz method.

Full size image

4 Nonconforming Time Discretization

The interface problems for the GT-Schur and GT-Schwarz methods are global in time, and solving them iteratively via Newton linearization and GMRES involves numerical solutions of nonlinear and linearized subdomain problems over the whole time interval (0,T). Thus independent time discretizations can be used in the subdomains. Let \( \mathcal {T}_{1} \) and \( \mathcal {T}_{2} \) be two possibly different partitions of the time interval (0,T) into sub-intervals (see Fig. 1). We denote by Ji,n the time interval (ti,n,ti,n− 1] and by Δti,n := (ti,n − ti,n− 1) for \( n=1, \dots , N_{i} \) and i = 1,2.

Fig. 1
figure 1

Nonconforming time grids in the subdomains

Full size image

In space, we assume that the partitions \( \mathcal {K}_{h,1} \) of subdomain Ω1 and \( \mathcal {K}_{h,2} \) of subdomain Ω2 are such that their union \(\mathcal {K}_{h}= \cup _{i=1}^{2} \mathcal {K}_{h,i}\) forms a finite element partition of Ω. Denote by \( \mathcal {E}_{h,{{\varGamma }}} \) the set of edges of elements of \(\mathcal {K}_{h,1}\) or \(\mathcal {K}_{h,2}\) that lie on Γ. For simplicity, we have considered conforming spatial discretization as our main focus in this work is the use of local time stepping. As for the monodomain problem (cf. (2.5), denote by \(M_{h,i} \subset L^{2}({{\varOmega }}_{i})\) and Σh,i ⊂ H(div,Ωi) the discrete spaces in each subdomain, where Mh,i consists of piecewise constant functions and Σh,i is the lowest order Raviart-Thomas space. The discrete interface space is given by

$$ {{\varLambda}}_{h} := \left\{ \lambda \in L^{2}(\mathcal{E}_{h,{{\varGamma}}} ): \lambda\vert_{E}= \text{constant on } E, \forall E \in \mathcal{E}_{h,{{\varGamma}}}\right\}. $$

Numerical solutions of the subdomain problems are obtained using the EI-MFE scheme as presented in Section 2.

For i = 1,2, we denote by \( P_{0}(\mathcal {T}_{i}, {{\varLambda }}_{h}) \) the space of piecewise constant functions in time on grid \(\mathcal {T}_{i}\) with values in Λh

$$ P_{0}(\mathcal{T}_{i}, {{\varLambda}}_{h}) = \left\{ \phi: (0,T) \rightarrow {{\varLambda}}_{h}, \phi \text{is constant on} J_{i,n}, \ \forall n=1, \dots, N_{i} \right\}. $$

In order to exchange data on the space-time interface between different time grids, we define an L2 projection πji from \(P_{0} (\mathcal {T}_{i}, {{\varLambda }}_{h})\) onto \(P_{0}(\mathcal {T}_{j}, {{\varLambda }}_{h})\) (see [21, 30]): for \( \phi \in P_{0} (\mathcal {T}_{i}, {{\varLambda }}_{h})\), \({{\varPi }}_{ji} \phi \mid _{J_{j,n}}\) is the average value of ϕ on Jj,n, for \(n=1, \dots , N_{j}\), i = 1,2, and j = (3 − i).

4.1 For GT-Schur Method

The discrete interface unknown, denoted by λh, is chosen to be piecewise constant in time on one grid, either \(\mathcal {T}_{1}\) or \(\mathcal {T}_{2}\). For instance, let \(\lambda _{h} \in P_{0}(\mathcal {T}_{1}, {{\varLambda }}_{h})\) and let ψ1 = π11(λh) = Id(λh). The weak continuity of the pressure in time across the interface is fulfilled by letting

$$ \psi_{2} = {{\varPi}}_{21} (\lambda_{h}) \in P_{0} (\mathcal{T}_{2}, {{\varLambda}}_{h}). $$

The fully discrete counterpart of the normal flux continuity, i.e., the interface problem (3.6), is weakly enforced over the time intervals of \(\mathcal {T}_{1}\) as follows

$$ {\int}_{J_{1,n}} {\int}_{{{\varGamma}}} \left[\mathcal{S}^{\text{DtN}}_{1}(\lambda_{h}) + {{\varPi}}_{12} \left( \mathcal{S}^{\text{DtN}}_{2}({{\varPi}}_{21}(\lambda_{h}))\right) \right] \eta d\gamma ds= 0, \quad \forall \eta \in {{\varLambda}}_{h} $$

for \(n=1, \dots , N_{1}\). Similarly for the linearized interface problem, we choose \({g_{h}^{k}} \in P_{0}(\mathcal {T}_{1}, {{\varLambda }}_{h})\) for \(k=1,2,\dots \), and enforce weakly (3.7) over each time interval of \(\mathcal {T}_{1}\)

$$ \begin{array}{@{}rcl@{}} && {\int}_{J_{1,n}} {\int}_{{{\varGamma}}} \left[\mathcal{S}^{\text{DtN,lin}}_{1,{\lambda_{h}^{k}}}({g_{h}^{k}}) + {{\varPi}}_{12} \left( \mathcal{S}^{\text{DtN,lin}}_{2, {{\varPi}}_{21}({\lambda_{h}^{k}})} ({{\varPi}}_{21}({g_{h}^{k}}))\right)\right] \eta d\gamma ds \\ && \quad = {\int}_{J_{1,n}} {\int}_{{{\varGamma}}} \left[ - \mathcal{S}^{\text{DtN}}_{1}({\lambda_{h}^{k}}) - {{\varPi}}_{12} \left( \mathcal{S}^{\text{DtN}}_{2}({{\varPi}}_{21}({\lambda_{h}^{k}}))\right) \right] \eta d\gamma ds, \quad \forall \eta \in {{\varLambda}}_{h} \end{array} $$

for \(n=1, \dots , N_{1}\).

4.2 For GT-Schwarz Method

The two interface unknowns represent the Robin terms on each subdomain, thus we let \(\xi _{h,i} \in P_{0}(\mathcal {T}_{i}, {{\varLambda }}_{h})\) for i = 1,2. The fully discrete counterpart of the nonlinear interface problem (3.13) is given by

$$ \begin{array}{@{}rcl@{}} && {\int}_{J_{1,n}} {\int}_{{{\varGamma}}} \left[\xi_{h,1} - {{\varPi}}_{12} \left( \mathcal{S}^{\text{RtR}}_{2}(\xi_{h,2})\right)\right] \zeta d\gamma ds = 0, \quad \forall \zeta \in {{\varLambda}}_{h}, \forall n=1, \dots, N_{1}, \\ && {\int}_{J_{2,n}} {\int}_{{{\varGamma}}} \left[\xi_{h,2} - {{\varPi}}_{21}\left( \mathcal{S}^{\text{RtR}}_{1}(\xi_{h,1})\right)\right] \zeta d\gamma ds = 0, \quad \forall \zeta \in {{\varLambda}}_{h}, \forall n=1, \dots, N_{2}. \end{array} $$

Similarly for the linearized interface problem (3.14), we let \(r_{h,i}^{k} \in P_{0}(\mathcal {T}_{i}, {{\varLambda }}_{h})\) and enforce

$$ \begin{array}{@{}rcl@{}} && {\int}_{J_{i,n}} {\int}_{{{\varGamma}}} \left[r^{k}_{h,i} - {{\varPi}}_{ij} \left( \mathcal{S}^{\text{RtR,lin}}_{j,\xi^{k}_{h,j}}(r^{k}_{h,j})\right)\right] \zeta d\gamma ds \\ && \quad = {\int}_{J_{i,n}} {\int}_{{{\varGamma}}} \left[-\xi_{h,i} + {{\varPi}}_{ij}\left( \mathcal{S}^{\text{RtR}}_{j}(\xi_{h,j})\right)\right] \zeta d\gamma ds, \quad \forall \zeta \in {{\varLambda}}_{h} \end{array} $$

for \(n=1, \dots , N_{i}\), i = 1,2, and j = (3 − i).

5 Numerical Results

We study numerical performance of the proposed GT-Schur and GT-Schwarz methods on two test cases: Test case 1 with continuous and constant conductivity coefficients, and Test case 2 with nonlinear and heterogeneous conductivity functions. We consider the decomposition into two nonoverlapping subdomains in the numerical experiments; the case of multiple subdomains will be investigated in our future work. We shall verify the accuracy in space and in time, the convergence of nonlinear and linear iterations for the proposed methods as well as numerical optimized Robin parameters for GT-Schwarz. Note that we disregard gravity in our numerical experiments and the code to generate the results below is implemented in FreeFem++ [31] in a sequential setting.

Regarding the nonlinear iterative solvers for the interface problems associated with GT-Schur and GT-Schwarz, we set 𝜖 = 5 × 10− 4 and stop Newton iterations when

$$ \text{either} \quad \left\| \sum\limits_{i=1}^{2} \boldsymbol{Q}_{i} \cdot \boldsymbol{n}_{i}\vert_{t=T} \right\|_{L^{2}({{\varLambda}})} < \epsilon, \quad \text{or} \quad \left( \text{error} <\epsilon\right), $$
(5.1)

where

$$ \text{error}=\left\{\begin{array}{ll} \|g^{k} \vert_{t=T}\|_{L^{2}({{\varLambda}})} & \text{for GT-Schur (cf. Algorithm 1)}, \\ \|\boldsymbol{r}^{k} \vert_{t=T}\|_{(L^{2}({{\varLambda}}))^{2}} & \text{for GT-Schwarz (cf. Algorithm 2)}. \end{array} \right. $$

For the linear iterative solvers, the tolerance for GMRES is set for both methods to be ε = 10− 7. We shall compare the convergence of GMRES for different algorithms: GT-Schur with no preconditioner, GT-Schur with the Neumann-Neumann (N-N) preconditioner, and GT-Schwarz. Since one iteration of GT-Schur with the preconditioner costs twice as much as one iteration of GT-Schur (without preconditioning) or GT-Schwarz (in terms of number of subdomain solves), we report the number of subdomain solves (instead of number of iterations) required by each algorithm to reach the same tolerance.

5.1 Test Case 1 with Homogeneous Coefficients

The spatial domain is Ω = (0,1)2 and the final time T = 1. We decompose Ω into Ω1 = (0,0.5) × (0,1) and Ω2 = (0.5,1) × (0,1). The saturation functions are quadratic, Θi(ψ) = ψ2 for i = 1,2, and the conductivity parameters are constant, K1 = K2 = 1. The model equation becomes

$$ \begin{array}{rl} \partial_{t} (\psi^{2}) + \nabla \cdot \boldsymbol{Q} &= f \\ \boldsymbol{Q}&=-\nabla \psi \end{array} \quad \text{in} {{\varOmega}} \times (0,T). $$
(5.2)

We impose Dirichlet boundary conditions and choose the initial condition as well as the right-hand side f such that the exact solution to (5.2) is given by

$$ \psi_{\text{exact}}=4-2x-4t^{5}x(1-x)y(1-y). $$

For GT-Schwarz, the Robin parameters are α1,2 = α2,1 = 10.5. This value gives the fastest convergence of GMRES for this test case as will be discussed in Section 5.3.

We first verify the convergence rates when both spatial mesh size h and time step size Δt decrease. Let h = Δt ∈{1/10,1/20,1/40,1/80,1/160}; for conforming time grids, Δti = Δt, i = 1,2, while for nonconforming time grids, Δt1 = Δt and Δt2 = 5/4Δt. Figure 2 shows the errors of the pressure (in \(L^{2}({{\varOmega }}_{i})\)-norm) and velocity (in \(L^{2}({{\varOmega }}_{i})\)- and H(div,Ωi)-norms) at T = 1 with conforming and nonconforming time grids. GT-Schur and GT-Schwarz give the same errors when Δt1 = Δt2, however, when the time step sizes are not the same, the results by the two methods are slightly different. We see that first-order convergence is preserved with nonconforming time grids, and the errors are almost the same as those with fine time steps on the whole domain - especially the L2 errors of pressure and velocity. The velocity errors in H(div,Ω2) −norm with different time steps are a little larger than those with conforming time steps, note that the time step in Ω2 is chosen to be greater than that in Ω1. All the errors are obtained by performing 2 Newton iterations for both GT-Schur and GT-Schwarz, which guarantees the stopping criterion (5.1). For the convergence of GMRES, in Table 1 we show the average numbers of subdomain solves per Newton iteration for GT-Schur without or with the Neumann-Neumann preconditioner and GT-Schwarz. We observe that the preconditioner significantly accelerates the convergence of GT-Schur when the mesh size and time step size are small, and the numbers of subdomain solves are quite independent of h and Δt. For GT-Schwarz, the convergence is fast and the numbers of subdomain solves slightly increase when h and Δt decrease. GT-Schwarz is less sensitive to the use of nonconforming time grids, while for preconditioned GT-Schur, the convergence is a little slower with different time steps than with uniform time steps.

Fig. 2
figure 2

[Test case 1] Errors of pressure and velocity in Ω1 (left) and in Ω2 (right) at T = 1 with decreasing spatial mesh sizes and time step sizes. Each plot shows the results with conforming time grids (red) and nonconforming time grids using GT-Schur (blue) or GT-Schwarz (cyan)

Full size image
Table 1 [Test case 1] Average numbers of linearized subdomain solves per Newton iteration with decreasing spatial mesh sizes and time step sizes; the tolerance for GMRES is set to be 10− 7
Full size table

Next, we fix the spatial mesh h = 1/200 and investigate the errors in time only. Table 2 shows the errors at T = 1 as well as the convergence rates of pressure and velocity by the GT-Schur and GT-Schwarz methods with nonconforming time steps. We see that the errors in Ω2 are similar for both methods, however, in Ω1, the L2 errors of pressure and velocity by GT-Schwarz are slightly smaller than those by GT-Schur, while the velocity errors in H(div,Ω1) −norm by GT-Schur is smaller than by GT-Schwarz. Nevertheless, all the convergence rates are close to 1 for both methods as expected. Regarding the iterative solvers, we again perform 2 Newton iterations for all algorithms, and report in Table 3 the average numbers of linearized subdomain solves per Newton iteration. Clearly, GT-Schur with no preconditioner converges very slow, and thus preconditioning is essential. The preconditioned GT-Schur and GT-Schwarz are comparable in terms of convergence speed, and they are quite independent of the time step sizes.

Table 2 [Test case 1] Errors of pressure and velocity in each subdomain at T = 1 with fixed h = 1/200 and varying time step sizes Δt1≠Δt2. The corresponding convergence rates are shown in square brackets
Full size table
Table 3 [Test case 1] Average numbers of linearized subdomain solves per Newton iteration with nonconforming time steps; the mesh size is fixed, h = 1/200, and the tolerance for GMRES is set to be 10− 7
Full size table

5.2 Test Case 2 with Heterogeneous Coefficients

This test case is taken from [53] where the domain of calculation Ω = (− 1,1) × (0,1) is decomposed into Ω1 = (− 1,0) × (0,1) and Ω2 = (0,1) × (0,1). The conductivity functions are nonlinear and given by \(K_{1}({{\varTheta }}_{1})={{{\varTheta }}_{1}^{2}}\) and \(K_{2}({{\varTheta }}_{2})={{{\varTheta }}_{2}^{3}}\). The saturation functions are

$$ {{\varTheta}}_{i}(\psi)=\begin{cases} \frac{1}{(1-\psi)^{\frac{1}{i+1}}} & \text{if } \psi <0, \\ 1 & \text{if } \psi \geq 0, \end{cases}\quad i=1,2. $$

The right-hand side functions are

$$ \begin{array}{@{}rcl@{}} f_{1}(x,y,t) &=& \frac{4}{(1+x^{2}+y^{2})^{2}}-\frac{t}{\sqrt{(1+t^{2})^{3}(1+x^{2}+y^{2})}}, \quad (x,y) \in {{\varOmega}}_{1}, t>0,\\ f_{2}(x,y,t) &=& \frac{2(1-y^{2})}{(1+y^{2})^{2}}-\frac{2t}{3\sqrt[3]{(1+t^{2})^{4}(1+y^{2})}}, {\kern46.25pt} (x,y) \in {{\varOmega}}_{2}, t>0, \end{array} $$

so that the exact solution is given by

$$ \begin{array}{@{}rcl@{}} \psi_{1}(x,y,t) &=& 1-(1+t^{2})(1+x^{2}+y^{2}), \quad (x,y) \in {{\varOmega}}_{1}, t>0,\\ \psi_{2}(x,y,t) &=& 1-(1+t^{2})(1+y^{2}), \qquad\qquad (x,y) \in {{\varOmega}}_{2}, t>0. \end{array} $$

Both Dirichlet and Neumann boundary conditions are imposed as follows

$$ \begin{array}{@{}rcl@{}} \psi_{1}&=&1-(1+t^{2})(2+y^{2}) \quad \text{on } x=-1, t>0,\\ K_{1}({{\varTheta}}_{1}(\psi_{1})) \partial_{y} \psi_{1}&=& \begin{cases} 0 & \text{on } y=0, t>0,\\ \frac{2}{2+x^{2}} & \text{on } y=1, t>0, \end{cases} \\ \psi_{2}&=&1-(1+t^{2})(1+y^{2}) \quad \text{on } x=1, t>0, \\ K_{2}({{\varTheta}}_{2}(\psi_{2})) \partial_{y} \psi_{2}&=& \begin{cases} 0 & \text{on } y=0, t>0,\\ 1 & \text{on } y=1, t>0. \end{cases} \end{array} $$

We vary the mesh size h and the nonconforming time step sizes where h = Δt1 ∈{1/10,1/20,1/40,1/80} and Δt2 = 5/4Δt1. For this test case, the Robin parameters are α1,2 = α2,1 = 2.5. The number of Newton iterations required to reach the tolerance (5.1) and the average number of linearized subdomain solves (for GMRES) per Newton iteration are shown in Table 4. As the problem is highly nonlinear, more Newton iterations are needed for both GT-Schur and GT-Schwarz. For GMRES, for this heterogeneous problem, the Neumann-Neumann preconditioner still works efficiently and the convergence of preconditioned GT-Schur is almost independent of the mesh size and time step sizes. GT-Schwarz with the numerically optimized Robin parameter (cf. Section 5.3) gives fast convergence, and the number of iterations only increases slightly when decreasing h and Δti. Figure 3 shows the errors of pressure and velocity in each subdomain for both conforming and nonconforming time grids. We see that GT-Schur with Δt2 > Δt1 gives nearly the same errors as with Δt2 = Δt1, while the errors by GT-Schwarz with nonconforming time steps are slightly larger, especially the velocity errors.

Fig. 3
figure 3

[Test case 2] Errors of pressure and velocity in Ω1 (left) and in Ω2 (right) at T = 1 with decreasing spatial mesh sizes and time step sizes. Each plot shows the results with conforming time grids (red) and nonconforming time grids using GT-Schur (blue) or GT-Schwarz (cyan)

Full size image
Table 4 [Test case 2] Convergence results of GT-Schur and GT-Schwarz with decreasing spatial mesh sizes and time step sizes where Δt1 < Δt2
Full size table

5.3 The Choice of Robin Parameters

We now analyze numerically the effect of Robin parameters on the convergence of the nonlinear and linear iterative solvers for GT-Schwarz. We choose the mesh size h = 1/10 and nonconforming time steps Δt1 = 1/10 and Δt2 = 1/8. Let α1,2 = α2,1 = α, and run GT-Schwarz with values of α ∈ (0,50). The tolerance for both nonlinear and linear iterative solvers is 10− 11, and we record the residuals with various α after fixed numbers of Newton and GMRES iterations, namely NNewton and NGMRES. For Test case 1, NNewton = 2 and NGMRES = 15, while for Test case 2, NNewton = 5 and NGMRES = 20. Figure 4 shows Newton and GMRES residuals after the same numbers of nonlinear and linear iterations with different values of α. We see that for Test case 1, α ≈ 10.5 gives the smallest GMRES residual and for Test case 2, the value is α ≈ 2.5. These are the Robin parameters used in the previous subsections. However, such values do not lead to the smallest Newton residuals (cf. the red curves in Fig. 4). As the number of Newton iterations is often small, we have chosen the Robin parameters that optimize the convergence of GMRES (i.e., the linear solver). Further investigations as well as explicit formulas to compute the optimized Robin parameters based on the framework of the OSWR algorithm [6, 22] shall be studied in future work.

Fig. 4
figure 4

Newton and GMRES residuals of GT-Schwarz as functions of the Robin parameter α = α1,2 = α2,1 for Test case 1 (left) and Test case 2 (right)

Full size image

6 Conclusion

We developed two different nonlinear domain decomposition methods, namely GT-Schur and GT-Schwarz, for partially saturated flow in a heterogeneous porous medium where local time discretizations are allowed in different parts of the medium. Both methods rely on a reformulation of the initial problem as a space-time interface problem, through the use of trace operators. GT-Schur uses the time-dependent Dirichlet-to-Neumann operator and GT-Schwarz uses the time-dependent Robin-to-Robin operator. For each method, the nonlinear interface problem is solved by a nested iteration approach which involves, at each Newton iteration, the solution of a linearized interface problem and, at each Krylov iteration, parallel solution of the time-dependent linearized Richards equation in each subdomain. In addition, the Neumann-Neumann preconditioner is considered for GT-Schur to accelerate the convergence of the linearized iterative solver. The subdomain problems are discretized in time by backward Euler with nonmatching time grids, and in space by the lowest order Raviart-Thomas space on a conforming spatial mesh. The proposed methods were numerically verified on both homogeneous and heterogeneous test cases with known exact solutions. Numerical results show that GT-Schur with preconditioner and GT-Schwarz with well-chosen Robin parameters converge fast, and all schemes preserve orders of accuracy in space and in time with different time step sizes. We notice that the preconditioned GT-Schur method is almost independent of the spatial and temporal step sizes, and gives smaller errors in velocity than GT-Schwarz when the subdomain time steps are different. The effect of various Robin parameters on the convergence of Newton and GMRES iterations was also investigated numerically. Our next steps include the study of theoretical optimized Robin parameters, convergence analysis of GT-Schur and GT-Schwarz and their numerical performance on more realistic test cases.