On Schwarz's domain decomposition methods for elliptic boundary value problems

Summary. We study the additive and multiplicative Schwarz domain decomposition methods for elliptic boundary value problem of order 2 r based on an appropriate spline space of smoothness . The finite element method reduces an elliptic boundary value problem to a linear system of equations. It is well known that as the number of triangles in the underlying triangulation is increased, which is indispensable for increasing the accuracy of the approximate solution, the size and condition number of the linear system increases. The Schwarz domain decomposition methods will enable us to break the linear system into several linear subsystems of smaller size. We shall show in this paper that the approximate solutions from the multiplicative Schwarz domain decomposition method converge to the exact solution of the linear system geometrically. We also show that the additive Schwarz domain decomposition method yields a preconditioner for the preconditioned conjugate gradient method. We tested these methods for the biharmonic equation with Dirichlet boundary condition over an arbitrary polygonal domain using cubic spline functions over a quadrangulation of the given domain. The computer experiments agree with our theoretical results. Received December 28, 1995 / Revised version received November 17, 1998 / Published online September 24, 1999     

基于几何非协调分解的Lagrange乘子区域分解方法

本文考虑将Lagrange乘子区域分解方法应用于几何非协调分解的情况来求解二阶椭圆问题.由于采用几何非协调区域分解,每个局部乘子空间关联到多个界面,我们按照一定的规则选取合适的乘子面来定义乘子空间.利用局部正则化技巧,可以消去内部变量,得到关于Lagrange乘子的界面方程.采用一种经济的预条件迭代方法求解界面方程,且相关的预条件子是可扩展的.     

A preconditioned domain decomposition algorithm for the solution of the elliptic Neumann problem

A new preconditioned conjugate gradient (PCG)-based domain decomposition method is given for the solution of linear equations arising in the finite element method applied to the elliptic Neumann problem. The novelty of the proposed method is in the recommended preconditioner which is constructed by using cyclic matrix. The resulting preconditioned algorithms are well suited to parallel computation.     

Preconditioned iterative methods on sparse subspaces

When some rows of the system matrix and a preconditioner coincide, preconditioned iterations can be reduced to a sparse subspace. Taking advantage of this property can lead to considerable memory and computational savings. This is particularly useful with the GMRES method. We consider the iterative solution of a discretized partial differential equation on this sparse subspace. With a domain decomposition method and a fictitious domain method the subspace corresponds a small neighborhood of an interface. As numerical examples we solve the Helmholtz equation using a fictitious domain method and an elliptic equation with a jump in the diffusion coefficient using a separable preconditioner.     

Suitable iterative methods for solving the linear system arising in the three fields domain decomposition method

There are two approaches for applying substructuring preconditioner for the linear system corresponding to the discrete Steklov–Poincaré operator arising in the three fields domain decomposition method for elliptic problems. One of them is to apply the preconditioner in a common way, i.e. using an iterative method such as preconditioned conjugate gradient method [S. Bertoluzza, Substructuring preconditioners for the three fields domain decomposition method, I.A.N.-C.N.R, 2000] and the other one is to apply iterative methods like for instance bi-conjugate gradient method, conjugate gradient square and etc. which are efficient for nonsymmetric systems (the preconditioned system will be nonsymmetric). In this paper, second approach will be followed and extensive numerical tests will be presented which imply that the considered iterative methods are efficient.     

Multiscale Domain Decomposition Methods for Elliptic Problems with High Aspect Ratios

Abstract In this paper we study some nonoverlapping domain decomposition methods for solving a classof elliptic problems arising from composite materials and flows in porous media which contain many spatialscales. Our preconditioner differs from traditional domain decomposition preconditioners by using a coarsesolver which is adaptive to small scale heterogeneous features. While the convergence rate of traditional domaindecomposition algorithms using coarse solvers based on linear or polynomial interpolations may deteriorate inthe presence of rapid small scale oscillations or high aspect ratios, our preconditioner is applicable to multiple-scale problems without restrictive assumptions and seems to have a convergence rate nearly independent ofthe aspect ratio within the substructures. A rigorous convergence analysis based on the Schwarz framework iscarried out, and we demonstrate the efficiency and robustness of the proposed preconditioner through numericalexperiments which include problems with multipl     

Substructured two-grid and multi-grid domain decomposition methods

