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     

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     

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     

Wavelet approximations for first kind boundary integral equations on polygons

Summary. An elliptic boundary value problem in the interior or exterior of a polygon is transformed into an equivalent first kind boundary integral equation. Its Galerkin discretization with degrees of freedom on the boundary with spline wavelets as basis functions is analyzed. A truncation strategy is presented which allows to reduce the number of nonzero elements in the stiffness matrix from to entries. The condition numbers are bounded independently of the meshwidth. It is proved that the compressed scheme thus obtained yields in operations approximate solutions with the same asymptotic convergence rates as the full Galerkin scheme in the boundary energy norm as well as in interior points. Numerical examples show the asymptotic error analysis to be valid already for moderate values of . Received March 12, 1994 / Revised version received January 9, 1995     

On the convergence of a dual-primal substructuring method

Summary.   In the Dual-Primal FETI method, introduced by Farhat et al. [5], the domain is decomposed into non-overlapping subdomains, but the degrees of freedom on crosspoints remain common to all subdomains adjacent to the crosspoint. The continuity of the remaining degrees of freedom on subdomain interfaces is enforced by Lagrange multipliers and all degrees of freedom are eliminated. The resulting dual problem is solved by preconditioned conjugate gradients. We give an algebraic bound on the condition number, assuming only a single inequality in discrete norms, and use the algebraic bound to show that the condition number is bounded by for both second and fourth order elliptic selfadjoint problems discretized by conforming finite elements, as well as for a wide class of finite elements for the Reissner-Mindlin plate model. Received January 20, 2000 / Revised version received April 25, 2000 / Published online December 19, 2000     

Schwarz methods with local refinement for the p-version finite element method

Summary. In some applications, the accuracy of the numerical solution of an elliptic problem needs to be increased only in certain parts of the domain. In this paper, local refinement is introduced for an overlapping additive Schwarz algorithm for the $-version finite element method. Both uniform and variable degree refinements are considered. The resulting algorithm is highly parallel and scalable. In two and three dimensions, we prove an optimal bound for the condition number of the iteration operator under certain hypotheses on the refinement region. This bound is independent of the degree $, the number of subdomains $ and the mesh size $. In the general two dimensional case, we prove an almost optimal bound with polylogarithmic growth in $. Received February 20, 1993 / Revised version received January 20, 1994     

Bounds on spectral condition numbers of matrices arising in the p-version of the finite element method

Summary. We estimate condition numbers of -version matrices for tensor product elements with two choices of reference element degrees of freedom. In one case (Lagrange elements) the condition numbers grow exponentially in , whereas in the other (hierarchical basis functions based on Tchebycheff polynomials) the condition numbers grow rapidly but only algebraically in . We conjecture that regardless of the choice of basis the condition numbers grow like or faster, where is the dimension of the spatial domain. Received August 8, 1992 / Revised version received March 25, 1994     

A two-level domain decomposition method for the iterative solution of high frequency exterior Helmholtz problems

Summary. We present a Lagrange multiplier based two-level domain decomposition method for solving iteratively large-scale systems of equations arising from the finite element discretization of high-frequency exterior Helmholtz problems. The proposed method is essentially an extension of the regularized FETI (Finite Element Tearing and Interconnecting) method to indefinite problems. Its two key ingredients are the regularization of each subdomain matrix by a complex interface lumped mass matrix, and the preconditioning of the interface problem by an auxiliary coarse problem constructed to enforce at each iteration the orthogonality of the residual to a set of carefully chosen planar waves. We show numerically that the proposed method is scalable with respect to the mesh size, the subdomain size, and the wavenumber. We report performance results for a submarine application that highlight the efficiency of the proposed method for the solution of high frequency acoustic scattering problems discretized by finite elements. Received March 17, 1998 / Revised version received June 7, 1999 / Published online January 27, 2000     

Discrete boundary element methods on general meshes in 3D

