Search

Algebraic multigrid (AMG) is one of the most widely used solution techniques for linear systems of equations arising from discretized partial differential equations. The popularity of AMG stems from its potential to solve linear systems in almost linear time, that is with an O(n) complexity, where n is the problem size. This capability is crucial at the present, where the increasing availability of massive HPC platforms pushes for the solution of very large problems. The key for a rapidly converging AMG method is a good interplay between the smoother and the coarse-grid correction, which in turn requires the use of an effective prolongation. From a theoretical viewpoint, the prolongation must accurately represent near kernel components and, at the same time, be bounded in the energy norm. For challenging problems, however, ensuring both these requirements is not easy and is exactly the goal of this work. We propose a constrained minimization procedure aimed at reducing prolongation energy while preserving the near kernel components in the span of interpolation. The proposed algorithm is based on previous energy minimization approaches utilizing a preconditioned restricted conjugate gradients method, but has new features and a specific focus on parallel performance and implementation. It is shown that the resulting solver, when used for large real-world problems from various application fields, exhibits excellent convergence rates and scalability and outperforms at least some more traditional AMG approaches. [ABSTRACT FROM AUTHOR]

Current trends in computer architectures now mean that faster computation speed must come primarily from increased concurrency, not faster clock speeds, which are stagnating. Thus, this situation creates bottlenecks for serial algorithms, including the well‐known bottleneck for sequential time‐integration, where each individual time‐value (i.e., time‐step) is computed sequentially. One approach to alleviate this and achieve parallelism in time is with multigrid. In this work, we consider multigrid‐reduction‐in‐time (MGRIT), a multilevel method applied to the time dimension that computes multiple time‐steps in parallel. Like all multigrid methods, MGRIT relies on the complementary relationship between relaxation on a fine‐grid and a correction from the coarse grid to solve the problem. All current MGRIT implementations are based on unweighted‐Jacobi relaxation; here we introduce the concept of weighted relaxation to MGRIT. We derive new convergence bounds for weighted relaxation, and use this analysis to guide the selection of relaxation weights. Numerical results then demonstrate that by choosing appropriate non‐unitary relaxation weights, one can achieve faster convergence rates and lower iteration counts for MGRIT when compared with unweighted relaxation. In most cases, weighted relaxation yields a 10%–20% saving in iterations, which is significant when using large high‐performance computers. For A‐stable integration schemes, results also illustrate that under‐relaxation can restore convergence in some cases where unweighted relaxation is not convergent. [ABSTRACT FROM AUTHOR]

This paper presents a multilevel convergence framework for multigrid-reduction-intime (MGRIT) as a generalization of previous two-grid estimates. The framework provides a priori upper bounds on the convergence of MGRIT V- and F-cycles, with different relaxation schemes, by deriving the respective residual and error propagation operators. The residual and error operators are functions of the time-stepping operator, analyzed directly and bounded in the norm, both numerically and analytically. We present various upper bounds of different computational cost and varying sharpness. These upper bounds are complemented by proposing analytic formulae for the approximate convergence factor of V-cycle algorithms that take the number of fine grid time points, the temporal coarsening factors, and the eigenvalues of the time-stepping operator as parameters. The paper concludes with supporting numerical investigations of parabolic (anisotropic diffusion) and hyperbolic (wave equation) model problems. We assess the sharpness of the bounds and the quality of the approximate convergence factors. Observations from these numerical investigations demonstrate the value of the proposed multilevel convergence framework for estimating MGRIT convergence a priori and for the design of a convergent algorithm. We further highlight that observations in the literature are captured by the theory, including that two-level Parareal and multilevel MGRIT with F-relaxation do not yield scalable algorithms and the benefit of a stronger relaxation scheme. An important observation is that with increasing numbers of levels MGRIT convergence deteriorates for the hyperbolic model problem, while constant convergence factors can be achieved for the diffusion equation. The theory also indicates that L-stable Runge--Kutta schemes are more amendable to multilevel parallel-in-time integration with MGRIT than A-stable Runge--Kutta schemes. [ABSTRACT FROM AUTHOR]

