Composite Finite Elements for Elliptic Boundary Value Problems with Discontinuous Coefficients

In this paper, we will introduce composite finite elements for solving elliptic boundary value problems with discontinuous coefficients. The focus is on problems where the geometry of the interfaces between the smooth regions of the coefficients is very complicated. On the other hand, efficient numerical methods such as, e.g., multigrid methods, wavelets, extrapolation, are based on a multi-scale discretization of the problem. In standard finite element methods, the grids have to resolve the structure of the discontinuous coefficients. Thus, straightforward coarse scale discretizations of problems with complicated coefficient jumps are not obvious. In this paper, we define composite finite elements for problems with discontinuous coefficients. These finite elements allow the coarsening of finite element spaces independently of the structure of the discontinuous coefficients. Thus, the multigrid method can be applied to solve the linear system on the fine scale. We focus on the construction of the composite finite elements and the efficient, hierarchical realization of the intergrid transfer operators. Finally, we present some numerical results for the multigrid method based on the composite finite elements (CFE–MG).     

A Domain Decomposition Preconditioner for p-FEM Discretizations of Two-dimensional Elliptic Problems

In this paper, a uniformly elliptic second order boundary value problem in 2-D discretized by the p-version of the finite element method is considered. An inexact Dirichlet-Dirichlet domain decomposition pre-conditioner for the system of linear algebraic equations is investigated. Two solvers for the problem in the sub-domains, a pre-conditioner for the Schur-complement and an extension operator operating from the edges of the elements into the interior are proposed as ingredients for the inexact DD-pre-conditioner. In the main part of the paper, several numerical experiments on a parallel computer are given.     

hp-adaptive Two-Level Methods for Boundary Integral Equations on Curves

p - and hp-versions of the Galerkin boundary element method for hypersingular and weakly singular integral equations of the first kind on curves. We derive a-posteriori error estimates that are based on stable two-level decompositions of enriched ansatz spaces. The Galerkin errors are estimated by inverting local projection operators that are defined on small subspaces of the second level. A p-adaptive and two hp-adaptive algorithms are defined and numerical experiments confirm their efficiency. Received August 30, 2000; revised April 3, 2001     

Nitsche Type Mortaring for some Elliptic Problem with Corner Singularities

The paper deals with Nitsche type mortaring as a finite element method (FEM) for treating non-matching meshes of triangles at the interface of some domain decomposition. The approach is applied to the Poisson equation with Dirichlet boundary conditions (as a model problem) under the aspect that the interface passes re-entrant corners of the domain. For such problems and non-matching meshes with and without local refinement near the re-entrant corner, some properties of the finite element scheme and error estimates are proved. They show that appropriate mesh grading yields convergence rates as known for the classical FEM in presence of regular solutions. Finally, a numerical example illustrates the approach and the theoretical results. Received July 5, 2001; revised February 5, 2002 Published online April 25, 2002     

Stabilised hp-Finite Element Approximation of Partial Differential Equations with Nonnegative Characteristic Form

This paper is devoted to the a priori error analysis of the hp-version of a streamline-diffusion finite element method for partial differential equations with nonnegative characteristic form. This class of equations includes second-order elliptic and parabolic problems, first-order hyperbolic problems and second-order problems of mixed elliptic-parabolic-hyperbolic type. We derive error bounds which are simultaneously optimal in both the mesh size h and the spectral order p. Numerical examples are presented to confirm the theoretical results. Received October 28, 1999; revised May 26, 2000     

Numerical Integrations and Unit Resolution Multipliers for Domain Decomposition Methods with Nonmatching Grids

In this paper, we are concerned with the non-overlapping domain decomposition method (DDM) with nonmatching grids for three-dimensional problems. The weak continuity of the DDM solution on the interface is imposed by some Lagrange multiplier. We shall first analyze the influence of the numerical integrations over the interface on the (non-conforming) approximate solution. Then we will propose a simple approach to construct multiplier spaces, one of which can be simply spanned by some smooth basis functions with local compact supports, and thus makes the numerical integrations on the interface rather simple and inexpensive. Also it is shown this multiplier space can generate an optimal approximate solution. Numerical results are presented to compare the new method with the point to point method widely used in engineering.     

A Cascadic Multigrid Algorithm for Semilinear Indefinite Elliptic Problems

We propose a cascadic multigrid algorithm for a semilinear indefinite elliptic problem. We use a standard finite element discretization with piecewise linear finite elements. The arising nonlinear equations are solved by a cascadic organization of Newton's method with frozen derivative on a sequence of nested grids. This gives a simple version of a multigrid method without projections on coarser grids. The cascadic multigrid algorithm starts on a comparatively coarse grid where the number of unknowns is small enough to obtain an approximate solution within sufficiently high precision without substantial computational effort. On each finer grid we perform exactly one Newton step taking the approximate solution from the coarsest grid as initial guess. The linear Newton systems are solved iteratively by a Jacobi-type iteration with special parameters using the approximate solution from the previous grid as initial guess. We prove that for a sufficiently fine initial grid and for a sufficiently good start approximation the algorithm yields an approximate solution within the discretization error on the finest grid and that the method has multigrid complexity with logarithmic multiplier. Received February 1999, revised July 13, 1999     

