Analysis of algebraic multigrid parameters for two-dimensional steady-state heat diffusion equations

In this work, it is provided a comparison for the algebraic multigrid (AMG) and the geometric multigrid (GMG) parameters, for Laplace and Poisson two-dimensional equations in square and triangular grids. The analyzed parameters are the number of: inner iterations in the solver, grids and unknowns. For the AMG, the effects of the grid reduction factor and the strong dependence factor in the coarse grid on the necessary CPU time are studied. For square grids the finite difference method is used, and for the triangular grids, the finite volume one. The results are obtained with the use of an adapted AMG1R6 code of Ruge and Stüben. For the AMG the following components are used: standard coarsening, standard interpolation, correction scheme (CS), lexicographic Gauss–Seidel and V-cycle. Comparative studies among the CPU time of the GMG, AMG and singlegrid are made. It was verified that: (1) the optimum inner iterations is independent of the multigrid, however it is dependent on the grid; (2) the optimum number of grids is the maximum number; (3) AMG was shown to be sensitive to both the variation of the grid reduction factor and the strong dependence factor in the coarse grid; (4) in square grids, the GMG CPU time is 20% of the AMG one.     

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.     

Multigrid applications to three-dimensional elliptic coordinate generation

The multigrid algorithm was applied to solve the coupled set of elliptic quasilinear partial differential equations associated with three-dimensional coordinate generation. The results indicate that the multigrid scheme is more than twice as fast as conventional relaxation schemes on moderate-size grids. Convergence factors of order 0.90 per work unit were achieved on 36,000-point grids. The paper covers the form of transformation, develops the set of generation equations, and gives details on the multigrid approach used. Included are a development of the full-approximation storage scheme, details of the smoothing-rate analysis, and a section devoted to rational programming techniques applicable to the multigrid algorithm.     

A multigrid method for grid generation with line-spacing control

A multigrid method for grid generation on two-dimensional regions and its applications to test problems are presented. The multigrid algorithm deals with the solution of elliptic differential problems which occur in the computation of boundary-fitted grids. The solution of elliptic systems of partial differential equations, which correspond to transformed Poisson systems, is carried out by a full approximation storage (FAS) algorithm. The components of the method, such as the relaxation for error smoothing and the coarsening strategy, are evaluated on problems in which sources of attractions are considered, and the generated grids are shown by figures.     

Comparison of two cell-centered multigrid schemes for problems with discontinuous coefficients

Two different schemes for constructing coarse-grid operators are implemented in a linear multigrid code. In the first scheme, the construction of the coarse-grid operators is done using a variational approach. Certain conservation properties of the fine-grid matrices are shown to be preserved on the coarser grids by the variational construction. In the second scheme, the diffusion coefficients for the coarse grids are calculated by a simple restriction of the coefficient from the fine grid, using a flux conservation principle. The multigrid codes are then applied to solve the linear equations from an IMPES formulation of a two-phase porous-media flow model. A standard elliptic model problem with jump discontinuous coefficients is also solved using the two multigrid schemes. In simple cases of particular elliptic equations these two schemes are identical. However, in more general cases, such as in reservoir problems, these schemes differ. It is shown that multigrid efficiency typical of the constant coefficient cases is obtained for these problems involving discontinuous coefficients. © 1993 John Wiley & Sons, Inc.     

Numerical algorithm for solving diffusion-type equations on the basis of multigrid methods

A new numerical algorithm based on multigrid methods is proposed for solving equations of the parabolic type. Theoretical error estimates are obtained for the algorithm as applied to a two-dimensional initial-boundary value model problem for the heat equation. The good accuracy of the algorithm is demonstrated using model problems including ones with discontinuous coefficients. As applied to initial-boundary value problems for diffusion equations, the algorithm yields considerable savings in computational work compared to implicit schemes on fine grids or explicit schemes with a small time step on fine grids. A parallelization scheme is given for the algorithm.     

基于PDE和几何曲率流驱动扩散的图像分析与处理

本文介绍由变分优化模型导出的偏微分方程(PDEs)模型与几何曲率流驱动扩散在图像恢复方面的应用，以及多种非线性异质扩散模型，讨论了PDEs模型在图像分析与处理方面的优点，理论与实验结果表明，要恢复得到商质量的图像，PDEs模型的利用是极为必要的．文中还介绍了求解PDEs模型的数值方案．其中，曲率计算是一个关键问题，其结果直接参与自适应扩散的控制．详细总结了基于有限差分和水平集方法，求解藕合非线性异质扩散模型方程的数值方案，追求高质量图像、高精度计算方法、降低计算复杂性是本文处理方法不断进步的发展动力。     

Sparse-grid finite-volume multigrid for 3D-problems

We introduce a multigrid algorithm for the solution of a second order elliptic equation in three dimensions. For the approximation of the solution we use a partially ordered hierarchy of finite-volume discretisations. We show that there is a relation with semicoarsening and approximation by more-dimensional Haar wavelets. By taking a proper subset of all possible meshes in the hierarchy, a sparse grid finite-volume discretisation can be constructed.The multigrid algorithm consists of a simple damped point-Jacobi relaxation as the smoothing procedure, while the coarse grid correction is made by interpolation from several coarser grid levels.The combination of sparse grids and multigrid with semi-coarsening leads to a relatively small number of degrees of freedom,N, to obtain an accurate approximation, together with anO(N) method for the solution. The algorithm is symmetric with respect to the three coordinate directions and it is fit for combination with adaptive techniques.To analyse the convergence of the multigrid algorithm we develop the necessary Fourier analysis tools. All techniques, designed for 3D-problems, can also be applied for the 2D case, and — for simplicity — we apply the tools to study the convergence behaviour for the anisotropic Poisson equation for this 2D case.     

