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     

Error estimates for a mixed finite volume method for the p-Laplacian problem

In this work we propose and analyze a mixed finite volume method for the p-Laplacian problem which is based on the lowest order Raviart–Thomas element for the vector variable and the P1 nonconforming element for the scalar variable. It is shown that this method can be reduced to a P1 nonconforming finite element method for the scalar variable only. One can then recover the vector approximation from the computed scalar approximation in a virtually cost-free manner. Optimal a priori error estimates are proved for both approximations by the quasi-norm techniques. We also derive an implicit error estimator of Bank–Weiser type which is based on the local Neumann problems.This work was supported by the Post-doctoral Fellowship Program of Korea Science & Engineering Foundation (KOSEF).     

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.     

A characterization of mapping unstructured grids onto structured grids and using multigrid as a preconditioner

Many problems based on unstructured grids provide a natural multigrid framework due to using an adaptive gridding procedure. When the grids are saved, even starting from just a fine grid problem poses no serious theoretical difficulties in applying multigrid. A more difficult case occurs when a highly unstructured grid problem is to be solved with no hints how the grid was produced. Here, there may be no natural multigrid structure and applying such a solver may be quite difficult to do. Since unstructured grids play a vital role in scientific computing, many modifications have been proposed in order to apply a fast, robust multigrid solver. One suggested solution is to map the unstructured grid onto a structured grid and then apply multigrid to a sequence of structured grids as a preconditioner. In this paper, we derive both general upper and lower bounds on the condition number of this procedure in terms of computable grid parameters. We provide examples to illuminate when this preconditioner is a useful (e. g.,p orh-p formulated finite element problems on semi-structured grids) or should be avoided (e.g., typical computational fluid dynamics (CFD) or boundary layer problems). We show that unless great care is taken, this mapping can lead to a system with a high condition number which eliminates the advantage of the multigrid method. This work was partially supported by ONR Grant # N0014-91-J-1576.     

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.     

The convergence of spline collocation for strongly elliptic equations on curves

Summary Most boundary element methods for two-dimensional boundary value problems are based on point collocation on the boundary and the use of splines as trial functions. Here we present a unified asymptotic error analysis for even as well as for odd degree splines subordinate to uniform or smoothly graded meshes and prove asymptotic convergence of optimal order. The equations are collocated at the breakpoints for odd degree and the internodal midpoints for even degree splines. The crucial assumption for the generalized boundary integral and integro-differential operators is strong ellipticity. Our analysis is based on simple Fourier expansions. In particular, we extend results by J. Saranen and W.L. Wendland from constant to variable coefficient equations. Our results include the first convergence proof of midpoint collocation with piecewise constant functions, i.e., the panel method for solving systems of Cauchy singular integral equations.Dedicated to Prof. Dr. Dr. h.c. mult. Lothar Collatz on the occasion of his 75th birthdayThis work was begun at the Technische Hochschule Darmstadt where Professor Arnold was supported by a North Atlantic Treaty Organization Postdoctoral Fellowship. The work of Professor Arnold is supported by NSF grant BMS-8313247. The work of Professor Wendland was supported by the Stiftung Volkswagenwerk     

Additive Schwarz methods for thep-version finite element method

Summary In this paper, we study some additive Schwarz methods (ASM) for thep-version finite element method. We consider linear, scalar, self adjoint, second order elliptic problems and quadrilateral elements in the finite element discretization. We prove a constant bound independent of the degreep and the number of subdomainsN, for the condition number of the ASM iteration operator. This optimal result is obtained first in dimension two. It is then generalized to dimensionn and to a variant of the method on the interface. Numerical experiments confirming these results are reported. As is the case for other additive Schwarz methods, our algorithms are highly parallel and scalable.This work was supported in part by the Applied Math. Sci. Program of the U.S. Department of Energy under contract DE-FG02-88ER25053 and, in part, by the National Science Foundation under Grant NSF-CCR-9204255     

Fourier analysis of schwarz alternating methods for piecewise hermite bicubic orthogonal spline collocation

