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     

A second-order hybrid finite difference scheme for a system of singularly perturbed initial value problems

A system of coupled singularly perturbed initial value problems with two small parameters is considered. The leading term of each equation is multiplied by a small positive parameter, but these parameters may have different magnitudes. The solution of the system has boundary layers that overlap and interact. The structure of these layers is analyzed, and this leads to the construction of a piecewise-uniform mesh that is a variant of the usual Shishkin mesh. On this mesh a hybrid finite difference scheme is proved to be almost second-order accurate, uniformly in both small parameters. Numerical results supporting the theory are presented.     

Stability and accuracy of adapted finite element methods for singularly perturbed problems

The stability and accuracy of a standard finite element method (FEM) and a new streamline diffusion finite element method (SDFEM) are studied in this paper for a one dimensional singularly perturbed connvection-diffusion problem discretized on arbitrary grids. Both schemes are proven to produce stable and accurate approximations provided that the underlying grid is properly adapted to capture the singularity (often in the form of boundary layers) of the solution. Surprisingly the accuracy of the standard FEM is shown to depend crucially on the uniformity of the grid away from the singularity. In other words, the accuracy of the adapted approximation is very sensitive to the perturbation of grid points in the region where the solution is smooth but, in contrast, it is robust with respect to perturbation of properly adapted grid inside the boundary layer. Motivated by this discovery, a new SDFEM is developed based on a special choice of the stabilization bubble function. The new method is shown to have an optimal maximum norm stability and approximation property in the sense that where u _N is the SDFEM approximation in linear finite element space V ^N of the exact solution u. Finally several optimal convergence results for the standard FEM and the new SDFEM are obtained and an open question about the optimal choice of the monitor function for the moving grid method is answered. This work was supported in part by NSF DMS-0209497 and NSF DMS-0215392 and the Changjiang Professorship through Peking University.     

On the stability of the $L_2$ projection in fractional Sobolev spaces

Summary.   In this paper we prove the stability of the projection onto the finite element trial space of piecewise polynomial, in particular, piecewise linear basis functions in for . We formulate explicit and computable local mesh conditions to be satisfied which depend on the Sobolev index s. In conclusion we prove a stability condition needed in the numerical analysis of mixed and hybrid boundary element methods as well as in the construction of efficient preconditioners in adaptive boundary and finite element methods. Received October 14, 1999 / Revised version received March 24, 2000 / Published online October 16, 2000     

Multilevel diagonal scaling preconditioners for boundary element equations on locally refined meshes

Summary. We study a multilevel preconditioner for the Galerkin boundary element matrix arising from a symmetric positive-definite bilinear form. The associated energy norm is assumed to be equivalent to a Sobolev norm of positive, possibly fractional, order m on a bounded (open or closed) surface of dimension d, with . We consider piecewise linear approximation on triangular elements. Successive levels of the mesh are created by selectively subdividing elements within local refinement zones. Hanging nodes may be created and the global mesh ratio can grow exponentially with the number of levels. The coarse-grid correction consists of an exact solve, and the correction on each finer grid amounts to a simple diagonal scaling involving only those degrees of freedom whose associated nodal basis functions overlap the refinement zone. Under appropriate assumptions on the choice of refinement zones, the condition number of the preconditioned system is shown to be bounded by a constant independent of the number of degrees of freedom, the number of levels and the global mesh ratio. In addition to applying to Galerkin discretisation of hypersingular boundary integral equations, the theory covers finite element methods for positive-definite, self-adjoint elliptic problems with Dirichlet boundary conditions. Received October 5, 2001 / Revised version received December 5, 2001 / Published online April 17, 2002 The support of this work through Visiting Fellowship grant GR/N21970 from the Engineering and Physical Sciences Research Council of Great Britain is gratefully acknowledged. The second author was also supported by the Australian Research Council     

Fast parallel solvers for symmetric boundary element domain decomposition equations

Summary. The boundary element method (BEM) is of advantage in many applications including far-field computations in magnetostatics and solid mechanics as well as accurate computations of singularities. Since the numerical approximation is essentially reduced to the boundary of the domain under consideration, the mesh generation and handling is simpler than, for example, in a finite element discretization of the domain. In this paper, we discuss fast solution techniques for the linear systems of equations obtained by the BEM (BE-equations) utilizing the non-overlapping domain decomposition (DD). We study parallel algorithms for solving large scale Galerkin BE–equations approximating linear potential problems in plane, bounded domains with piecewise homogeneous material properties. We give an elementary spectral equivalence analysis of the BEM Schur complement that provides the tool for constructing and analysing appropriate preconditioners. Finally, we present numerical results obtained on a massively parallel machine using up to 128 processors, and we sketch further applications to elasticity problems and to the coupling of the finite element method (FEM) with the boundary element method. As shown theoretically and confirmed by the numerical experiments, the methods are of algebraic complexity and of high parallel efficiency, where denotes the usual discretization parameter. Received August 28, 1996 / Revised version received March 10, 1997     

