Skip to main content
main-content
Top

About this book

These are the proceedings of the 24th International Conference on Domain Decomposition Methods in Science and Engineering, which was held in Svalbard, Norway in February 2017.

Domain decomposition methods are iterative methods for solving the often very large systems of equations that arise when engineering problems are discretized, frequently using finite elements or other modern techniques. These methods are specifically designed to make effective use of massively parallel, high-performance computing systems.

The book presents both theoretical and computational advances in this domain, reflecting the state of art in 2017.

Table of Contents

Frontmatter

Plenary Talks (PT)

Frontmatter

Robust Block Preconditioners for Biot’s Model

In this paper, we design robust and efficient block preconditioners for the two-field formulation of Biot’s consolidation model, where stabilized finite-element discretizations are used. The proposed block preconditioners are based on the well-posedness of the discrete linear systems. Block diagonal (norm-equivalent) and block triangular preconditioners are developed, and we prove that these methods are robust with respect to both physical and discretization parameters. Numerical results are presented to support the theoretical results.

James H. Adler, Francisco J. Gaspar, Xiaozhe Hu, Carmen Rodrigo, Ludmil T. Zikatanov

An Additive Schwarz Analysis for Multiplicative Schwarz Methods: General Case

We analyze multiplicative Schwarz methods through the additive Schwarz theory. As a by-product we recover the Xu-Zikatanov identity for the norm of product operators. This extends earlier work by the author on multiplicative Schwarz methods that use symmetric positive definite solvers for the subspace corrections.

Susanne C. Brenner

Scalable Cardiac Electro-Mechanical Solvers and Reentry Dynamics

We present a scalable solver for the three-dimensional cardiac electro-mechanical coupling (EMC) model, which represents, currently, the most complete mathematical description of the interplay between the electrical and mechanical phenomena occurring during a heartbeat. The most computational demanding parts of the EMC model are: the electrical current flow model of the cardiac tissue, called Bidomain model, consisting of two non-linear partial differential equations of reaction-diffusion type; the quasi-static finite elasticity model for the deformation of the cardiac tissue. Our finite element parallel solver is based on: Block Jacobi and Multilevel Additive Schwarz preconditioners for the solution of the linear systems deriving from the discretization of the Bidomain equations; Newton-Krylov-Algebraic-Multigrid or Newton-Krylov-BDDC algorithms for the solution of the non-linear algebraic system deriving from the discretization of the finite elasticity equations. Three-dimensional numerical test on two linux clusters show the effectiveness and scalability of the EMC solver in simulating both physiological and pathological cardiac dynamics.

P. Colli Franzone, L. F. Pavarino, S. Scacchi, Stefano Zampini

On Overlapping Domain Decomposition Methods for High-Contrast Multiscale Problems

We review some important ideas in the design and analysis of robust overlapping domain decomposition algorithms for high-contrast multiscale problems.

Juan Galvis, Eric T. Chung, Yalchin Efendiev, Wing Tat Leung

INTERNODES for Heterogeneous Couplings

The INTERNODES (INTERpolation for NOnconforming DEcompositionS) method is an interpolation based approach to solve partial differential equations on non-conforming discretizations. In this paper we apply the INTERNODES method to different problems such as the Fluid Structure Interaction problem and the Stokes-Darcy coupled problem that models the filtration of fluids in porous media. Our results highlight the flexibility of the method as well as its optimal rate of convergence.

Paola Gervasio, Alfio Quarteroni

Domain Decomposition Approaches for PDE Based Mesh Generation

Adaptive, partial differential equation (PDE) based, mesh generators are introduced. The mesh PDE is typically coupled to the physical PDE of interest and one has to be careful not to introduce undue computational burden. Here we provide an overview of domain decomposition approaches to reduce this computational overhead and provide a parallel solver for the coupled PDEs. A preview of a new analysis for optimized Schwarz methods for the mesh generation problem using the theory of M-functions is given. We conclude by introducing a two-grid method with FAS correction for the grid generation problem.

Ronald D. Haynes

Modeling, Structure and Discretization of Hierarchical Mixed-Dimensional Partial Differential Equations