The rates of convergence of two Schwarz alternating methods are analyzed for the iterative solution of a discrete problem which arises when orthogonal spline collocation with piecewise Hermite bicubics is applied to the Dirichlet problem for Poisson's equation on a rectangle. In the first method, the rectangle is divided into two overlapping subrectangles, while three overlapping subrectangles are used in the second method. Fourier analysis is used to obtain explicit formulas for the convergence factors by which theH ¹-norm of the errors is reduced in one iteration of the Schwarz methods. It is shown numerically that while these factors depend on the size of overlap, they are independent of the partition stepsize. Results of numerical experiments are presented which confirm the established rates of convergence of the Schwarz methods.This research was supported in part by funds from the National Science Foundation grant CCR-9103451.     

Auxiliary space preconditioning in H 0(curl; Ω)

We adapt the principle of auxiliary space preconditioning as presented in [J. Xu, The auxiliary space method and optimal multigrid preconditioning techniques for unstructured grids, Computing, 56 (1996), pp. 215–235.] to H (curl; ω)-elliptic variational problems discretized by means of edge elements. The focus is on theoretical analysis within the abstract framework of subspace correction. Employing a Helmholtz-type splitting of edge element vector fields we can establish asymptotic h-uniform optimality of the preconditioner defined by our auxiliary space method. This author was fully supported by Hong Kong RGC grant (Project No. 403403) This author acknowledges the support from a Direct Grant of CUHK during his visit at The Chinese University of Hong Kong.     

<Emphasis Type="Italic">L</Emphasis><Superscript>1</Superscript>-minimization methods for Hamilton–Jacobi equations: the one-dimensional case

A new approximation technique based on L ¹-minimization is introduced. It is proven that the approximate solution converges to the viscosity solution in the case of one-dimensional stationary Hamilton–Jacobi equation with convex Hamiltonian. This material is based upon work supported by the National Science Foundation grant DMS-0510650. J.-L. Guermond is on leave from LIMSI, UPRR 3251 CNRS, BP 133, 91403 Orsay Cedex, France.     

<Emphasis Type="Italic">hp</Emphasis>-Discontinuous Galerkin methods for strongly nonlinear elliptic boundary value problems

In this paper, we have analyzed a one parameter family of hp-discontinuous Galerkin methods for strongly nonlinear elliptic boundary value problems with Dirichlet boundary conditions. These methods depend on the values of the parameter , where θ = + 1 corresponds to the nonsymmetric and θ = −1 corresponds to the symmetric interior penalty methods when and f(u,∇u) = −f, that is, for the Poisson problem. The error estimate in the broken H ¹ norm, which is optimal in h (mesh size) and suboptimal in p (degree of approximation) is derived using piecewise polynomials of degree p ≥ 2, when the solution . In the case of linear elliptic problems also, this estimate is optimal in h and suboptimal in p. Further, optimal error estimate in the L ² norm when θ = −1 is derived. Numerical experiments are presented to illustrate the theoretical results. Supported by DST-DAAD (PPP-05) project.     

The hierarchical basis multigrid method

Summary We derive and analyze the hierarchical basis-multigrid method for solving discretizations of self-adjoint, elliptic boundary value problems using piecewise linear triangular finite elements. The method is analyzed as a block symmetric Gauß-Seidel iteration with inner iterations, but it is strongly related to 2-level methods, to the standard multigridV-cycle, and to earlier Jacobi-like hierarchical basis methods. The method is very robust, and has a nearly optimal convergence rate and work estimate. It is especially well suited to difficult problems with rough solutions, discretized using highly nonuniform, adaptively refined meshes.     

Galerkin-wavelet methods for two-point boundary value problems

Summary Anti-derivatives of wavelets are used for the numerical solution of differential equations. Optimal error estimates are obtained in the applications to two-point boundary value problems of second order. The orthogonal property of the wavelets is used to construct efficient iterative methods for the solution of the resultant linear algebraic systems. Numerical examples are given.This work was supported by National Science Foundation     

Dual-mixed finite element approximation of Stokes and nonlinear Stokes problems using trace-free velocity gradients

