Domain Decomposition Methods in Science and Engineering XXII

In this paper we study the performance of h- and p-multigrid algorithms for high order Discontinuous Galerkin discretizations of elliptic problems. We test the performance of the multigrid schemes employing a wide class of smoothers and considering both two- and three-dimensional test cases.

The main goal of this paper is to design, analyze, and test a BDDC (Balancing Domain Decomposition by Constraints, see [12, 23]) preconditioner for Isogeometric Analysis (IGA), based on a novel type of interface averaging, which we will denote by deluxe scaling, with either full or reduced set of primal constraints. IGA is an innovative numerical methodology, introduced in [17] and first analyzed in [1], where the geometry description of the PDE domain is adopted from a Computer Aided Design (CAD) parametrization usually based on Non-Uniform Rational B-Splines (NURBS) and the same NURBS basis functions are also used as the PDEs discrete basis, following an isoparametric paradigm; see the monograph [10]. Recent works on IGA preconditioners have focused on overlapping Schwarz preconditioners [3, 5, 7, 9], multigrid methods [16], and non-overlapping preconditioners [4, 8, 20].

The robust preconditioning of linear systems of algebraic equations arising from discretizations of partial differential equations (PDE) is a fastly developing area of scientific research. In many applications these systems are very large, sparse and therefore it is vital to construct (quasi-)optimal iterative methods that converge independently of problem parameters.

A new nonlinear version of the well-known FETI-DP method (Finite Element Tearing and Interconnecting Dual-Primal) is introduced. In this method, the nonlinear problem is decomposed before linearization. Nonlinear approaches to domain decomposition can be viewed as a strategy to localize computational work for the efficient use with future extreme-scale supercomputers. As opposed to known nonlinear FETI-DP algorithms, in the new method the coarse solver can be replaced by a preconditioner, i.e., the coarse solve can be inexact. It is expected that the new method can show a superior parallel scalability if the number of subdomains is large. If the coarse solver is exact and the method is applied to linear problems then the method is equivalent to the standard FETI-DP method. Numerical results for up to 32,768 cores are presented using cycles of an algebraic multigrid for the coarse problem of the new method.

We generalize substructuring methods to problems for functions v: Ω → M, where Ω is a domain in ℝd $$\mathbb{R}^{d}$$ and M is a Riemannian manifold. Examples for such functions include configurations of liquid crystals, ferromagnets, and deformations of Cosserat materials. We show that a substructuring theory can be developed for such problems. While the theory looks very similar to the linear theory on a formal level, the objects it deals with are much more general. In particular, iterates of the algorithms are elements of nonlinear Sobolev spaces, and test functions are replaced by sections in certain vector bundles. We derive various solution algorithms based on preconditioned Richardson iterations for a nonlinear Steklov–Poincaré formulation. Preconditioners appear as bundle homomorphisms. As a numerical example we compute the deformation of a geometrically exact Cosserat shell with a Neumann–Neumann algorithm.

Mathematical problems involving the coupling of an incompressible viscous flow with an elastic structure appear in a large variety of engineering fields (see, e.g., [14, 17, 19–21]). This problem is considered here within a heterogenous domain decomposition framework, with the aim of using independent well-suited solvers for the fluid and the solid. One of the main difficulties that have to be faced under this approach is that the coupling can be very stiff. In particular, traditional Dirichlet-Neumann explicit coupling methods, which solve for the fluid (Dirichlet) and for the solid (Neumann) only once per time-step, are unconditionally unstable whenever the amount of added-mass effect in the system is large (see, e.g., [5, 12]). Typically this happens when the fluid and solid densities are close and the fluid domain is slender, as in hemodynamical applications. This explains, in part, the tremendous amount of work devoted over the last decade to the development of alternative coupling paradigms (see, e.g., [7] for a review).

There are many physical problems such as multiphase flows and fluid-structure interactions whose solutions are piecewise smooth but may have discontinuity across some curved interfaces. The direct application of standard finite element method may not perform well. In this paper, we study some special finite element methods for this type of problems. For simplicity of exposition, we consider the case that there is only one interface which is smooth. Let $$\varOmega,\varOmega _{1} \subset \mathbb{R}^{2}$$ be two bounded domains with $$\varOmega _{1} \subset \varOmega$$ . We assume that Γ = ∂ Ω₁ is sufficiently smooth, and $$\varGamma \cap \partial \varOmega =\emptyset$$ . To be focused on the influence of Γ, we assume $$\varOmega = (-1,1)^{2}$$ .

We will consider BDDC domain decomposition algorithms for finite element approximations of a variety of elliptic problems. The BDDC (Balancing Domain Decomposition by Constraints) algorithms were introduced by Dohrmann [5], following the introduction of FETI-DP by Farhat et al. [9]. These two families are closely related algorithmically and have a common theory. The design of a BDDC algorithm involves the choice of a set of primal degrees of freedom and the choice of an averaging operator, which restores the continuity of the approximate solution across the interface between the subdomains into which the domain of the given problem has been partitioned. We will also refer to these operators as scalings.

