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.     

Generalizing reduction-based algebraic multigrid

Algebraic multigrid (AMG) methods are often robust and effective solvers for solving the large and sparse linear systems that arise from discretized PDEs and other problems, relying on heuristic graph algorithms to achieve their performance. Reduction-based AMG (AMGr) algorithms attempt to formalize these heuristics by providing two-level convergence bounds that depend concretely on properties of the partitioning of the given matrix into its fine- and coarse-grid degrees of freedom. MacLachlan and Saad (SISC 2007) proved that the AMGr method yields provably robust two-level convergence for symmetric and positive-definite matrices that are diagonally dominant, with a convergence factor bounded as a function of a coarsening parameter. However, when applying AMGr algorithms to matrices that are not diagonally dominant, not only do the convergence factor bounds not hold, but measured performance is notably degraded. Here, we present modifications to the classical AMGr algorithm that improve its performance on matrices that are not diagonally dominant, making use of strength of connection, sparse approximate inverse (SPAI) techniques, and interpolation truncation and rescaling, to improve robustness while maintaining control of the algorithmic costs. We present numerical results demonstrating the robustness of this approach for both classical isotropic diffusion problems and for non-diagonally dominant systems coming from anisotropic diffusion.     

A new cascadic multigrid

We present a new cascadic multigrid for elliptic problems.     

A new cascadic multigrid

We present a new cascadic multigrid for elliptic problems.     

Remarks on multigrid convergence theorems

Multigrid has become an important iterative method for the solution of discrete elliptic equations. However, there is much to be done in the theory of convergence proofs. At the present time there are two general two-level methods for general convergence proofs: an algebraic approach and a duality approach. While these theories do not give sharp estimates, they provide good, general, rigorous convergence theorems. In this note we study the relationship between these theories. While the approach and thought process leading to these theories are different, the results are essentially the same. Indeed, the basic estimates required by these theories are the same.     

Algebraic analysis of multigrid algorithms

We study the convergence rate of multilevel algorithms from an algebraic point of view. This requires a detailed analysis of the constant in the strengthened Cauchy–Schwarz inequality between the coarse‐grid space and a so‐called complementary space. This complementary space may be spanned by standard hierarchical basis functions, prewavelets or generalized prewavelets. Using generalized prewavelets, we are able to derive a constant in the strengthened Cauchy–Schwarz inequality which is less than 0.31 for the L² and H¹ bilinear form. This implies a convergence rate less than 0.15. So, we are able to prove fast multilevel convergence. Furthermore, we obtain robust estimations of the convergence rate for a large class of anisotropic ellipic equations, even for some that are not H¹‐elliptic. Copyright © 1999 John Wiley & Sons, Ltd.     

Artificial damping in multigrid methods

When the solution and problem coefficients are highly oscillatory, the computed solution may not show characteristics of the original physical problem unless the numerical mesh is sufficiently fine. In the case, the coarse grid problem of a multigrid (MG) algorithm must be still huge and poorly-conditioned, and therefore, it is hard to solve by either a direct method or an iterative scheme. This article suggests a MG algorithm for such problems in which the coarse grid problem is slightly modified by an artificial damping (compressibility) term. It has been numerically observed that the artificial damping, even if slight, makes the coarse grid problem much easier to solve, without deteriorating the overall convergence rate of the MG method. For most problems, 2–6 times speed up have been observed.     

The hierarchical basis multigrid method

Summary We derive and analyze the hierarchical basis-multigrid method for solving discretizations of self-adjoint, elliptic boundary value problems using piecewise linear triangular finite elements. The method is analyzed as a block symmetric Gauß-Seidel iteration with inner iterations, but it is strongly related to 2-level methods, to the standard multigridV-cycle, and to earlier Jacobi-like hierarchical basis methods. The method is very robust, and has a nearly optimal convergence rate and work estimate. It is especially well suited to difficult problems with rough solutions, discretized using highly nonuniform, adaptively refined meshes.     

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.     

Analysis of tensor product multigrid

