A generalized BPX multigrid framework covering nonnested V-cycle methods

More than a decade ago, Bramble, Pasciak and Xu developed a framework in analyzing the multigrid methods with nonnested spaces or noninherited quadratic forms. It was subsequently known as the BPX multigrid framework, which was widely used in the analysis of multigrid and domain decomposition methods. However, the framework has an apparent limit in the analysis of nonnested V-cycle methods, and it produces a variable V-cycle, or nonuniform convergence rate V-cycle methods, or other nonoptimal results in analysis thus far.

This paper completes a long-time effort in extending the BPX multigrid framework so that it truly covers the nonnested V-cycle. We will apply the extended BPX framework to the analysis of many V-cycle nonnested multigrid methods. Some of them were proven previously only for two-level and W-cycle iterations. Some numerical results are presented to support the theoretical analysis of this paper.

     

Optimal Multigrid Methods with New Transfer Operators Based on Finite Difference Approximations

We constructed new interpolation operator in multigrid methods, which is efficient to transfer residual error from coarse grid to fine grid. This operator used idea of solving local residual equation using the standard stencil and the skewed stencil of the centered difference approximation to the Laplacian operator. We also compared our new multigrid methods with traditional multigrid methods, and found that new method is optimal.     

Convergence analysis of multigrid methods with residual scaling techniques

In this paper, multigrid methods with residual scaling techniques for symmetric positive definite linear systems are considered. The idea of perturbed two-grid methods proposed in [7] is used to estimate the convergence factor of multigrid methods with residual scaled by positive constant scaling factors. We will show that if the convergence factors of the two-grid methods are uniformly bounded by σ (σ<0.5), then the convergence factors of the W-cycle multigrid methods are uniformly bounded by σ/(1−σ), whether the residuals are scaled at some or all levels. This result extends Notay’s Theorem 3.1 in [7] to more general cases. The result also confirms the viewpoint that the W-cycle multigrid method will converge sufficiently well as long as the convergence factor of the two-grid method is small enough. In the case where the convergence factor of the two-grid method is not small enough, by appropriate choice of the cycle index γ, we can guarantee that the convergence factor of the multigrid methods with residual scaling techniques still has a uniform bound less than σ/(1−σ). Numerical experiments are provided to show that the performance of multigrid methods can be improved by scaling the residual with a constant factor. The convergence rates of the two-grid methods and the multigrid methods show that the W-cycle multigrid methods perform better if the convergence rate of the two-grid method becomes smaller. These numerical experiments support the proposed theoretical results in this paper.     

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.     

Comparison of multigrid algorithms for high‐order continuous finite element discretizations

We present a comparison of different multigrid approaches for the solution of systems arising from high‐order continuous finite element discretizations of elliptic partial differential equations on complex geometries. We consider the pointwise Jacobi, the Chebyshev‐accelerated Jacobi, and the symmetric successive over‐relaxation smoothers, as well as elementwise block Jacobi smoothing. Three approaches for the multigrid hierarchy are compared: (1) high‐order h‐multigrid, which uses high‐order interpolation and restriction between geometrically coarsened meshes; (2) p‐multigrid, in which the polynomial order is reduced while the mesh remains unchanged, and the interpolation and restriction incorporate the different‐order basis functions; and (3) a first‐order approximation multigrid preconditioner constructed using the nodes of the high‐order discretization. This latter approach is often combined with algebraic multigrid for the low‐order operator and is attractive for high‐order discretizations on unstructured meshes, where geometric coarsening is difficult. Based on a simple performance model, we compare the computational cost of the different approaches. Using scalar test problems in two and three dimensions with constant and varying coefficients, we compare the performance of the different multigrid approaches for polynomial orders up to 16. Overall, both h‐multigrid and p‐multigrid work well; the first‐order approximation is less efficient. For constant coefficients, all smoothers work well. For variable coefficients, Chebyshev and symmetric successive over‐relaxation smoothing outperform Jacobi smoothing. While all of the tested methods converge in a mesh‐independent number of iterations, none of them behaves completely independent of the polynomial order. When multigrid is used as a preconditioner in a Krylov method, the iteration number decreases significantly compared with using multigrid as a solver. Copyright © 2015 John Wiley & Sons, Ltd.     

High Accuracy Solution of Three-Dimensional Biharmonic Equations