Mixed-dimensional partial differential equations arise in several physical applications, wherein parts of the domain have extreme aspect ratios. In this case, it is often appealing to model these features as lower-dimensional manifolds embedded into the full domain. Examples are fractured and composite materials, but also wells (in geological applications), plant roots, or arteries and veins.In this manuscript, we survey the structure of mixed-dimensional PDEs in the context where the sub-manifolds are a single dimension lower than the full domain, including the important aspect of intersecting sub-manifolds, leading to a hierarchy of successively lower-dimensional sub-manifolds. We are particularly interested in partial differential equations arising from conservation laws. Our aim is to provide an introduction to such problems, including the mathematical modeling, differential geometry, and discretization.

J. M. Nordbotten, W. M. Boon

Balancing Domain Decomposition by Constraints Algorithms for Curl-Conforming Spaces of Arbitrary Order

We construct Balancing Domain Decomposition by Constraints methods for the linear systems arising from arbitrary order, finite element discretizations of the H(curl) model problem in three-dimensions. Numerical results confirm that the proposed algorithm is quasi-optimal in the coarse-to-fine mesh ratio, and poly-logarithmic in the polynomial order of the curl-conforming discretization space. Additional numerical experiments, including higher-order geometries, upscaled finite elements, and adaptive coarse spaces, prove the robustness of our algorithm. A scalable three-level extension is presented, and it is validated with large scale experiments using up to 16,384 subdomains and almost a billion of degrees of freedom.

Stefano Zampini, Panayot Vassilevski, Veselin Dobrev, Tzanio Kolev

Talks in Minisymposia (MT)

Frontmatter

Restricted Additive Schwarz Method for Some Inequalities Perturbed by a Lipschitz Operator

We introduce and analyze a restricted additive Schwarz method for some inequalities perturbed by a Lipschitz operator. An existence and uniqueness result concerning the solution of the inequalities we consider is given. Also, we introduce the method as a subspace correction algorithm, prove the convergence and estimate the error in a general framework of a finite dimensional Hilbert space. By introducing the finite element spaces, we get that our algorithm is really a restricted additive Schwarz method and conclude that the convergence condition and convergence rate are independent of the mesh parameters and of both the number of subdomains and the parameters of the domain decomposition, but the convergence condition is a little more restrictive than the existence and uniqueness condition of the solution.

Lori Badea

Does SHEM for Additive Schwarz Work Better than Predicted by Its Condition Number Estimate?

The SHEM (Spectral Harmonically Enriched Multiscale) coarse space is a new coarse space for arbitrary overlapping or non-overlapping domain decomposition methods.

Petter E. Bjørstad, Martin J. Gander, Atle Loneland, Talal Rahman

Two-Level Preconditioners for the Helmholtz Equation

In this paper we compare numerically two different coarse space definitions for two-level domain decomposition preconditioners for the Helmholtz equation, both in two and three dimensions. While we solve the pure Helmholtz problem without absorption, the preconditioners are built from problems with absorption. In the first method, the coarse space is based on the discretization of the problem with absorption on a coarse mesh, with diameter constrained by the wavenumber. In the second method, the coarse space is built by solving local eigenproblems involving the Dirichlet-to-Neumann (DtN) operator.

Marcella Bonazzoli, Victorita Dolean, Ivan G. Graham, Euan A. Spence, Pierre-Henri Tournier

A Two-Level Domain-Decomposition Preconditioner for the Time-Harmonic Maxwell’s Equations

The construction of fast iterative solvers for the indefinite time-harmonic Maxwell’s system at mid- to high-frequency is a problem of great current interest. Some of the difficulties that arise are similar to those encountered in the case of the mid- to high-frequency Helmholtz equation. Here we investigate how two-level domain-decomposition preconditioners recently proposed for the Helmholtz equation work in the Maxwell case, both from the theoretical and numerical points of view.

Marcella Bonazzoli, Victorita Dolean, Ivan G. Graham, Euan A. Spence, Pierre-Henri Tournier

A Coarse Space to Remove the Logarithmic Dependency in Neumann–Neumann Methods

Domain Decomposition Methods are the most widely used methods for solving large linear systems that arise from the discretization of partial differential equations.

Faycal Chaouqui, Martin J. Gander, Kévin Santugini-Repiquet

A Crank-Nicholson Domain Decomposition Method for Optimal Control Problem of Parabolic Partial Differential Equation

