Domain Decomposition Methods in Science and Engineering XXV

The classical alternating Schwarz method does not need a partition of unity in its definition [3]: one solves one subdomain after the other, stores subdomain solutions, and always uses the newest data available from the neighboring subdomains. In the parallel Schwarz method introduced by Lions in [10], where all subdomains are solved simultaneously, one also stores subdomain solutions, but one has to distinguish two cases: if in the decomposition there are never more than two subdomains that intersect, which we call the no crosspoint assumption, then one also does not need a partition of unity to define the method, one simply takes data from the neighboring subdomains with which the subdomain intersects, and in that case the parallel Schwarz method has a variational interpretation [10].

FETI-DP (dual-primal finite element tearing and interconnecting) and BDDC (balancing domain decomposition by constraints) are among the leading non-overlapping domain decomposition preconditioners.

Elliptic boundary value problems with oscillatory coefficients play a key role in the mathematical modelling and simulation of complex multiscale problems, for instance transport processes in porous media or the mechanical analysis of composite and multifunctional materials.

Recently, methods that do not rely on the regularity of the solution were introduced: generalized finite element methods [1], the rough polyharmonic splines [22], the variational multiscale method (VMS) [13], and the Localized Orthogonal Decomposition (LOD) [16, 10].

Over the last decade, substantial research efforts have gone into developing preconditioners for time harmonic wave propagation problems, like the Helmholtz and the time harmonic Maxwell’s equations. Such equations are much harder to solve than diffusive problems like Laplace’s equation, because of two main reasons: first, the pollution effect [1] requires much finer meshes than would be necessary just to resolve the signal computed, and second, classical iterative methods all exhibit severe convergence problems when trying to solve the very large discrete linear systems obtained [9].

Let Ω $$ \subset \mathbb{R}^{2} $$ be a polygonal domain with an immersed simple closed smooth interface $$ \Gamma \in C^{2} $$ , such that $$ \overline{\Omega}=\overline{\Omega}^{-}\cup\overline{\Omega}^{+} $$ , and Γ := $$ \overline{\Omega}^{-}\cap\overline{\Omega}^{+} $$ is far away from ∂Ω (i.e, either Ω+ or Ω- is a floating subdomain; i.e., one of them does not touch ∂Ω).

On the other hand, Virtual Element Methods (VEM) [1, 12, 13] allow to handle general polygonal elements. In the case of triangular elements, VEM reduces to the usual FEM. Thus, VEM is a natural choice for constructing space of functions on irregular subdomains.

Neumann-Neumann methods (NNMs) are among the best parallel solvers for discretized partial differential equations, see [12] and references therein. Their common polylogarithmic condition number estimate shows their effectiveness for many discretized elliptic problems, see [9, 10, 5].

“Vous n’avez vraiment rien à faire”!1 This was the smiling reaction of Laurence Halpern when the first author told her about our wish to accurately estimate the convergence rate of the Schwarz method for the solution of the ddm logo2, see Figure 1 (left).

The minimization problem (2) is discretized in [4] by a partition of unity method (PUM). The goal of this paper is to use the ideas in [5] for an obstacle problem of clamped Kirchhoff plates to develop preconditioners for the discrete problems in [4].

In this note we describe a parallel solver for the discretized weakly singular spacetime boundary integral equation of the spatially two-dimensional heat equation. The global space-time nature of the system matrices leads to improved parallel scalability in distributed memory systems in contrast to time-stepping methods where the parallelization is usually limited to spatial dimensions.

In this study, we present Balancing Domain Decomposition by Constraints (BDDC) preconditioners for three-dimensional scalar elliptic and linear elasticity problems in which the direct solution of the coarse problem is replaced by a preconditioner based on a smaller vertex-based coarse space.

Numerical simulation of wave phenomena is routinely used in seismic studies, where simulated wave signals are compared against experimental ones to infer subterranean information. Various wave systems can be used to model wave propagation in earth media. Here, we consider the system of isotropic elastic wave equations described in Section 2.

Multilevel methods such as multigrid and domain decomposition are among the most efficient and scalable solvers developed to date. Adapting them to the next generation of supercomputers and improving their performance and scalability is crucial for exascale computing and beyond.

There has been substantial attention on coarse correction in the domain decomposition community over the last decade, sparked by the interest of solving high contrast and multiscale problems, since in this case, the convergence of two-level domain decomposition methods is deteriorating when the contrast becomes large, see [1, 10, 16, 17, 11, 9, 8] and references therein.

An algorithm is said to beweakly scalable if it can solve progressively larger problems with an increasing number of processors in a fixed amount of time. According to classical Schwarz theory, the parallel Schwarz method (PSM) is not scalable (see, e.g., [2, 7]).

Overlapping Schwarz waveform relaxation (SWR) provides space–time parallelism by iteratively solving partial differential equations (PDEs) over a time window on overlapping spatial subdomains. SWR has been studied for many problems at the continuous and discrete levels.