This review article serves to summarize the many advances in time-parallel computations since the excellent review article by Gander, “50 years of Time Parallel Integration” (Gander, in: 50 years of time parallel time integration. Multiple shooting and time domain decomposition, Springer, Berlin, 2015). We focus, when possible, on applications of time parallelism and the observed speedup and efficiency, highlighting the challenges and benefits of parallel time computations. The applications covered range from numerous PDE-based simulations (both hyperbolic and parabolic), to PDE-constrained optimization, powergrid simulations, and machine learning. The time-parallel methods covered range from various iterative schemes (multigrid, waveform, multiple shooting, domain decomposition) to direct time-parallel methods. [ABSTRACT FROM AUTHOR]

This paper provides a unified and detailed presentation of root-node-style algebraic multigrid (AMG). AMG is a popular and effective iterative method for solving large, sparse linear systems that arise from discretizing partial differential equations. However, while AMG is designed for symmetric positive definite (SPD) matrices, certain SPD problems, such as anisotropic diffusion, are still not adequately addressed by existing methods. Non-SPD problems pose an even greater challenge, and in practice AMG is often not considered as a solver for such problems. The focus of this paper is on so-called root-node AMG, which can be viewed as a combination of classical and aggregation-based multigrid. An algorithm for root-node AMG is outlined, and a filtering strategy is developed, which is able to control the cost of using root-node AMG, particularly on difficult problems. New theoretical motivation is provided for root-node and energy-minimization as applied to symmetric as well nonsymmetric systems. Numerical results are then presented demonstrating the robust ability of root-node AMG to solve nonsymmetric problems, systems-based problems, and difficult SPD problems, including strongly anisotropic diffusion, convection-diffusion, and upwind steady-state transport, in a scalable manner. New detailed estimates of the computational cost of the setup and solve phases are given for each example, providing additional support for root-node AMG over alternative methods. [ABSTRACT FROM AUTHOR]

Algebraic multigrid (AMG) is an O(n) solution process for many large sparse linear systems. A hierarchy of progressively coarser grids which utilize complementary relaxation and interpolation operators is constructed. High-energy error is reduced by relaxation, while low-energy error is mapped to coarse-grid matrices and reduced there. However, large parallel communication costs often limit parallel scalability. As the multigrid hierarchy is formed, each coarse matrix is formed through a triple matrix product. The resulting coarse grids often have significantly more nonzeros per row than the original fine-grid operator, thereby generating high parallel communication costs associated with sparse matrix-vector multiplication (SpMV) on coarse levels. In this paper, we introduce a method that systematically removes entries in coarse-grid matrices after the hierarchy is formed, leading to improved communication costs. We sparsify by removing weakly connected or unimportant entries in the matrix, leading to improved solve time. The main trade-off is that if the heuristic identifying unimportant entries is used too aggressively, then AMG convergence can suffer. To counteract this, the original hierarchy is retained, allowing entries to be reintroduced into the solver hierarchy if convergence is too slow. This enables a balance between communication cost and convergence, as necessary. In this paper we present new algorithms for reducing communication and present a number of computational experiments in support. [ABSTRACT FROM AUTHOR]