A parallel domain decomposition algorithm is considered for solving an optimal control problem governed by a parabolic partial differential equation. The proposed algorithm relies on non-iterative and non-overlapping domain decomposition, which uses some implicit sub-domain problems and explicit flux approximations at each time step in every iteration. In addition, outer iterations are introduced to achieve the parallelism. Numerical experiments are supplied to show the efficiency of our proposed method.

Jixin Chen, Danping Yang

Partition of Unity Methods for Heterogeneous Domain Decomposition

In many applications, mathematical and numerical models involve simultaneously more than one single phenomenon. In this situation different equations are used in possibly overlapping subregions of the domain in order to approximate the physical model and obtain an efficient reduction of the computational cost. The coupling between the different equations must be carefully handled to guarantee accurate results. However in many cases, since the geometry of the overlapping subdomains is neither given a-priori nor characterized by coupling equations, a matching relation between the different equations is not available; see, e.g. Degond and Jin (SIAM J Numer Anal 42(6):2671–2687, 2005), Gander et al. (Numer Algorithm 73(1):167–195, 2016) and references therein. To overcome this problem, we introduce a new methodology that interprets the (unknown) decomposition of the domain by associating each subdomain to a partition of unity (membership) function. Then, by exploiting the feature of the partition of unity method developed in Babuska and Melenk (Int J Numer Methods Eng 40:727–758, 1996) and Griebel and Schweitzer (SIAM J Sci Comput 22(3):853–890, 2000), we define a new domain-decomposition strategy that can be easily embedded in infinite-dimensional optimization settings. This allows us to develop a new optimal control methodology that is capable to design coupling mechanisms between the different approximate equations. Numerical experiments demonstrate the efficiency of the proposed framework.

Gabriele Ciaramella, Martin J. Gander

Integral Equation Based Optimized Schwarz Method for Electromagnetics

The optimized Schwarz method (OSM) is recognized as one of the most efficient domain decomposition strategies without overlap for the solution to wave propagation problems in harmonic regime.

Xavier Claeys, Bertrand Thierry, Francis Collino

Analysis of the Shifted Helmholtz Expansion Preconditioner for the Helmholtz Equation

We study in this paper the so-called expansion preconditioner which is a generalization of the shifted Helmholtz preconditioner. We show that this preconditioner can reduce the number of GMRES iterations if the meshsize is small enough and the shift is at most of the size of the wavenumber. For larger shifts however, for which the preconditioner would become easier to invert than the underlying Helmholtz operator, the performance degrades, like for the Shifted Helmholtz preconditioner.

Pierre-Henri Cocquet, Martin J. Gander

A Finite Difference Method with Optimized Dispersion Correction for the Helmholtz Equation

We propose a new finite difference method (FDM) with optimized dispersion correction for the Helmholtz equation.

Pierre-Henri Cocquet, Martin J. Gander, Xueshuang Xiang

Optimized Schwarz Methods for Elliptic Optimal Control Problems

The present paper deals with the design of optimized Robin-Schwarz methods for the algorithm of optimal control proposed in Benamou (SIAM J Numer Anal 33(6):2401–2416, 1996). In both overlapping and non-overlapping cases, a full analysis of the problem is provided, and is illustrated with numerical tests.

Bérangère Delourme, Laurence Halpern, Binh Thanh Nguyen

Auxiliary Space Preconditioners for a DG Discretization of H(curl; Ω)-Elliptic Problem on Hexahedral Meshes

We present a family of preconditioners based on the auxiliary space method for a discontinuous Galerkin discretization on cubical meshes of H(curl;Ω)-elliptic problems with possibly discontinuous coefficients. We address the influence of possible discontinuities in the coefficients on the asymptotic performance of the proposed solvers and present numerical results in two dimensions.

Blanca Ayuso de Dios, Ralf Hiptmair, Cecilia Pagliantini

Is Minimising the Convergence Rate a Good Choice for Efficient Optimized Schwarz Preconditioning in Heterogeneous Coupling? The Stokes-Darcy Case

Optimized Schwarz Methods (OSM) are domain decomposition techniques based on Robin-type interface condition that have become increasingly popular in the last two decades. Ensuring convergence also on non-overlapping decompositions, OSM are naturally advocated for the heterogeneous coupling of multi-physics problems. Classical approaches optimize the coefficients in the Robin condition by minimizing the effective convergence rate of the resulting iterative algorithm. However, when OSM are used as preconditioners for Krylov solvers of the resulting interface problem, such parameter optimization does not necessarily guarantee the fastest convergence. This drawback is already known for homogeneous decomposition, but in the case of heterogeneous decomposition, the poor performance of the classical optimization approach becomes utterly evident. In this paper, we highlight this drawback for the Stokes/Darcy problem and propose a more effective optimization procedure.