For second order elliptic partial differential equations, such as diffusion or elasticity, with arbitrary and high coefficient jumps, the convergence rate of domain decomposition methods with classical coarse spaces typically deteriorates. One remedy is the use of adaptive coarse spaces, which use eigenfunctions computed from local generalized eigenvalue problems to enrich the standard coarse space; see, e.g., [19, 6, 5, 4, 22, 23, 3, 16, 17, 14, 7, 8, 24, 1, 20, 2, 13, 21, 10, 9, 11]. This typically results in a condition number estimate of the form

This article describes a parallel implementation of a two-level overlapping Schwarz preconditioner with the GDSW (Generalized Dryja–Smith–Widlund) coarse space described in previous work [12, 10, 15] into the Trilinos framework; cf. [16]. The software is a significant improvement of a previous implementation [12]; see Sec. 4 for results on the improved performance.

The GDSW (Generalized Dryja–Smith–Widlund) preconditioner is a two-level overlapping Schwarz domain decomposition preconditioner [23] with exact local solvers [5, 4].

In error form, the alternating Schwarz method for the solution to (1) is

We study a simplified model for two–phase flow in porous media, where the medium is made of two (or more) different rock types. Each rock type is a subdomain with a distinct capillary pressure function so that the saturation becomes discontinuous across the interface between the different regions. This leads to the phenomenon of capillary trapping (see [12] or [4]).

In this paper, a two-level overlapping Schwarz algorithm is proposed for solving finite element discretization of the following model problem

The convergence rate of classical domain decomposition methods for diffusion or elasticity problems usually deteriorates when large coefficient jumps occur along or across the interface between subdomains. In fact, the constant in the classical condition number bounds [11, 12] will depend on the coefficient jump.

The problem is discretized by an h-p symmetric interior higher-order [4] discontinuous Galerkin finite element method. In a k-th order multipenalty method, one penalizes the jumps of scaled normal higher-order derivatives up to order across the interelement boundaries—so the standard interior penalty method corresponds to taking k = 0.

In order to obtain a scalable domain decomposition method (DDM) for elliptic problems, a coarse space is necessary and an associated coarse problem has to be solved in each iteration. In the presence of arbitrary, large coefficient jumps or in case of almost incompressible elastic materials, the convergence rate of standard DDM deteriorates.

Time-periodic problems appear naturally in engineering applications. For instance,the time-periodic steady-state behavior of an electromagnetic device is often the main interest in electrical engineering, because devices are operated most of their life-time in this state.

Among many applications of parallel computing, solving large systems of ordinary differential equations (ODEs) which arise from large scale electronic circuits, or discretizations of partial differential equations (PDEs), form an important part.

This type of equation often arises from the implicit discretization of a time-dependent problem or from a steady state calculation, for example the Forchheimer equation [5] in porous media flow.

To solve (1), we consider nonlinear domain decomposition methods of the Schwarz type, e.g., ASPIN (Additive Schwarz Preconditioned Inexact Newton) [1, 10] or RASPEN (Restricted Additive Schwarz Preconditioned Exact Newton) [3].

Time parallel time integration has received substained attention over the last decades, for a review, see [2]. More recently, renewed interest in this area was sparked by the invention of the Parareal algorithm [5] for solving initial value problems like

In 2001 Randolph E. Bank and Peter K. Jimack [1] introduced a new domain decomposition method for the adaptive solution of elliptic partial differential equations, see also [2].

In many real physical phenomena, there is heterogeneity, e.g., in some ground flow problems in heterogeneous media.When some finite element discretization method is applied to a physical model, one usually obtains a discrete problem which is very hard to solve by a preconditioned iterative method like, e.g., Preconditioned Conjugate Gradient (PCG) method.

In the context of Numerical Weather Prediction (NWP) and more precisely in the context of regional weather prediction models, the spatial domains considered usually are non-convex, because of the orography representing mountain ranges.

The relaxed Jacobi algorithm written at the continuous level was proven to converge exponentially. However, it was only a conjecture, hinted at by numerical experiments in [5, Section 8], that the discretized algorithm using finite elements has a rate of convergence uniformly bounded with respect to the discretization parameter

Linear Elasticity models how elastic solids deform in the presence of surface and volume forces. The model of Linear Elasticity is valid for small deformations. For large deformations, the nonlinear theory of elasticity should be used instead. For an introduction to Linear Elasticity, we refer the reader to [3]. Linear Elasticity is commonly discretized using Finite Element Methods, see [1, Chap. 11].

Now it is necessary to advance our capabilities to direct simulation of many emerging problems of coastal ocean flows. Two examples of such flow problems are the 2010 Gulf of Mexico oil spill and the 2011 Japan tsunami. The two examples come from different backgrounds, however, they present a same challenge to our modeling capacity; the both examples involve distinct types of physical phenomena at vastly different scales, and they are multiscale and multiphysics flows in nature.

