A new cascadic multigrid

We present a new cascadic multigrid for elliptic problems.     

A cascadic multigrid algorithm for the Stokes equations

A variant of multigrid schemes for the Stokes problem is discussed. In particular, we propose and analyse a cascadic version for the Stokes problem. The analysis of the transfer between the grids requires special care in order to establish that the complexity is the same as that for classical multigrid algorithms. Received September 10, 1997 / Revised version received February 20, 1998     

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     

Economical cascadic multigrid method (ECMG)

In this paper,an economical cascadic multigrid method is proposed.Compared with the usual cascadic multigrid method developed by Bornemann and Deuflhard,the new one requires less iterations on each level,especially on the coarser grids.Many operations can be saved in the new cascadic multigrid algorithms.The main ingredient is the control of the iteration numbers on the each level to preserve the accuracy without over iterations.The theoretical justification is based on the observations that the error reduction rate of an iteration scheme in terms of the smoothing property is no longer accurate while the iteration number is big enough.A new formulae of the error reduction rate is employed in our new algorithm.Numerical experiments are reported to support our theory.     

A modulus-based cascadic multigrid method for elliptic variational inequality problems

Numerical Algorithms - In this paper, by using a modulus-based matrix splitting method as a smoother, a new modulus-based cascadic multigrid method is presented for solving elliptic variational...     

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     

Extrapolation cascadic multigrid method on piecewise uniform grid

The triangular linear fnite elements on piecewise uniform grid for an elliptic problem in convex polygonal domain are discussed.Global superconvergence in discrete H1-norm and global extrapolation in discrete L2-norm are proved.Based on these global estimates the conjugate gradient method(CG)is efective,which is applied to extrapolation cascadic multigrid method(EXCMG).The numerical experiments show that EXCMG is of the global higher accuracy for both function and gradient.     

A cascadic multigrid method for a kind of semilinear elliptic problem

In this paper, we analyze a cascadic multigrid method for semilinear elliptic problems in which the derivative of the semilinear term is Hölder continuous. We first investigate the standard finite element error estimates of this kind of problem. We then solve the corresponding discrete problems using the cascadic multigrid method. We prove that the algorithm has an optimal order of convergence in energy norm and quasi-optimal computational complexity. We also report some numerical results to support the theory.     

Analysis of extrapolation cascadic multigrid method(EXCMG)

Based on an asymptotic expansion of finite element,a new extrapolation formula and extrapolation cascadic multigrid method(EXCMG)are proposed,in which the new extrapolation and quadratic interpolation are used to provide a better initial value on refined grid.In the case of triple grids,the error of the new initial value is analyzed in detail.A larger scale computation is completed in PC.     

A new wavelet multigrid method

The standard multigrid procedure performs poorly or may break down when used to solve certain problems, such as elliptic problems with discontinuous or highly oscillatory coefficients. The method discussed in this paper solves this problem by using a wavelet transform and Schur complements to obtain the necessary coarse grid, interpolation, and restriction operators. A factorized sparse approximate inverse is used to improve the efficiency of the resulting method. Numerical examples are presented to demonstrate the versatility of the method.     

Convergence of a multigrid cascadic algorithm for second-order finite elements in a domain with smooth boundary

A cascadic multigrid algorithm is substantiated for a grid problem obtained by discretization of a second-order elliptic equation with second-order finite elements on triangles. The efficiency of the algorithm is proved. In particular, it is shown that the number of arithmetic operations required to achieve the order of accuracy of an approximate solution equal to that of the discretization error depends linearly on the number of unknowns. The rate of convergence is found to be higher than one for linear finite elements despite achieving a higher order of accuracy.     

OpenMG: A new multigrid implementation in Python

In many large‐scale computations, systems of equations arise in the form Au = b, where A is a linear operation to be performed on the unknown data u, producing the known right‐hand side, b, which represents some constraint of known or assumed behavior of the system being modeled. Because such systems can be very large, solving them directly can be too slow. In contrast, a multigrid method removes different components of the error at different resolutions using smoothers that reduce high‐frequency components of the error more readily than low. Here, we present an open‐source multigrid solver written only in Python. OpenMG is a pure Python experimentation environment for testing multigrid concepts, not a production solver. The particular restriction method implemented is for ‘standard’ multigrid. By making the code simple and modular, we make the algorithmic details clear. The resulting solver is tested on an implicit pressure reservoir simulation problem with satisfactory results.Copyright © 2013 John Wiley & Sons, Ltd.     