Marco Discacciati, Luca Gerardo-Giorda

Preconditioned Space-Time Boundary Element Methods for the One-Dimensional Heat Equation

In this note we describe a space-time boundary element discretization of the heat equation and an efficient and robust preconditioning strategy which is based on the use of boundary integral operators of opposite orders, but which requires a suitable stability condition for the boundary element spaces used for the discretization. We demonstrate the method for the simple spatially one-dimensional case. However, the presented results, particularly the stability analysis of the boundary element spaces, can be used to extend the method to the two- and three-dimensional problem.

Stefan Dohr, Olaf Steinbach

On High-Order Approximation and Stability with Conservative Properties

In this paper, we explore a method for the construction of locally conservative flux fields. The flux values are obtained through the use of a Ritz formulation in which we augment the resulting linear system of the continuous Galerkin (CG) formulation in a higher-order approximation space. These methodologies have been successfully applied to multi-phase flow models with heterogeneous permeability coefficients that have high-variation and discontinuities. The increase in accuracy associated with the high order approximation of the pressure solutions is inherited by the flux fields and saturation solutions. Our formulation allows us to use the saddle point problems analysis to study approximation and stability properties as well as iterative methods design for the resulting linear system. In particular, here we show that the low-order finite element problem preconditions well the high-order conservative discrete system. We present numerical evidence to support our findings.

Juan Galvis, Eduardo Abreu, Ciro Díaz, Marcus Sarkis

A Nonlinear ParaExp Algorithm

We derive and analyze a nonlinear variant of the ParaExp algorithm introduced in Gander and Güttel (SIAM J Sci Comput 35(2):C123–C142, 2013) for linear evolution problems. We show that the nonlinear ParaExp algorithm converges in a finite number of steps, and that it can be interpreted as a parareal algorithm where the coarse integrator solves the linear part of the evolution problem. We also provide a numerical example illustrating the efficiency of the new algorithm.

Martin J. Gander, Stefan Güttel, Madalina Petcu

On Optimal Coarse Spaces for Domain Decomposition and Their Approximation

We consider a general second order elliptic model problem.

Martin J. Gander, Laurence Halpern, Kévin Santugini-Repiquet

Analysis of Overlap in Waveform Relaxation Methods for RC Circuits

Waveform relaxation (WR) methods are based on partitioning large circuits into sub-circuits which can be solved separately, and an iteration using transmission conditions then leads to better and better approximations of the entire circuit. Optimized waveform relaxation (OWR) methods work similarly, but they use more effective transmission conditions between sub-circuits. We study here for the first time the influence of overlap on WR and OWR applied to RC circuits. We derive an optimization problem which characterizes the best choice of certain resistance parameters in the transmission conditions for convergence, and give an asymptotic solution of this optimization problem. We also illustrate our results with numerical experiments.

Martin J. Gander, Pratik M. Kumbhar, Albert E. Ruehli

Convergence of Substructuring Methods for Elliptic Optimal Control Problems

We study in this paper Dirichlet–Neumann and Neumann–Neumann methods for the parallel solution of elliptic optimal control problems. Unlike in the case of single linear or non-linear elliptic problems, we need to solve here two coupled elliptic problems that arise as a part of optimality system for the optimal control problem. We present a rigorous convergence analysis for the case of two non-overlapping subdomains, which shows that both methods converge in at most three iterations. We illustrate our findings with numerical results.

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

Complete, Optimal and Optimized Coarse Spaces for Additive Schwarz

The additive Schwarz method does not converge in general when used as a stationary iterative method, it must be used as a preconditioner for a Krylov method. In the two level variant of the additive Schwarz method, a coarse grid correction is added to make the method scalable. We introduce a new coarse space for the additive Schwarz method which makes it convergent when used as a stationary iterative method, and show that an optimal choice even makes the method nilpotent, i.e. it converges in one iteration, independently of the overlap and the number of subdomains. We then show how this optimal choice can be approximated leading to a spectral harmonically enriched coarse space, based on interface eigenvalue problems. We present a convergence analysis of our new coarse corrections in the two subdomain case in two spatial dimensions, and also compare them with GenEO recently proposed by Spillane, Dolean, Hauret, Nataf, Pechstein, and Scheichl, and the local spectral multiscale coarse space proposed by Galvis and Efendiev.

