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.     

Fast and Robust Sixth Order Multigrid Computation for 3D Convection Diffusion Equation

We present a sixth-order explicit compact finite difference scheme to solve the three-dimensional (3D) convection-diffusion equation. We first use a multiscale multigrid method to solve the linear systems arising from a 19-point fourth-order discretization scheme to compute the fourth-order solutions on both a coarse grid and a fine grid. Then an operator-based interpolation scheme combined with an extrapolation technique is used to approximate the sixth-order accurate solution on the fine grid. Since the multigrid method using a standard point relaxation smoother may fail to achieve the optimal grid-independent convergence rate for solving convection-diffusion equations with a high Reynolds number, we implement the plane relaxation smoother in the multigrid solver to achieve better grid independency. Supporting numerical results are presented to demonstrate the efficiency and accuracy of the sixth-order compact (SOC) scheme, compared with the previously published fourth-order compact (FOC) scheme.     

High-order discretization and multigrid solution of elliptic nonlinear constrained optimal control problems

High(-mixed)-order finite difference discretization of optimality systems arising from elliptic nonlinear constrained optimal control problems are discussed. For the solution of these systems, an efficient and robust multigrid algorithm is presented. Theoretical and experimental results show the advantages of higher-order discretization and demonstrate that the proposed multigrid scheme is able to solve efficiently constrained optimal control problems also in the limit case of bang-bang control.     

Multigrid and multilevel methods for quadratic spline collocation

Multigrid methods are developed and analyzed for quadratic spline collocation equations arising from the discretization of one-dimensional second-order differential equations. The rate of convergence of the two-grid method integrated with a damped Richardson relaxation scheme as smoother is shown to be faster than 1/2, independently of the step-size. The additive multilevel versions of the algorithms are also analyzed. The development of quadratic spline collocation multigrid methods is extended to two-dimensional elliptic partial differential equations. Multigrid methods for quadratic spline collocation methods are not straightforward: because the basis functions used with quadratic spline collocation are not nodal basis functions, the design of efficient restriction and extension operators is nontrivial. Experimental results, with V-cycle and full multigrid, indicate that suitably chosen multigrid iteration is a very efficient solver for the quadratic spline collocation equations. Supported by Communications and Information Technology Ontario (CITO), Canada. Supported by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Computational and Technology Research, U.S. Department of Energy, under Contract W-31-109-Eng-38.     

Convergence analysis of a multigrid method for convection–diffusion equations

Summary. This paper is concerned with the convergence analysis of robust multigrid methods for convection-diffusion problems. We consider a finite difference discretization of a 2D model convection-diffusion problem with constant coefficients and Dirichlet boundary conditions. For the approximate solution of this discrete problem a multigrid method based on semicoarsening, matrix-dependent prolongation and restriction and line smoothers is applied. For a multigrid W-cycle we prove an upper bound for the contraction number in the euclidean norm which is smaller than one and independent of the mesh size and the diffusion/convection ratio. For the contraction number of a multigrid V-cycle a bound is proved which is uniform for a class of convection-dominated problems. The analysis is based on linear algebra arguments only. Received April 26, 2000 / Published online June 20, 2001     

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.     

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     

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.     

Multigrid method for solving convection-diffusion problems with dominant convection

A modification of the multigrid method for the solution of linear algebraic equation systems with a strongly nonsymmetric matrix obtained after difference approximation of the convection-diffusion equation with dominant convection is proposed. Specially created triangular iterative methods have been used as the smoothers of the multigrid method. Some theoretical and numerical results are presented.     

The analysis of multigrid algorithms for cell centered finite difference methods

In this paper, we examine multigrid algorithms for cell centered finite difference approximations of second order elliptic boundary value problems. The cell centered application gives rise to one of the simplest non-variational multigrid algorithms. We shall provide an analysis which guarantees that the W-cycle and variable V-cycle multigrid algorithms converge with a rate of iterative convergence which can be bounded independently of the number of multilevel spaces. In contrast, the natural variational multigrid algorithm converges much more slowly.     

The frequency decomposition multi-grid method

Summary The convergence analysis of a special variant of the additive Schwarz iteration is presented. It can be applied to the frequency decomposition multigrid method and yields robust convergence.     

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     

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     

Auxiliary space preconditioning in H 0(curl; Ω)

We adapt the principle of auxiliary space preconditioning as presented in [J. Xu, The auxiliary space method and optimal multigrid preconditioning techniques for unstructured grids, Computing, 56 (1996), pp. 215–235.] to H (curl; ω)-elliptic variational problems discretized by means of edge elements. The focus is on theoretical analysis within the abstract framework of subspace correction. Employing a Helmholtz-type splitting of edge element vector fields we can establish asymptotic h-uniform optimality of the preconditioner defined by our auxiliary space method. This author was fully supported by Hong Kong RGC grant (Project No. 403403) This author acknowledges the support from a Direct Grant of CUHK during his visit at The Chinese University of Hong Kong.     

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     

Fourier analysis of a robust multigrid method for convection-diffusion equations

Summary. We consider a two-grid method for solving 2D convection-diffusion problems. The coarse grid correction is based on approximation of the Schur complement. As a preconditioner of the Schur complement we use the exact Schur complement of modified fine grid equations. We assume constant coefficients and periodic boundary conditions and apply Fourier analysis. We prove an upper bound for the spectral radius of the two-grid iteration matrix that is smaller than one and independent of the mesh size, the convection/diffusion ratio and the flow direction; i.e. we have a (strong) robustness result. Numerical results illustrating the robustness of the corresponding multigrid -cycle are given. Received October 14, 1994     

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.     

A survey of multilevel preconditioned iterative methods

We survey multilevel iterative methods applied for solving large sparse systems with matrices, which depend on a level parameter, such as arise by the discretization of boundary value problems for partial differential equations when successive refinements of an initial discretization mesh is used to construct a sequence of nested difference or finite element meshes.We discuss various two-level (two-grid) preconditioning techniques, including some for nonsymmetric problems. The generalization of these techniques to the multilevel case is a nontrivial task. We emphasize several ways this can be done including classical multigrid methods and a recently proposed algebraic multilevel preconditioning method. Conditions for which the methods have an optimal order of computational complexity are presented.On leave from the Institute of Mathematics, and Center for Informatics and Computer Technology, Bulgarian Academy of Sciences, Sofia, Bulgaria. The research of the second author reported here was partly supported by the Stichting Mathematisch Centrum, Amsterdam.     

The hierarchical basis multigrid method for convection-diffusion equations

Summary We make a theoretical study of the application of a standard hierarchical basis multigrid iteration to the convection diffusion equation, discretized using an upwind finite element discretizations. We show behavior that in some respects is similar to the symmetric positive definite case, but in other respects is markedly different. In particular, we find the rate of convergence depends significantly on parameters which measure the strength of the upwinding, and the size of the convection term. Numerical calculations illustrating some of these effects are given.The work of this author was supported by the Office of Naval Research under contract N00014-89J-1440.The work of this author was supported by the Office of Naval Research under contract N00014-89J-1440.     

A basic norm equivalence for the theory of multilevel methods

Summary Subspace decompositions of finite element spaces based onL ₂-like orthogonal projections play an important role for the construction and analysis of multigrid like iterative methods. Recently several authors have proved the equivalence of the associated discrete norms with theH ¹-norm. The present paper gives an elementary, self-contained derivation of this result which is based on the use ofK-functionals known from the theory of interpolation spaces.