An iterative substructuring method for the p-version of the boundary element method for hypersingular integral operators in three dimensions

Summary. We study preconditioners for the -version of the boundary element method for hypersingular integral equations in three dimensions. The preconditioners are based on iterative substructuring of the underlying ansatz spaces which are constructed by using discretely harmonic basis functions. We consider a so-called wire basket preconditioner and a non-overlapping additive Schwarz method based on the complete natural splitting, i.e. with respect to the nodal, edge and interior functions, as well as an almost diagonal preconditioner. In any case we add the space of piecewise bilinear functions which eliminate the dependence of the condition numbers on the mesh size. For all these methods we prove that the resulting condition numbers are bounded by . Here, is the polynomial degree of the ansatz functions and is a constant which is independent of and the mesh size of the underlying boundary element mesh. Numerical experiments supporting these results are reported. Received July 8, 1996 / Revised version received January 8, 1997     

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     

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     

Schwarz alternating and iterative refinement methods for mixed formulations of elliptic problems,part I: Algorithms and numerical results

Summary We describe sequential and parallel algorithms based on the Schwarz alternating method for the solution of mixed finite element discretizations of elliptic problems using the Raviart-Thomas finite element spaces. These lead to symmetric indefinite linear systems and the algorithms have some similarities with the traditional block Gauss-Seidel or block Jacobi methods with overlapping blocks. The indefiniteness requires special treatment. The sub-blocks used in the algorithm correspond to problems on a coarse grid and some overlapping subdomains and is based on a similar partition used in an algorithm of Dryja and Widlund for standard elliptic problems. If there is sufficient overlap between the subdomains, the algorithm converges with a rate independent of the mesh size, the number of subdomains and discontinuities of the coefficients. Extensions of the above algorithms to the case of local grid refinement is also described. Convergence theory for these algorithms will be presented in a subsequent paper.This work was supported in part by the National Science Foundation under Grant NSF-CCR-8903003, while the author was a graduate student at New York University, and in part by the Army Research Office under Grant DAAL 03-91-G-0150, while the author was a Visiting Assistant Researcher at UCLA     

An overlapping domain decomposition preconditioner for a class of discontinuous Galerkin approximations of advection-diffusion problems

We consider a scalar advection-diffusion problem and a recently proposed discontinuous Galerkin approximation, which employs discontinuous finite element spaces and suitable bilinear forms containing interface terms that ensure consistency. For the corresponding sparse, nonsymmetric linear system, we propose and study an additive, two-level overlapping Schwarz preconditioner, consisting of a coarse problem on a coarse triangulation and local solvers associated to a family of subdomains. This is a generalization of the corresponding overlapping method for approximations on continuous finite element spaces. Related to the lack of continuity of our approximation spaces, some interesting new features arise in our generalization, which have no analog in the conforming case. We prove an upper bound for the number of iterations obtained by using this preconditioner with GMRES, which is independent of the number of degrees of freedom of the original problem and the number of subdomains. The performance of the method is illustrated by several numerical experiments for different test problems using linear finite elements in two dimensions.

     

Analysis of a Stokes interface problem

We consider a stationary Stokes problem with a piecewise constant viscosity coefficient. For the variational formulation of this problem we prove a well-posedness result in which the constants are uniform with respect to the jump in the viscosity coefficient. We apply a standard discretization with a pair of LBB stable finite element spaces. The main result of the paper is an infsup result for the discrete problem that is uniform with respect to the jump in the viscosity coefficient. From this we derive a robust estimate for the discretization error. We prove that the mass matrix with respect to some suitable scalar product yields a robust preconditioner for the Schur complement. Results of numerical experiments are presented that illustrate this robustness property. This author was supported by the German Research Foundation through the guest program of SFB 540     

Multigrid in H (div) and H (curl)

Summary. We consider the solution of systems of linear algebraic equations which arise from the finite element discretization of variational problems posed in the Hilbert spaces and in three dimensions. We show that if appropriate finite element spaces and appropriate additive or multiplicative Schwarz smoothers are used, then the multigrid V-cycle is an efficient solver and preconditioner for the discrete operator. All results are uniform with respect to the mesh size, the number of mesh levels, and weights on the two terms in the inner products. Received June 12, 1998 / Revised version received March 12, 1999 / Published online January 27, 2000     