Martin J. Gander, Bo Song

Heterogeneous Optimized Schwarz Methods for Coupling Helmholtz and Laplace Equations

Optimized Schwarz methods have increasingly drawn attention over the last decades because of their improvements in terms of robustness and computational cost compared to the classical Schwarz method. Optimized Schwarz methods are also a natural framework to study heterogeneous phenomena, where the spatial decomposition is provided by the multi-physics of the problem, because of their good convergence properties in the absence of overlap. We propose here zeroth order optimized transmission conditions for the coupling between the Helmholtz equation and the Laplace equation, giving asymptotically optimized choices for the parameters, and illustrating our analytical results with numerical experiments.

Martin J. Gander, Tommaso Vanzan

Restrictions on the Use of Sweeping Type Preconditioners for Helmholtz Problems

Sweeping type preconditioners have become a focus of attention for solving high frequency time harmonic wave propagation problems. These methods can be found under various names in the literature: in addition to sweeping, one finds the older approach of the Analytic Incomplete LU (AILU), optimized Schwarz methods, and more recently also source transfer domain decomposition, method based on single layer potentials, and method of polarized traces. An important innovation in sweeping methods is to use perfectly matched layer (PML) transmission conditions. In the constant wavenumber case, one can approximate the optimal transmission conditions represented by the Dirichlet to Neumann operator (DtN) arbitrarily well using large enough PMLs. We give in this short manuscript a simple, compact representation of these methods which allows us to explain exactly how they work, and test what happens in the case of non-constant wave number, in particular layered media in the difficult case where the layers are aligned against the sweeping direction. We find that iteration numbers of all these methods remain robust for very small contrast variations, in the order of a few percent, but then deteriorate, with linear growth both in the wave number as well as in the number of subdomains, as soon as the contrast variations reach order one.

Martin J. Gander, Hui Zhang

Convergence of Asynchronous Optimized Schwarz Methods in the Plane

A convergence proof of Asynchronous Optimized Schwarz Methods applied to a shifted Laplacian problem, with negative shift, in ℝ 2 $$\mathbb {R}^2$$ is presented. Sufficient conditions for convergence involving initial values of the approximation of the solution are discussed.

José C. Garay, Frédéric Magoulès, Daniel B. Szyld

INTERNODES for Elliptic Problems

The INTERNODES (INTERpolation for NOnconforming DEcompositionS) method is an interpolation based approach to solve partial differential equations on non-conforming discretizations. In this paper we sketch its formulation when it is applied to second-order elliptic problems. Therefore we apply it to the Kellogg’s test case with jumping coefficients and to an infinitely differentiable test solution. In both cases, INTERNODES attains optimal rate of convergence (i.e., that of the best approximation error in each subdomain).

Paola Gervasio, Alfio Quarteroni

A Nonlinear Elimination Preconditioned Newton Method with Applications in Arterial Wall Simulation

Arterial wall can be modeled by a quasi-incompressible, anisotropic and hyperelastic equation that allows large deformation. Most existing nonlinear solvers for the steady hyperelastic problem are based on pseudo time stepping, which often requires a large number of time steps especially for the case of large deformation. It is also reported that the quasi-incompressibility and high anisotropy have negative effects on the convergence of both Newton’s iteration and the linear Jacobian solver. In this paper, we propose and study a nonlinearly preconditioned Newton method based on nonlinear elimination to calculate the steady solution directly without pseudo time integration. We show numerically that the nonlinear elimination preconditioner accelerates Newton’s convergence in cases with large deformation, quasi-incompressibility and high anisotropy.

Shihua Gong, Xiao-Chuan Cai

Parallel-in-Time for Parabolic Optimal Control Problems Using PFASST