We are interested in PDE based mesh generation. The mesh is computed as the solution of a mesh PDE which is coupled to the physical PDE of interest. In [3] we proposed a stochastic domain decomposition (SDD) method to find adaptive meshes for steady state problems by solving a linear elliptic mesh generator. The SDD approach, as originally formulated in [1], relies on a numerical evaluation of the probabilistic form of the exact solution of the linear elliptic boundary value problem. Monte-Carlo simulations are used to evaluate this probabilistic form only at the sub-domain interfaces. These interface approximations can be computed independently and are then used as Dirichlet boundary conditions for the deterministic sub-domain solves. It is generally not necessary to solve the mesh PDEs with high accuracy. Only a good quality mesh, one that allows an accurate representation of the physical PDE, is required. This lower accuracy requirement makes the proposed SDD method computationally more attractive, reducing the number of Monte-Carlo simulations required.

Some geometric and algebraic aspects of various domain decomposition methods (DDMs) are considered. They are applied to a parallel solution of very large sparse SLAEs resulting from approximation of multi-dimensional mixed boundary value problems on non-structured grids. DDMs are used with parameterized overlapping of subdomains and various types of boundary conditions at the inner boundaries. An algorithm for automatic construction of a balancing domain decomposition for overlapping subdomains is presented. Subdomain SLAEs are solved by a direct or iterative preconditioned method in Krylov subspaces, whereas external iterations are performed by the FGMRES method. An experimental analysis of the algorithms is carried out on a set of model problems.

The electrical activity of the heart is a complex phenomenon strictly related to its physiology, fiber structure and anatomy.

Over the past years, the shifted Laplacian has been advocated as a way of making multigrid work for the indefinite Helmholtz equation. The idea is to use a shift into the complex plane of the wave number in the operator, and then to use the shifted operator as a preconditioner for a Krylov method. The hope is that due to the shift, it becomes possible to use standard multigrid to invert the preconditioner, and if the shift is not too big, it is still an effective preconditioner for the Helmholtz equation with a real wave number. There are however two conflicting requirements here: the shift should be not too large for the shifted preconditioner to be a good preconditioner, and it should be large enough for multigrid to work. It was rigorously proved last year that the preconditioner is good if the shift is at most of the size of the wavenumber. We prove here rigorously that if the shift is less than the size of the wavenumber squared, multigrid will not work. It is therefore not possible to solve the shifted Laplace preconditioner with multigrid in the regime where it is a good preconditioner.

Multitrace formulations (MTF) for boundary integral equations (BIE) were developed over the last few years in [1, 2, 4] for the simulation of electromagnetic problems in piecewise constant media, see also [3] for associated boundary integral methods. The MTFs are naturally adapted to the developments of new block preconditioners, as indicated in [5], but very little is known so far about such associated iterative solvers. The goal of our presentation is to give an elementary introduction to MTFs, and also to establish a natural connection with the more classical Dirichlet-Neumann algorithms that are well understood in the domain decomposition literature, see for example [6, 7]. We present for a model problem a convergence analysis for a naturally arising block iterative method associated with the MTF, and also first numerical results to illustrate what performance one can expect from such an iterative solver.

In this paper we consider a boundary value problem for elliptic second order partial differential equations with highly discontinuous coefficients in a 2D polygonal region Ω. The problem is discretized by a (full) DG method on triangular elements using the space of piecewise linear functions. The goal of this paper is to study a special version of FETI-DP preconditioner, called deluxe, for the resulting discrete system of this discretization. The deluxe version for continuous FE discretization is considered in [1], for standard FETI-DP methods for composite DG method, see [4], for full DG, see [4], and for conforming FEM, see the book [5].

Second order elliptic problem with discontinuous coefficient in 2-D is considered. The problem is discretized by a symmetric interior penalty discontinuous Galerkin (DG) finite element method with triangular elements and piecewise linear functions. The resulting discrete problem is solved by a two-level additive Schwarz method. It turns out that the rate of convergence of the method is independent of the jumps of coefficient if its variation inside substructures is bounded. Numerical experiments are reported which confirm theoretical results.

In this paper we present an algebraic multigrid for discontinuous Galerkin methods. Coarser grid levels are created by applying a semi-coarsening approach based on an edge-coloring of the matrix-graph. The grid-transfer uses local basis transformations between the polynomial bases of neighboring elements. Along the coarsening process, the implicit block structure of the linear system is preserved. High frequency errors are reduced by applying an overlapping block smoother. The overlapping patches are constructed and locally weighted depending on the problem type. As model problems serve the Poisson and Stokes equations. The multigrid method is implemented in C++ using the DUNE framework.

Domain Decomposition methods provide a flexible tool for developing Multi-Physics simulations and coupling different discretization methods. In the DUNE framework different strategies to implement Domain Decomposition methods are available. In general, parallel computations with unrelated meshes pose a major computer science challenge. We discuss an efficient algorithm to relate unrelated distributed meshes in a parallel simulation. For distributed meshes, the necessary coupling information is in general not available locally, which requires the user to use explicit parallel communication. We present an abstraction that hides this non-locality and allows the user to implement his Domain Decomposition strategy in a clear mathematical setting. The mathematical concept admits an easy implementation of a wide range of Domain Decomposition methods, without the necessity to directly deal with the aspects of parallel computations.

We employ domain decomposition to 2D systems representing concrete-like materials by describing the material across multiple scales with different models and meshes. This enables us to perform failure mechanics using nonlinear material models such as the gradient-enhanced damage (GD) model. Early results of classical FETI show that heterogeneous materials combined with the GD model necessitates new developments in preconditioners for solving the interface problem iteratively. Alternatively, recent advancements in parallel direct solvers and the ubiquity of computer memory enables solving domain decomposition problems through the fully assembled matrix. Speed and memory usage of various solvers will be presented.