A boundary multiplier/fictitious domain method for the steady incompressible Navier-Stokes equations

Summary. We analyze the error of a fictitious-domain method with boundary Lagrange multiplier. It is applied to solve a non-homogeneous steady incompressible Navier-Stokes problem in a domain with a multiply-connected boundary. The interior mesh in the fictitious domain and the boundary mesh are independent, up to a mesh-length ratio. Received February 24, 1999 / Revised version received January 30, 2000 / Published online October 16, 2000     

A primal mixed formulation for exterior transmission problems in ${\bf R}^2$

Summary.   We combine a primal mixed finite element approach with a Dirichlet-to-Neumann mapping (arising from the boundary integral equation method) to study the weak solvability and Galerkin approximations of a class of linear exterior transmission problems in potential theory. Our results are mainly based on the Babuska-Brezzi theory for variational problems with constraints. We establish the uniqueness of solution for the continuous and discrete formulations, and show that finite element subspac es of Lagrange type satisfy the discrete compatibility conditions. In addition, we provide the error analysis, including polygonal approximations of the domain, and prove strong convergence of the Galerkin solutions. Moreover, under additional regularity assumptions on the solution of the continuous formulation, we obtain the asymptotic rate of convergence O(h). Received August 25, 1998 / Revised version received March 8, 2000 / Published online October 16, 2000     

Convergence analysis of a multigrid method for convection–diffusion equations

Summary. This paper is concerned with the convergence analysis of robust multigrid methods for convection-diffusion problems. We consider a finite difference discretization of a 2D model convection-diffusion problem with constant coefficients and Dirichlet boundary conditions. For the approximate solution of this discrete problem a multigrid method based on semicoarsening, matrix-dependent prolongation and restriction and line smoothers is applied. For a multigrid W-cycle we prove an upper bound for the contraction number in the euclidean norm which is smaller than one and independent of the mesh size and the diffusion/convection ratio. For the contraction number of a multigrid V-cycle a bound is proved which is uniform for a class of convection-dominated problems. The analysis is based on linear algebra arguments only. Received April 26, 2000 / Published online June 20, 2001     

A cascadic multigrid algorithm for semilinear elliptic problems

Summary. We propose a cascadic multigrid algorithm for a semilinear elliptic problem. The nonlinear equations arising from linear finite element discretizations are solved by Newton's method. Given an approximate solution on the coarsest grid on each finer grid we perform exactly one Newton step taking the approximate solution from the previous grid as initial guess. The Newton systems are solved iteratively by an appropriate smoothing method. We prove that the algorithm yields an approximate solution within the discretization error on the finest grid provided that the start approximation is sufficiently accurate and that the initial grid size is sufficiently small. Moreover, we show that the method has multigrid complexity. Received February 12, 1998 / Revised version received July 22, 1999 / Published online June 8, 2000     

A finite volume method based on the Crouzeix–Raviart element for elliptic PDE's in two dimensions

We introduce and analyse a finite volume method for the discretization of elliptic boundary value problems in . The method is based on nonuniform triangulations with piecewise linear nonconforming spaces. We prove optimal order error estimates in the –norm and a mesh dependent –norm. Received September 10, 1997 / Revised version received March 18, 1998     

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     

Continuous-discontinuous finite element method for convection-diffusion problems with characteristic layers

We study convergence properties of a numerical method for convection-diffusion problems with characteristic layers on a layer-adapted mesh. The method couples standard Galerkin with an h-version of the nonsymmetric discontinuous Galerkin finite element method with bilinear elements. In an associated norm, we derive the error estimate as well as the supercloseness result that are uniform in the perturbation parameter. Applying a post-processing operator for the discontinuous Galerkin method, we construct a new numerical solution with enhanced convergence properties.     

A trapping principle and convergence result for finite element approximate solutions of steady reaction/diffusion systems

