Martin J. Gander

Martin J. Gander, Hui Zhang

Solving time-harmonic wave propagation problems by iterative methods is a difficult task, and over the last two decades, an important research effort has gone into developing preconditioners for the simplest representative of such wave propagation problems, the Helmholtz equation. A specific class of these new preconditioners are considered here. They were developed by researchers with various backgrounds using formulations and notations that are very different, and all are among the most promising preconditioners for the Helmholtz equation. The goal of the present manuscript is to show that this class of preconditioners are based on a common mathematical principle, and they can all be formulated in the context of domain decomposition methods called optimized Schwarz methods. This common formulation allows us to explain in detail how and why all these methods work. The domain decomposition formulation also allows us to avoid technicalities in the implementation description we give of these recent methods. The equivalence of these methods with optimized Schwarz methods translates at the discrete level into equivalence with approximate block LU decomposition preconditioners, and we give in each case the algebraic version, including a detailed description of the approximations used. While we chose to use the Helmholtz equation for which these methods were developed, our notation is completely general and the algorithms we give are written for an arbitrary second order elliptic operator. The algebraic versions are even more general, assuming only a connectivity pattern in the discretization matrix.

V. Dolean, M. J. Gander, F. Kwok et al.

For linear problems, domain decomposition methods can be used directly as iterative solvers, but also as preconditioners for Krylov methods. In practice, Krylov acceleration is almost always used, since the Krylov method finds a much better residual polynomial than the stationary iteration, and thus converges much faster. We show in this paper that also for non-linear problems, domain decomposition methods can either be used directly as iterative solvers, or one can use them as preconditioners for Newton's method. For the concrete case of the parallel Schwarz method, we show that we obtain a preconditioner we call RASPEN (Restricted Additive Schwarz Preconditioned Exact Newton) which is similar to ASPIN (Additive Schwarz Preconditioned Inexact Newton), but with all components directly defined by the iterative method. This has the advantage that RASPEN already converges when used as an iterative solver, in contrast to ASPIN, and we thus get a substantially better preconditioner for Newton's method. The iterative construction also allows us to naturally define a coarse correction using the multigrid full approximation scheme, which leads to a convergent two level non-linear iterative domain decomposition method and a two level RASPEN non-linear preconditioner. We illustrate our findings with numerical results on the Forchheimer equation and a non-linear diffusion problem.

Martin J. Gander, Atle Loneland, Talal Rahman

We propose a new, harmonically enriched multiscale coarse space (HEM) for domain decomposition methods. For a coercive high contrast model problem, we show how to enrich the coarse space so that the method is robust against any variations and discontinuities in the problem parameters both inside subdomains and across and along subdomain boundaries. We prove our results for an enrichment strategy based on solving simple, lower dimensional eigenvalue problems on the interfaces between subdomains, and we call the resulting coarse space the spectral harmonically enriched multiscale coarse space (SHEM). We then also give a variant that performs equally well in practice, and does not require the solve of eigenvalue problems, which we call non-spectral harmonically enriched multiscale coarse space (NSHEM). Our enrichment process naturally reaches the optimal coarse space represented by the full discrete harmonic space, which enables us to turn the method into a direct solver (OHEM). We also extensively test our new coarse spaces numerically, and the results confirm our analysis

Martin J. Gander, Soheil Hajian

Schwarz methods are attractive parallel solution techniques for solving large-scale linear systems obtained from discretizations of partial differential equations (PDEs). Due to the iterative nature of Schwarz methods, convergence rates are an important criterion to quantify their performance. Optimized Schwarz methods (OSM) form a class of Schwarz methods that are designed to achieve faster convergence rates by employing optimized transmission conditions between subdomains. It has been shown recently that for a two-subdomain case, OSM is a natural solver for hybridizable discontinuous Galerkin (HDG) discretizations of elliptic PDEs. In this paper, we generalize the preceding result to the many-subdomain case and obtain sharp convergence rates with respect to the mesh size and polynomial degree, the subdomain diameter, and the zeroth-order term of the underlying PDE, which allows us for the first time to give precise convergence estimates for OSM used to solve parabolic problems by implicit time stepping. We illustrate our theoretical results with numerical experiments.

Martin J. Gander, Laurence Halpern, Véronique Martin