Discretized parabolic control problems lead to very large systems of equations, because trajectories must be approximated forward and backward in time. It is therefore of interest to devise parallel solvers for such systems, and a natural idea is to apply Schwarz preconditioners to the large space-time discretized problem. The performance of Schwarz preconditioners for elliptic problems is well understood, but how do such preconditioners perform on discretized parabolic control problems? We present a convergence analysis for a class of Schwarz methods applied to a model parabolic optimal control problem. We show that just applying a classical Schwarz method in time already implies better transmission conditions than the ones usually used in the elliptic case, and we propose an even better variant based on optimized Schwarz theory.

Optimized Schwarz methods (OS) use Robin or higher order transmission conditions instead of the classical Dirichlet ones. An optimal Schwarz method for a general second-order elliptic problem and a decomposition into strips was presented in [13]. Here optimality means that the method converges in a finite number of steps, and this was achieved by replacing in the transmission conditions the higher order operator by the subdomain exterior Dirichlet-to-Neumann (DtN) maps. It is even possible to design an optimal Schwarz method that converges in two steps for an arbitrary decomposition and an arbitrary partial differential equation (PDE), see [6], but such algorithms are not practical, because the operators involved are highly non-local. Substantial research was therefore devoted to approximate these optimal transmission conditions, see for example the early reference [11], or the overview [5] which coined the term “optimized Schwarz method”, and references therein. In particular for the Helmholtz equation, Gander et al. [9] presents optimized second-order approximations of the DtN, Toselli [17] (improperly) and Schädle and Zschiedrich [14] (properly) tried for the first time using perfectly matched layers (PML, see [1]) to approximate the DtN in OS.

For the prediction of flooding at the borders of the major lakes in the Netherlands, a new system is in operational use. At the moment the time horizon of forecasts is 2 days ahead. To enlarge this time horizon, the shallow-water models of the lakes will be applied in combination with short-to-medium weather ensemble forecasts up to 15 days. Therefore, in this paper we study how to run ensembles with these models efficiently on current hardware. For this purpose, we use domain decomposition in the shallow-water models to have a good balance between computational times and (parallel) efficiency.

The principle of sweeping to accelerate the solution of wave propagation problems has recently retained much interest, yet with different approaches (Engquist and Ying, Multiscale Model Simul 9(2):686–710, 2011; Stolk, J Comput Phys 241:240–252, 2013). We recently proposed a preconditioner for the optimized Schwarz algorithm, based on a propagation of information using a double sequence of subproblems solves, or sweeps (Vion et al., A DDM double sweep preconditioner for the Helmholtz equation with matrix probing of the DtN map, Mathematical and Numerical Aspects of Wave Propagation WAVES 2013, June 2013; Vion and Geuzaine, J Comput Phys, 2014, Preprint, submitted). Although this procedure significantly reduces the number of iterations when many subproblems are involved, the sequential nature of the process hinders the scalability of the algorithm on parallel computer architectures. Here we propose a modified version of the algorithm that concurrently runs partial sweeps on smaller groups of domains, which efficiently reduces the preconditioner application time on parallel machines. We show that the algorithm is applicable to both Helmholtz and Maxwell equations.

It has been widely recognized that one of the major challenges in the simulation of flow and transport problems is finding the numerical solution of the pressure equation [2].

It has been shown in [4] that block Jacobi iterates of a discretization obtained from hybridizable discontinuous Galerkin methods (HDG) can be viewed as non-overlapping Schwarz methods with Robin transmission condition. The Robin parameter is exactly the penalty parameter μ of the HDG method. There is a stability constraint on the penalty parameter and the usual choice of μ results in slow convergence of the Schwarz method. In this paper we show how to overcome this problem without changing μ.

We investigate a geometric full multigrid method for solving the large sparse linear systems which arise in isogeometric discretizations of elliptic partial differential equations. We observe that the full multigrid approach performs much better than the V-cycle multigrid method in many cases, in particular in higher dimensions with increased spline degrees. Often, a single cycle of the full multigrid process is sufficient to obtain a quasi-optimal solution in the L₂-norm. A modest increase in the number of smoothing steps suffices to restore optimality in cases where the V-cycle performs badly.

In this paper, we develop a fully implicit finite difference scheme for the lattice Boltzmann equations. A parallel, highly scalable Newton–Krylov–RAS algorithm is presented to solve the large sparse nonlinear system of equations arising at each time step. RAS is a restricted additive Schwarz preconditioner built with a cheaper discretization. The accuracy of the proposed method is carefully studied by comparing with other benchmark solutions. We show numerically that the nonlinearly implicit method is scalable on a supercomputer with more than 10,000 processors.

We present numerical results for a multigrid method employing overlapping Schwarz smoothers in various V-cycle configurations. The method is based on finite element discretizations of the Stokes problem employing Hdiv-conforming velocity spaces and matching pressure spaces. The method acts on the combined velocity and pressure spaces and thus does not need a Schur complement approximation.

A Newton-Krylov-FETI-DP method for solving problems in elastoplasticity is considered. In some cases additional coarse constraints are necessary to guarantee good convergence of the pcg algorithm. To enhance the coarse space in the FETI-DP method, we use a strategy introduced in Mandel and Sousedík (Comput. Methods Appl. Mech. Eng. 196, 1389–1399, 2007). We implement this method using a deflation approach.

