A multi-grid method with a priori and a posteriori level choice for the regularization of nonlinear ill-posed problems

Summary In this paper we study a multi-grid method for the numerical solution of nonlinear systems of equations arising from the discretization of ill-posed problems, where the special eigensystem structure of the underlying operator equation makes it necessary to use special smoothers. We provide uniform contraction factor estimates and show that a nested multigrid iteration together with an a priori or a posteriori chosen stopping index defines a regularization method for the ill-posed problem, i.e., a stable solution method, that converges to an exact solution of the underlying infinite-dimensional problem as the data noise level goes to zero, with optimal rates under additional regularity conditions. Supported by the Fonds zur F?rderung der wissenschaftlichen Forschung under grant T 7-TEC and project F1308 within Spezialforschungsbereich 13     

Nonlinear multigrid method for solving the anisotropic image denoising models

In this paper, we study a nonlinear multigrid method for solving a general image denoising model with two L ¹-regularization terms. Different from the previous studies, we give a simpler derivation of the dual formulation of the general model by augmented Lagrangian method. In order to improve the convergence rate of the proposed multigrid method, an improved dual iteration is proposed as its smoother. Furthermore, we apply the proposed method to the anisotropic ROF model and the anisotropic LLT model. We also give the local Fourier analysis (LFAs) of the Chambolle’s dual iterations and a modified smoother for solving these two models, respectively. Numerical results illustrate the efficiency of the proposed method and indicate that such a multigrid method is more suitable to deal with large-sized images.     

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.     

An algebraic multigrid method for finite element systems on criss-cross grids

In this paper, we design and analyze an algebraic multigrid method for a condensed finite element system on criss-cross grids and then provide a convergence analysis. Criss-cross grid finite element systems represent a large class of finite element systems that can be reduced to a smaller system by first eliminating certain degrees of freedoms. The algebraic multigrid method that we construct is analogous to many other algebraic multigrid methods for more complicated problems such as unstructured grids, but, because of the specialty of our problem, we are able to provide a rigorous convergence analysis to our algebraic multigrid method. Dedicated to Professor Charles A. Micchelli on the occasion of his 60th birthday The work was supported in part by NSAF(10376031) and National Major Key Project for basic researches and by National High-Tech ICF Committee in China.     

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.     

A Multigrid Method Based on Incomplete Gaussian Elimination

In this paper we introduce and analyse a new Schur complement approximation based on incomplete Gaussian elimination. The approximate Schur complement is used to develop a multigrid method. This multigrid method has an algorithmic structure that is very similar to the algorithmic structure of classical multigrid methods. The resulting method is almost purely algebraic and has interesting properties with respect to variation in problem parameters.     

A convergence analysis of nonlinear implicit iterative method for nonlinear ill-posed problems

Implicit iterative method acquires good effect in solving linear ill-posed problems. We have ever applied the idea of implicit iterative method to solve nonlinear ill-posed problems, under the restriction that α is appropriate large, we proved the monotonicity of iterative error and obtained the convergence and stability of iterative sequence, numerical results show that the implicit iterative method for nonlinear ill-posed problems is efficient. In this paper, we analyze the convergence and stability of the corresponding nonlinear implicit iterative method when α_k are determined by Hanke criterion.     

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 multigrid‐based shifted Laplacian preconditioner for a fourth‐order Helmholtz discretization

In this paper, an iterative solution method for a fourth‐order accurate discretization of the Helmholtz equation is presented. The method is a generalization of that presented in (SIAM J. Sci. Comput. 2006; 27 :1471–1492), where multigrid was employed as a preconditioner for a Krylov subspace iterative method. The multigrid preconditioner is based on the solution of a second Helmholtz operator with a complex‐valued shift. In particular, we compare preconditioners based on a point‐wise Jacobi smoother with those using an ILU(0) smoother, we compare using the prolongation operator developed by de Zeeuw in (J. Comput. Appl. Math. 1990; 33 :1–27) with interpolation operators based on algebraic multigrid principles, and we compare the performance of the Krylov subspace method Bi‐conjugate gradient stabilized with the recently introduced induced dimension reduction method, IDR(s). These three improvements are combined to yield an efficient solver for heterogeneous problems. Copyright © 2009 John Wiley & Sons, Ltd.     

Recursive two-levelILU preconditioner for nonsymmetric M-matrices

We develop in this paper some preconditioners for sparse non-symmetric M-matrices, which combine a recursive two-level blockILU factorization with multigrid method, we compare these preconditioners on matrices arising from discretized convection-diffusion equations using upwind finite difference schemes and multigrid orderings, some comparison theorems and experiment results are demonstrated.     

MULTIGRID METHODS FOR OBSTACLE PROBLEMS

In this review,we intend to clarify the underlying ideas and the relations between various multigrid methods ranging from subset decomposition,to projected subspace decomposition and truncated multigrid.In addition,we present a novel globally convergent inexact active set method which is closely related to truncated multigrid.The numerical properties of algorithms are carefully assessed by means of a degenerate problem and a problem with a complicated coincidence set.     

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.     

A numerical method for the Cahn–Hilliard equation with a variable mobility

We consider a conservative nonlinear multigrid method for the Cahn–Hilliard equation with a variable mobility of a model for phase separation in a binary mixture. The method uses the standard finite difference approximation in spatial discretization and the Crank–Nicholson semi-implicit scheme in temporal discretization. And the resulting discretized equations are solved by an efficient nonlinear multigrid method. The continuous problem has the conservation of mass and the decrease of the total energy. It is proved that these properties hold for the discrete problem. Also, we show the proposed scheme has a second-order convergence in space and time numerically. For numerical experiments, we investigate the effects of a variable mobility.     

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.     

平面线弹性纯位移边值问题低阶非协调矩形元的Robust多重网格方法

1引 言 对于各向同性,均匀介质的平面线弹性问题,当Lamé常数λ→∞(泊松率v→0.5)时,即对于几乎不可压介质,通常的协调有限元格式的解往往不再收敛到原问题的解,或者达不到最优收敛阶,这就是所谓的闭锁现象(见[3],[7],[8]及[10]).究其原因,在通常的有限元分析中,其误差估计的系数与λ有关,当λ→∞时,该系数将趋于无穷大.因此为克服闭锁现象就需要构造特殊的有限元格式,使得当λ→∞时,有限元逼近解仍然收敛到原问题的解.     

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.     

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.     

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.     

Multigrid method for nonlinear integral equations

In this paper, we introduce a multigrid method for solving the nonliear Urysohn integral equation. The algorithm is derived from a discrete resolvent equation which approximates the continuous resolvent equation of the nonlinear Urysohn integral equation. The algorithm is mathematically equivalent to Atkinson’s adaptive twogrid iteration. But the two are different computationally. We show the convergence of the algorithm and its equivalence to Atkinson’s adaptive twogrid iteration. In our numerical example, we compare our algorithm to other multigrid methods for solving the nonliear Urysohn integral equation including the nonlinear multigrid method introduced by Hackbush.