In gradient-based methods for parabolic optimal control problems, it is necessary to solve both the state equation and a backward-in-time adjoint equation in each iteration of the optimization method. In order to facilitate fully parallel gradient-type and nonlinear conjugate gradient methods for the solution of such optimal control problems, we discuss the application of the parallel-in-time method PFASST to adjoint gradient computation. In addition to enabling time parallelism, PFASST provides high flexibility for handling nonlinear equations, as well as potential extra computational savings from reusing previous solutions in the optimization loop. The approach is demonstrated here for a model reaction-diffusion optimal control problem.

Sebastian Götschel, Michael L. Minion

An Adaptive GDSW Coarse Space for Two-Level Overlapping Schwarz Methods in Two Dimensions

We propose robust coarse spaces for two-level overlapping Schwarz preconditioners, which are extensions of the energy minimizing coarse space known as GDSW (Generalized Dryja, Smith, Widlund). The resulting two-level methods with adaptive coarse spaces are robust for second order elliptic problems in two dimensions, even in presence of a highly heterogeneous coefficient function, and reduce to the standard GDSW algorithm if no additional coarse basis functions are used.

Alexander Heinlein, Axel Klawonn, Jascha Knepper, Oliver Rheinbach

Improving the Parallel Performance of Overlapping Schwarz Methods by Using a Smaller Energy Minimizing Coarse Space

We consider a recent overlapping Schwarz method with an energy-minimizing coarse space of reduced size. In numerical experiments for up to 64,000 cores, we show that the parallel efficiency and the total time to solution is improved significantly, compared to our previous overlapping Schwarz method using an alternative energy-minimizing coarse space.

Alexander Heinlein, Axel Klawonn, Oliver Rheinbach, Olof B. Widlund

Inexact Dual-Primal Isogeometric Tearing and Interconnecting Methods

In Isogeometric Analysis (IgA), non-trivial computational domains are often composed of volumetric patches where each of them is discretized by means of tensor-product B-splines or NURBS. In such a setting, the dual-primal IsogEometric Tearing and Interconnecting (IETI-DP) method, that is nothing but the generalization of the FETI-DP method to IgA, has proven to be a very efficient solver for huge systems of IgA equations. Using IETI-DP, basically any patch-local solver can be extended to the global problem. So far, only direct solvers have been considered as patch-local solvers. In the present paper, we compare them with the option of using robust multigrid as patch-local solver. This is of special interest for large-scale patch-local systems or/and for large spline degrees, because the convergence of standard smoothers deteriorates with large spline degrees and the robust multigrid smoother chosen is only available on tensor-product discretizations.

Christoph Hofer, Ulrich Langer, Stefan Takacs

Coupling Parareal and Dirichlet-Neumann/Neumann-Neumann Waveform Relaxation Methods for the Heat Equation

The Dirichlet-Neumann and Neumann-Neumann waveform relaxation methods are non-overlapping spatial domain decomposition methods to solve evolution problems, while the parareal algorithm is in time parallel fashion. Based on the combinations of space and time parallel strategies, we present and analyze parareal Dirichlet-Neumann and parareal Neumann-Neumann waveform relaxation for parabolic problems. Between these two algorithms, parareal Neumann-Neumann waveform relaxation is a space-time parallel algorithm, which increases the parallelism both in space and time. We derive for the heat equation the convergence results for both algorithms in one spatial dimension. We also illustrate our theoretical results with numerical experiments.

Yao-Lin Jiang, Bo Song

Preconditioning of Iterative Eigenvalue Problem Solvers in Adaptive FETI-DP

Adaptive FETI-DP and BDDC methods are robust methods that can be used for highly heterogeneous problems when standard approaches fail. In these approaches, local generalized eigenvalue problems are solved approximately, and the eigenvectors are used to enhance the coarse problem. Here, a few iterations of an approximate eigensolver are usually sufficient. Different preconditioning options for the iterative LOBPCG eigenvalue problem solver are considered. Numerical results are presented for linear elasticity problems with heterogeneous coefficients.

Axel Klawonn, Martin Kühn, Oliver Rheinbach

Using Algebraic Multigrid in Inexact BDDC Domain Decomposition Methods

A highly scalable implementation of an inexact BDDC (Balancing Domain Decomposition by Constraints) method is presented, and scalability results for linear elasticity problems in two and three dimensions for up to 131,072 computational cores of the JUQUEEN BG/Q are shown. In this method, the inverse action of the partially coupled stiffness matrix is replaced by V-cycles of an AMG (algebraic multigrid) method. The use of classical AMG for systems of PDEs, based on a nodal coarsening approach is compared with a recent AMG method using an explicit interpolation of the rigid body motions (global matrix approach; GM). It is illustrated, that for systems of PDEs an appropriate AMG interpolation is mandatory for fast convergence, i.e., using exact interpolation of rigid body modes in elasticity.

