Coupling of Nonconforming Finite Elements and Boundary Elements I: A Priori Estimates

Nonconforming finite element methods are sometimes considered as a variational crime and so we may regard its coupling with boundary element methods. In this paper, the symmetric coupling of nonconforming finite elements and boundary elements is established and a priori error estimates are shown. The coupling involves a further continuous layer on the interface in order to separate the nonconformity in the domain from its boundary data which are required to be continuous. Numerical examples prove the new scheme useful in practice. A posteriori error control and adaptive algorithms will be studied in the forthcoming Part II. Received: November 26, 1997; revised February 10, 1999     

Multilevel Approximation of Boundary Integral Operators

Received March 29, 2000; revised June 7, 2001     

A Finite Element-Boundary Element Algorithm for Inhomogeneous Boundary Value Problems

Received January 25, 2001; revised July 17, 2001     

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     

A Higher-Order Scheme for Quasilinear Boundary Value Problems with Two Small Parameters

Received September 28, 2000; revised February 13, 2001     

Preconditioners for Solving Stochastic Boundary Integral Equations with Weakly Singular Kernels

A stochastic linear heat conduction problem is reduced to a special weakly singular integral equation of the second kind. The smoothness of the solution to a multidimensional weakly singular integral equation is investigated. It is also indicated that the derivatives of solutions may have singularities of certain order near the boundary of domain. The solution in the form of a multidimensional cubic spline is studied using circulant integral operators and a special mesh near the boundary with respect to all variables. Furthermore, stable numerical algorithms are given. Received: June 22, 1998; revised November 11, 1998     

Weighted Error Estimates for Finite Element Solutions of Variational Inequalities

In this note the studies begun in Blum and Suttmeier (1999) on adaptive finite element discretisations for nonlinear problems described by variational inequalities are continued. Similar to the concept proposed, e.g., in Becker and Rannacher (1996) for variational equalities, weighted a posteriori estimates for controlling arbitrary functionals of the discretisation error are constructed by using a duality argument. Numerical results for the obstacle problem demonstrate the derived error bounds to be reliable and, used for an adaptive grid refinement strategy, to produce economical meshes. Received September 6, 1999; revised February 8, 2000     

A Solution Method for a Certain Nonlinear Interface Problem in Unbounded Domains

In this paper, we consider a kind of nonlinear interface problem in unbounded domains. To solve this problem, we discuss a new coupling of finite element and boundary element by adding an auxiliary circle. We first derive the optimal error estimate of finite element approximation to the coupled FEM-BEM problem. Then we introduce a preconditioning steepest descent method for solving the discrete system by constructing a cheap domain decomposition preconditioner. Moreover, we give a complete analysis to the convergence speed of this iterative method. Received March 30, 2000; revised November 29, 2000     

A Coupled Multigrid Method for Nonconforming Finite Element Discretizations of the 2D-Stokes Equation

This paper investigates a multigrid method for the solution of the saddle point formulation of the discrete Stokes equation obtained with inf–sup stable nonconforming finite elements of lowest order. A smoother proposed by Braess and Sarazin (1997) is used and L ²-projection as well as simple averaging are considered as prolongation. The W-cycle convergence in the L ²-norm of the velocity with a rate independently of the level and linearly decreasing with increasing number of smoothing steps is proven. Numerical tests confirm the theoretically predicted results. Received January 19, 1999; revised September 13, 1999     

A Multigrid Method for Nonconforming FE-Discretisations with Application to Non-Matching Grids

Nonconforming finite element discretisations require special care in the construction of the prolongation and restriction in the multigrid process. In this paper, a general scheme is proposed, which guarantees the approximation property. As an example, the technique is applied to the discretisation by non-matching grids (mortar elements). Received: October 15, 1998     

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     

On the Attainable Order of Collocation Methods for the Neutral Functional-Differential Equations with Proportional Delays

