A characterization of mapping unstructured grids onto structured grids and using multigrid as a preconditioner

Many problems based on unstructured grids provide a natural multigrid framework due to using an adaptive gridding procedure. When the grids are saved, even starting from just a fine grid problem poses no serious theoretical difficulties in applying multigrid. A more difficult case occurs when a highly unstructured grid problem is to be solved with no hints how the grid was produced. Here, there may be no natural multigrid structure and applying such a solver may be quite difficult to do. Since unstructured grids play a vital role in scientific computing, many modifications have been proposed in order to apply a fast, robust multigrid solver. One suggested solution is to map the unstructured grid onto a structured grid and then apply multigrid to a sequence of structured grids as a preconditioner. In this paper, we derive both general upper and lower bounds on the condition number of this procedure in terms of computable grid parameters. We provide examples to illuminate when this preconditioner is a useful (e. g.,p orh-p formulated finite element problems on semi-structured grids) or should be avoided (e.g., typical computational fluid dynamics (CFD) or boundary layer problems). We show that unless great care is taken, this mapping can lead to a system with a high condition number which eliminates the advantage of the multigrid method. This work was partially supported by ONR Grant # N0014-91-J-1576.     

Multigrid algorithms for a vertex–centered covolume method for elliptic problems

Summary. We analyze V–cycle multigrid algorithms for a class of perturbed problems whose perturbation in the bilinear form preserves the convergence properties of the multigrid algorithm of the original problem. As an application, we study the convergence of multigrid algorithms for a covolume method or a vertex–centered finite volume element method for variable coefficient elliptic problems on polygonal domains. As in standard finite element methods, the V–cycle algorithm with one pre-smoothing converges with a rate independent of the number of levels. Various types of smoothers including point or line Jacobi, and Gauss-Seidel relaxation are considered. Received August 19, 1999 / Revised version received July 10, 2000 / Published online June 7, 2001     

On computing the pressure by thep version of the finite element method for Stokes problem

Summary This paper introduces and analyzes two ways of extracting the hydrostatic pressure when solving Stokes problem using thep version of the finite element method. When one uses a localH ¹ projection, we show that optimal rates of convergence for the pressure approximation is achieved. When the pressure is not inH ¹. or the value of the pressure is only needed at a few points, one may extract the pressure pointwise using e.g. a single layer potential recovery. Negative, zero, and higher norm estimates for the Stokes velocity are derived within the framework of thep version of the F.E.M.Partially supported by ONR grants N00014-87-K-0427 and N00014-90-J-1238     

A cascadic multigrid algorithm for semilinear elliptic problems

Summary. We propose a cascadic multigrid algorithm for a semilinear elliptic problem. The nonlinear equations arising from linear finite element discretizations are solved by Newton's method. Given an approximate solution on the coarsest grid on each finer grid we perform exactly one Newton step taking the approximate solution from the previous grid as initial guess. The Newton systems are solved iteratively by an appropriate smoothing method. We prove that the algorithm yields an approximate solution within the discretization error on the finest grid provided that the start approximation is sufficiently accurate and that the initial grid size is sufficiently small. Moreover, we show that the method has multigrid complexity. Received February 12, 1998 / Revised version received July 22, 1999 / Published online June 8, 2000     

Error estimates of the lumped mass finite element method for semilinear elliptic problems

We are concerned with the semilinear elliptic problems. We first investigate the L²-error estimate for the lumped mass finite element method. We then use the cascadic multigrid method to solve the corresponding discrete problem. On the basis of the finite element error estimates, we prove the optimality of the proposed multigrid method. We also report some numerical results to support the theory.     

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.     

Multigrid for the mortar element method for P1 nonconforming element

In this paper, a multigrid algorithm is presented for the mortar element method for P1 nonconforming element. Based on the theory developed by Bramble, Pasciak, Xu in [5], we prove that the W-cycle multigrid is optimal, i.e. the convergence rate is independent of the mesh size and mesh level. Meanwhile, a variable V-cycle multigrid preconditioner is constructed, which results in a preconditioned system with uniformly bounded condition number. Received May 11, 1999 / Revised version received April 1, 2000 / Published online October 16, 2000     