Abstract. This paper is concerned with the stability and convergence of fully discrete Galerkin methods for boundary integral equations on bounded piecewise smooth surfaces in . Our theory covers equations with very general operators, provided the associated weak form is bounded and elliptic on , for some . In contrast to other studies on this topic, we do not assume our meshes to be quasiuniform, and therefore the analysis admits locally refined meshes. To achieve such generality, standard inverse estimates for the quasiuniform case are replaced by appropriate generalised estimates which hold even in the locally refined case. Since the approximation of singular integrals on or near the diagonal of the Galerkin matrix has been well-analysed previously, this paper deals only with errors in the integration of the nearly singular and smooth Galerkin integrals which comprise the dominant part of the matrix. Our results show how accurate the quadrature rules must be in order that the resulting discrete Galerkin method enjoys the same stability properties and convergence rates as the true Galerkin method. Although this study considers only continuous piecewise linear basis functions on triangles, our approach is not restricted in principle to this case. As an example, the theory is applied here to conventional “triangle-based” quadrature rules which are commonly used in practice. A subsequent paper [14] introduces a new and much more efficient “node-based” approach and analyses it using the results of the present paper. Received December 10, 1997 / Revised version received May 26, 1999 / Published online April 20, 2000 –? Springer-Verlag 2000     

On a hybrid boundary element method

Summary. In this paper we study a symmetric boundary element method based on a hybrid discretization of the Steklov–Poincaré operator well suited for a symmetric coupling of finite and boundary elements. The representation used involves only single and double layer potentials and does not require the discretization of the hypersingular integral operator as in the symmetric formulation. The stability of the hybrid Galerkin discretization is based on a BBL–like stability condition for the trial spaces. Numerical examples confirm the theoretical results. Received December 15, 1997 / Revised version received December 21, 1998/ Published online November 17, 1999     

A preconditioner for the h-p version of the finite element method in two dimensions

Summary. A preconditioner, based on a two-level mesh and a two-level orthogonalization, is proposed for the - version of the finite element method for two dimensional elliptic problems in polygonal domains. Its implementation is in parallel on the subdomain level for the linear or bilinear (nodal) modes, and in parallel on the element level for the high order (side and internal) modes. The condition number of the preconditioned linear system is of order , where is the diameter of the -th subdomain, and are the diameter of elements and the maximum polynomial degree used in the subdomain. This result reduces to well-known results for the -version (i.e. ) and the -version (i.e. ) as the special cases of the - version. Received August 15, 1995 / Revised version received November 13, 1995     

The approximation theory for the p-version finite element method and application to non-linear elliptic PDEs

Approximation theoretic results are obtained for approximation using continuous piecewise polynomials of degree p on meshes of triangular and quadrilateral elements. Estimates for the rate of convergence in Sobolev spaces , are given. The results are applied to estimate the rate of convergence when the p-version finite element method is used to approximate the -Laplacian. It is shown that the rate of convergence of the p-version is always at least that of the h-version (measured in terms of number of degrees of freedom used). If the solution is very smooth then the p-version attains an exponential rate of convergence. If the solution has certain types of singularity, the rate of convergence of the p-version is twice that of the h-version. The analysis generalises the work of Babuska and others to the case . In addition, the approximation theoretic results find immediate application for some types of spectral and spectral element methods. Received August 2, 1995 / Revised version received January 26, 1998     

Wavelet adaptive method for second order elliptic problems: boundary conditions and domain decomposition

Summary. Wavelet methods allow to combine high order accuracy, multilevel preconditioning techniques and adaptive approximation, in order to solve efficiently elliptic operator equations. One of the main difficulty in this context is the efficient treatment of non-homogeneous boundary conditions. In this paper, we propose a strategy that allows to append such conditions in the setting of space refinement (i.e. adaptive) discretizations of second order problems. Our method is based on the use of compatible multiscale decompositions for both the domain and its boundary, and on the possibility of characterizing various function spaces from the numerical properties of these decompositions. In particular, this allows the construction of a lifting operator which is stable for a certain range of smoothness classes, and preserves the compression of the solution in the wavelet basis. An explicit construction of the wavelet bases and the lifting is proposed on fairly general domains, based on conforming domain decomposition techniques. Received November 2, 1998 / Published online April 20, 2000     