Two-level Schwarz domain decomposition methods are very powerful techniques for the efficient numerical solution of partial differential equations (PDEs). A two-level domain decomposition method requires two main components: a one-level preconditioner (or its corresponding smoothing iterative method), which is based on domain decomposition techniques, and a coarse correction step, which relies on a coarse space. The coarse space must properly represent the error components that the chosen one-level method is not capable to deal with. In the literature, most of the works introduced efficient coarse spaces obtained as the span of functions defined on the entire space domain of the considered PDE. Therefore, the corresponding two-level preconditioners and iterative methods are defined in volume. In this paper, we use the excellent smoothing properties of Schwarz domain decomposition methods to define, for general elliptic problems, a new class of substructured two-level methods, for which both Schwarz smoothers and coarse correction steps are defined on the interfaces (except for the application of the smoother that requires volumetric subdomain solves). This approach has several advantages. On the one hand, the required computational effort is cheaper than the one required by classical volumetric two-level methods. On the other hand, our approach does not require, like classical multi-grid methods, the explicit construction of coarse spaces, and it permits a multilevel extension, which is desirable when the high dimension of the problem or the scarce quality of the coarse space prevents the efficient numerical solution. Numerical experiments demonstrate the effectiveness of the proposed new numerical framework.

     

Domain decomposition method and elastic multi-structures: The stiffened plate problem

Summary Domain decomposition methods allow faster solution of partial differential equations in many cases. The efficiency of these methods mainly depends on the variables and operators chosen for the coupling between the subdomains; it is the preconditioning problem. In the modeling of multistructures, the partial differential equations have some specific properties that must be taken into account in a domain decomposition method. Different kinds of elliptic problems modeling stiffened plates in linearized elasticity are compared. One of them is remarkable as far as domain decomposition is concerned, since it is possible to associate particularly efficient preconditioner. A theoretical estimate for the conditioning is given, which is confirmed by several numerical experiments.     

A balancing domain decomposition by constraints preconditioner for a weakly over‐penalized symmetric interior penalty method

We develop a balancing domain decomposition by constraints preconditioner for a weakly over‐penalized symmetric interior penalty method for second‐order elliptic problems. We show that the condition number of the preconditioned system satisfies similar estimates as those for conforming finite element methods. Corroborating numerical results are also presented. Copyright © 2012 John Wiley & Sons, Ltd.     

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.     

An alternating preconditioner for saddle point problems

Based on matrix splittings, a new alternating preconditioner with two parameters is proposed for solving saddle point problems. Some theoretical analyses for the eigenvalues of the associated preconditioned matrix are given. The choice of the parameters is considered and the quasi-optimal parameters are obtained. The new preconditioner with these quasi-optimal parameters significantly improves the convergence rate of the generalized minimal residual (GMRES) iteration. Numerical experiments from the linearized Navier-Stokes equations demonstrate the efficiency of the new preconditioner, especially on the larger viscosity parameter ν. Further extensions of the preconditioner to generalized saddle point matrices are also checked.     

Applications of a space decomposition method to linear and nonlinear elliptic problems

This work presents some space decomposition algorithms for a convex minimization problem. The algorithms has linear rate of convergence and the rate of convergence depends only on four constants. The space decomposition could be a multigrid or domain decomposition method. We explain the detailed procedure to implement our algorithms for a two-level overlapping domain decomposition method and estimate the needed constants. Numerical tests are reported for linear as well as nonlinear elliptic problems. © 1998 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 14: 717–737, 1998     

Analysis of optimal preconditioners for CutFEM

In this article, we consider a class of unfitted finite element methods for scalar elliptic problems. These so-called CutFEM methods use standard finite element spaces on a fixed unfitted triangulation combined with the Nitsche technique and a ghost penalty stabilization. As a model problem we consider the application of such a method to the Poisson interface problem. We introduce and analyze a new class of preconditioners that is based on a subspace decomposition approach. The unfitted finite element space is split into two subspaces, where one subspace is the standard finite element space associated to the background mesh and the second subspace is spanned by all cut basis functions corresponding to nodes on the cut elements. We will show that this splitting is stable, uniformly in the discretization parameter and in the location of the interface in the triangulation. Based on this we introduce an efficient preconditioner that is uniformly spectrally equivalent to the stiffness matrix. Using a similar splitting, it is shown that the same preconditioning approach can also be applied to a fictitious domain CutFEM discretization of the Poisson equation. Results of numerical experiments are included that illustrate optimality of such preconditioners for the Poisson interface problem and the Poisson fictitious domain problem.     

Convergence rate analysis of an asynchronous space decomposition method for convex minimization