In this paper, we consider several finite-difference approximations for the three-dimensional biharmonic equation. A symbolic algebra package is utilized to derive a family of finite-difference approximations for the biharmonic equation on a 27 point compact stencil. The unknown solution and its first derivatives are carried as unknowns at selected grid points. This formulation allows us to incorporate the Dirichlet boundary conditions automatically and there is no need to define special formulas near the boundaries, as is the case with the standard discretizations of biharmonic equations. We exhibit the standard second-order, finite-difference approximation that requires 25 grid points. We also exhibit two compact formulations of the 3D biharmonic equations; these compact formulas are defined on a 27 point cubic grid. The fourth-order approximations are used to solve a set of test problems and produce high accuracy numerical solutions. The system of linear equations is solved using a variety of iterative methods. We employ multigrid and preconditioned Krylov iterative methods to solve the system of equations. Test results from two test problems are reported. In these experiments, the multigrid method gives excellent results. The multigrid preconditioning also gives good results using Krylov methods.     

Multigrid methods for H(div) in three dimensions with nonoverlapping domain decomposition smoothers

We design and analyze V‐cycle multigrid methods for an H(div) problem discretized by the lowest‐order Raviart–Thomas hexahedral element. The smoothers in the multigrid methods involve nonoverlapping domain decomposition preconditioners that are based on substructuring. We prove uniform convergence of the V‐cycle methods on bounded convex hexahedral domains (rectangular boxes). Numerical experiments that support the theory are also presented.     

An Improvement of Multigrid Methods Using Multiple Grids on Each Layer for Parallel Computing

Multigrid methods are widely used and well studied for linear solvers and preconditioners of Krylov subspace methods. The multigrid method is one of the most powerful approaches for solving large scale linear systems;however, it may show low parallel efficiency on coarse grids. There are several kinds of research on this issue. In this paper, we intend to overcome this difficulty by proposing a novel multigrid algorithm that has multiple grids on each layer.Numerical results indicate that the proposed method shows a better convergence rate compared with the existing multigrid method.     

Multigrid Methods with Newton-Gauss-Seidel Smoothing and Constraint Preserving Interpolation for Obstacle Problems

In this paper, we propose a multigrid algorithm based on the full approximate scheme for solving the membrane constrained obstacle problems and the minimal surface obstacle problems in the formulations of HJB equations. A Newton-Gauss-Seidel (NGS) method is used as smoother. A Galerkin coarse grid operator is proposed for the membrane constrained obstacle problem. Comparing with standard FAS with the direct discretization coarse grid operator, the FAS with the proposed operator converges faster. A special prolongation operator is used to interpolate functions accurately from the coarse grid to the fine grid at the boundary between the active and inactive sets. We will demonstrate the fast convergence of the proposed multigrid method for solving two model obstacle problems and compare the results with other multigrid methods.     

Uniform Convergence of Adaptive Multigrid Methods for Elliptic Problems and Maxwell's Equations

We consider the convergence theory of adaptive multigrid methods for second-order elliptic problems and Maxwell's equations. The multigrid algorithm only performs pointwise Gauss-Seidel relaxations on new degrees of freedom and their "immediate" neighbors. In the context of lowest order conforming finite element approximations, we present a unified proof for the convergence of adaptive multigrid V-cycle algorithms. The theory applies to any hierarchical tetrahedral meshes with uniformly bounded shape-regularity measures. The convergence rates for both problems are uniform with respect to the number of mesh levels and the number of degrees of freedom. We demonstrate our convergence theory by two numerical experiments.     

Modulus‐based multigrid methods for linear complementarity problems

By employing modulus‐based matrix splitting iteration methods as smoothers, we establish modulus‐based multigrid methods for solving large sparse linear complementarity problems. The local Fourier analysis is used to quantitatively predict the asymptotic convergence factor of this class of multigrid methods. Numerical results indicate that the modulus‐based multigrid methods of the W‐cycle can achieve optimality in terms of both convergence factor and computing time, and their asymptotic convergence factors can be predicted perfectly by the local Fourier analysis of the corresponding modulus‐based two‐grid methods.     

Multigrid Waveform Relaxation for Anisotropic Partial Differential Equations