We describe a BDDC algorithm, see e.g., [1], and an adaptive coarse space enforced by a transformation of basis for the iterative solution of scalar diffusion problems with a discontinuous diffusion coefficient. The coefficient varies over several orders of magnitude both inside of the subdomains and along the interface. A related algorithm for FETI-DP with a balancing preconditioner has been already described in [6, 7]. Other adaptive coarse space constructions for FETI, FETI-DP, and BDDC methods have been proposed in [8, 10]. We also present some preliminary numerical results for different scalings, including the recent deluxe scaling; cf., [2].

In this paper we present a novel technique based on domain decomposition which enables us to perform the fast marching method (FMM) [4] on massive parallel high performance computers (HPC) for given triangulated geometries. The FMM is a widely used numerical method and one of the fastest serial state-of-the-art techniques for computing the solution to the Eikonal equation.

The Isogeometric Analysis (IGA), that was introduced by Hughes et al. [9] and has since been developed intensively, see also monograph [4], is a very suitable framework for representing and discretizing Partial Differential Equations (PDEs) on surfaces. We refer the reader to the survey paper by Dziuk and Elliot [7] where different finite element approaches to the numerical solution of PDEs on surfaces are discussed. Very recently, Dedner et al. [6] have used and analyzed the Discontinuous Galerkin (DG) finite element method for solving elliptic problems on surfaces. The IGA of second-order PDEs on surfaces has been introduced and numerically studied by Dede and Quarteroni [5] for the single-patch case. Brunero [3] presented some discretization error analysis of the DG-IGA applied to plane (2d) diffusion problems that carries over to plane linear elasticity problems which have recently been studied numerically in [1]. Evans and Hughes [8] used the DG technology in order to handle no-slip boundary conditions and multi-patch geometries for IGA of Darcy-Stokes-Brinkman equations. The efficient generation of the IGA equations, their fast solution, and the implementation of adaptive IGA schemes are currently hot research topics. The use of DG technologies will certainly facilitate the handling of the multi-patch case.

A FETI-DP algorithm is proposed for solving the system of linear equations arising from the mixed finite element approximations of a three dimensional saddle problem. A preconditioned conjugate gradient method is used in the algorithm with either a lumped or a Dirichlet preconditioner, and scalable convergence rates are proved without a divergence free condition for the coarse space. Numerical experiments of solving a three-dimensional incompressible Stokes problem demonstrate the performance of the proposed algorithm.

In this paper, we analyze the approximation error of an explicit Fuzzy Domain Decomposition Method (eFDDM) (Gander and Michaud, Fuzzy domain decomposition: a new perspective on heterogeneous DD methods, in Domain Decomposition Methods in Science and Engineering XXI, ed. by J. Erhel, M.J. Gander, L. Halpern, G. Pichot, T. Sassi, O.B. Widlund. Lecture Notes in Computational Science and Engineering. Springer, Berlin, 2013) using matched asymptotic expansions (Cousteix and Mauss, Asymptotic Analysis and Boundary Layers, Springer, Berlin, 2007). We show that the global convergence of the method for an advection dominated diffusion problem is of order $$\mathcal{O}(\nu )$$ and have numerical evidence that the method is of order $$\mathcal{O}(\nu ^{3/2})$$ in the boundary layer. Our results generalize the results of Gander and Martin (An asymptotic approach to compare coupling mechanisms for different partial differential equations, in Domain Decomposition Methods in Science and Engineering XX, ed. by R. Bank, M. Holst, O.B. Widlund, J. Xu. Lecture Notes in Computational Science and Engineering, Springer, Berlin, 2012) to this new method and show that the eFDDM is a viable alternative to other coupling methods.

We consider a second order elliptic boundary value problem in the variational form: find u∗ ∈ H₀1(Ω), for a given polygonal (polyhedral) domain $$\varOmega \subset \mathbb{R}^{d},\,d = 2,3$$ and a source term f ∈ L2(Ω), such that 1 $$\displaystyle{ \underbrace{\mathop{\int _{\varOmega }\nabla u^{{\ast}}(x) \cdot \nabla v(x)\,dx}}\limits _{\equiv a(u^{{\ast}},v)} =\underbrace{\mathop{ \int _{\varOmega }f(x)v(x)\,dx}}\limits _{\equiv (f,v)},\quad \text{for all }v \in H_{0}^{1}(\varOmega ). }$$ The Bank–Holst parallel adaptive meshing paradigm [1–3] is utilised to solve (1) in a combination of domain decomposition and adaptivity.

The purpose of this paper is to introduce a BDDC method for vector field problems discretized with the lowest order Raviart-Thomas finite elements. Our method is based on a new type of weighted average, a deluxe scaling, developed to deal with more than one variable coefficient. Numerical experiments show that the deluxe scaling is robust and more powerful than traditional methods.

To leverage the computational capability of modern supercomputers, existing algorithms need to be reformulated in a manner that allows for many concurrent operations. In this paper, we outline a framework that reformulates classical Schwarz waveform relaxation so that successive waveform iterates can be computed in a parallel pipeline fashion after an initial start-up cost. The communication costs for various implementations are discussed, and numerical scaling results are presented.