A multigrid method for Reissner-Mindlin plates

Summary The numerical solution of the Mindlin-Reissner plate equations by a multigrid method is studied. Difficulties arise only if the thickness parameter is significantly smaller than the mesh parameter. In this case an augmented Lagrangian method is applied to transform the given problem into a sequence of problems with relaxed penalty parameter. With this a parameter independent iteration is obtained.     

Effective preconditioning of Uzawa type schemes for a generalized Stokes problem

Summary. The Schur complement of a model problem is considered as a preconditioner for the Uzawa type schemes for the generalized Stokes problem (the Stokes problem with the additional term in the motion equation). The implementation of the preconditioned method requires for each iteration only one extra solution of the Poisson equation with Neumann boundary conditions. For a wide class of 2D and 3D domains a theorem on its convergence is proved. In particular, it is established that the method converges with a rate that is bounded by some constant independent of . Some finite difference and finite element methods are discussed. Numerical results for finite difference MAC scheme are provided. Received May 2, 1997 / Revised version received May 10, 1999 / Published online May 8, 2000     

A multigrid method for a Petrov-Galerkin discretization of the Stokes equations

Summary We introduce a multigrid method for the solution of the discrete Stokes equations, arising from a Petrov-Galerkin formulation. The stiffness matrix is nonsymmetric but coercive, hence we consider smoothing iterations which are not suitable for usual indefinite problems. In this report, we prove convergence for a multigrid method with Richardson iteration in the smoothing part.     

The cascadic multigrid method for elliptic problems

Summary. The paper deals with certain adaptive multilevel methods at the confluence of nested multigrid methods and iterative methods based on the cascade principle of [10]. From the multigrid point of view, no correction cycles are needed; from the cascade principle view, a basic iteration method without any preconditioner is used at successive refinement levels. For a prescribed error tolerance on the final level, more iterations must be spent on coarser grids in order to allow for less iterations on finer grids. A first candidate of such a cascadic multigrid method was the recently suggested cascadic conjugate gradient method of [9], in short CCG method, whichused the CG method as basic iteration method on each level. In [18] it has been proven, that the CCG method is accurate with optimal complexity for elliptic problems in 2D and quasi-uniform triangulations. The present paper simplifies that theory and extends it to more general basic iteration methods like the traditional multigrid smoothers. Moreover, an adaptive control strategy for the number of iterations on successive refinement levels for possibly highly non-uniform grids is worked out on the basis of a posteriori estimates. Numerical tests confirm the efficiency and robustness of the cascadic multigrid method. Received November 12, 1994 / Revised version received October 12, 1995     

Dual hybrid methods for the elasticity and the Stokes problems: a unified approach

Summary. A unified approach to construct finite elements based on a dual-hybrid formulation of the linear elasticity problem is given. In this formulation the stress tensor is considered but its symmetry is relaxed by a Lagrange multiplier which is nothing else than the rotation. This construction is linked to the approximations of the Stokes problem in the primitive variables and it leads to a new interpretation of known elements and to new finite elements. Moreover all estimates are valid uniformly with respect to compressibility and apply in the incompressible case which is close to the Stokes problem. Received June 20, 1994 / Revised version received February 16, 1996     

Efficient geometric multigrid implementation for triangular grids

This paper deals with a stencil-based implementation of a geometric multigrid method on semi-structured triangular grids (triangulations obtained by regular refinement of an irregular coarse triangulation) for linear finite element methods. An efficient and elegant procedure to construct these stencils using a reference stencil associated to a canonical hexagon is proposed. Local Fourier Analysis (LFA) is applied to obtain asymptotic convergence estimates. Numerical experiments are presented to illustrate the efficiency of this geometric multigrid algorithm, which is based on a three-color smoother.     

