An a posteriori residual error estimator for the finite element method on anisotropic tetrahedral meshes

Summary. A new a posteriori residual error estimator is defined and rigorously analysed for anisotropic tetrahedral finite element meshes. All considerations carry over to anisotropic triangular meshes with minor changes only. The lower error bound is obtained by means of bubble functions and the corresponding anisotropic inverse inequalities. In order to prove the upper error bound, it is vital that an anisotropic mesh corresponds to the anisotropic function under consideration. To measure this correspondence, a so-called matching function is defined, and its discussion shows it to be a useful tool. With its help anisotropic interpolation estimates and subsequently the upper error bound are proven. Additionally it is pointed out how to treat Robin boundary conditions in a posteriori error analysis on isotropic and anisotropic meshes. A numerical example supports the anisotropic error analysis. Received April 6, 1999 / Revised version received July 2, 1999 / Published online June 8, 2000     

Crouzeix-Raviart type finite elements on anisotropic meshes

Summary. The paper deals with a non-conforming finite element method on a class of anisotropic meshes. The Crouzeix-Raviart element is used on triangles and tetrahedra. For rectangles and prismatic (pentahedral) elements a novel set of trial functions is proposed. Anisotropic local interpolation error estimates are derived for all these types of element and for functions from classical and weighted Sobolev spaces. The consistency error is estimated for a general differential equation under weak regularity assumptions. As a particular application, an example is investigated where anisotropic finite element meshes are appropriate, namely the Poisson problem in domains with edges. A numerical test is described. Received May 19, 1999 / Revised version received February 2, 2000 / Published online February 5, 2001     

Nonconforming mixed finite element approximation to the stationary Navier-Stokes equations on anisotropic meshes

The main aim of this paper is to study the error estimates of a rectangular nonconforming finite element for the stationary Navier-Stokes equations under anisotropic meshes. That is, the nonconforming rectangular element is taken as approximation space for the velocity and the piecewise constant element for the pressure. The convergence analysis is presented and the optimal error estimates both in a broken H¹-norm for the velocity and in an L²-norm for the pressure are derived on anisotropic meshes.     

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     

A posteriori error estimators for nonconforming finite element methods of the linear elasticity problem

In this work we derive and analyze a posteriori error estimators for low-order nonconforming finite element methods of the linear elasticity problem on both triangular and quadrilateral meshes, with hanging nodes allowed for local mesh refinement. First, it is shown that equilibrated Neumann data on interelement boundaries are simply given by the local weak residuals of the numerical solution. The first error estimator is then obtained by applying the equilibrated residual method with this set of Neumann data. From this implicit estimator we also derive two explicit error estimators, one of which is similar to the one proposed by Dörfler and Ainsworth (2005) [24] for the Stokes problem. It is established that all these error estimators are reliable and efficient in a robust way with respect to the Lamé constants. The main advantage of our error estimators is that they yield guaranteed, i.e., constant-free upper bounds for the energy-like error (up to higher order terms due to data oscillation) when a good estimate for the inf-sup constant is available, which is confirmed by some numerical results.     

The sdfem on Shishkin meshes for linear convection-diffusion problems

Summary. We consider singularly perturbed linear elliptic problems in two dimensions. The solutions of such problems typically exhibit layers and are difficult to solve numerically. The streamline diffusion finite element method (SDFEM) has been proved to produce accurate solutions away from any layers on uniform meshes, but fails to compute the boundary layers precisely. Our modified SDFEM is implemented with piecewise linear functions on a Shishkin mesh that resolves boundary layers, and we prove that it yields an accurate approximation of the solution both inside and outside these layers. The analysis is complicated by the severe nonuniformity of the mesh. We give local error estimates that hold true uniformly in the perturbation parameter , provided only that , where mesh points are used. Numerical experiments support these theoretical results. Received February 19, 1999 / Revised version received January 27, 2000 / Published online August 2, 2000     

On optimal triangular meshes for minimizing the gradient error

Summary Construction of optimal triangular meshes for controlling the errors in gradient estimation for piecewise linear interpolation of data functions in the plane is discussed. Using an appropriate linear coordinate transformation, rigorously optimal meshes for controlling the error in quadratic data functions are constructed. It is shown that the transformation can be generated as a curvilinear coordinate transformation for anyC data function with nonsingular Hessian matrix. Using this transformation, a construction of nearly optimal meshes for general data functions is described and the error equilibration properties of these meshes discussed. In particular, it is shown that equilibration of errors is not a sufficient condition for optimality. A comparison of meshes generated under several different criteria is made, and their equilibrating properties illustrated.This work was supported by the Natural Sciences and Engineering Research Council of Canada, by the Information Technology Research Centre, which is funded by the Province of Ontario, by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy under contract DE-AC05-84OR21400 with Martin Marietta Energy Systems, Inc., and through an appointment to the U.S. Department of Energy Postgraduate Research Program administered by Oak Ridge Associated Universities     

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     

Finite element LES and VMS methods on tetrahedral meshes

Finite element methods for problems given in complex domains are often based on tetrahedral meshes. This paper demonstrates that the so-called rational Large Eddy Simulation model and a projection-based Variational Multiscale method can be extended in a straightforward way to tetrahedral meshes. Numerical studies are performed with an inf-sup stable second order pair of finite elements with discontinuous pressure approximation.     

Inf-sup stable non-conforming finite elements of arbitrary order on triangles