Axel Klawonn, Martin Lanser, Oliver Rheinbach

On the Accuracy of the Inner Newton Iteration in Nonlinear Domain Decomposition

We introduce an energy minimizing nonlinear preconditioner for our nonlinear FETI-DP methods, and we will show numerical results for some problems in two dimensions based on the scaled p-Laplace operator. The equivalence of nonlinear FETI-DP methods and specific right-preconditioned Newton-Krylov methods was already shown. In nonlinear FETI-DP methods, the preconditioner describes a nonlinear elimination process. In the variants proposed here, the evolution of a problem dependent global energy is controlled during the elimination process, which guarantees that the application of the nonlinear preconditioner does not increase the global energy. Often, stopping the inner Newton iteration early, based on the energy criterion, gives better performance of the overall method. In this paper, a comparison of the classical nonlinear FETI-DP methods with nonlinear FETI-DP methods using an energy minimizing nonlinear preconditioner is provided.

Axel Klawonn, Martin Lanser, Oliver Rheinbach, Matthias Uran

Adaptive BDDC and FETI-DP Methods with Change of Basis Formulation

In this paper, BDDC (Balancing Domain Decomposition by Constraints) and FETI-DP (Dual-Primal Finite Element Tearing and Interconnecting) algorithms with a change of basis for adaptive primal constraints are analyzed.

Hyea Hyun Kim, Eric T. Chung, Junxian Wang

Nonoverlapping Three Grid Additive Schwarz for hp-DGFEM with Discontinuous Coefficients

We discuss a nonoverlapping additive Schwarz method for an h-p DGFEM discretization of an elliptic PDE with discontinuous coefficients, where the fine grid is decomposed into subdomains of size H and the coarse grid consists of cells size H $$\mathcal {H}$$ such that h ≤ H ≤ H $$h\leq H \leq \mathcal {H}$$ . We prove the condition number is O ( p 2 ∕ q ) ⋅ O ( H 2 ∕ H h ) $$O(p^2/q)\cdot O(\mathcal {H}^2/Hh)$$ and is independent from the jumps of the coefficient if the discontinuities are aligned with the coarse grid.

Piotr Krzyżanowski

Adaptive Deluxe BDDC Mixed and Hybrid Primal Discretizations

Major progress has been made recently to make FETI-DP and BDDC preconditioners robust with respect to any variation of coefficients inside and/or across the subdomains.

Alexandre Madureira, Marcus Sarkis

Additive Schwarz with Vertex Based Adaptive Coarse Space for Multiscale Problems in 3D

In this paper an overlapping additive Schwarz method with a spectrally enriched coarse space is proposed. The method is for solving the standard Finite Element discretization of second order elliptic problems in there dimensions with discontinuous coefficients, where the discontinuities are inside subdomains and across subdomain boundaries. In case when the coarse space is large enough the convergence of the PCG method is independent of jumps in the coefficient.

Leszek Marcinkowski, Talal Rahman

An Immersed Boundary Method Based on the L 2-Projection Approach

In this paper we present a framework for Fluid-Structure Interaction simulations. Taking inspiration from the Immersed Boundary technique introduced by Peskin (J Comput Phys 10(2):252–271, 1972) we employ the finite element method for discretizing the equations of the solid structure and the finite difference method for discretizing the fluid flow. The two discretizations are coupled by using a volume based L 2-projection approach to transfer elastic forces and velocities between the fluid and the solid domain. We present results for a Fluid–Structure Interaction benchmark which describes self-induced oscillating deformations of an elastic beam in a flow channel.

Maria Giuseppina Chiara Nestola, Barna Becsek, Hadi Zolfaghari, Patrick Zulian, Dominik Obrist, Rolf Krause

Combining Space-Time Multigrid Techniques with Multilevel Monte Carlo Methods for SDEs

In this work we combine multilevel Monte Carlo methods for time-dependent stochastic differential equations with a space-time multigrid method. The idea is to use the space-time hierarchy from the multilevel Monte Carlo method also for the solution process of the arising linear systems. This symbiosis leads to a robust and parallel method with respect to space, time and probability. We show the performance of this approach by several numerical experiments which demonstrate the advantages of this approach.