Additive Schwarz method for the p-version of the boundary element method for the single layer potential operator on a plane screen

Summary. We analyze an additive Schwarz preconditioner for the p-version of the boundary element method for the single layer potential operator on a plane screen in the three-dimensional Euclidean space. We decompose the ansatz space, which consists of piecewise polynomials of degree p on a mesh of size h, by introducing a coarse mesh of size . After subtraction of the coarse subspace of piecewise constant functions on the coarse mesh this results in local subspaces of piecewise polynomials living only on elements of size H. This decomposition yields a preconditioner which bounds the spectral condition number of the stiffness matrix by . Numerical results supporting the theory are presented. Received August 15, 1998 / Revised version received November 11, 1999 / Published online December 19, 2000     

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.     

Robust iterative methods for elliptic problems with highly varying coefficients in thin substructures

Summary. In this paper we introduce a class of robust multilevel interface solvers for two-dimensional finite element discrete elliptic problems with highly varying coefficients corresponding to geometric decompositions by a tensor product of strongly non-uniform meshes. The global iterations convergence rate is shown to be of the order with respect to the number of degrees of freedom on the single subdomain boundaries, uniformly upon the coarse and fine mesh sizes, jumps in the coefficients and aspect ratios of substructures. As the first approach, we adapt the frequency filtering techniques [28] to construct robust smoothers on the highly non-uniform coarse grid. As an alternative, a multilevel averaging procedure for successive coarse grid correction is proposed and analyzed. The resultant multilevel coarse grid preconditioner is shown to have (in a two level case) the condition number independent of the coarse mesh grading and jumps in the coefficients related to the coarsest refinement level. The proposed technique exhibited high serial and parallel performance in the skin diffusion processes modelling [20] where the high dimensional coarse mesh problem inherits a strong geometrical and coefficients anisotropy. The approach may be also applied to magnetostatics problems as well as in some composite materials simulation. Received December 27, 1994     

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.     

Overlapping Schwarz preconditioners for spectral element methods in nonstandard domains and heterogeneous media

Overlapping Schwarz preconditioners are constructed and numerically studied for Gauss-Lobatto-Legendre (GLL) spectral element discretizations of heterogeneous elliptic problems on nonstandard domains defined by Gordon-Hall transfinite mappings. The results of several test problems in the plane show that the proposed preconditioners retain the good convergence properties of overlapping Schwarz preconditioners for standard affine GLL spectral elements, i.e. their convergence rate is independent of the number of subdomains, of the spectral degree in the case of generous overlap and of the discontinuity jumps in the coefficients of the elliptic operator, while in the case of small overlap, the convergence rate depends on the inverse of the overlap size.     

Fourier analysis of a robust multigrid method for convection-diffusion equations

Summary. We consider a two-grid method for solving 2D convection-diffusion problems. The coarse grid correction is based on approximation of the Schur complement. As a preconditioner of the Schur complement we use the exact Schur complement of modified fine grid equations. We assume constant coefficients and periodic boundary conditions and apply Fourier analysis. We prove an upper bound for the spectral radius of the two-grid iteration matrix that is smaller than one and independent of the mesh size, the convection/diffusion ratio and the flow direction; i.e. we have a (strong) robustness result. Numerical results illustrating the robustness of the corresponding multigrid -cycle are given. Received October 14, 1994     

A two-level additive Schwarz preconditioner for nonconforming plate elements

Summary. A two-level additive Schwarz preconditioner is developed for the systems resulting from the discretizations of the plate bending problem by the Morley finite element, the Fraeijs de Veubeke finite element, the Zienkiewicz finite element and the Adini finite element. The condition numbers of the preconditioned systems are shown to be bounded independent of mesh sizes and the number of subdomains in the case of a generous overlap. Received February 1, 1994 / Revised version received October 24, 1994     

An additive Schwarz preconditioner for p-version boundary element approximation of the hypersingular operator in three dimensions