Often computational models are too expensive to be solved in the entire domain of simulation, and a cheaper model would suffice away from the main zone of interest. We present for the concrete example of an evolution problem of advection reaction diffusion type a heterogeneous domain decomposition algorithm which allows us to recover a solution that is very close to the solution of the fully viscous problem, but solves only an inviscid problem in parts of the domain. Our new algorithm is based on the factorization of the underlying differential operator, and we therefore call it factorization algorithm. We give a detailed error analysis, and show that we can obtain approximations in the viscous region which are much closer to the viscous solution in the entire domain of simulation than approximations obtained by other heterogeneous domain decomposition algorithms from the literature.

X. Claeys, V. Dolean, M. J. Gander

Multitrace formulations (MTFs) are based on a decomposition of the problem domain into subdomains, and thus domain decomposition solvers are of interest. The fully rigorous mathematical MTF can however be daunting for the non-specialist. We introduce in this paper MTFs on a simple model problem using concepts familiar to researchers in domain decomposition. This allows us to get a new understanding of MTFs and a natural block Jacobi iteration, for which we determine optimal relaxation parameters. We then show how iterative multitrace formulation solvers are related to a well known domain decomposition method called optimal Schwarz method: a method which used Dirichlet to Neumann maps in the transmission condition. We finally show that the insight gained from the simple model problem leads to remarkable identities for Calderon projectors and related operators, and the convergence results and optimal choice of the relaxation parameter we obtained is independent of the geometry, the space dimension of the problem{\color{black}, and the precise form of the spatial elliptic operator, like for optimal Schwarz methods. We illustrate our analysis with numerical experiments.

Martin J. Gander, Martin Neumüller

We present and analyze for a scalar linear evolution model problem a time multigrid algorithm for DG-discretizations in time. We derive asymptotically optimized parameters for the smoother, and also an asymptotically sharp convergence estimate for the two grid cycle. Our results hold for any A-stable time stepping scheme and represent the core component for space-time multigrid methods for parabolic partial differential equations. Our time multigrid method has excellent strong and weak scaling properties for parallelization in time, which we show with numerical experiments.

Martin J. Gander, Mario Ohlberger, Stephan Rave

We consider a new class of Parareal algorithms, which use ideas from localized reduced basis methods to construct the coarse solver from truncated SVD approximations of the transfer operators mapping initial values for a given time interval to the solution at the end of the interval. By leveraging randomized singular value decompositions, these low-rank approximations are obtained embarrassingly parallel by computing local fine solutions for random initial values. We show a priori and a posteriori error bounds in terms of the computed singular values of the transfer operators. Our numerical experiments demonstrate that our approach can significantly outperform Parareal with single-step coarse solvers. At the same time, it permits to further increase parallelism in Parareal by trading global iterations for a larger number of independent local solves.

Fabrizio Donzelli, Martin J. Gander, Ronald D. Haynes

The magnetotelluric approximation of the Maxwell's equations is used to model the propagation of low frequency electro-magnetic waves in the Earth's subsurface, with the purpose of reconstructing the presence of mineral or oil deposits. We propose a classical Schwarz method for solving this magnetotelluric approximation of the Maxwell equations, and prove its convergence using maximum principle techniques. This is not trivial, since solutions are complex valued, and we need a new result that the magnetotelluric approximations satisfy a maximum modulus principle for our proof. We illustrate our analysis with numerical experiments.

Romain Brunet, Victorita Dolean, Martin J. Gander

We show that applying a classical Schwarz method to the time harmonic Navier equations, which are an important model for linear elasticity, leads in general to a divergent method for low to intermediate frequencies. This is even worse than for Helmholtz and time harmonic Maxwell's equations, where the classical Schwarz method is also not convergent, but low frequencies only stagnate, they do not diverge. We illustrate the divergent modes by numerical examples, and also show that when using the classical Schwarz method as a preconditioner for a Krylov method, convergence difficulties remain.

Martin J. Gander, Hui Zhang, Haiyang Zhou

We consider the Dirichlet problem of the indefinite Helmholtz equation in 1D, $u''+k^2u=f$ in $(0,1)$, $u(0)=g_0$, $u(1)=g_1$, with a constant wavenumber $k\in(0,\infty)\backslashπ\mathbb{N}$ and a source term $f\in H^p_0(0,1)$, $p\ge 4$. We propose an approach based on Fourier analysis to derive wavenumber explicit sharp estimates of absolute and relative errors of \emph{finite difference} methods. Such results have been well known for \emph{finite element} methods (FEM). We use the approach to analyze the classical centered finite difference scheme. For the Fourier interpolants of the discrete solution with homogeneous (or inhomogeneous) Dirichlet conditions, we show rigorously, under the two assumptions $k>20$ and $k(kh)^2/σ_k\le4/(π-2)$ with $σ_k:=\operatorname{dist}(k,π\mathbb{N})$, that the worst case attainable convergence order of the absolute error with $\sum_{p=0}^4k^{-p}\|f^{(p)}\|_{L^2}=O(1)$ (or $|g_i|\asymp k^{-1}$) is $(kh)^2/σ_k^2$ in the $L^2$-norm and $k(kh)^2/σ_k^2$ in the $H^1$-semi-norm, and that of the relative error is $k(kh)^2/σ_k$ in both $L^2$- and $H^1$-semi-norms if $\|u^{(p)}\|_{L^2}/\|u^{(p-2)}\|_{L^2}\asymp k^2$ for $p=2,3$. In particular, the lower bounds of these error estimates are established rigorously in the same orders as the upper bounds, which is the main novelty of this work. We show also that the Fourier analysis approach can be used as a convenient visual tool for evaluating finite difference schemes in presence of source terms, which is beyond the scope of dispersion analysis. The results from the theory and visual analysis are corroborated by numerical experiments.

Romain Brunet, Victorita Dolean, Martin J. Gander

We study for the first time Schwarz domain decomposition methods for the solution of the Navier equations modeling the propagation of elastic waves. These equations in the time harmonic regime are difficult to solve by iterative methods, even more so than the Helmholtz equation. We first prove that the classical Schwarz method is not convergent when applied to the Navier equations, and can thus not be used as an iterative solver, only as a preconditioner for a Krylov method. We then introduce more natural transmission conditions between the subdomains, and show that if the overlap is not too small, this new Schwarz method is convergent. We illustrate our results with numerical experiments, both for situations covered by our technical two subdomain analysis, and situations that go far beyond, including many subdomains, cross points, heterogeneous materials in a transmission problem, and Krylov acceleration. Our numerical results show that the Schwarz method with adapted transmission conditions leads systematically to a better solver for the Navier equations than the classical Schwarz method.

Martin J. Gander, Felix Kwok, Bankim C. Mandal

We present a Waveform Relaxation (WR) version of the Dirichlet-Neumann algorithm, formulated specially for multiple subdomains splitting for general parabolic and hyperbolic problems. This method is based on a non-overlapping spatial domain decomposition, and the iteration involves subdomain solves in space-time with corresponding interface condition, and finally organize an exchange of information between neighboring subdomains. Using a Fourier-Laplace transform argument, for a particular relaxation parameter, we present convergence analysis of the algorithm for the heat and wave equations. We prove superlinear convergence for finite time window in case of the heat equation, and finite step convergence for the wave equation. The convergence behavior however depends on the size of the subdomains and the time window length on which the algorithm is employed. We illustrate the performance of the algorithm with numerical results, and show a comparison with classical and optimized Schwarz WR methods.

Martin J. Gander, Martin Neumüller

We present and analyze a new space-time parallel multigrid method for parabolic equations. The method is based on arbitrarily high order discontinuous Galerkin discretizations in time, and a finite element discretization in space. The key ingredient of the new algorithm is a block Jacobi smoother. We present a detailed convergence analysis when the algorithm is applied to the heat equation, and determine asymptotically optimal smoothing parameters, a precise criterion for semi-coarsening in time or full coarsening, and give an asymptotic two grid contraction factor estimate. We then explain how to implement the new multigrid algorithm in parallel, and show with numerical experiments its excellent strong and weak scalability properties.

Victorita Dolean, Martin Gander, Luca Gerardo-Giorda

Over the last two decades, classical Schwarz methods have been extended to systems of hyperbolic partial differential equations, and it was observed that the classical Schwarz method can be convergent even without overlap in certain cases. This is in strong contrast to the behavior of classical Schwarz methods applied to elliptic problems, for which overlap is essential for convergence. Over the last decade, optimized Schwarz methods have been developed for elliptic partial differential equations. These methods use more effective transmission conditions between subdomains, and are also convergent without overlap for elliptic problems. We show here why the classical Schwarz method applied to the hyperbolic problem converges without overlap for Maxwell's equations. The reason is that the method is equivalent to a simple optimized Schwarz method for an equivalent elliptic problem. Using this link, we show how to develop more efficient Schwarz methods than the classical ones for the Maxwell's equations. We illustrate our findings with numerical results.