We analyze the convergence rate of an asynchronous space decomposition method for constrained convex minimization in a reflexive Banach space. This method includes as special cases parallel domain decomposition methods and multigrid methods for solving elliptic partial differential equations. In particular, the method generalizes the additive Schwarz domain decomposition methods to allow for asynchronous updates. It also generalizes the BPX multigrid method to allow for use as solvers instead of as preconditioners, possibly with asynchronous updates, and is applicable to nonlinear problems. Applications to an overlapping domain decomposition for obstacle problems are also studied. The method of this work is also closely related to relaxation methods for nonlinear network flow. Accordingly, we specialize our convergence rate results to the above methods. The asynchronous method is implementable in a multiprocessor system, allowing for communication and computation delays among the processors.

     

The generalized HSS method for solving singular linear systems

For the singular, non-Hermitian, and positive semidefinite linear systems, we propose an alternating-direction iterative method with two parameters based on the Hermitian and skew-Hermitian splitting. The semi-convergence analysis and the quasi-optimal parameters of the proposed method are discussed. Moreover, the corresponding preconditioner based on the splitting is given to improve the semi-convergence rate of the GMRES method. Numerical examples are given to illustrate the theoretical results and the efficiency of the generalized HSS method either as a solver or a preconditioner for GMRES.     

On a Toeplitz Representation of the H1/2 Norm

Some representations of the H1/2 norm are used as Schur complement preconditioner in PCG based domain decomposition algorithms for elliptic problems. These norm representations are efficient preconditioners but the corresponding matrices are dense, so they need FFT algorithm for matrix-vector multiplications. Here we give a new matrix representation of this norm by a special Toeplitz matrix. It contains only O(log(n)) different entries at each row, where n is the number of rows and so a matrix-vector computation can be done by O(nlog(n)) arithmetic operation without using FFT algorithm. The special properties of this matrix assure that it can be used as preconditioner. This is proved by estimating spectral equivalence constants and this fact has also been verified by numerical tests.     

A robust hierarchical basis preconditioner on general meshes

Summary. In this paper, we introduce a multi-level direct sum space decomposition of general, possibly locally refined linear or multi-linear finite element spaces. The resulting additive Schwarz preconditioner is optimal for symmetric second order elliptic problems. Moreover, it turns out to be robust with respect to coefficient jumps over edges in the coarsest mesh, perturbations with positive zeroth order terms, and, after a further decomposition of the spaces, also with respect to anisotropy along the grid lines. Important for an efficient implementation is that stable bases of the subspaces defining our decomposition, consisting of functions having small supports can be easily constructed. Received September 8, 1995 / Revised version received October 31, 1996     

Trace Averaging Domain Decomposition Method with Nonconforming Finite Elements

1.IntroductionDomaindec0mpositionreferstonumericaJmethodsf0robtainingsoluti0nsofsci-entificandengineeringproblemsbycombiningsoluti0nstoproblemspo8ed0nphysica1subdomains,or,moregeneraJly,byc0mbiningsoluti0nst0appropriatelyconstructedsubproblems.IthasbeenasubjectofintenseinterestreceDtlybecause0fitssultabil-ityforimplementationonhighperformancecomputerarchitectures.Somepapersarelistedinthereferencesherein,wlilchindicatethatmuchprogresshasbeenmadeinthestudyofnonoverlaPdomaindecompositionmethods…     

Nonoverlapping Domain Decomposition Method with Mixed Element for Elliptic Problems

1.IntroductionDomaindecompositionasanewmethodofcomputationalmathematics,waJsdevel-opedsincethedevelopmentofparallelcomputersandmultiprocessorsupercomputers-Usingdomaindecompositionwecandecreasethescaleoftheproblemandimplementthesub-problemsonparallelcomputer.Fromatechnicalpointofviewmostofdo-maindecompositionmethodsconsideredsofarhavebeendealingwithfiniteelementmethods.In[1,2]ZhangandHuanghavegivenakindofnonoverlappingdomaindecompositionprocedurewithpiecewiselinearfiniteelementapproximation.…     

A robust optimal preconditioner for the mixed finite element discretization of elliptic optimal control problems

In this paper, we consider the efficient solving of the resulting algebraic system for elliptic optimal control problems with mixed finite element discretization. We propose a block‐diagonal preconditioner for the symmetric and indefinite algebraic system solved with minimum residual method, which is proved to be robust and optimal with respect to both the mesh size and the regularization parameter. The block‐diagonal preconditioner is constructed based on an isomorphism between appropriately chosen solution space and its dual for a general control problem with both state and gradient state observations in the objective functional. Numerical experiments confirm the efficiency of our proposed preconditioner.