In this work a finite element method for a dual-mixed approximation of Stokes and nonlinear Stokes problems is studied. The dual-mixed structure, which yields a twofold saddle point problem, arises in a formulation of this problem through the introduction of unknown variables with relevant physical meaning. The method approximates the velocity, its gradient, and the total stress tensor, but avoids the explicit computation of the pressure, which can be recovered through a simple postprocessing technique. This method improves an existing approach for these problems and uses Raviart-Thomas elements and discontinuous piecewise polynomials for approximating the unknowns. Existence, uniqueness, and error results for the method are given, and numerical experiments that exhibit the reduced computational cost of this approach are presented.     

Quadratic spline collocation methods for elliptic partial differential equations

We consider Quadratic Spline Collocation (QSC) methods for linear second order elliptic Partial Differential Equations (PDEs). The standard formulation of these methods leads to non-optimal approximations. In order to derive optimal QSC approximations, high order perturbations of the PDE problem are generated. These perturbations can be applied either to the PDE problem operators or to the right sides, thus leading to two different formulations of optimal QSC methods. The convergence properties of the QSC methods are studied. OptimalO(h ^3–j ) global error estimates for thejth partial derivative are obtained for a certain class of problems. Moreover,O(h ^4–j ) error bounds for thejth partial derivative are obtained at certain sets of points. Results from numerical experiments verify the theoretical behaviour of the QSC methods. Performance results also show that the QSC methods are very effective from the computational point of view. They have been implemented efficiently on parallel machines.This research was supported in part by David Ross Foundation (U.S.A) and NSERC (Natural Sciences and Engineering Research Council of Canada).     

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     

The finite element method for parabolic equations

Summary In this first of two papers, computable a posteriori estimates of the space discretization error in the finite element method of lines solution of parabolic equations are analyzed for time-independent space meshes. The effectiveness of the error estimator is related to conditions on the solution regularity, mesh family type, and asymptotic range for the mesh size. For clarity the results are limited to a model problem in which piecewise linear elements in one space dimension are used. The results extend straight-forwardly to systems of equations and higher order elements in one space dimension, while the higher dimensional case requires additional considerations. The theory presented here provides the basis for the analysis and adaptive construction of time-dependent space meshes, which is the subject of the second paper. Computational results show that the approach is practically very effective and suggest that it can be used for solving more general problems.The work was partially supported by ONR Contract N00014-77-C-0623     

A posteriori error estimator based on gradient recovery by averaging for discontinuous Galerkin methods

We consider some (anisotropic and piecewise constant) diffusion problems in domains of R², approximated by a discontinuous Galerkin method with polynomials of any fixed degree. We propose an a posteriori error estimator based on gradient recovery by averaging. It is shown that this estimator gives rise to an upper bound where the constant is one up to some additional terms that guarantee reliability. The lower bound is also established. Moreover these additional terms are negligible when the recovered gradient is superconvergent. The reliability and efficiency of the proposed estimator is confirmed by some numerical tests.     

On a numerical approach to Stefan-like problems

Summary This paper is devoted to the numerical analysis of a bidimensional two-phase Stefan problem. We approximate the enthalpy formulation byC ⁰ piecewise linear finite elements in space combined with a semi-implicit scheme in time. Under some restrictions related to the finite element mesh and to the timestep, we prove positivity, stability and convergence results. Various numerial tests are presented and discussed in order to show the accuracy of our scheme.This work is supported by the Fonds National Suisse pour la Recherche Scientifique.     

An augmented mixed finite element method for 3D linear elasticity problems

In this paper we introduce and analyze a new augmented mixed finite element method for linear elasticity problems in 3D. Our approach is an extension of a technique developed recently for plane elasticity, which is based on the introduction of consistent terms of Galerkin least-squares type. We consider non-homogeneous and homogeneous Dirichlet boundary conditions and prove that the resulting augmented variational formulations lead to strongly coercive bilinear forms. In this way, the associated Galerkin schemes become well posed for arbitrary choices of the corresponding finite element subspaces. In particular, Raviart-Thomas spaces of order 0 for the stress tensor, continuous piecewise linear elements for the displacement, and piecewise constants for the rotation can be utilized. Moreover, we show that in this case the number of unknowns behaves approximately as 9.5 times the number of elements (tetrahedrons) of the triangulation, which is cheaper, by a factor of 3, than the classical PEERS in 3D. Several numerical results illustrating the good performance of the augmented schemes are provided.