Finite Volume Element Approximations of Nonlocal in Time One-Dimensional Flows in Porous Media

Various finite volume element schemes for parabolic integro-differential equations in 1-D are derived and studied. These types of equations arise in modeling reactive flows or material with memory effects. Our main goal is to develop a general framework for obtaining finite volume element approximations and to study the error analysis. We consider the lowest-order (linear and L-splines) finite volume elements, although higher-order volume elements can be considered as well under this framework. It is proved that finite volume element approximations are convergent with optimal order in H ¹-norms, suboptimal order in the L ²-norm and super-convergent order in a discrete H ¹-norm. Received August 3, 1998; revised October 11, 1999     

The Streamline–Diffusion Method for Conforming and Nonconforming Finite Elements of Lowest Order Applied to Convection–Diffusion Problems

We consider the streamline-diffusion finite element method with finite elements of lowest order for solving convection-diffusion problems. Our investigations cover both conforming and nonconforming finite element approximations on triangular and quadrilateral meshes. Although the considered finite elements are of the same interpolation order their stability and approximation properties are quite different. We give a detailed overview on the stability and the convergence properties in the L ²- and in the streamline–diffusion norm. Numerical experiments show that often the theoretical predictions on the convergence properties are sharp. Received December 7, 1999; revised October 5, 2000     

The Fourier-Nitsche-mortaring for elliptic problems with reentrant edges

The Fourier method is combined with the Nitsche-finite-element method (as a mortar method) and applied to the Dirichlet problem of the Poisson equation in three-dimensional axisymmetric domains with reentrant edges generating singularities. The approximating Fourier method yields a splitting of the 3D problem into a set of 2D problems on the meridian plane of the given domain. For solving the 2D problems bearing corner singularities, the Nitsche-finite-element method with non-matching meshes and mesh grading near reentrant corners is applied. Using the explicit representation of some singularity function of non-tensor product type, the rate of convergence of the Fourier-Nitsche-mortaring is estimated in some H ¹-like norm as well as in the L ₂-norm for weak regularity of the solution. Finally, some numerical results are presented.      

Multilevel Gauging for Edge Elements

The vector potential of a solenoidal vector field, if it exists, is not unique in general. Any procedure that aims to determine such a vector potential typically involves a decision on how to fix it. This is referred to by the term gauging. Gauging is an important issue in computational electromagnetism, whenever discrete vector potentials have to be computed. In this paper a new gauging algorithm for discrete vector potentials is introduced that relies on a hierarchical multilevel decomposition. With minimum computational effort it yields vector potentials whose L ²-norm does not severely blow up. Thus the new approach compares favorably to the widely used co-tree gauging. Received May 27, 1999; revised October 22, 1999     

Variable Order Panel Clustering

We present a new version of the panel clustering method for a sparse representation of boundary integral equations. Instead of applying the algorithm separately for each matrix row (as in the classical version of the algorithm) we employ more general block partitionings. Furthermore, a variable order of approximation is used depending on the size of blocks. We apply this algorithm to a second kind Fredholm integral equation and show that the complexity of the method only depends linearly on the number, say n, of unknowns. The complexity of the classical matrix oriented approach is O(n ²) while, for the classical panel clustering algorithm, it is O(nlog⁷ n). Received July 28, 1999; revised September 21, 1999     

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.     

L ∞-error estimates of higher order mixed finite element approximations for elliptic optimal control problems

In this paper, we investigate the L ^∞-error estimates of the numerical solutions of linear-quadratic elliptic control problems by using higher order mixed finite element methods. The state and co-state are approximated by the order k Raviart-Thomas mixed finite element spaces and the control variable is approximated by piecewise polynomials of order k (k≥1). Optimal L ^∞-error estimates are derived for both the control and the state approximations. These results are seemed to be new in the literature of the mixed finite element methods for optimal control problems.     

Iterative Stokes Solvers in the Harmonic Velte Subspace