Summary. Additive Schwarz preconditioners are developed for the p-version of the boundary element method for the hypersingular integral equation on surfaces in three dimensions. The principal preconditioner consists of decomposing the subspace into local spaces associated with the element interiors supplemented with a wirebasket space associated with the the element interfaces. The wirebasket correction involves inverting a diagonal matrix. If exact solvers are used on the element interiors then theoretical analysis shows that growth of the condition number of the preconditioned system is bounded by for an open surface and for a closed surface. A modified form of the preconditioner only requires the inversion of a diagonal matrix but results in a further degradation of the condition number by a factor . Received December 15, 1998 / Revised version received March 26, 1999 / Published online March 16, 2000     

Two-level additive Schwarz preconditioners for C 0 interior penalty methods

We study two-level additive Schwarz preconditioners that can be used in the iterative solution of the discrete problems resulting from C⁰ interior penalty methods for fourth order elliptic boundary value problems. We show that the condition number of the preconditioned system is bounded by C(1+(H³/δ³)), where H is the typical diameter of a subdomain, δ measures the overlap among the subdomains and the positive constant C is independent of the mesh sizes and the number of subdomains. This work was supported in part by the National Science Foundation under Grant No. DMS-03-11790.     

Schwarz preconditioners for the spectral element discretization of the steady Stokes and Navier-Stokes equations

Summary. The - spectral element discretization of the Stokes equation gives rise to an ill-conditioned, indefinite, symmetric linear system for the velocity and pressure degrees of freedom. We propose a domain decomposition method which involves the solution of a low-order global, and several local problems, related to the vertices, edges, and interiors of the subdomains. The original system is reduced to a symmetric equation for the velocity, which can be solved with the conjugate gradient method. We prove that the condition number of the iteration operator is bounded from above by , where C is a positive constant independent of the degree N and the number of subdomains, and is the inf-sup condition of the pair -. We also consider the stationary Navier-Stokes equations; in each Newton step, a non-symmetric indefinite problem is solved using a Schwarz preconditioner. By using an especially designed low-order global space, and the solution of local problems analogous to those decribed above for the Stokes equation, we are able to present a complete theory for the method. We prove that the number of iterations of the GMRES method, at each Newton step, is bounded from above by . The constant C does not depend on the number of subdomains or N, and it does not deteriorate as the Newton iteration proceeds. Received March 2, 1998 / Revised version received October 12, 1999 / Published online March 20, 2001     

Schwarz preconditioned CG algorithm for the mortar finite element

We propose a simple and effective hybrid (multiplicative) Schwarz precondtioner for solving systems of algebraic equations resulting from the mortar finite element discretization of second order elliptic problems on nonmatching meshes. The preconditioner is embedded in a variant of the classical preconditioned conjugate gradient (PCG) for an effective implementation reducing the cost of computing the matrix-vector multiplication in each iteration of the PCG. In fact, it serves as a framework for effective implementation of a class of hybrid Schwarz preconditioners. The preconditioners of this class are based on solving a sequence of non-overlapping local subproblems exactly, and the coarse problems either exactly or inexactly (approximately). The classical PCG algorithm is reformulated in order to make reuse of the results of matrix-vector multiplications that are already available from the preconditioning step resulting in an algorithm which is cost effective. An analysis of the proposed preconditioner, with numerical results, showing scalability with respect to the number of subdomains, and a convergence which is independent of the jumps of the coefficients are given.     

非嵌套网格上的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）等…     

Additive Schwarz algorithms for the p version of the Galerkin boundary element method

Summary. We study some additive Schwarz algorithms for the version Galerkin boundary element method applied to some weakly singular and hypersingular integral equations of the first kind. Both non-overlapping and overlapping methods are considered. We prove that the condition numbers of the additive Schwarz operators grow at most as independently of h, where p is the degree of the polynomials used in the Galerkin boundary element schemes and h is the mesh size. Thus we show that additive Schwarz methods, which were originally designed for finite element discretisation of differential equations, are also efficient preconditioners for some boundary integral operators, which are non-local operators. Received June 15, 1997 / Revised version received July 7, 1998 / Published online February 17, 2000