We introduce a family of scalar non-conforming finite elements of arbitrary order k≥1 with respect to the H¹-norm on triangles. Their vector-valued version generates together with a discontinuous pressure approximation of order k−1 an inf-sup stable finite element pair of order k for the Stokes problem in the energy norm. For k=1 the well-known Crouzeix-Raviart element is recovered.     

A variational approach to optimal meshes

Summary. A variational approach for the optimization of triangular or tetrahedral meshes is presented. Starting from some very basic assumptions we will rigorously demonstrate that the functional controlling optimality is of a certain type related to energy functionals in non linear elasticity. It will be proved that these functionals attain their minima over admissible sets of mesh deformations which respect boundary conditions. In addition the injectivity of the deformed mesh is discussed. Thereby it is possible to construct suitable meshes for various numerical applications. Received March 14, 1994 / Revised version received August 8, 1994     

Numerical simulation of fluid-structure interaction problems on hybrid meshes with algebraic multigrid methods

Fluid-structure interaction problems arise in many fields of application such as flows around elastic structures and blood flow in arteries. The method presented in this paper for solving such a problem is based on a reduction to an equation at the interface, involving the so-called Steklov-Poincaré operators. This interface equation is solved by a Newton iteration, for which directional derivatives involving shape derivatives with respect to the interface perturbation have to be evaluated appropriately. One step of the Newton iteration requires the solution of several decoupled linear sub-problems in the structure and the fluid domains. These sub-problems are spatially discretized by a finite element method on hybrid meshes. For the time discretization, implicit first-order methods are used for both sub-problems. The discretized equations are solved by algebraic multigrid methods.     

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     

Edge residuals dominate a posteriori error estimates for linear finite element methods on anisotropic triangular and tetrahedral meshes

Summary. Both for the - and -norms, we prove that, up to higher order perturbation terms, edge residuals yield global upper and local lower bounds on the error of linear finite element methods on anisotropic triangular or tetrahedral meshes. We also show that, with a correct scaling, edge residuals yield a robust error estimator for a singularly perturbed reaction-diffusion equation. Received April 19, 1999 / Published online April 20, 2000     

Characterizing the inf-sup condition on product spaces

In this paper we establish characterization results for the continuous and discrete inf-sup conditions on product spaces. The inf-sup condition for each component of the bilinear form involved and suitable decompositions of the pivot space in terms of the associated null spaces are the key ingredients of our theorems. We illustrate the theory through its application to bilinear forms arising from the variational formulations of several boundary value problems. Dedicated to Professor Ivo Babuska on the occasion of his 82nd birthday. This research was partially supported by Centro de Modelamiento Matemático (CMM) of the Universidad de Chile, by Centro de Investigación en Ingenierí a Matemática (CI²MA) of the Universidad de Concepción, by FEDER/MCYT Project MTM2007-63204, and by Gobierno de Aragón (Grupo Consolidado PDIE).     

Mixed hp-DGFEM for incompressible flows II: Geometric edge meshes

We consider the Stokes problem of incompressible fluid flowin three-dimensional polyhedral domains discretized on hexahedralmeshes with hp-discontinuous Galerkin finite elements of typeQ_k for the velocity and Q_k–1 for the pressure. We provethat these elements are inf-sup stable on geometric edge meshesthat are refined anisotropically and non-quasiuniformly towardsedges and corners. The discrete inf-sup constant is shown tobe independent of the aspect ratio of the anisotropic elementsand is of O(k^–3/2) in the polynomial degree k, as in thecase of conforming Q_k–Q_k–2 approximations on thesame meshes.     

An algorithm for coarsening unstructured meshes

Summary. We develop and analyze a procedure for creating a hierarchical basis of continuous piecewise linear polynomials on an arbitrary, unstructured, nonuniform triangular mesh. Using these hierarchical basis functions, we are able to define and analyze corresponding iterative methods for solving the linear systems arising from finite element discretizations of elliptic partial differential equations. We show that such iterative methods perform as well as those developed for the usual case of structured, locally refined meshes. In particular, we show that the generalized condition numbers for such iterative methods are of order , where is the number of hierarchical basis levels. Received December 5, 1994     

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     

Finite element methods on piecewise equidistant meshes for interior turning point problems

We consider linear second order singularly perturbed two-point boundary value problems with interior turning points. Piecewise linear Galerkin finite element methods are constructed on various piecewise equidistant meshes designed for such problems. These methods are proved to be convergent, uniformly in the singular perturbation parameter, in a weighted energy norm and the usualL ² norm. Supporting numerical results are presented.     

Infinitesimally flexible meshes and discrete minimal surfaces

We explore the geometry of isothermic meshes, conical meshes, and asymptotic meshes around the Christoffel dual construction of a discrete minimal surface. We present a discrete Legendre transform which realizes discrete minimal surfaces as conical meshes. Conical meshes turn out to be infinitesimally flexible if and only if their spherical image is isothermic, which implies that discrete minimal surfaces constructed in this way are infinitesimally flexible, and therefore possess reciprocal-parallel meshes. These are discrete minimal surfaces in their own right. In our study of relative kinematics of infinitesimally flexible meshes, we encounter characterizations of flexibility and isothermicity which are of incidence-geometric nature and are related to the classical Desargues configuration. The Lelieuvre formula for asymptotic meshes leads to another characterization of isothermic meshes in the sphere which is based on triangle areas. Authors’ addresses: Johannes Wallner (corresponding author), Institut für Geometrie, TU Graz, Kopernikusgasse 24, A 8010 Graz, Austria; Helmut Pottmann, Institut für Diskrete Mathematik und Geometrie, TU Wien, Wiedner Hauptstr. 8-10/104, A 1040 Wien, Austria