Linear and nonlinear substructured Restricted Additive Schwarz iterations and preconditioning

Iterative substructuring Domain Decomposition (DD) methods have been extensively studied, and they are usually associated with nonoverlapping decompositions. It is less known that classical overlapping DD methods can also be formulated in substructured form, i.e., as iterative methods acting on variables defined exclusively on the interfaces of the overlapping domain decomposition. We call such formulations substructured domain decomposition methods. We introduce here a substructured version of Restricted Additive Schwarz (RAS) which we call SRAS. We show that RAS and SRAS are equivalent when used as iterative solvers, as they produce the same iterates, while they are substantially different when used as preconditioners for GMRES. We link the volume and substructured Krylov spaces and show that the iterates are different by deriving the least squares problems solved at each GMRES iteration. When used as iterative solvers, SRAS presents computational advantages over RAS, as it avoids computations with matrices and vectors at the volume level. When used as preconditioners, SRAS has the further advantage of allowing GMRES to store smaller vectors and perform orthogonalization in a lower dimensional space. We then consider nonlinear problems, and we introduce SRASPEN (Substructured Restricted Additive Schwarz Preconditioned Exact Newton), where SRAS is used as a preconditioner for Newton’s method. In contrast to the linear case, we prove that Newton’s method applied to the preconditioned volume and substructured formulation produces the same iterates in the nonlinear case. Next, we introduce two-level versions of nonlinear SRAS and SRASPEN. Finally, we validate our theoretical results with numerical experiments.

     

Using Local Spectral Information in Domain Decomposition Methods – A Brief Overview in a Nutshell

For second-order elliptic partial differential equations large discontinuities in the coefficients yield ill-conditioned stiffness matrices. The convergence of domain decomposition methods (DDM) can be improved by incorporating (numerically computed) local eigenvectors into the coarse space. Different adaptive coarse spaces for DDM have been constructed and used successfully. For two-level Schwarz, FETI-1 and BDD methods, adaptive coarse spaces with a rigorous theoretical basis are known for 2D and 3D. Although successfully in use for almost a decade, a theory for adaptive coarse spaces for FETI-DP and BDDC was lacking. While the problem was recently settled for 2D, the estimate for the 3D adaptive algorithm required improved coarse spaces. We give an brief overview of the literature, i. e., the different known approaches, and show numerical results for a specific adaptive FETI-DP method in 3D, where the condition number bound could only recently be proven. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A two level domain decomposition preconditioner based on local Dirichlet-to-Neumann maps

Coarse grid correction is a key ingredient in order to have scalable domain decomposition methods. In this Note we construct the coarse grid space using the low frequency modes of the subdomain DtN (Dirichlet–Neumann) maps, and apply the obtained two-level preconditioner to the linear system arising from an overlapping domain decomposition. Our method is suitable for the parallel implementation and its efficiency is demonstrated by numerical examples on problems with high heterogeneities.     

A domain decomposition method based on the iterative operator splitting method

In this article a new approach is proposed for constructing a domain decomposition method based on the iterative operator splitting method. The convergence properties of such a method are studied. The main feature of the proposed idea is the decoupling of space and time. We present a multi-iterative operator splitting method that combines iteratively the space and time splitting. We confirm with numerical applications the effectiveness of the proposed iterative operator splitting method in comparison with the classical Schwarz waveform relaxation method as a standard method for domain decomposition. We provide improved results and convergence rates.     

Two-level Schwarz method for unilateral variational inequalities

The numerical solution of variational inequalities of obstacletype associated with second-order elliptic operators is considered.Iterative methods based on the domain decomposition approachare proposed for discrete obstacle problems arising from thecontinuous, piecewise linear finite element approximation ofthe differential problem. A new variant of the Schwarz methodology,called the two-level Schwarz method, is developed offering thepossibility of making use of fast linear solvers (e.g., linearmultigrid and fictitious domain methods) for the genuinely nonlinearobstacle problems. Namely, by using particular monotonicityresults, the computational domain can be partitioned into (mesh)subdomains with linear and nonlinear (obstacle-type) subproblems.By taking advantage of this domain decomposition and fast linearsolvers, efficient implementation algorithms for large-scalediscrete obstacle problems can be developed. The last part ofthe paper is devoted to illustrate numerical experiments.     

非嵌套网格上的Morley元两水平加性Schwarz方法