Algebraic multigrid (AMG) is a popular and effective solver for systems of linear equations that arise from discretized partial differential equations. While AMG has been effectively implemented on large scale parallel machines, challenges remain, especially when moving to exascale. In particular, stencil sizes (the number of nonzeros in a row) tend to increase further down in the coarse grid hierarchy, and this growth leads to more communication. Thus, as problem size increases and the number of levels in the hierarchy grows, the overall efficiency of the parallel AMG method decreases, sometimes dramatically. This growth in stencil size is due to the standard Galerkin coarse grid operator, PTAP, where P is the prolongation (i.e., interpolation) operator. For example, the coarse grid stencil size for a simple three-dimensional (3D) seven-point finite differencing approximation to diffusion can increase into the thousands on present day machines, causing an associated increase in communication costs. We therefore consider algebraically truncating coarse grid stencils to obtain a non-Galerkin coarse grid. First, the sparsity pattern of the non-Galerkin coarse grid is determined by employing a heuristic minimal "safe" pattern together with strength-of-connection ideas. Second, the nonzero entries are determined by collapsing the stencils in the Galerkin operator using traditional AMG techniques. The result is a reduction in coarse grid stencil size, overall operator complexity, and parallel AMG solve phase times. [ABSTRACT FROM AUTHOR]

SUMMARY A smoothed aggregation-based algebraic multigrid solver for anisotropic diffusion problems is presented. Algebraic multigrid is a popular and effective method for solving sparse linear systems that arise from discretizing partial differential equations. However, although algebraic multigrid was designed for elliptic problems, the case of non-grid-aligned anisotropic diffusion is not adequately addressed by existing methods. To achieve scalable performance, it is shown that neither new coarsening nor new relaxation strategies are necessary. Instead, a novel smoothed aggregation approach is developed that combines long-distance interpolation, coarse-grid injection, and an energy-minimization strategy that finds the interpolation weights. Previously developed theory by Falgout and Vassilevski is used to discern that existing coarsening strategies are sufficient, but that existing interpolation methods are not. In particular, an interpolation quality measure tracks 'closeness' to the ideal interpolant and guides the interpolation sparsity pattern choice. Although the interpolation quality measure is computable for only small model problems, an inexact, but computable, measure is proposed for larger problems. This paper concludes with encouraging numerical results that also potentially show broad applicability (e.g., for linear elasticity). Copyright © 2012 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Algebraic multigrid methods solve sparse linear systems Ax = b by automatic construction of a multilevel hierarchy. This hierarchy is defined by grid transfer operators that must accurately capture algebraically smooth error relative to the relaxation method. We propose a methodology to improve grid transfers through energy minimization. The proposed strategy is applicable to Hermitian, non-Hermitian, definite, and indefinite problems. Each column of the grid transfer operator P is minimized in an energy-based norm while enforcing two types of constraints: a defined sparsity pattern and preservation of specified modes in the range of P. A Krylov-based strategy is used to minimize energy, which is equivalent to solving APj = 0 for each column ) of P, with the constraints ensuring a nontrivial solution. For the Hermitian positive definite case, a conjugate gradient (CG-)based method is utilized to construct grid transfers, while methods based on generalized minimum residual (GMRES) and CG on the normal equations (CGNR) are explored for the general case. The approach is flexible, allowing for arbitrary coarsenings, unrestricted sparsity patterns, straightforward long-distance interpolation, and general use of constraints, either user-defined or auto-generated. We conclude with numerical evidence in support of the proposed framework. [ABSTRACT FROM AUTHOR]

We outline a smoothed aggregation algebraic multigrid method for 1D and 2D scalar Helmholtz problems with exterior radiation boundary conditions. We consider standard 1D finite difference discretizations and 2D discontinuous Galerkin discretizations. The scalar Helmholtz problem is particularly difficult for algebraic multigrid solvers. Not only can the discrete operator be complex-valued, indefinite, and non-self-adjoint, but it also allows for oscillatory error components that yield relatively small residuals. These oscillatory error components are not effectively handled by either standard relaxation or standard coarsening procedures. We address these difficulties through modifications of SA and by providing the SA setup phase with appropriate wave-like near null-space candidates. Much is known a priori about the character of the near null-space, and our method uses this knowledge in an adaptive fashion to find appropriate candidate vectors. Our results for GMRES preconditioned with the proposed SA method exhibit consistent performance for fixed points-per-wavelength and decreasing mesh size. Copyright © 2010 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

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) [ABSTRACT FROM AUTHOR]