The convergence of V-cycle multigrid algorithms for axisymmetric Laplace and Maxwell equations

We investigate some simple finite element discretizations for the axisymmetric Laplace equation and the azimuthal component of the axisymmetric Maxwell equations as well as multigrid algorithms for these discretizations. Our analysis is targeted at simple model problems and our main result is that the standard V-cycle with point smoothing converges at a rate independent of the number of unknowns. This is contrary to suggestions in the existing literature that line relaxations and semicoarsening are needed in multigrid algorithms to overcome difficulties caused by the singularities in the axisymmetric Maxwell problems. Our multigrid analysis proceeds by applying the well known regularity based multigrid theory. In order to apply this theory, we prove regularity results for the axisymmetric Laplace and Maxwell equations in certain weighted Sobolev spaces. These, together with some new finite element error estimates in certain weighted Sobolev norms, are the main ingredients of our analysis.

     

Accuracy,robustness and efficiency comparison in iterative computation of convection diffusion equation with boundary layers

Nine‐point fourth‐order compact finite difference scheme, central difference scheme, and upwind difference scheme are compared for solving the two‐dimensional convection diffusion equations with boundary layers. The domain is discretized with a stretched nonuniform grid. A grid transformation technique maps the nonuniform grid to a uniform one, on which the difference schemes are applied. A multigrid method and a multilevel preconditioning technique are used to solve the resulting sparse linear systems. We compare the accuracy of the computed solutions from different discretization schemes, and demonstrate the relative efficiency of each scheme. Comparisons of maximum absolute errors, iteration counts, CPU timings, and memory cost are made with respect to the two solution strategies. © 2000 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 16: 379–394, 2000     

On the convergence of nonnested multigrid methods with nested spaces on coarse grids

Multigrid methods for discretized partial differential problems using nonnested conforming and nonconforming finite elements are here defined in the general setting. The coarse‐grid corrections of these multigrid methods make use of different finite element spaces from those on the finest grid. In general, the finite element spaces on the finest grid are nonnested, while the spaces are nested on the coarse grids. An abstract convergence theory is developed for these multigrid methods for differential problems without full elliptic regularity. This theory applies to multigrid methods of nonnested conforming and nonconforming finite elements with the coarse‐grid corrections established on nested conforming finite element spaces. Uniform convergence rates (independent of the number of grid levels) are obtained for both the V and W‐cycle methods with one smoothing on all coarse grids and with a sufficiently large number of smoothings solely on the finest grid. In some cases, these uniform rates are attained even with one smoothing on all grids. The present theory also applies to multigrid methods for discretized partial differential problems using mixed finite element methods. © 2000 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 16: 265–284, 2000     

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.     

A nonstandard multigrid method with flexible multiple semicoarsening for the numerical solution of the pressure equation in a Navier-Stokes solver

Numerical methods for the incompressible Reynolds-averaged Navier-Stokes equations discretized by finite difference techniques on collocated cell-centered structured grids are considered in this paper. A widespread solution method to solve the pressure-velocity coupling problem is to use a segregated approach, in which the computational work is deeply controlled by the solution of the pressure problem. This pressure equation is an elliptic partial differential equation with possibly discontinuous or anisotropic coeffficients. The resulting singular linear system needs efficient solution strategies especially for 3-dimensional applications. A robust method (close to MG-S [22,34]) combining multiple cell-centered semicoarsening strategies, matrix-independent transfer operators, Galerkin coarse grid approximation is therefore designed. This strategy is both evaluated as a solver or as a preconditioner for Krylov subspace methods on various 2- or 3-dimensional fluid flow problems. The robustness of this method is shown. This revised version was published online in June 2006 with corrections to the Cover Date.     

一种新的并行代数多重网格粗化算法

近年来,受实际应用领域中大规模科学计算问题的驱动,在大规模并行机上实现代数多重网格（AMG）算法成为数值计算领域的研究热点。本文针对经典AMG方法,提出一种新的并行网格粗化算法一多阶段并行RS算法（MPRS）。我们将新算法集成到了高性能预条件子软件包Hypre中。大量数值实验结果显示,新算法适合更广泛的问题,相对其他并行粗化算法,明显地改善了AMG并行计算的可扩展性。对三维27点格式有限差分离散的Poisson方程,在64个处理机上并行AMG求解,含8百万个未知量,新算法比RS3算法减少了近60的三维Poisson方程,近32万个未知量,在16个处理机上并行AMG—GMRES求解,新算法所需的迭代步数大约为其他粗化算法的一半,显示了很好的算法可扩展性。     

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 boundary integral equations

Summary Multigrid methods are applied for solving algebraic systems of equations that occur to the numerical treatment of boundary integral equations of the first and second kind. These methods, originally formulated for partial differential equations of elliptic type, combine relaxation schemes and coarse grid corrections. The choice of the relaxation scheme is found to be essential to attain a fast convergent iterative process. Theoretical investigations show that the presented relaxation scheme provides a multigrid algorithm of which the rate of convergence increases with the dimension of the finest grid. This is illustrated for the calculation of potential flow around an aerofoil.     

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.     

Geometric and algebraic multigrid techniques for fluid dynamics problems on unstructured grids

Issues concerning the implementation and practical application of geometric and algebraic multigrid techniques for solving systems of difference equations generated by the finite volume discretization of the Euler and Navier–Stokes equations on unstructured grids are studied. The construction of prolongation and interpolation operators, as well as grid levels of various resolutions, is discussed. The results of the application of geometric and algebraic multigrid techniques for the simulation of inviscid and viscous compressible fluid flows over an airfoil are compared. Numerical results show that geometric methods ensure faster convergence and weakly depend on the method parameters, while the efficiency of algebraic methods considerably depends on the input parameters.