The very rapidly increasing number of cores in state-of-the-art supercomputers fuels both the need for and the interest in novel numerical algorithms inherently designed to feature concurrency. In addition to the mature field of space-parallel approaches (e.g. domain decomposition techniques), time-parallel methods that allow concurrency along the temporal dimension are now an increasingly active field of research, although first ideas, like in [12], go back several decades. A prominent and widely studied algorithm in this area is Parareal, introduced in [10], which has the advantage that one can couple and reuse classical time-stepping schemes in an iterative fashion to parallelize in time. However, there also exist a number of other approaches, e.g. the “parallel implicit time algorithm” (PITA) from [5], the “parallel full approximation scheme in space and time” (PFASST) from [4] or “revisionist integral deferred corrections” (RIDC) from [3] to name a few. Parareal in particular and temporal parallelism in general has been considered early as an addition to spatial parallelism in order to extend strong scaling limits, see [11]. Efficacy of this approach in large-scale parallel simulations on hundreds of thousands of cores has been demonstrated for the PFASST algorithm in [14].

In this paper, we introduce a new coarse space algorithm, the “Discontinuous Coarse Space Robin Jump Minimizer” (DCS-RJMin), to be used in conjunction with one-level domain decomposition methods (DDMs). This new algorithm makes use of Discontinuous Coarse Spaces (DCS), and is designed for DDM that naturally produce discontinuous iterates such as Optimized Schwarzs Methods (OSM). This algorithm is suitable both at the continuous level and for cell-centered finite volume discretizations. At the continuous level, we prove, under some conditions on the parameters of the algorithm, that the difference between two consecutive iterates goes to 0. We also provide numerical results illustrating the convergence behavior of the DCS-RJMin algorithm.

Implicit integration methods based on collocation are attractive for a number of reasons, e.g. their ideal (for Gauss-Legendre nodes) or near ideal (Gauss-Radau or Gauss-Lobatto nodes) order and stability properties. However, straightforward application of a collocation formula with M nodes to an initial value problem with dimension d requires the solution of one large Md × Md system of nonlinear equations.

The intrusive polynomial chaos approach for uncertainty quantification in numerous engineering problems constitutes a computationally challenging task. Indeed, Galerkin projection in the spectral stochastic finite element method (SSFEM) leads to a large-scale linear system for the polynomial chaos coefficients of the solution process. The development of robust and efficient solution strategies for the resulting linear system therefore is of paramount importance for the applicability of the SSFEM to practical engineering problems. The solution algorithms should be parallel and scalable in order to exploit the available multiprocessor supercomputers. Therefore, we formulate a two-level Schwarz preconditioner for the polynomial chaos based uncertainty quantification of large-scale computational models.

A modeling system is presented for prediction of multiscale and multiphysics coastal ocean processes, and a numerical experiment is made to evaluate its performance. The system is a hybrid of a fully three dimensional fluid dynamics (F3DFD) model and a geophysical fluid dynamics (GFD) model. In particular, it integrates the Solver for Incompressible Flow on Overset Meshes (SIFOM) and the Finite Volume Coastal Ocean Model (FVCOM) using a domain decomposition method implemented with Chimera grids. In the hybrid SIFOM–FVCOM system, SIFOM is employed to capture small-scale local phenomena, and FVCOM is used to simulate large-scale background coastal flows. Simulation of a transient sill flow demonstrates that, while its performance is promising, the hybrid SIFOM–FVCOM system encounters difficulties in correctly resolving the flow at current front where there is strong unsteadiness and thus it needs further improvement.

In this paper, we develop an overlapping domain decomposition (DD) based Jacobi-Davidson (JD) algorithm for a polynomial eigenvalue problem arising from quantum dot simulation. Both DD and JD have several adjustable components. The goal of the work is to figure out if it is possible to choose the right components of DD and JD such that the resulting approach has a near linear speedup for a fine mesh calculation. Through experiments, we find that the key is to use two different coarse meshes. One is used to obtain a good initial guess that helps to achieve quadratic convergence of the nonlinear JD iterations. The other guarantees scalable convergence of the linear solver of the correction equation. We report numerical experiments carried out on a supercomputer with over 10,000 processors.

In [1], one- and two-level Schwarz methods have been proposed for variational inequalities with contraction operators. This type of inequalities generalizes the problems modeled by quasi-linear or semilinear inequalities. It is proved there that the convergence rates of the two-level methods are almost independent of the mesh and overlapping parameters. However, the original convex set, which is defined on the fine grid, is used to find the corrections on the coarse grid, too. This leads to a suboptimal computing complexity. A remedy can be found in adopting minimization techniques from the construction of multigrid methods for the constrained minimization of functionals. In this case, to avoid visiting the fine grid, some level convex sets for the corrections on the coarse levels have been proposed in [4, 7–10] and the review article [6] for complementarity problems, and in [2] for two two-obstacle problems. In this paper, we introduce and investigate the convergence of a new multigrid algorithm for the inequalities with contraction operators, and we have adopted the construction of the level convex sets which has been introduced in [2]. In this way, the introduced multigrid method has an optimal computing complexity of the iterations. Also, the convergence theorems for the methods introduced in [1] contain a convergence condition depending on the total number of the subdomains in the decompositions of the domain. The convergence condition of a direct extension of these methods to more than two-levels will introduce an upper bound for the number of mesh levels which can be used in the method. In comparison with these methods, the convergence condition of the algorithm introduced in this paper is less restrictive and depends neither on the number of the subdomains in the decompositions of the domain nor on the number of levels. Moreover, this convergence condition is very similar with the condition of existence and uniqueness of the solution of the problem.