Multigrid waveform relaxation provides fast iterative methods for the solution of time-dependent partial differential equations. In this paper we consider anisotropic problems and extend multigrid methods developed for the stationary elliptic case to waveform relaxation methods for the time-dependent parabolic case. We study line-relaxation, semicoarsening and multiple semicoarsening multilevel methods. A two-grid Fourier–Laplace analysis is used to estimate the convergence of these methods for the rotated anisotropic diffusion equation. We treat both continuous time and discrete time algorithms. The results of the analysis are confirmed by numerical experiments.     

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     

On constrained Newton linearization and multigrid for variational inequalities

Summary. We consider the fast solution of a class of large, piecewise smooth minimization problems. For lack of smoothness, usual Newton multigrid methods cannot be applied. We propose a new approach based on a combination of convex minization with constrained Newton linearization. No regularization is involved. We show global convergence of the resulting monotone multigrid methods and give polylogarithmic upper bounds for the asymptotic convergence rates. Efficiency is illustrated by numerical experiments. Received March 22, 1999 / Revised version received February 24, 2001 / Published online October 17, 2001     

Some numerical experiments with multigrid methods on Shishkin meshes

Piecewise uniform meshes introduced by Shishkin, are a very useful tool to construct robust and efficient numerical methods to approximate the solution of singularly perturbed problems. For small values of the diffusion coefficient, the step size ratios, in this kind of grids, can be very large. In this case, standard multigrid methods are not convergent. To avoid this troublesome, in this paper we propose a modified multigrid algorithm, which works fine on Shishkin meshes. We show some numerical experiments confirming that the proposed multigrid method is convergent, and it has similar properties that standard multigrid for classical elliptic problems.     

Numerical solution of the incompressible Navier-Stokes equations by Krylov subspace and multigrid methods

We consider numerical solution methods for the incompressible Navier-Stokes equations discretized by a finite volume method on staggered grids in general coordinates. We use Krylov subspace and multigrid methods as well as their combinations. Numerical experiments are carried out on a scalar and a vector computer. Robustness and efficiency of these methods are studied. It appears that good methods result from suitable combinations of GCR and multigrid methods.     

WEB-Spline–Based Multigrid Methods for the Stationary Stokes Problem

We discuss a multigrid technique in solving a large system of linear algebraic equations arising in the approximation of Stokes equations by a new strategy based on weighted extended B-spline (WEB-spline) methods. Three types of WEB-spline–based Stokes elements satisfying the inf-sup condition are considered. First for a linear-constant type of Stokes element, we give the detailed multigrid algorithm and its convergence proof. The convergence proof of the multigrid algorithm for a bubble-stabilized WEB-spline–based Stokes element is dealt with separately. Multigrid method in the case of bubble-condensed variational form is simplified using the techniques from the bubble-stabilized case.     

Distributive smoothers in multigrid for problems with dominating grad–div operators

In this paper, we present efficient multigrid methods for systems of partial differential equations that are governed by a dominating grad–div operator. In particular, we show that distributive smoothing methods give multigrid convergence factors that are independent of problem parameters and of the mesh sizes in space and time. The applications range from model problems to secondary consolidation Biot's model. We focus on the smoothing issue and mainly solve academic problems on Cartesian‐staggered grids. Copyright © 2008 John Wiley & Sons, Ltd.     

ON CONVERGENCE OF MULTIGRID METHOD FOR NONNEGATIVE DEFINITE SYSTEMS

In this paper, we consider multigrid methods for solving symmetric nonnegative definite matrix equations. We present some interesting features of the multigrid method and prove that the method is convergent in L2 space and the convergent solution is unique for such nonnegative definite system and given initial guess.     

A robust multigrid approach for variational image registration models

Variational registration models are non-rigid and deformable imaging techniques for accurate registration of two images. As with other models for inverse problems using the Tikhonov regularization, they must have a suitably chosen regularization term as well as a data fitting term. One distinct feature of registration models is that their fitting term is always highly nonlinear and this nonlinearity restricts the class of numerical methods that are applicable. This paper first reviews the current state-of-the-art numerical methods for such models and observes that the nonlinear fitting term is mostly ‘avoided’ in developing fast multigrid methods. It then proposes a unified approach for designing fixed point type smoothers for multigrid methods. The diffusion registration model (second-order equations) and a curvature model (fourth-order equations) are used to illustrate our robust methodology. Analysis of the proposed smoothers and comparisons to other methods are given. As expected of a multigrid method, being many orders of magnitude faster than the unilevel gradient descent approach, the proposed numerical approach delivers fast and accurate results for a range of synthetic and real test images.