Search

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]

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]

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]