The hierarchial preconditioning on unstructured grids

We present the implementation of two hierarchically preconditioned methods for the fast solution of mesh equations that approximate 2D-elliptic boundary value problems on unstructured quasi uniform triangulations. Based on the fictitious space approach the original problem can be embedded into an auxiliary one, where both the hierarchical grid information and the preconditioner are well defined. We implemented the corresponding Yserentant preconditioned conjugate gradient method as well as thebpx-preconditioned cg-iteration having optimal computational costs. Several numerical examples demonstrate the efficiency of the artificially constructed hierarchical methods which can be of importance in industrial engineering, where often only the nodal coordinates and the element connectivity of the underlying (fine) discretization are available.     

Local Discontinuous Galerkin Methods for Partial Differential Equations with Higher Order Derivatives

In this paper we review the existing and develop new local discontinuous Galerkin methods for solving time dependent partial differential equations with higher order derivatives in one and multiple space dimensions. We review local discontinuous Galerkin methods for convection diffusion equations involving second derivatives and for KdV type equations involving third derivatives. We then develop new local discontinuous Galerkin methods for the time dependent bi-harmonic type equations involving fourth derivatives, and partial differential equations involving fifth derivatives. For these new methods we present correct interface numerical fluxes and prove L ² stability for general nonlinear problems. Preliminary numerical examples are shown to illustrate these methods. Finally, we present new results on a post-processing technique, originally designed for methods with good negative-order error estimates, on the local discontinuous Galerkin methods applied to equations with higher derivatives. Numerical experiments show that this technique works as well for the new higher derivative cases, in effectively doubling the rate of convergence with negligible additional computational cost, for linear as well as some nonlinear problems, with a local uniform mesh.     

Robust Multigrid Methods for Nearly Incompressible Elasticity

We consider multigrid methods for problems in linear elasticity which are robust with respect to the Poisson ratio. Therefore, we consider mixed approximations involving the displacement vector and the pressure, where the pressure is approximated by discontinuous functions. Then, the pressure can be eliminated by static condensation. The method is based on a saddle point smoother which was introduced for the Stokes problem and which is transferred to the elasticity system. The performance and the robustness of the multigrid method are demonstrated on several examples with different discretizations in 2D and 3D. Furthermore, we compare the multigrid method for the saddle point formulation and for the condensed positive definite system. Received February 5, 1999; revised October 5, 1999     

Variable Additive Preconditioning Procedures

Iterative methods with variable preconditioners of additive type are proposed. The scaling factors of each summand in the additive preconditioners are optimized within each iteration step. It is proved that the presented methods converge at least as fast as the Richardson's iterative method with the corresponding additive preconditioner with optimal scaling factors. In the presented numerical experiments the suggested methods need nearly the same number of iterations as the usual preconditioned conjugate gradient method with the corresponding additive preconditioner with numerically determined fixed optimal scaling factors. Received: June 10, 1998; revised October 16, 1998     

Nitsche Type Mortaring for Singularly Perturbed Reaction-diffusion Problems

The paper is concerned with the Nitsche mortaring in the framework of domain decomposition where non-matching meshes and weak continuity of the finite element approximation at the interface are admitted. The approach is applied to singularly perturbed reaction-diffusion problems in 2D. Non-matching meshes of triangles being anisotropic in the boundary layers are applied. Some properties as well as error estimates of the Nitsche mortar finite element schemes are proved. In particular, using a suitable degree of anisotropy of triangles in the boundary layers of a rectangle, convergence rates as known for the conforming finite element method are derived. Numerical examples illustrate the approach and the results.     

Multigrid for Discrete Differential Forms on Sparse Grids

Discrete differential forms are a generalization of the common H¹()-conforming Lagrangian elements. For the latter, Galerkin schemes based on sparse grids are well known, and so are fast iterative multilevel solvers for the discrete Galerkin equations. We extend both the sparse grid idea and the design of multilevel methods to arbitrary discrete differential forms. The focus of this presentation will be on issues of efficient implementation and numerical studies of convergence of multigrid solvers.     

BDDC and FETI-DP preconditioners for spectral element discretizations

Two of the most recent and important nonoverlapping domain decomposition methods, the BDDC method (Balancing Domain Decomposition by Constraints) and the FETI-DP method (Dual-Primal Finite Element Tearing and Interconnecting) are here extended to spectral element discretizations of second-order elliptic problems. In spite of the more severe ill-conditioning of the spectral element discrete systems, compared with low-order finite elements and finite differences, these methods retain their good properties of scalability, quasi-optimality and independence on the discontinuities of the elliptic operator coefficients across subdomain interfaces.     