1．引言设0是RZ中的有界多边形区域，其边界为Rfl．考虑下面的重调和Dirichlet问题：（1．1）的变分形式为：求。EHI（fi）使得对？／EL‘（m，问题（1．幻的唯一可解性可由冯（m上的M线性型的强制性和连续性以及La。Mlgram定理得出（of［4］）．令人一｛丸）是n的一个三角剖分，并且满足最小角条件，其中h是它的网格参数．设Vh为Money元空间［41．问题（1．2）的有限元离散问题为：求。eVh使得当有限元参数人很小时，这个方程组很大，而且矩阵A的条件数变得非常大，直接求解，存贮量及计算量都很大．如果B可逆，则方程组（1．4）等…     

On the abstract theory of additive and multiplicative Schwarz algorithms

Summary. In recent years, it has been shown that many modern iterative algorithms (multigrid schemes, multilevel preconditioners, domain decomposition methods etc.) for solving problems resulting from the discretization of PDEs can be interpreted as additive (Jacobi-like) or multiplicative (Gauss-Seidel-like) subspace correction methods. The key to their analysis is the study of certain metric properties of the underlying splitting of the discretization space into a sum of subspaces and the splitting of the variational problem on into auxiliary problems on these subspaces. In this paper, we propose a modification of the abstract convergence theory of the additive and multiplicative Schwarz methods, that makes the relation to traditional iteration methods more explicit. The analysis of the additive and multiplicative Schwarz iterations can be carried out in almost the same spirit as in the traditional block-matrix situation, making convergence proofs of multilevel and domain decomposition methods clearer, or, at least, more classical. In addition, we present a new bound for the convergence rate of the appropriately scaled multiplicative Schwarz method directly in terms of the condition number of the corresponding additive Schwarz operator. These results may be viewed as an appendix to the recent surveys [X], [Ys]. Received February 1, 1994 / Revised version received August 1, 1994     

Domain decomposition for multiscale PDEs

We consider additive Schwarz domain decomposition preconditioners for piecewise linear finite element approximations of elliptic PDEs with highly variable coefficients. In contrast to standard analyses, we do not assume that the coefficients can be resolved by a coarse mesh. This situation arises often in practice, for example in the computation of flows in heterogeneous porous media, in both the deterministic and (Monte–Carlo simulated) stochastic cases. We consider preconditioners which combine local solves on general overlapping subdomains together with a global solve on a general coarse space of functions on a coarse grid. We perform a new analysis of the preconditioned matrix, which shows rather explicitly how its condition number depends on the variable coefficient in the PDE as well as on the coarse mesh and overlap parameters. The classical estimates for this preconditioner with linear coarsening guarantee good conditioning only when the coefficient varies mildly inside the coarse grid elements. By contrast, our new results show that, with a good choice of subdomains and coarse space basis functions, the preconditioner can still be robust even for large coefficient variation inside domains, when the classical method fails to be robust. In particular our estimates prove very precisely the previously made empirical observation that the use of low-energy coarse spaces can lead to robust preconditioners. We go on to consider coarse spaces constructed from multiscale finite elements and prove that preconditioners using this type of coarsening lead to robust preconditioners for a variety of binary (i.e., two-scale) media model problems. Moreover numerical experiments show that the new preconditioner has greatly improved performance over standard preconditioners even in the random coefficient case. We show also how the analysis extends in a straightforward way to multiplicative versions of the Schwarz method. We would like to thank Bill McLean for very useful discussions concerning this work. We would also like to thank Maksymilian Dryja for helping us to improve the result in Theorem 4.3.     

Schwarz methods for inequalities with contraction operators

We prove the convergence of some multiplicative and additive Schwarz methods for inequalities which contain contraction operators. The problem is stated in a reflexive Banach space and it generalizes the well-known fixed-point problem in the Hilbert spaces. Error estimation theorems are given for three multiplicative algorithms and two additive algorithms. We show that these algorithms are in fact Schwarz methods if the subspaces are associated with a decomposition of the domain. Also, for the one- and two-level methods in the finite element spaces, we write the convergence rates as functions of the overlapping and mesh parameters. They are similar with the convergence rates of these methods for linear problems. Besides the direct use of the five algorithms for the inequalities with contraction operators, we can use the above results to obtain the convergence rate of the Schwarz method for other types of inequalities or nonlinear equations. In this way, we prove the convergence and estimate the error of the one- and two-level Schwarz methods for some inequalities in Hilbert spaces which are not of the variational type, and also, for the Navier–Stokes problem. Finally, we give conditions of existence and uniqueness of the solution for all problems we consider. We point out that these conditions and the convergence conditions of the proposed algorithms are of the same type.     

Domain decomposition preconditioners for multiscale problems in linear elasticity