We consider anisotropic second order elliptic boundary value problems in two dimensions, for which the anisotropy is exactly aligned with the coordinate axes. This includes cases where the operator features a singular perturbation in one coordinate direction, whereas its restriction to the other direction remains neatly elliptic. Most prominently, such a situation arises when polar coordinates are introduced.The common multigrid approach to such problems relies on line relaxation in the direction of the singular perturbation combined with semi-coarsening in the other direction. Taking the idea from classical Fourier analysis of multigrid, we employ eigenspace techniques to separate the coordinate directions. Thus, convergence of the multigrid method can be examined by looking at one-dimensional operators only. In a tensor product Galerkin setting, this makes it possible to confirm that the convergence rates of the multigrid V-cycle are bounded independently of the number of grid levels involved. In addition, the estimates reveal that convergence is also robust with respect to a singular perturbation in one coordinate direction.Finally, we supply numerical evidence that the algorithm performs satisfactorily in settings more general than those covered by the proof.     

Analysis of matrix-dependent multigrid algorithms

Convergence theory for a multigrid method with matrix-dependent restriction, prolongation and coarse-grid operators is developed for a class of SPD problems. It motivates the construction of improved multigrid versions for diffusion problems with discontinuous coefficients. A computational two-level analysis method for a class of separable problems is also available. It motivates the design of matrix-dependent multigrid algorithms and, in particular, multiple coarse-grid correction algorithms for highly indefinite equations. Numerical experiments show the advantage of the present methods for several examples. © 1998 John Wiley & Sons, Ltd.     

Note on the multigrid W-cycle

The multigrid W-cycle for the solution of sparse linear systems implemented with Galerkin schemes on the coarse levels is considered. It is shown that the recalculation of the fine-level residual in the middle of the W-cycle is unnecessary since it yields an algorithm which is mathematically equivalent to the one in which such recalculation is not used.     

Parallel time integration with multigrid

With current trends in computer architectures leading towards systems with more, but not faster, processors, faster time-to-solution must come from greater parallelism. We present a family of truly multilevel approaches to parallel time integration based on multigrid reduction (MGR) principles. The resulting multigrid-reduction-in-time (MGRIT) algorithms are non-intrusive approaches, which directly use an existing time propagator and, thus, can easily exploit substantially more computational resources then standard sequential time-stepping. Furthermore, we demonstrate that MGRIT offers excellent strong and weak parallel scaling up to thousands of processors for solving diffusion equations in two and three space dimensions. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Using block smoothers in multigrid methods

We present a general setting for the analysis of blocked smoothers using the LFA. (© 2012 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Nonnested multigrid methods for linear problems

This article presents an application of nonnested and unstructured multigrid methods to linear elastic problems. A variational formulation for transfer operators and some multigrid strategies, including adaptive algorithms, are presented. Expressions for the performance evaluation of multigrid strategies and its comparison with direct and preconditioned conjugate gradient algorithms are also presented. A C++ implementation of the multigrid algorithms and the quadtree and octree data structures for transfer operators are discussed. Some two‐ and three‐dimensional elasticity examples are analyzed. © 2001 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 17:313–331, 2001     

Optimal polynomial smoothers for multigrid V-cycles

The idea of using polynomial methods to improve simple smoother iterations within a multigrid method for a symmetric positive definite system is revisited. A two-level bound going back to Hackbusch is optimized by a very simple iteration, a close cousin of the Chebyshev semi-iterative method, but based on the Chebyshev polynomials of the fourth instead of first kind. A full V-cycle bound for general polynomial smoothers is derived using the V-cycle theory of McCormick. The fourth-kind Chebyshev iteration is quasi-optimal for the V-cycle bound. The optimal polynomials for the V-cycle bound can be found numerically, achieving about an 18% lower error contraction factor bound than the fourth-kind Chebyshev iteration, asymptotically as the number of smoothing steps $k\to \infty$. Implementation of the optimized iteration is discussed, and the performance of the polynomial smoothers is illustrated with numerical examples.     

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.     

Cascadic multigrid methods for parabolic problems

In this paper,we consider the cascadic multigrid method for a parabolic type equation.Backward Euler approximation in time and linear finite element approximation in space are employed.A stability result is established under some conditions on the smoother.Using new and sharper estimates for the smoothers that reflect the precise dependence on the time step and the spatial mesh parameter,these conditions are verified for a number of popular smoothers.Optimal error bound sare derived for both smooth and non-smooth data.Iteration strategies guaranteeing both the optimal accuracy and the optimal complexity are presented.     

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.