The solution of differential equations with implicit methods requires the solution of a nonlinear problem at each time step. We consider Newton-Krylov ([8], Chap. 3) methods to solve these nonlinear problems: the linearized system of each Newton iteration of each time step is solved by a Krylov method. Generally speaking, the most time-consuming part of the numerical simulation is the solution of the sequence of linear systems by the Krylov method. Then, providing a good preconditioner is a critical point: a balance must be found between the ability of the preconditioner to reduce the number of Krylov iterations, and its computational cost. The method that combines a Newton-Krylov method with a Schwarz domain decomposition preconditioner is called Newton-Krylov-Schwarz (NKS) [5]. In this paper, we deal with the Restricted Additive Schwarz (RAS) preconditioner [4]. We propose to freeze this preconditioner for a few time steps, and to partially update it. Here, the partial update of the preconditioner consists in recomputing some parts of the preconditioner associated to certain subdomains, keeping the other ones frozen. These partial updates improve the efficiency and the longevity of the frozen preconditioner. Furthermore, they can be computed asynchronously in order to improve the parallelism.

In this paper, we are interested in impenetrable surfaces with relatively large size on which a heterogeneous object of relatively small size is posed. In this case, a straightforward FEM-BEM (finite and boundary element methods) coupling leads to a linear system of very large scale difficult to solve [7]. In this work, we propose an alternative method derived from a modification of the adaptive radiation condition approach [1, 11, 12]. This technique consists of enclosing the computational domain by an artificial truncating surface on which the adaptive radiation condition is posed. This condition is expressed using integral operators acting as a correction term of the absorbing boundary condition. However, enclosing completely the computational domain by an artificial surface in this range leads to problems with very large size, and results in very slow convergence of the iterative procedure. We propose to localize this surface only around the heterogenous region, which will generates a relatively small bounded domain dealt with by a FEM, and suitably coupled with a BEM expressing the solution on the impenetrable surface. The resulting formulation, based on a particular overlapping domain decomposition method, is solved iteratively where FEM and BEM linear systems are solved separately. The wave problem considered in this paper is stated as follows 1 $$\displaystyle{ \left \{\begin{array}{l} \nabla \cdot (\chi \nabla u) +\chi \kappa ^{2}n^{2}u = 0\quad \text{in}\ \varOmega, \\ \chi \partial _{\mathbf{n}}u = -f\text{ on }\varGamma, \\ \lim _{\vert x\vert \rightarrow \infty }\vert x\vert ^{1/2}(\partial _{\vert x\vert }u - i\kappa u) = 0,\end{array} \right. }$$ where Ω is the complement of the impenetrable obstacle. We indicate by Ω₁ a bounded domain filled by a possibly heterogeneous material and posed on a slot Γ _slot on which are applied the sources producing the radiated wave u. The interface $$\varSigma$$ separates Ω₁ from the free propagation domain Ω₀, n denotes the normal to Γ or to $$\varSigma$$ directed outwards respectively the impenetrable obstacle enclosed by Γ or the domain Ω₁ (see Fig. 1), χ and n indicate, respectively, the relative dielectric permittivity and the relative magnetic permeability, and κ is the wave number. Let us note finally that $$\chi = n = 1$$ in Ω₀. For the sake of presentation, we express problem (1) in the form of the following system 2 $$\displaystyle{ \left \{\begin{array}{l} \varDelta u_{0} +\kappa ^{2}u_{0} = 0\;\text{in}\ \varOmega _{0}, \\ \partial _{\mathbf{n}}u_{0} = 0\;\text{on }\varGamma \cap \partial \varOmega _{0}, \\ \lim _{\vert x\vert \rightarrow \infty }\vert x\vert ^{1/2}(\partial _{\vert x\vert }u_{0} - i\kappa u_{0}) = 0, \end{array} \right. }$$ 3 $$\displaystyle{ \left \{\begin{array}{l} \nabla \cdot (\chi \nabla u_{1}) +\chi \kappa ^{2}n^{2}u_{1} = 0\;\text{in}\ \varOmega _{1}, \\ \chi \partial _{\mathbf{n}}u_{1} = -f\text{ on }\varGamma \cap \partial \varOmega _{1}.\end{array} \right. }$$ These boundary-value problems are coupled on $$\varSigma$$ through the transmission conditions 4 $$\displaystyle{ u_{0} = u_{1},\quad \partial _{\mathbf{n}}u_{0} =\chi \partial _{\mathbf{n}}u_{1}. }$$

Wind power is an increasingly popular renewable energy. In the design process of the wind turbine blade, the accurate aerodynamic simulation is important. In the past, most of the wind turbine simulations were carried out with some low fidelity methods, such as the blade element momentum method [9]. Recently, with the rapid development of the supercomputers, high fidelity simulations based on 3D unsteady Navier-Stokes (N-S) equations become more popular. For example, Sorensen et al. studied the 3D wind turbine rotor using the Reynolds-Averaged Navier-Stokes (RANS) framework where a finite volume method and a semi-implicit method are used for the spatial and temporal discretization, respectively [17]. Bazilevs et al. investigated the aerodynamic of the NREL 5 MW offshore baseline wind turbine rotor using large eddy simulation built with a deforming-spatial-domain/stabilized space-time formulation [3, 11] and later extended the simulation to the full wind turbine including both the rotor and the tower [10]. Li et al. conducted dynamic overset CFD simulations for the NREL phase VI wind turbine using RANS and detached eddy models [15].

A space-time domain decomposition algorithm for the compressible Navier–Stokes problem has been designed, with the aim of implementing it in three dimensions, in an industrial code. The system is discretised with a second order implicit scheme in time and Finite Volumes Method in space. To achieve full speedup performance, a Schwarz Waveform Relaxation method coupled with a Newton procedure is used, as it allows local space and time stepping. The performances of different parallelisation strategies (using OpenMP, MPI and GPUs) are compared in difficult configurations.

We study non-overlapping Schwarz Methods for solving second order time-harmonic 3D Maxwell equations in heterogeneous media. Choosing the interfaces between the subdomains to be aligned with the discontinuities in the coefficients, we show for a model problem that while the classical Schwarz method is not convergent, optimized transmission conditions dependent on the discontinuities of the coefficients lead to convergent methods. We prove asymptotically that the resulting methods converge in certain cases independently of the mesh parameter, and convergence can even become better as the coefficient jumps increase.

Over the last 5 years, classical and optimized Schwarz methods with Robin transmission conditions have been developed for anisotropic elliptic problems discretized by Discrete Duality Finite Volume (DDFV) schemes. We present here the case of higher order transmission conditions in the framework of DDFV. We prove convergence of the algorithm for a large class of symmetric transmission operators, including the discrete Ventcell operator. We also illustrate numerically that using optimized Ventcell transmission conditions leads to much faster algorithms than when using Robin transmission conditions, especially in case of anisotropic elliptic operators.

With the advent of very large scale parallel computer, having millions of processing cores, it has become important to also use the time direction for parallelization. Among the successful methods doing this are the parareal algorithm, the paraexp algorithm, PFASST and also waveform relaxation methods of Schwarz or Dirichlet-Neumann or Neumann type. We present here a mathematical analysis of a further method to parallelize in time, proposed by Maday and Ronquist in 2007. It is based on the diagonalization of the time stepping matrix. Like for many time domain parallelization methods, this seems at first not to be a very promising approach, since this matrix is essentially triangular, and for a fixed time step even a Jordan block, and thus not diagonalizable. If one however chooses different time steps, diagonalization is possible, and one has to trade of between the accuracy due to necessarily having different time steps, and numerical errors in the diagonalization process of these almost not diagonalizable matrices. We study this trade-off mathematically and propose an optimization strategy for the choice of the parameters, for a Backward Euler discretization of the heat equation in two dimensions.

We present a Waveform Relaxation (WR) version of the Dirichlet-Neumann and Neumann-Neumann algorithms for the wave equation in space time. Each method is based on a non-overlapping spatial domain decomposition, and the iteration involves subdomain solves in space time with corresponding interface condition, followed by a correction step. Using a Laplace transform argument, for a particular relaxation parameter, we prove convergence of both algorithms in a finite number of steps for finite time intervals. The number of steps depends on the size of the subdomains and the time window length on which the algorithms are employed. We illustrate the performance of the algorithms with numerical results, and also show a comparison with classical and optimized Schwarz WR methods.

We consider Bayesian inversion of parametric operator equations for the case of a large number of measurements. Increased computational efficiency over standard averaging approaches, per measurement, is obtained by binning the data and applying a multilevel Monte Carlo method, specifying optimal forward solution tolerances per level. Based on recent bounds of convergence rates of adaptive Smolyak quadratures in Bayesian inversion for single observation data, the bin sizes in large sets of measured data are optimized and a rate of convergence of the error vs. work is derived analytically and confirmed by numerical experiments.

The Optimized Schwarz Method (OSM) is a domain decomposition method based on the introduction of generalized Robin interface conditions obtained by linearly combining the two physical interface conditions through the introduction of suitable symbols, and then on the optimization of such symbols within a proper subset, see [10, 13]. This method has been considered so far for many problems in the case of flat interfaces, see, e.g., [3, 5–7, 11, 16, 17]. Recently, OSM has been considered and analyzed for the case of cylindrical interfaces in [8, 9], and for the case of circular interfaces in [2]. In particular, in [8] we developed a general convergence analysis of the Schwarz method for elliptic problems and an optimization procedure within the constants, with application to the fluid-structure interaction (FSI) problem.

The Optimized Schwarz method has been introduced and analyzed over the last decade, where the convergence speed of the Jacobi iteration is significantly enhanced by using general transmission conditions on the interfaces together with optimized parameters. In particular, Ventcell transmission conditions (see [3–6, 8–10]) have been studied for the primal formulation with different numerical schemes showing that the convergence of the Optimized Schwarz algorithm with Ventcell conditions is improved over that with Robin conditions. Ventcell conditions are second order differential conditions, see [12].

In many practical applications in fluid dynamics, a very large range of scales spanning many orders of magnitude are simultaneously present; one possibility to perform an economical and accurate approximation of the solution is to use different discretizations in different regions of the computational domain to match with the physical scales. The mortar element method introduced in [3] allows such a use of different discretizations in an optimal way in the sense that the error is bounded by the sum of the subregion-by-subregion approximation errors without constraint on the choice of the different discretizations. An extension to fluids is given in [1]. An alternative and simpler method, the New Interface Cement Equilibrated Mortar (NICEM) method proposed in [6] and analyzed in [8] for an elliptic problem, allows to optimally match Robin conditions on non-conforming grids. An extension to Ventcel conditions is given in [9]. The main feature of this approach is that, on each side of the interface, the jump of the Robin or Ventcel condition should be L2-orthogonal to a well chosen finite element space on the interface (in that case there is no master and slave sides, which makes the method simpler). Thus, it allows to combine different approximations in different subdomains in the framework of optimized Schwarz algorithms which are based on optimized Robin or Ventcel transmission conditions and lead to robust and fast algorithms (see [5, 7]).

Domain decomposition methods are subject to a greater interest, due to obvious implication for parallel computing. Non-overlapping methods are particularly well suited for coupled problems through an interface as bonded structures (e.g. [4]) air/water flows (e.g. [2]), two-body contact problems (e.g. [6, 9]), etc. For these coupled problems, the domain decomposition methods applied in a natural way, since the sub-domains are already defined.

The finite element discretization of partial differential equations (PDEs) requires the selection of suitable finite element spaces. While high-order finite elements often lead to solutions of higher accuracy, their associated discrete linear systems of equations are often more difficult to solve (and to set up) compared to those of lower order elements.

A non-overlapping domain decomposition method based on augmented Lagrangian with a penalty term was introduced in the previous works by the authors [6, 7], which is a variant of the FETI-DP method. In this paper we present a further study focusing on the case of small penalty parameters in terms of condition number estimate and practical efficiency. The full analysis of the proposed method can be found in [8].

We developed parallel time domain decomposition methods to solve systems of linear ordinary differential equations (ODEs) based on the Aitken-Schwarz [5] or primal Schur complement domain decomposition methods [4]. The methods require the transformation of the initial value problem in time defined on ]0, T] into a time boundary values problem. Let f(t, y(t)) be a function belonging to $$\mathcal{C}^{1}(\mathbb{R}^{+}, \mathbb{R}^{d})$$ and consider the Cauchy problem for the first order ODE: 1 $$\displaystyle{ \left \{\begin{array}{@{}l@{\quad }l@{}} \dot{y} = f(t,y(t)),\,t \in ]0,T],\;y(0) =\alpha \in \mathbb{R}^{d}.\quad \end{array} \right. }$$