We explore the prospects of utilizing the decomposition of the function space (H ¹ ₀) ⁿ (where n=2,3) into three orthogonal subspaces (as introduced by Velte) for the iterative solution of the Stokes problem. It is shown that Uzawa and Arrow-Hurwitz iterations – after at most two initial steps – can proceed fully in the third, smallest subspace. For both methods, we also compute optimal iteration parameters. Here, for two-dimensional problems, the lower estimate of the inf-sup constant by Horgan and Payne proves useful and provides an inclusion of the spectrum of the Schur complement operator of the Stokes problem. We further consider the conjugate gradient method in the third Velte subspace and derive a corresponding convergence estimate. Computational results show the effectiveness of this approach for discretizations which admit a discrete Velte decomposition. Received June 11, 1999; revised October 27, 2000     

Approximating Local Averages of Fluid Velocities: The Stokes Problem

As a first step to developing mathematical support for finite element approximation to the large eddies in fluid motion we consider herein the Stokes problem. We show that the local average of the usual approximate flow field u ^h over radius δ provides a very accurate approximation to the flow structures of O(δ) or greater. The extra accuracy appears for quadratic or higher velocity elements and degrades to the usual finite element accuracy as the averaging radius δ→h (the local meshwidth). We give both a priori and a posteriori error estimates incorporating this effect. Received December 3, 1999; revised October 16, 2000     

<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.      

A Refined Finite Element Convergence Theory for Highly Indefinite Helmholtz Problems

It is well known that standard h-version finite element discretisations using lowest order elements for Helmholtz' equation suffer from the following stability condition: ``The mesh width h of the finite element mesh has to satisfy k <sup>2</sup> h≲1', where k denotes the wave number. This condition rules out the reliable numerical solution of Helmholtz equation in three dimensions for large wave numbers k≳50. In our paper, we will present a refined finite element theory for highly indefinite Helmholtz problems where the stability of the discretisation can be checked through an ``almost invariance' condition. As an application, we will consider a one-dimensional finite element space for the Helmholtz equation and apply our theory to prove stability under the weakened condition hk≲1 and optimal convergence estimates. Dedicated to Prof. Dr. Ivo Babuška on the occasion of his 80th birthday.     

Verification of Reduced Convergence Rates

In this short article, we recalculate the numerical example in Kíek and Neittaanmäki (1987) for the Poisson solution u=x(1–x)siny in the unit square S as . By the finite difference method, an error analysis for such a problem is given from our previous study by where h is the meshspacing of the uniform square grids used, and C₁ and C₂ are two positive constants. Let =u–u_h, where u_h is the finite difference solution, and is the discrete H¹ norm. Several techniques are employed to confirm the reduced rate of convergence, and to give the constants, C₁=0.09034 and C₂=0.002275 for a stripe domain. The better performance for arises from the fact that the constant C₁ is much large than C₂, and the h in computation is not small enough.     

The Inf-Sup Condition for the Mapped Q k ?P k?1 disc Element in Arbitrary Space Dimensions

 One of the most popular pairs of finite elements for solving mixed formulations of the Stokes and Navier–Stokes problem is the Q _k −P _k−1 ^disc element. Two possible versions of the discontinuous pressure space can be considered: one can either use an unmapped version of the P _k−1 ^disc space consisting of piecewise polynomial functions of degree at most k−1 on each cell or define a mapped version where the pressure space is defined as the image of a polynomial space on a reference cell. Since the reference transformation is in general not affine but multilinear, the two variants are not equal on arbitrary meshes. It is well-known, that the inf-sup condition is satisfied for the first variant. In the present paper we show that the latter approach satisfies the inf-sup condition as well for k≥2 in any space dimension. Received January 31, 2001; revised May 2, 2002 Published online: July 26, 2002     

Finite Element Methods for Eigenvalue Problems on a Rectangle with (Semi-) Periodic Boundary Conditions on a Pair of Adjacent Sides

This paper deals with a class of elliptic differential eigenvalue problems (EVPs) of second order on a rectangular domain Ω⊂ℝ², with periodic or semi-periodic boundary conditions (BCs) on two adjacent sides of Ω. On the remaining sides, classical Dirichlet or Robin type BCs are imposed. First, we pass to a proper variational formulation, which is shown to fit into the framework of abstract EVPs for strongly coercive, bounded and symmetric bilinear forms in Hilbert spaces. Next, the variational EVP serves as the starting point for finite element approximations. We consider finite element methods (FEMs) without and with numerical quadrature, both with triangular and with rectangular meshes. The aim of the paper is to show that well-known error estimates, established for finite element approximations of elliptic EVPs with classical BCs, remain valid for the present type of EVPs, including the case of multiple exact eigenvalues. Finally, the analysis is illustrated by a non-trivial numerical example, the exact eigenpairs of which can be determined. Received March 2, 1999; revised July 8, 1999     