We analyze two‐level overlapping Schwarz domain decomposition methods for vector‐valued piecewise linear finite element discretizations of the PDE system of linear elasticity. The focus of our study lies in the application to compressible, particle‐reinforced composites in 3D with large jumps in their material coefficients. We present coefficient‐explicit bounds for the condition number of the two‐level additive Schwarz preconditioned linear system. Thereby, we do not require that the coefficients are resolved by the coarse mesh. The bounds show a dependence of the condition number on the energy of the coarse basis functions, the coarse mesh, and the overlap parameters, as well as the coefficient variation. Similar estimates have been developed for scalar elliptic PDEs by Graham et al. 1 The coarse spaces to which they apply here are assumed to contain the rigid body modes and can be considered as generalizations of the space of piecewise linear vector‐valued functions on a coarse triangulation. The developed estimates provide a concept for the construction of coarse spaces, which can lead to preconditioners that are robust with respect to high contrasts in Young's modulus and the Poisson ratio of the underlying composite. To confirm the sharpness of the theoretical findings, we present numerical results in 3D using vector‐valued linear, multiscale finite element and energy‐minimizing coarse spaces. The theory is not restricted to the isotropic (Lamé) case, extends to the full‐tensor case, and allows applications to multiphase materials with anisotropic constituents in two and three spatial dimensions. However, the bounds will depend on the ratio of largest to smallest eigenvalue of the elasticity tensor.     

Parallel solution of elasticity problems using overlapping aggregations

The finite element (FE) solution of geotechnical elasticity problems leads to the solution of a large system of linear equations. For solving the system, we use the preconditioned conjugate gradient (PCG) method with two-level additive Schwarz preconditioner. The preconditioning is realised in parallel. A coarse space is usually constructed using an aggregation technique. If the finite element spaces for coarse and fine problems on structural grids are fully compatible, relations between elements of matrices of the coarse and fine problems can be derived. By generalization of these formulae, we obtain an overlapping aggregation technique for the construction of a coarse space with smoothed basis functions. The numerical tests are presented at the end of the paper.     

A two-level finite element method for the Navier–Stokes equations based on a new projection

We consider a fully discrete two-level approximation for the time-dependent Navier–Stokes equations in two dimension based on a time-dependent projection. By defining this new projection, the iteration between large and small eddy components can be reflected by its associated space splitting. Hence, we can get a weakly coupled system of large and small eddy components. This two-level method applies the finite element method in space and Crank–Nicolson scheme in time. Moreover,the analysis and some numerical examples are shown that the proposed two-level scheme can reach the same accuracy as the classical one-level Crank–Nicolson method with a very fine mesh size h by choosing a proper coarse mesh size H. However, the two-level method will involve much less work.     

A comparison of overlapping Schwarz methods and block preconditioners for saddle point problems

Three domain decomposition methods for saddle point problems are introduced and compared. The first two are block‐diagonal and block‐triangular preconditioners with diagonal blocks approximated by an overlapping Schwarz technique with positive definite local and coarse problems. The third is an overlapping Schwarz preconditioner based on indefinite local and coarse problems. Numerical experiments show that while all three methods are numerically scalable, the last method is almost always the most efficient. Copyright © 2000 John Wiley & Sons, Ltd.     

Neumann–Neumann waveform relaxation algorithm in multiple subdomains for hyperbolic problems in 1D and 2D

We present a Waveform Relaxation (WR) version of the Neumann–Neumann algorithm for the wave equation in space‐time. The method is based on a nonoverlapping spatial domain decomposition, and the iteration involves subdomain solves in space‐time with corresponding interface conditions, followed by a correction step. Using a Fourier‐Laplace transform argument, for a particular relaxation parameter, we prove convergence of the algorithm in a finite number of steps for the finite time intervals. The number of steps depends on the size of the subdomains and the time window length on which the algorithm is employed. We illustrate the performance of the algorithm with numerical results, followed by a comparison with classical and optimized Schwarz WR methods. © 2016 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 33: 514–530, 2017     

Overlapping Schwarz methods on unstructured meshes using non-matching coarse grids

Summary. We consider two level overlapping Schwarz domain decomposition methods for solving the finite element problems that arise from discretizations of elliptic problems on general unstructured meshes in two and three dimensions. Standard finite element interpolation from the coarse to the fine grid may be used. Our theory requires no assumption on the substructures that constitute the whole domain, so the substructures can be of arbitrary shape and of different size. The global coarse mesh is allowed to be non-nested to the fine grid on which the discrete problem is to be solved, and neither the coarse mesh nor the fine mesh need be quasi-uniform. In addition, the domains defined by the fine and coarse grid need not be identical. The one important constraint is that the closure of the coarse grid must cover any portion of the fine grid boundary for which Neumann boundary conditions are given. In this general setting, our algorithms have the same optimal convergence rate as the usual two level overlapping domain decomposition methods on structured meshes. The condition number of the preconditioned system depends only on the (possibly small) overlap of the substructures and the size of the coarse grid, but is independent of the sizes of the subdomains. Received March 23, 1994 / Revised version received June 2, 1995     