In this paper we introduce an additive Schwarz method for a Crouzeix-Raviart Finite Volume Element (CRFVE) discretization of a second order elliptic problem with discontinuous coefficients, where the discontinuities are inside subdomains and across subdomain boundaries. The proposed methods depends linearly or quadratically on the mesh parameters H∕h, i.e., depending on the distribution of the coefficient in the model problem, the parameters describing the convergence of the GMRES method used to solve the preconditioned system depends linearly or quadratically on the mesh parameters. Also, under certain restrictions on the distribution of the coefficient, the convergence of the GMRES method is independent of jumps in the coefficient.

In this paper, we present two variants of the Additive Schwarz Method (ASM) for a Crouzeix-Raviart finite volume (CRFV) discretization of the second order elliptic problem with discontinuous coefficients, where the discontinuities are only across subdomain boundaries. The resulting system, which is nonsymmetric, is solved using the preconditioned GMRES iteration, where in one variant of the ASM the preconditioner is symmetric while in the other variant it is nonsymmetric. The proposed methods are almost optimal, in the sense that the convergence of the GMRES iteration, in the both cases, depend only poly-logarithmically on the mesh parameters.

It is of interest to solve large scale sparse linear systems on distributed computers, using Krylov subspace methods along with domain decomposition methods. If accurate subdomain solutions are used, the restricted additive Schwarz preconditioner allows a reduction to the interface via the Schur complement, which leads to an unpreconditioned reduced operator for the interface unknowns. Our purpose is to form a preconditioner for this interface operator by approximating it as a low-rank correction of the identity matrix. To this end, we use a sequence of orthogonal vectors and their image under the interface operator, which are both available after some iterations of the generalized minimal residual method.