In this paper, we extend the recent results of H. Brunner in BIT (1997) for the DDE y′(t)= by(qt), y(0)=1 and the DVIE y(t)=1+∫₀ ^t by(qs)ds with proportional delay qt, 0<q≤1, to the neutral functional-differential equation (NFDE): and the delay Volterra integro-differential equation (DVIDE) : with proportional delays p _i t and q _i t, 0<p _i ,q _i ≤1 and complex numbers a,b _i and c _i . We analyze the attainable order of m-stage implicit (collocation-based) Runge-Kutta methods at the first mesh point t=h for the collocation solution v(t) of the NFDE and the `iterated collocation solution u _it (t)' of the DVIDE to the solution y(t), and investigate the existence of the collocation polynomials M _m (t) of v(th) or M^ _m (t) of u _it (th), t∈[0,1] such that the rational approximant v(h) or u _it (h) is the (m,m)-Padé approximant to y(h) and satisfies |v(h)−y(h)|=O(h ^{2 m +1}). If they exist, then we actually give the conditions of M _m (t) and M^ _m (t), respectively. Received September 17, 1998; revised September 30, 1999     

Two-Level Additive Schwarz Preconditioners for the h-p Version of the Galerkin Boundary Element Method for 2-d Problems

We study two-level additive Schwarz preconditioners for the h-p version of the Galerkin boundary element method when used to solve hypersingular integral equations of the first kind, which arise from the Neumann problems for the Laplacian in two dimensions. Overlapping and non-overlapping methods are considered. We prove that the non-overlapping preconditioner yields a system of equations having a condition number bounded by   where H _i is the length of the i-th subdomain, h _i is the maximum length of the elements in this subdomain, and p is the maximum polynomial degree used. For the overlapping method, we prove that the condition number is bounded by   where δ is the size of the overlap and H=max _i H _i . We also discuss the use of the non-overlapping method when the mesh is geometrically graded. The condition number in that case is bounded by clog² M, where M is the degrees of freedom. Received October 27, 2000, revised March 26, 2001     

High Accuracy Analysis of the Adini's Nonconforming Element

Received September 14, 2000; revised September 25, 2001     

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     

A Method for Approximate Inversion of the Hyperbolic CDF

It has been observed by E. Eberlein and U. Keller that the hyperbolic distribution fits logarithmic rates of returns of a stock much better than the normal distribution. We give a method for sampling from the hyperbolic distribution by the inversion method, which is suited for simulation using low discrepancy point sets. Instead of directly inverting the cumulative distribution function (CDF) we provide an approximation of the inverse function which is simple to obtain by standard numerical methods and which is fast to compute. Received May 16, 2002; revised November 5, 2002 Published online: December 12, 2002 RID="*" ID="*" Partly supported by the Austrian Science Fund Project S8305.     

An Iterative Substructuring Method for div-stable Finite Element Approximations of the Oseen Problem

We apply an iterative substructuring algorithm with transmission conditions of Robin–Robin type to the discretized Oseen problem appearing as a linearized variant of the incompressible Navier–Stokes equations. Here we consider finite element approximations using velocity/pressure pairs which satisfy the Babuška–Brezzi stability condition. After proving well-posedness and strong convergence of the method, we derive an a-posteriori error estimate which controls convergence of the discrete subdomain solutions to the global discrete solution by measuring the jumps of the velocities at the interface. Additionally we obtain information how to design a parameter of the Robin interface condition which essentially influences the convergence speed. Numerical experiments confirm the theoretical results and the applicability of the method. Received February 18, 2000; revised February 21, 2001     

Gradient Recovery for Singularly Perturbed Boundary Value Problems I: One-Dimensional Convection-Diffusion

We consider a Galerkin finite element method that uses piecewise linears on a class of Shishkin-type meshes for a model singularly perturbed convection-diffusion problem. We pursue two approaches in constructing superconvergent approximations of the gradient. The first approach uses superconvergence points for the derivative, while the second one combines the consistency of a recovery operator with the superconvergence property of an interpolant. Numerical experiments support our theoretical results. Received November 12, 1999; revised September 9, 2000     

A Black-Box Iterative Solver Based on a Two-Level Schwarz Method

We propose a black-box parallel iterative method suitable for solving both elliptic and certain non-elliptic problems discretized on unstructured meshes. The method is analyzed in the case of the second order elliptic problems discretized on quasiuniform P1 and Q1 finite element meshes. The numerical experiments confirm the validity of the proved convegence estimate and show that the method can successfully be used for more difficult problems (e.g. plates, shells and Helmholtz equation in high-frequency domain.) Received: July 28, 1997; revised June 20, 1999     

Application of an Adaptive Sparse-Grid Technique to a Model Singular Perturbation Problem

In this paper we show how, under minimal conditions, a combination extrapolation can be introduced for an adaptive sparse grid. We apply this technique for the solution of a two-dimensional model singular perturbation problem, defined on the domain exterior of a circle. Received October 18, 1999