Recent Developments in Domain Decomposition Methods

We blend a fictitious domain decomposition method and the FETI-H substructuring algorithm to construct a fast finite element based solver for exterior Helmholtz problems characterized by partially axisymmetric and sound-soft scatterers. We highlight the computational merits of this solver, and demonstrate between one and two orders of magnitude reduction of the CPU time associated with the straightforward solution of such exterior Helmholtz problems.

In this paper, an iterative substructuring method with Lagrange multipliers is proposed for discrete problems arising from approximation of elliptic problem in two dimensions on non-matching meshes. The problem is formulated using a mortar technique. The algorithm belongs to the family of dual-primal FETI (Finite Element Tearing and Interconnecting) methods which has been analyzed recently for discretization on matching meshes. In this method the unknowns at the vertices of substructures are eliminated together with those of the interior nodal points of these substructures. It is proved that the preconditioner proposed is almost optimal; it is also well suited for parallel computations.

Balancing Neumann-Neumann methods are introduced and analyzed for the algebraic systems of linear equations for mixed finite element approximations of linear elasticity for incompressible and almost incompressible materials as well as composite materials with different Lamé parameters in different parts of the domain. These methods solve iteratively the saddle point Schur complement, resulting from the implicit elimination of the interior degrees of freedom, using a hybrid preconditioner based on a coarse mixed elasticity problem and local mixed elasticity problems with natural and essential boundary conditions. The resulting algorithm is very efficient, parallel, and robust with respect to material heterogeneities.

Coarse spaces play a crucial role in making Schwarz type domain decomposition methods scalable with respect to the number of subdomains. In this paper, we consider coarse spaces based on a class of partition of unity (PU) for some domain decomposition methods including the classical overlapping Schwarz method, and the new Schwarz method with harmonic overlap. PU has been used as a very powerful tool in the theoretical analysis of Schwarz type domain decomposition methods and meshless discretization schemes. In this paper, we show that PU can also be used effectively in the numerical construction of coarse spaces. PU based coarse spaces are easy to construct and need less communication than the standard finite-element-basis-function-based coarse space in distributed memory parallel implementations. We prove the new result that the condition number of the algorithms grows only linearly with respect to the relative size of the overlap. We also introduce the additive Schwarz method (AS) with harmonic overlap (ASHO), where all functions are made harmonic in part of the overlapping regions. As a result, the communication cost and condition number of ASHO is smaller than that of AS. Numerical experiments and a conditioning theory are presented in the paper.

We study two-level overlapping preconditioners with smoothed aggregation coarse spaces for the solution of sparse linear systems arising from finite element discretizations of second order elliptic problems. Smoothed aggregation coarse spaces do not require a coarse triangulation. After aggregation of the fine mesh nodes, a suitable smoothing operator is applied to obtain a family of overlapping subdomains and a set of coarse basis functions. We consider a set of algebraic assumptions on the smoother, that ensure optimal bounds for the condition number of the resulting preconditioned system. These assumptions only involve geometrical quantities associated to the sub domains, namely the diameter of the sub domains and the overlap. We first prove an upper bound for the condition number, which depends quadratically on the relative overlap. If additional assumptions on the coarse basis functions hold, a linear bound can be found. Finally, the performance of the preconditioners obtained by different smoothing procedures is illustrated by numerical experiments for linear finite elements in two dimensions.

We propose and analyze in an abstract framework a mortar method with approximate constraint, based on replacing the “master side” function appearing in the weak continuity condition with its projection on a suitably chosen auxiliary space. We show how to choose the auxiliary space in such a way that such a technique can be applied for computing the weak continuity constraints arising in the framework of the wavelet/FEM coupling.

Sound waves are propagating pressure fluctuations which are typically several orders of magnitude smaller than the pressure variations in the flow field that account for flow acceleration. On the other hand, these fluctuations travel at the speed of sound in the medium, not as a transported fluid quantity. Due to the above two properties, the Reynolds averaged Navier-Stokes (RANS) equations do not resolve the acoustic fluctuations. This paper discusses a defect correction method for this type of multi-scale problems in aeroacoustics.

We present a series of numerical results illustrating the performance of some non-overlapping domain decomposition algorithms for time-harmonic Maxwell equations in different physical situations. For the full-Maxwell equations with damping we consider the well-known Dirichlet/Neumann and Neumann/Neumann methods. Numerical evidence will show that both schemes are convergent with a rate independent of the mesh size. For the low-frequency model in a conductor, we consider again the Dirichlet/Neumann and the Neumann/Neumann algorithms. Both methods turn out to be efficient and robust. Finally, for the eddy-current problem, we implement an iterative procedure coupling a scalar problem in the insulator and a vector problem in the conductor.

For a symmetric and positive definite (SPD) matrix arising from the discretization of a partial differential equation with finite differences or finite elements on a structured grid in dimension d (d ≥ 3), we propose a SPD block ILU preconditioner whose factorized form requires a smaller amount of memory than the original matrix. Moreover, the computing time for the preconditioner solves is linear with respect to the number of unknowns. The preconditioner is built in d stages: in a first stage, we use the tangential filtering decomposition of Wittum et al [15,16,12,13], and obtain a preconditioner which remains rather difficult to factorize. Then, in a second stage, we apply again the tangential filtering decomposition to the diagonal blocks of this first preconditioner. The final stage consists of factorizing exactly the blocks corresponding to one dimensional problems. Such preconditioners can also be computed adaptively and combined in a multiplicative way. Numerical tests are presented, in particular for problems with highly heterogeneous media.

In this paper, we introduce a new implementation of the “parareal” time discretization aimed at solving unsteady nonlinear problems more efficiently, in particular those involving non-differentiable partial differential equations. As in the former implementation [3], the main goal of this scheme is to parallelize the time discretization to obtain an important speed up. As an application in financial mathematics, we consider the Black-Scholes equations for an American put. Numerical evidence of the important savings in computational time is also presented.

The paper is concerned with the mortar finite element discretization of scalar elliptic equations in three dimensions. The attention is focused on the influence of quadrature formulas on the discretization error. We show numerically that the optimality of the method is preserved if suitable quadrature formulas are used.

Adaptive finite element methods (FEM), generate linear equation systems that require dynamic and irregular patterns of data storage, access and computation, making their parallelization very difficult. Moreover, constantly evolving computer architectures often require new algorithms altogether. We describe here several solvers for solving such systems efficiently in two and three dimensions on multiple parallel architectures.