Overlapping Schwarz methods for Maxwell's equations in three dimensions

Summary. A two-level overlapping Schwarz method is considered for a Nédélec finite element approximation of 3D Maxwell's equations. For a fixed relative overlap, the condition number of the method is bounded, independently of the mesh size of the triangulation and the number of subregions. Our results are obtained with the assumption that the coarse triangulation is quasi-uniform and, for the Dirichlet problem, that the domain is convex. Our work generalizes well–known results for conforming finite elements for second order elliptic scalar equations. Numerical results for one and two-level algorithms are also presented. Received November 11, 1997 / Revised version received May 26, 1999 / Published online June 21, 2000     

Convergence of a substructuring method with Lagrange multipliers

Summary. We analyze the convergence of a substructuring iterative method with Lagrange multipliers, proposed recently by Farhat and Roux. The method decomposes finite element discretization of an elliptic boundary value problem into Neumann problems on the subdomains plus a coarse problem for the subdomain nullspace components. For linear conforming elements and preconditioning by the Dirichlet problems on the subdomains, we prove the asymptotic bound on the condition number , or ,where is the characteristic element size and subdomain size. Received January 3, 1995     

Exponential convergence of the hp-version for the boundary element method on open surfaces

Summary. We analyze the boundary element Galerkin method for weakly singular and hypersingular integral equations of the first kind on open surfaces. We show that the hp-version of the Galerkin method with geometrically refined meshes converges exponentially fast for both integral equations. The proof of this fast convergence is based on the special structure of the solutions of the integral equations which possess specific singularities at the corners and the edges of the surface. We show that these singularities can be efficiently approximated by piecewise tensor products of splines of different degrees on geometrically graded meshes. Numerical experiments supporting these results are presented. Received December 19, 1996 / Revised version received September 24, 1997 / Published online August 19, 1999     

Boundary element methods for Maxwell's equations on non-smooth domains

Summary. Variational boundary integral equations for Maxwell's equations on Lipschitz surfaces in are derived and their well-posedness in the appropriate trace spaces is established. An equivalent, stable mixed reformulation of the system of integral equations is obtained which admits discretization by Galerkin boundary elements based on standard spaces. On polyhedral surfaces, quasioptimal asymptotic convergence of these Galerkin boundary element methods is proved. A sharp regularity result for the surface multipliers on polyhedral boundaries with plane faces is established. Received January 5, 2001 / Revised version received August 6, 2001 / Published online December 18, 2001 Correspondence to: C. Schwab     

An unusual stabilized finite element method for a generalized Stokes problem

Summary. An unusual stabilized finite element is presented and analyzed herein for a generalized Stokes problem with a dominating zeroth order term. The method consists in subtracting a mesh dependent term from the formulation without compromising consistency. The design of this mesh dependent term, as well as the stabilization parameter involved, are suggested by bubble condensation. Stability is proven for any combination of velocity and pressure spaces, under the hypotheses of continuity for the pressure space. Optimal order error estimates are derived for the velocity and the pressure, using the standard norms for these unknowns. Numerical experiments confirming these theoretical results, and comparisons with previous methods are presented. Received April 26, 2001 / Revised version received July 30, 2001 / Published online October 17, 2001 Correspondence to: Gabriel R. Barrenechea     

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     

$C^1$ error estimation on the boundary for an exterior Neumann problem in $\mathbb R^3$

Summary.   In this paper we establish a error estimation on the boundary for the solution of an exterior Neumann problem in . To solve this problem we consider an integral representation which depends from the solution of a boundary integral equation. We use a full piecewise linear discretisation which on one hand leads to a simple numerical algorithm but on the other hand the error analysis becomes more difficult due to the singularity of the integral kernel. We construct a particular approximation for the solution of the boundary integral equation, for the solution of the Neumann problem and its gradient on the boundary and estimate their error. Received May 11, 1998 / Revised version received July 7, 1999 / Published online August 24, 2000