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.

     

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.     

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.     

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.     

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 full multigrid method for nonlinear eigenvalue problems

We introduce a type of full multigrid method for the nonlinear eigenvalue problem. The main idea is to transform the solution of the nonlinear eigenvalue problem into a series of solutions of the corresponding linear boundary value problems on the sequence of finite element spaces and nonlinear eigenvalue problems on the coarsest finite element space. The linearized boundary value problems are solved by some multigrid iterations. Besides the multigrid iteration, all other efficient iteration methods for solving boundary value problems can serve as the linear problem solver. We prove that the computational work of this new scheme is truly optimal, the same as solving the linear corresponding boundary value problem. In this case, this type of iteration scheme certainly improves the overfull efficiency of solving nonlinear eigenvalue problems. Some numerical experiments are presented to validate the efficiency of the new method.     

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.     

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.     

A note on terminology in multigrid methods

We compare terminology used in the literature on multigrid methods for compressible computational fluid dynamics to that used in linear multigrid theory. Several popular iterative and direct smoothers are presented side-by-side using the same terminology. We argue for greater analysis of these methods in order to place them into a more rigorous framework and to identify the most promising candidates for future development. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

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.     

Multigrid methods for a parameter dependent problem in primal variables

Summary. In this paper we consider multigrid methods for the parameter dependent problem of nearly incompressible materials. We construct and analyze multilevel-projection algorithms, which can be applied to the mixed as well as to the equivalent, non-conforming finite element scheme in primal variables. For proper norms, we prove that the smoothing property and the approximation property hold with constants that are independent of the small parameter. Thus we obtain robust and optimal convergence rates for the W-cycle and the variable V-cycle multigrid methods. The numerical results pretty well conform the robustness and optimality of the multigrid methods proposed. Received June 17, 1998 / Revised version received October 26, 1998 / Published online September 7, 1999     

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.     

Local Fourier Analysis of Multigrid Methods with Polynomial Smoothers and Aggressive Coarsening

We focus on the study of multigrid methods with aggressive coarsening and polynomial smoothers for the solution of the linear systems corresponding to finite difference/element discretizations of the Laplace equation. Using local Fourier analysis we determine automatically the optimal values for the parameters involved in defining the polynomial smoothers and achieve fast convergence of cycles with aggressive coarsening. We also present numerical tests supporting the theoretical results and the heuristic ideas. The methods we introduce are highly parallelizable and efficient multigrid algorithms on structured and semi-structured grids in two and three spatial dimensions.     

A full multigrid method for semilinear elliptic equation

A full multigrid finite element method is proposed for semilinear elliptic equations. The main idea is to transform the solution of the semilinear problem into a series of solutions of the corresponding linear boundary value problems on the sequence of finite element spaces and semilinear problems on a very low dimensional space. The linearized boundary value problems are solved by some multigrid iterations. Besides the multigrid iteration, all other efficient numerical methods can also serve as the linear solver for solving boundary value problems. The optimality of the computational work is also proved. Compared with the existing multigrid methods which need the bounded second order derivatives of the nonlinear term, the proposed method only needs the Lipschitz continuation in some sense of the nonlinear term.     

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.     

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.     

An accelerated algebraic multigrid algorithm for total-variation denoising

The variational partial differential equation (PDE) approach for image denoising restoration leads to PDEs with nonlinear and highly non-smooth coefficients. Such PDEs present convergence difficulties for standard multigrid methods. Recent work on algebraic multigrid methods (AMGs) has shown that robustness can be achieved in general but AMGs are well known to be expensive to apply. This paper proposes an accelerated algebraic multigrid algorithm that offers fast speed as well as robustness for image PDEs. Experiments are shown to demonstrate the improvements obtained.     

Efficient numerical methods for pricing American options under stochastic volatility

Five numerical methods for pricing American put options under Heston's stochastic volatility model are described and compared. The option prices are obtained as the solution of a two‐dimensional parabolic partial differential inequality. A finite difference discretization on nonuniform grids leading to linear complementarity problems with M‐matrices is proposed. The projected SOR, a projected multigrid method, an operator splitting method, a penalty method, and a componentwise splitting method are considered. The last one is a direct method while all other methods are iterative. The resulting systems of linear equations in the operator splitting method and in the penalty method are solved using a multigrid method. The projected multigrid method and the componentwise splitting method lead to a sequence of linear complementarity problems with one‐dimensional differential operators that are solved using the Brennan and Schwartz algorithm. The numerical experiments compare the accuracy and speed of the considered methods. The accuracies of all methods appear to be similar. Thus, the additional approximations made in the operator splitting method, in the penalty method, and in the componentwise splitting method do not increase the error essentially. The componentwise splitting method is the fastest one. All multigrid‐based methods have similar rapid grid independent convergence rates. They are about two or three times slower that the componentwise splitting method. On the coarsest grid the speed of the projected SOR is comparable with the multigrid methods while on finer grids it is several times slower. ©John Wiley & Sons, Inc. © 2007 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2007     

Conservative solution of the Fokker–Planck equation for stochastic chemical reactions

In this paper we discuss multigrid methods for ill-conditioned symmetric positive definite block Toeplitz matrices. Our block Toeplitz systems are general in the sense that the individual blocks are not necessarily Toeplitz, but we restrict our attention to blocks of small size. We investigate how transfer operators for prolongation and restriction have to be chosen such that our multigrid algorithms converge quickly. We point out why these transfer operators can be understood as block matrices as well and how they relate to the zeroes of the generating matrix function. We explain how our new algorithms can also be combined efficiently with the use of a natural coarse grid operator. We clearly identify a class of ill-conditioned block Toeplitz matrices for which our algorithmic ideas are suitable. In the final section we present an outlook to well-conditioned block Toeplitz systems and to problems of vector Laplace type. In the latter case the small size blocks can be interpreted as degrees of freedom associated with a node. A large number of numerical experiments throughout the article confirms convincingly that our multigrid solvers lead to optimal order convergence. AMS subject classification (2000) 65N55, 65F10     

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.