A robust two-level domain decomposition preconditioner for systems of PDEs

Coarse spaces are instrumental in obtaining scalability for domain decomposition methods. However, it is known that most popular choices of coarse spaces perform rather weakly in presence of heterogeneities in the coefficients in the partial differential equations, especially for systems. Here, we introduce in a variational setting a new coarse space that is robust even when there are such heterogeneities. We achieve this by solving local generalized eigenvalue problems which isolate the terms responsible for slow convergence. We give a general theoretical result and then some numerical examples on a heterogeneous elasticity problem.     

A coarse–fine‐mesh stabilization for an alternating Schwarz domain decomposition method

Domain decomposition methods can be solved in various ways. In this paper, domain decomposition in strips is used. It is demonstrated that a special version of the Schwarz alternating iteration method coupled with coarse–fine‐mesh stabilization leads to a very efficient solver, which is easy to implement and has a behavior nearly independent of mesh and problem parameters. The novelty of the method is the use of alternating iterations between odd‐ and even‐numbered subdomains and the replacement of the commonly used coarse‐mesh stabilization method with coarse–fine‐mesh stabilization.     

Parallel Smoothed Aggregation Multilevel Schwarz Preconditioned Newton-Krylov Algorithms for Poisson-Boltzmann Problems

We study a multilevel Schwarz preconditioned Newton-Krylov algorithm to solve the Poisson-Boltzmann equation with applications in multi-particle colloidal simulation. The smoothed aggregation-type coarse mesh space is introduced in collaboration with the one-level Schwarz method as a composite preconditioner for accelerating the convergence of a Krylov subspace method for solving the Jacobian system at each Newton step. The important feature of the proposed solution algorithm is that the geometric mesh information needed for constructing the multilevel preconditioner is the same as the one-level Schwarz method on the fine mesh. Other components, such as the definition of the coarse mesh, all the mesh transfer operators, and the coarse mesh problem, are taken care of by the Trillinos/ML packages of the Sandia National Laboratories in the United States. After algorithmic parameter tuning, we show that the proposed smoothed aggregation multilevel Newton-Krylov-Schwarz (NKS) algorithm numerically outperforms than smoothed aggregation multigrid method and one-level version of the NKS algorithm with satisfactory parallel performances up to a few thousand cores. Besides, we investigate how the electrostatic forces between particles for the separation distance depend on the radius of spherical colloidal particles and valence ratios of cation and anion in a cubic system.     

Multilevel Schwarz methods for elliptic problems with discontinuous coefficients in three dimensions

Summary. Multilevel Schwarz methods are developed for a conforming finite element approximation of second order elliptic problems. We focus on problems in three dimensions with possibly large jumps in the coefficients across the interface separating the subregions. We establish a condition number estimate for the iterative operator, which is independent of the coefficients, and grows at most as the square of the number of levels. We also characterize a class of distributions of the coefficients, called quasi-monotone, for which the weighted -projection is stable and for which we can use the standard piecewise linear functions as a coarse space. In this case, we obtain optimal methods, i.e. bounds which are independent of the number of levels and subregions. We also design and analyze multilevel methods with new coarse spaces given by simple explicit formulas. We consider nonuniform meshes and conclude by an analysis of multilevel iterative substructuring methods. Received April 6, 1994 / Revised version received December 7, 1994     

A comparison of some domain decomposition and ILU preconditioned iterative methods for nonsymmetric elliptic problems

In recent years, competitive domain-decomposed preconditioned iterative techniques of Krylov-Schwarz type have been developed for nonsymmetric linear elliptic systems. Such systems arise when convection-diffusion-reaction problems from computational fluid dynamics or heat and mass transfer are linearized for iterative solution. Through domain decomposition, a large problem is divided into many smaller problems whose requirements for coordination can be controlled to allow effective solution on parallel machines. A central question is how to choose these small problems and how to arrange the order of their solution. Different specifications of decomposition and solution order lead to a plethora of algorithms possessing complementary advantages and disadvantages. In this report we compare several methods, including the additive Schwarz algorithm, the classical multiplicative Schwarz algorithm, an accelerated multiplicative Schwarz algorithm, the tile algorithm, the CGK algorithm, the CSPD algorithm, and also the popular global ILU-family of preconditioners, on some nonsymmetric or indefinite elliptic model problems discretized by finite difference methods. The preconditioned problems are solved by the unrestarted GMRES method. A version of the accelerated multiplicative Schwarz method is a consistently good performer.