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

Received January 25, 2001; revised July 17, 2001     

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     

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

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     

Non-Nested Multi-Level Solvers for Finite Element Discretisations of Mixed Problems

We consider a general framework for analysing the convergence of multi-grid solvers applied to finite element discretisations of mixed problems, both of conforming and nonconforming type. As a basic new feature, our approach allows to use different finite element discretisations on each level of the multi-grid hierarchy. Thus, in our multi-level approach, accurate higher order finite element discretisations can be combined with fast multi-level solvers based on lower order (nonconforming) finite element discretisations. This leads to the design of efficient multi-level solvers for higher order finite element discretisations. Received May 17, 2001; revised February 2, 2002 Published online April 25, 2002     

A Robust Smoother for Convection-Diffusion Problems with Closed Characteristics

In this paper we analyze a model problem for the convection-diffusion equation where the reduced problem has closed characteristics. A full upwinding finite difference scheme is used to discretize the problem. Additionally to the strength of the convection, an arbitrary amount of crosswind-diffusion can be added on the discrete level. We present a smoother which is robust w.r.t. the strength of convection and the amount of crosswind-diffusion. It is of Gauss–Seidel type using a downwind ordering. To handle the cyclic dependencies a frequency-filtering algorithm is used. The algorithm is of nearly optimal complexity ?(n log n). It is proved that it fulfills a robust smoothing property.     

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     

Ordering Techniques for Two- and Three-Dimensional Convection-Dominated Elliptic Boundary Value Problems

Multigrid methods with simple smoothers have been proven to be very successful for elliptic problems with no or only moderate convection. In the presence of dominant convection or anisotropies as it might appear in equations of computational fluid dynamics (e.g. in the Navier-Stokes equations), the convergence rate typically decreases. This is due to a weakened smoothing property as well as to problems in the coarse grid correction. In order to obtain a multigrid method that is robust for convection-dominated problems, we construct efficient smoothers that obtain their favorable properties through an appropriate ordering of the unknowns. We propose several ordering techniques that work on the graph associated with the (convective part of the) stiffness matrix. The ordering algorithms provide a numbering together with a block structure which can be used for block iterative methods. We provide numerical results for the Stokes equations with a convective term illustrating the improved convergence properties of the multigrid algorithm when applied with an appropriate ordering of the unknowns. Received July 12, 1999; revised October 1, 1999     

On the Convergence of a Multigrid Method for Linear Reaction-Diffusion Problems

In this note we consider discrete linear reaction-diffusion problems. For the discretization a standard conforming finite element method is used. For the approximate solution of the resulting discrete problem a multigrid method with a damped Jacobi or symmetric Gauss-Seidel smoother is applied. We analyze the convergence of the multigrid V- and W-cycle in the framework of the approximation- and smoothing property. The multigrid method is shown to be robust in the sense that the contraction number can be bounded by a constant smaller than one which does not depend on the mesh size or on the diffusion-reaction ratio. Received June 15, 2000     

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     

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     

Multilevel Approximation of Boundary Integral Operators

Received March 29, 2000; revised June 7, 2001     

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     

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     

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     

Spectral Galerkin Discretization for Hydrodynamic Stability Problems

A spectral Galerkin discretization for calculating the eigenvalues of the Orr-Sommerfeld equation is presented. The matrices of the resulting generalized eigenvalue problem are sparse. A convergence analysis of the method is presented which indicates that a) no spurious eigenvalues occur and b) reliable results can only be expected under the assumption of scale resolution, i.e., that Re/p ² is small; here Re is the Reynolds number and p is the spectral order. Numerical experiments support that the assumption of scale resolution is necessary in order to obtain reliable results. Exponential convergence of the method is shown theoretically and observed numerically. Received November 11, 1998; revised March 1, 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     

Problem Dependent Generalized Prewavelets

In this paper, we present a new approach to construct robust multilevel algorithms for elliptic differential equations. The multilevel algorithms consist of multiplicative subspace corrections in spaces spanned by problem dependent generalized prewavelets. These generalized prewavelets are constructed by a local orthogonalization of hierarchical basis functions with respect to a so-called local coarse-grid space. Numerical results show that the local orthogonalization leads to a smaller constant in strengthened Cauchy-Schwarz inequality than the original hierarchical basis functions. This holds also for several equations with discontinuous coefficients. Thus, the corresponding multilevel algorithm is a fast and robust iterative solver. Received November 13, 2001; revised October 21, 2002 Published online: December 12, 2002