A new smoothed aggregation multigrid method for anisotropic problems

A new prolongator is proposed for smoothed aggregation (SA) multigrid. The proposed prolongator addresses a limitation of standard SA when it is applied to anisotropic problems. For anisotropic problems, it is fairly standard to generate small aggregates (used to mimic semi‐coarsening) in order to coarsen only in directions of strong coupling. Although beneficial to convergence, this can lead to a prohibitively large number of non‐zeros in the standard SA prolongator and the corresponding coarse discretization operator. To avoid this, the new prolongator modifies the standard prolongator by shifting support (non‐zeros within a prolongator column) from one aggregate to another to satisfy a specified non‐zero pattern. This leads to a sparser operator that can be used effectively within a multigrid V‐cycle. The key to this algorithm is that it preserves certain null space interpolation properties that are central to SA for both scalar and systems of partial differential equations (PDEs). We present two‐dimensional and three‐dimensional numerical experiments to demonstrate that the new method is competitive with standard SA for scalar problems, and significantly better for problems arising from PDE systems. Copyright © 2008 John Wiley & Sons, Ltd.     

Asymptotic expansions of finite element solutions to Robin problems in H 3 and their application in extrapolation cascadic multigrid method

For the Poisson equation with Robin boundary conditions,by using a few techniques such as orthogonal expansion(M-type),separation of the main part and the finite element projection,we prove for the first time that the asymptotic error expansions of bilinear finite element have the accuracy of O(h3)for u∈H3.Based on the obtained asymptotic error expansions for linear finite elements,extrapolation cascadic multigrid method(EXCMG)can be used to solve Robin problems effectively.Furthermore,by virtue of Richardson not only the accuracy of the approximation is improved,but also a posteriori error estimation is obtained.Finally,some numerical experiments that confirm the theoretical analysis are presented.     

A new type of full multigrid method for the elasticity eigenvalue problem

This paper introduces a new type of full multigrid method for the elasticity eigenvalue problem. The main idea is to avoid solving large scale elasticity eigenvalue problem directly by transforming the solution of the elasticity eigenvalue problem into a series of solutions of linear boundary value problems defined on a multilevel finite element space sequence and some small scale elasticity eigenvalue problems defined on the coarsest correction space. The involved linear boundary value problems will be solved by performing some multigrid iterations. Besides, some efficient techniques such as parallel computing and adaptive mesh refinement can also be absorbed in our algorithm. The efficiency and validity of the multigrid methods are verified by several numerical experiments.     

A new semi-smooth Newton multigrid method for control-constrained semi-linear elliptic PDE problems

In this paper a new multigrid algorithm is proposed to accelerate the convergence of the semi-smooth Newton method that is applied to the first order necessary optimality systems arising from a class of semi-linear control-constrained elliptic optimal control problems. Under admissible assumptions on the nonlinearity, the discretized Jacobian matrix is proved to have an uniformly bounded inverse with respect to mesh size. Different from current available approaches, a new numerical implementation that leads to a robust multigrid solver is employed to coarsen the grid operator. Numerical simulations are provided to illustrate the efficiency of the proposed method, which shows to be computationally more efficient than the full-approximation-storage multigrid in current literature. In particular, our proposed approach achieves a mesh-independent convergence and its performance is highly robust with respect to the regularization parameter.     

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.     

Single-level multigrid

A single-level multigrid algorithm is developed in which coarse-grid correction is performed on the fine grid. This negates the need for coarse grid storage allocation resulting in easy programmability. The algorithm differs from unigrid in that it mimics multigrid V(0, v) cycles which effectively overcomes the inefficiency of the unigrid technique. The single-level algorithm is therefore both easy to program and efficient. It is illustrated by two numerical examples and compared with unigrid and conventional multigrid.