Monotone multigrid methods for elliptic variational inequalities II

Summary. We derive globally convergent multigrid methods for discrete elliptic variational inequalities of the second kind as obtained from the approximation of related continuous problems by piecewise linear finite elements. The coarse grid corrections are computed from certain obstacle problems. The actual constraints are fixed by the preceding nonlinear fine grid smoothing. This new approach allows the implementation as a classical V-cycle and preserves the usual multigrid efficiency. We give estimates for the asymptotic convergence rates. The numerical results indicate a significant improvement as compared with previous multigrid approaches. Received March 26, 1994 / Revised version received September 22, 1994     

A mixed finite element method for solving the nonstationary stokes equation

Summary This paper deals with a mixed finite element method for approximating a fourth order initial value problem arising from the nonstationary Stokes problem. For piecewise linear shape functions error estimates are given with convergence rates similar to the elliptic case. Some numerical computations will illustrate the theoretical results.     

Coarse grid spaces for domains with a complicated boundary

It is shown that, with homogeneous Dirichlet boundary conditions, the condition number of finite element discretization matrices remains uniformly bounded independent of the size of the boundary elements provided that the size of the elements increases with their distance to the boundary. This fact allows the construction of simple multigrid methods of optimal complexity for domains of nearly arbitrary shape. This revised version was published online in June 2006 with corrections to the Cover Date.     

Multilevel methods for mixed finite elements in three dimensions

In this paper we consider second order scalar elliptic boundary value problems posed over three–dimensional domains and their discretization by means of mixed Raviart–Thomas finite elements [18]. This leads to saddle point problems featuring a discrete flux vector field as additional unknown. Following Ewing and Wang [26], the proposed solution procedure is based on splitting the flux into divergence free components and a remainder. It leads to a variational problem involving solenoidal Raviart–Thomas vector fields. A fast iterative solution method for this problem is presented. It exploits the representation of divergence free vector fields as s of the –conforming finite element functions introduced by Nédélec [43]. We show that a nodal multilevel splitting of these finite element spaces gives rise to an optimal preconditioner for the solenoidal variational problem: Duality techniques in quotient spaces and modern algebraic multigrid theory [50, 10, 31] are the main tools for the proof. Received November 4, 1996 / Revised version received February 2, 1998     

Error analysis of upwind‐discretizations for the steady‐state incompressible Navier–Stokes equations

Within the framework of finite element methods, the paper investigates a general approximation technique for the nonlinear convective term of the Navier–Stokes equations. The approach is based on an upwind method of finite volume type. It is proved that the discrete convective term satisfies a well‐known collection of sufficient conditions for convergence of the finite element solution. This revised version was published online in June 2006 with corrections to the Cover Date.     

Multigrid preconditioned Krylov subspace methods for three-dimensional numerical solutions of the incompressible Navier–Stokes equations

We consider numerical methods for the incompressible Reynolds averaged Navier–Stokes equations discretized by finite difference techniques on non-staggered grids in body-fitted coordinates. A segregated approach is used to solve the pressure–velocity coupling problem. Several iterative pressure linear solvers including Krylov subspace and multigrid methods and their combination have been developed to compare the efficiency of each method and to design a robust solver. Three-dimensional numerical experiments carried out on scalar and vector machines and performed on different fluid flow problems show that a combination of multigrid and Krylov subspace methods is a robust and efficient pressure solver. This revised version was published online in June 2006 with corrections to the Cover Date.     

An adaptive stabilized finite element method for the generalized Stokes problem

In this work we present an adaptive strategy (based on an a posteriori error estimator) for a stabilized finite element method for the Stokes problem, with and without a reaction term. The hierarchical type estimator is based on the solution of local problems posed on appropriate finite dimensional spaces of bubble-like functions. An equivalence result between the norm of the finite element error and the estimator is given, where the dependence of the constants on the physics of the problem is explicited. Several numerical results confirming both the theoretical results and the good performance of the estimator are given.