An Algebraic Multigrid Method for Higher-order Finite Element Discretizations

In this paper, we will design and analyze a class of new algebraic multigrid methods for algebraic systems arising from the discretization of second order elliptic boundary value problems by high-order finite element methods. For a given sparse stiffness matrix from a quadratic or cubic Lagrangian finite element discretization, an algebraic approach is carefully designed to recover the stiffness matrix associated with the linear finite element disretization on the same underlying (but nevertheless unknown to the user) finite element grid. With any given classical algebraic multigrid solver for linear finite element stiffness matrix, a corresponding algebraic multigrid method can then be designed for the quadratic or higher order finite element stiffness matrix by combining with a standard smoother for the original system. This method is designed under the assumption that the sparse matrix to be solved is associated with a specific higher order, quadratic for example, finite element discretization on a finite element grid but the geometric data for the underlying grid is unknown. The resulting new algebraic multigrid method is shown, by numerical experiments, to be much more efficient than the classical algebraic multigrid method which is directly applied to the high-order finite element matrix. Some theoretical analysis is also provided for the convergence of the new method.     

Superconvergence of a Mixed Covolume Method for Elliptic Problems

We consider a mixed covolume method for a system of first order partial differential equations resulting from the mixed formulation of a general self-adjoint elliptic problem with a variable full diffusion tensor. The system can be used to model the transport of a contaminant carried by a flow. We use the lowest order Raviart-Thomas mixed finite element space. We show the first order convergence in L ² norm and the superconvergence in certain discrete norms both for the pressure and velocity. Finally some numerical examples illustrating the error behavior of the scheme are provided. Supported by the National Natural Science Foundation of China under grant No. 10071044 and the Research Fund of Doctoral Program of High Education by State Education Ministry of China.     

Superconvergence of Local Discontinuous Galerkin Methods for Partial Differential Equations with Higher Order Derivatives

In this paper, we present a unified approach to study superconvergence behavior of the local discontinuous Galerkin (LDG) method for high-order time-dependent partial differential equations. We select the third and fourth order equations as our models to demonstrate this approach and the main idea. Superconvergence results for the solution itself and the auxiliary variables are established. To be more precise, we first prove that, for any polynomial of degree k, the errors of numerical fluxes at nodes and for the cell averages are superconvergent under some suitable initial discretization, with an order of \(O(h^{2k+1})\). We then prove that the LDG solution is \((k+2)\)-th order superconvergent towards a particular projection of the exact solution and the auxiliary variables. As byproducts, we obtain a \((k+1)\)-th and \((k+2)\)-th order superconvergence rate for the derivative and function value approximation separately at a class of Radau points. Moreover, for the auxiliary variables, we, for the first time, prove that the convergence rate of the derivative error at the interior Radau points can reach as high as \(k+2\). Numerical experiments demonstrate that most of our error estimates are optimal, i.e., the error bounds are sharp.     

On the reference mapping for quadrilateral and hexahedral finite elements on multilevel adaptive grids

We study the properties of the reference mapping for quadrilateral and hexahedral finite elements. We consider multilevel adaptive grids with possibly hanging nodes which are typically generated by adaptive refinement starting from a regular coarse grid. It turns out that for such grids the reference mapping behaves – up to a perturbation depending on the mesh size – like an affine mapping. As an application, we prove optimal estimates of the interpolation error for discontinuous mapped -elements on quadrilateral and hexahedral grids.     

Anisotropic interpolation error estimates for isoparametric quadrilateral finite elements

Anisotropic local interpolation error estimates are derived for quadrilateral and hexahedral Lagrangian finite elements with straight edges. These elements are allowed to have diameters with different asymptotic behaviour in different space directions. The case of affine elements (parallel-epipeds) with arbitrarily high degree of the shape functions is considered first. Then, a careful examination of the multi-linear map leads to estimates for certain classes of more general, isoparametric elements. As an application, the Galerkin finite element method for a reaction diffusion problem in a polygonal domain is considered. The boundary layers are resolved using anisotropic trapezoidal elements.     

<Emphasis Type="Italic">H</Emphasis><Superscript>1</Superscript>-interpolation on quadrilateral and hexahedral meshes with hanging nodes

We propose a Scott-Zhang type finite element interpolation operator of first order for the approximation of H ¹-functions by means of continuous piecewise mapped bilinear or trilinear polynomials. The novelty of the proposed interpolation operator is that it is defined for general non-affine equivalent quadrilateral and hexahedral elements and so-called 1-irregular meshes with hanging nodes. We prove optimal local approximation properties of this interpolation operator for functions in H ¹. As necessary ingredients we provide a definition of a hanging node and a rigorous analysis of the issue of constrained approximation which cover both the two- and three-dimensional case in a unified fashion.