A comparison study of different decoupled schemes for the evolutionary Stokes/Darcy problem is carried out. Stability and error estimates of a mass conservative multiple-time-step algorithm are provided under a time step restriction which depends on the physical parameters of the flow system and the ratio between the time steps applied in the free flow and porous medium domains. Numerical results are presented and the advantage of multirate time integration is demonstrated.

In this paper, we introduce the results for the Schwarz waveform relaxation (SWR) algorithm applied to a class of non-dissipative reaction diffusion equations. Both the Dirichlet and Robin transmission conditions (TCs) are considered. For the Dirichlet TC, we consider the algorithm for the nonlinear problem $$\partial _{t}u =\mu \partial _{xx}u + f(u)$$ , in the case of many subdomains.

Domain decomposition (DD) methods are important techniques for designing parallel algorithms for solving partial differential equations. Since the decomposition is often performed using automatic mesh partitioning tools, one can in general not make any assumptions on the shape or physical size of the subdomains, especially if local mesh refinement is used. In many of the popular domain decomposition methods, neighboring subdomains are not using the same type of boundary conditions, e.g. the Dirichlet-Neumann methods invented by Bjørstad and Widlund [2], or the two-sided optimized Schwarz methods proposed in [3], and one has to decide which subdomain uses which boundary condition. A similar question also arises in mortar methods, see [1], where one has to decide on the master and slave side at the interfaces. In [4], it was found that for optimized Schwarz methods, the subdomain geometry and problem boundary conditions influence the optimized Robin parameters for symmetrical finite domain decompositions, and in [5], it was observed numerically that swapping the optimized two-sided Robin parameters can accelerate the convergence for a circular domain decomposition.

The mostly used mathematical formulation of the inverse problem in electrocardiography is based on a least method using a transfer matrix that maps the electrical potential on the heart to the body surface potential (BSP). This mathematical model is ill based and a lot of works have been concentrating on the regularization term without thinking of reformulating the problem itself. We propose in this study to solve the inverse problem based on a domain decomposition technique on a fictitious mirror-like boundary conditions. We conduct BSP simulations to produce synthetic data and use it to evaluate the accuracy of the inverse problem solution.