The Balancing Domain Decomposition by Constraints (BDDC) algorithms, introduced in [4], are nonoverlapping domain decomposition methods. The coarse problems in the BDDC algorithms are given in terms of a set of primal constraints. An important advantage with such a coarse problem is that the Schur complements that arise in the computation will all be invertible. The BDDC algorithms have been extended to many different applications with different discretizations such as [9, 10, 13, 14, 2] and [11, 12].

Consider the following weak formulation of a fourth order problem on a bounded polygonal domain Ω in R2:

The aim of this work is to develop a block FETI–DP preconditioner for mixed formulations of almost incompressible elasticity discretized with mixed isogeometric analysis (IGA) methods with continuous pressure

The Helmholtz equation is the simplest model for time harmonic wave propagation, and it contains already all the fundamental difficulties such problems pose when trying to compute their solution numerically.

Continuous space-time finite element methods for parabolic problems have been recently studied, e.g., in [1, 9, 10, 13]. The main common features of these methods are very different from those of time-stepping methods. Time is considered to be just another spatial coordinate. The variational formulations are studied in the full spacetime cylinder that is then decomposed into arbitrary admissible simplex elements.

We require that each subdomain be a union of shape-regular triangular elements with nodes on the boundaries of neighboring subdomains matching across the interface

In this paper, we present the auxiliary space preconditioning techniques for solving the linear system arising from linear virtual element method (VEM) discretizations on polytopal meshes of second order elliptic problems in both 2D and 3D domains.

In the field of nuclear energy, computations of complex two-phase flows are required for the design and safety studies of nuclear reactors. System codes are dedicated to the thermal-hydraulic analysis of nuclear reactors at system scale by simulating the whole reactor.

The computational cost is a key issue in crack identification or propagation problems. using a fictitious domain method [2]. We consider a geological crack in which the sides do not pull apart. To avoid re-meshing, we propose an approach combining the finite element method, the fictitious domain method, and a domain decomposition approach.

Problems in volcanology often involve elasticity models in presence of cracks (see e.g. [5]). Most of the time the force exerted on the crack is unknown, and the position and shape of the crack are also frequently unknown or partially known (see e.g. [2]). The model may be approximated via boundary element methods.

Maxwell’s equations can be used to model the propagation of electro-magneticwaves in the subsurface of the Earth. The interaction of such waves with the material in the subsurface produces response waves, which carry information about the physical properties of the Earth’s subsurface, and their measurement allows geophysicists to detect the presence of mineral or oil deposits.

the propagation of waves in elastic media is a problem of undeniable practical importance in geophysics. in several important applications - e.g. seismic exploration or earthquake prediction - one seeks to infer unknown material properties of the earth’s subsurface by sending seismic waves down and measuring the scattered field which comes back, implying the solution of inverse problems.

We study the behavior of solutions of PDE models on domains containing a heterogeneous layer of aperture tending to zero. We consider general second order differential operators on the outer domains and elliptic operators inside the layer. Our study is motivated by the modeling of flow through fractured porous media, when one represents the fractures as entities of co-dimension one with respect to the surrounding rock matrix.

The Newton algorithm and its variants are frequently used to obtain the numerical solution of large nonlinear systems arising from the discretization of partial differential equations, e.g., the incompressible Navier-Stokes equations in computational fluid dynamics. Near quadratic convergence can be observed when the nonlinearities in the system are well-balanced.

We are interested in solving a problem of linear elasticity in three dimensions.

The discretization of elliptic PDEs leads to large coupled systems of equations. Domain decomposition methods (DDMs) are one approach to the solution of these systems, and can split the problem in away that allows for parallel computing.

Our prime motivation is thermal fluid-structure interaction (FSI) where two domains with jumps in the material coefficients are connected through an interface. There exist two main strategies to simulate FSI models: the monolithic approach where a new code is tailored for the coupled equations and the partitioned approach that allows to reuse existing software for each sub-problem. Here we want to develop multirate methods that contribute to the time parallelization of the sub-problems for the partitioned simulation of FSI problems.

Newton-Krylov domain decomposition methods are well suited for solving nonlinear structural mechanics problems in parallel, especially due to their scalability properties. A Newton-Raphson method in combination with a dual domain decomposition technique, such as a FETI method, takes advantage of the quadratic convergence behaviour of the Newton-Raphson algorithm and the scalabality and high parallelizability of FETI methods. In order to reduce expensive communication between computing cores and thus Newton-iterations, a localization step for nonlinearities was proposed for FETI2, FETI-DP andBDDCsolvers [12, 8].

Additive Schwarz Methods (ASM) are implemented in the PETSc library [2, 1, 3] within its PCASM preconditioning option. By default this applies the Restricted Additive Schwarz (RAS) method of Cai and Sarkis [4].

Recently a lot of attention has been devoted to the Stokes-Darcy coupling which is a system of equations used to model the flow of fluids in porous media. In [2, 1[ a non standard behaviour of the optimized Schwarz method (OSM) has been observed: the optimized parameters obtained solving the classical min-max problems do not lead to an optimized convergence.