Martin Neumüller, Andreas Thalhammer

On Block Triangular Preconditioners for the Interior Point Solution of PDE-Constrained Optimization Problems

We consider the numerical solution of saddle point systems of equations resulting from the discretization of PDE-constrained optimization problems, with additional bound constraints on the state and control variables, using an interior point method. In particular, we derive a Bramble–Pasciak Conjugate Gradient method and a tailored block triangular preconditioner which may be applied within it. Crucial to the usage of the preconditioner are carefully chosen approximations of the (1, 1)-block and Schur complement of the saddle point system. To apply the inverse of the Schur complement approximation, which is computationally the most expensive part of the preconditioner, one may then utilize methods such as multigrid or domain decomposition to handle individual sub-blocks of the matrix system.

John W. Pearson, Jacek Gondzio

Robust Multigrid Methods for Isogeometric Discretizations of the Stokes Equations

In recent publications, the author and his coworkers have proposed a multigrid method for solving linear systems arising from the discretization of partial differential equations in isogeometric analysis and have proven that the convergence rates are robust in both the grid size and the polynomial degree. So far the method has only been discussed for the Poisson problem. In the present paper, we discuss the extension the of these results to the Stokes equations.

Stefan Takacs

Contributed Talks and Posters (CT)

Frontmatter

A Smoother Based on Nonoverlapping Domain Decomposition Methods for H(div) Problems: A Numerical Study

The purpose of this paper is to introduce a V-cycle multigrid method for vector field problems discretized by the lowest order Raviart-Thomas hexahedral element. Our method is connected with a smoother based on a nonoverlapping domain decomposition method. We present numerical experiments to show the effectiveness of our method.

Susanne C. Brenner, Duk-Soon Oh

Optimized Schwarz Method for Poisson’s Equation in Rectangular Domains

An analysis of the convergence properties of Optimized Schwarz methods applied as solvers for Poisson’s Equation in a bounded rectangular domain with Dirichlet (physical) boundary conditions and Robin transmission conditions on the artificial boundaries is presented. To our knowledge this is the first time that this is done for multiple subdomains forming a 2D array in a bounded domain.

José C. Garay, Frédéric Magoulès, Daniel B. Szyld

The HTFETI Method Variant Gluing Cluster Subdomains by Kernel Matrices Representing the Rigid Body Motions

The proposed algorithm called the Hybrid Total Finite Element Tearing and Interconnecting method (HTFETI) is a variant of the TFETI domain decomposition method suitable for large-scale problems with hundreds of thousands of subdomains. The floating subdomains are gathered into several groups belonging to individual clusters. We use the new idea consisting in gluing the cluster subdomains using kernel matrices defined by the rigid body motions. This technique reduces the size of the coarse problem. While the size of the coarse problem depends linearly on the number of subdomains in the classical TFETI method, it depends linearly on the number of clusters in the HTFETI method. The zero weighted averages across the interfaces of neighbouring subdomains (an alternative to the constraints enforcing the continuity across the corners used, e.g., in the FETI-DP method) improve conditioning of the resulting system of linear equations.

Alexandros Markopoulos, Lubomír Říha, Tomáš Brzobohatý, Ondřej Meca, Radek Kučera, Tomáš Kozubek

Small Coarse Spaces for Overlapping Schwarz Algorithms with Irregular Subdomains

Methods are developed for automatically constructing small coarse spaces of low dimension for domain decomposition algorithms for problems in three dimensions. These constructions use equivalence classes of nodes on the interface between the subdomains into which the domain of a given elliptic problem has been subdivided, e.g., by a mesh partitioner; these equivalence classes already play a central role in the design, analysis, and programming of many domain decomposition algorithms. The coarse space elements are well defined even for irregular subdomains, are continuous, and well suited for use in two-level or multi-level preconditioners such as overlapping Schwarz algorithms. Significant reductions in the coarse space dimension can be achieved while not sacrificing the favorable condition number estimates for larger coarse spaces previously developed. The condition number estimates depend primarily on the Lipschitz parameters of the subdomains.

Olof B. Widlund, Clark R. Dohrmann

Backmatter

Additional information

Premium Partner

image credits