We consider nonlinear elliptic systems, with mixed boundary conditions, on a convex polyhedral domain Ω ⊂ R ^N . These are nonlinear divergence form generalizations of Δu = f(·, u), where f is outward pointing on the trapping region boundary. The motivation is that of applications to steady-state reaction/diffusion systems. Also included are reaction/diffusion/convection systems which satisfy the Einstein relations, for which the Cole-Hopf transformation is possible. For maximum generality, the theory is not tied to any specific application. We are able to demonstrate a trapping principle for the piecewise linear Galerkin approximation, defined via a lumped integration hypothesis on integrals involving f, by use of variational inequalities. Results of this type have previously been obtained for parabolic systems by Estep, Larson, and Williams, and for nonlinear elliptic equations by Karátson and Korotov. Recent minimum and maximum principles have been obtained by Jüngel and Unterreiter for nonlinear elliptic equations. We make use of special properties of the element stiffness matrices, induced by a geometric constraint upon the simplicial decomposition. This constraint is known as the non-obtuseness condition. It states that the inward normals, associated with an arbitrary pair of an element’s faces, determine an angle with nonpositive cosine. Drăgănescu, Dupont, and Scott have constructed an example for which the discrete maximum principle fails if this condition is omitted. We also assume vertex communication in each element in the form of an irreducibility hypothesis on the off-diagonal elements of the stiffness matrix. There is a companion convergence result, which yields an existence theorem for the solution. This entails a consistency hypothesis for interpolation on the boundary, and depends on the Tabata construction of simple function approximation, based on barycentric regions. This work was supported by the National Science Foundation under grant DMS-0311263.     

An analysis of finite element locking in a parameter dependent model problem

Summary. We consider the bilinear finite element approximation of smooth solutions to a simple parameter dependent elliptic model problem, the problem of highly anisotropic heat conduction. We show that under favorable circumstances that depend on both the finite element mesh and on the type of boundary conditions, the effect of parametric locking of the standard FEM can be reduced by a simple variational crime. In our analysis we split the error in two orthogonal components, the approximation error and the consistency error, and obtain different bounds for these separate components. Also some numerical results are shown. Received September 6, 1999 / Revised version received March 28, 2000 / Published online April 5, 2001     

Pointwise error estimates of the bilinear SDFEM on Shishkin meshes

A model singularly perturbed convection–diffusion problem in two space dimensions is considered. The problem is solved by a streamline diffusion finite element method (SDFEM) that uses piecewise bilinear finite elements on a Shishkin mesh. We prove that the method is convergent, independently of the diffusion parameter ε, with a pointwise accuracy of almost order 11/8 outside and inside the boundary layers. Numerical experiments support these theoretical results. © 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2013     

Hybrid Galerkin boundary elements: theory and implementation

Summary. In this paper we present a new quadrature method for computing Galerkin stiffness matrices arising from the discretisation of 3D boundary integral equations using continuous piecewise linear boundary elements. This rule takes as points some subset of the nodes of the mesh and can be used for computing non-singular Galerkin integrals corresponding to pairs of basis functions with non-intersecting supports. When this new rule is combined with standard methods for the singular Galerkin integrals we obtain a “hybrid” Galerkin method which has the same stability and asymptotic convergence properties as the true Galerkin method but a complexity more akin to that of a collocation or Nystr?m method. The method can be applied to a wide range of singular and weakly-singular first- and second-kind equations, including many for which the classical Nystr?m method is not even defined. The results apply to equations on piecewise-smooth Lipschitz boundaries, and to non-quasiuniform (but shape-regular) meshes. A by-product of the analysis is a stability theory for quadrature rules of precision 1 and 2 based on arbitrary points in the plane. Numerical experiments demonstrate that the new method realises the performance expected from the theory. Received January 22, 1998 / Revised version received May 26, 1999 / Published online April 20, 2000 –? Springer-Verlag 2000     

Collocation methods for solving linear differential-algebraic boundary value problems

Summary. We consider boundary value problems for linear differential-algebraic equations with variable coefficients with no restriction on the index. A well-known regularisation procedure yields an equivalent index one problem with d differential and a=n-d algebraic equations. Collocation methods based on the regularised BVP approximate the solution x by a continuous piecewise polynomial of degree k and deliver, in particular, consistent approximations at mesh points by using the Radau schemes. Under weak assumptions, the collocation problems are uniquely and stably solvable and, if the unique solution x is sufficiently smooth, convergence of order min {k+1,2k-1} and superconvergence at mesh points of order 2k-1 is shown. Finally, some numerical experiments illustrating these results are presented. Received October 1, 1999 / Revised version received April 25, 2000 / Published online December 19, 2000     

On the solution a of second order singularly-perturbed boundary value problem by the Sinc-Galerkin method

Sinc methods are now recognized as an efficient numerical method for problems whose solutions may have singularities, or infinite domains, or boundary layers. This work deals with the Sinc-Galerkin method for solving second order singularly perturbed boundary value problems. The method is then tested on linear and nonlinear examples and a comparison with spline method and finite element scheme is made. It is shown that the Sinc-Galerkin method yields better results.Received: January 3, 2003; revised: July 14, 2003