A Hermitian Box-scheme for One-dimensional Elliptic Equations – Application to Problems with High Contrasts in the Ellipticity

We introduce a new box-scheme, called ``hermitian box-scheme' on the model of the one-dimensional Poisson problem. The scheme combines features of the box-scheme of Keller, [20], [13], with the hermitian approximation of the gradient on a compact stencil, which is characteristic of compact schemes, [9], [21]. The resulting scheme is proved to be 4th order accurate for the primitive unknown u and its gradient p. The proved convergence rate is 1.5 for (u,p) in the discrete L ² norm. The connection with a non standard mixed finite element method is given. Finally, numerical results are displayed on pertinent 1-D elliptic problems with high contrasts in the ellipticity, showing in practice convergence rates ranging from 1 to 2.5 in the discrete H ¹ norm. This work has been performed with the support of the GDR MOMAS, (ANDRA, CEA, EDF, BRGM and CNRS): Modélisation pour le stockage des déchets radioactifs. The author thanks especially A. Bourgeat for his encouragements and his interest in this work.     

Bounds for theN lowest eigenvalues of fourth-order boundary value problems

We describe a method for the calculation of theN lowest eigenvalues of fourth-order problems inH ₀ ² (Ω). In order to obtain small error bounds, we compute the defects inH ⁻²(Ω) and, to obtain a bound for the rest of the spectrum, we use a boundary homotopy method. As an example, we compute strict error bounds (using interval arithmetic to control rounding errors) for the 100 lowest eigenvalues of the clamped plate problem in the unit square. Applying symmetry properties, we prove the existence of double eigenvalues.     

Condition Numbers of Approximate Schur Complements in Two- and Three-Dimensional Discretizations on Hierarchically Ordered Grids

We investigate multilevel incomplete factorizations of M-matrices arising from finite difference discretizations. The nonzero patterns are based on special orderings of the grid points. Hence, the Schur complements that result from block elimination of unknowns refer to a sequence of hierarchical grids. Having reached the coarsest grid, Gaussian elimination yields a complete decomposition of the last Schur complement. The main focus of this paper is a generalization of the recursive five-point/nine-point factorization method (which can be applied in two-dimensional problems) to matrices that stem from discretizations on three-dimensional cartesian grids. Moreover, we present a local analysis that considers fundamental grid cells. Our analysis allows to derive sharp bounds for the condition number associated with one factorization level (two-grid estimates). A comparison in case of the Laplace operator with Dirichlet boundary conditions shows: Estimating the relative condition number of the multilevel preconditioner by multiplying corresponding two-grid values gives the asymptotic bound O(h ^−0.347) for the two- respectively O(h ^−4/5) for the three-dimensional model problem. Received October 19, 1998; revised September 27, 1999     

Uniform Pointwise Convergence of Difference Schemes for Convection-Diffusion Problems on Layer-Adapted Meshes

We consider two convection-diffusion boundary value problems in conservative form: for an ordinary differential equation and for a parabolic equation. Both the problems are discretized using a four-point second-order upwind space difference operator on arbitrary and layer-adapted space meshes. We give ɛ-uniform maximum norm error estimates O(N ⁻²ln² N(+τ)) and O(N ⁻²(+τ)), respectively, for the Shishkin and Bakhvalov space meshes, where N is the space meshnodes number, τ is the time meshinterval. The smoothness condition for the Bakhvalov mesh is replaced by a weaker condition. Received December 14, 1999; revised September 13, 2000     

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     

Error Estimates of a FEM with Lumping for Parabolic PDEs

L ²-norm. This well-known FEM is given by the use of the vertical line method and conforming linear finite elements on a triangulation. The main result of the paper are new estimates in the L ²-norm for the additional error term originated by lumping. Using these ones, for the FEM with lumping we can apply directly the proof technique of error estimates known for conforming FEMs. Received May 17, 2001; revised November 2, 2001 Published online February 18, 2002