Search NASA⌕ Search

SEARCH · Search NASA

Results for “multigrid solvers”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 55 records · Page 3
All sourcesNASA NTRSDOE OSTI
NASA NTRS1997

Some Approaches Towards Constructing Optimally Efficient Multigrid Solvers for the Inviscid Flow Equations

Some important advances took place during the last several years in the development of genuinely multidimensional upwind schemes for the compressible Euler equations. In particular, a robust, high-resolution genuinely multidimensional scheme which can be used for any of the flow regimes computations was constructed. This paper summarizes briefly these developments and outlines the fundamental advantages of this approach.

Sidilkover, David↗
DOE OSTI2014

s-Step Krylov Subspace Methods as Bottom Solvers for Geometric Multigrid

Geometric multigrid solvers within adaptive mesh refinement (AMR) applications often reach a point where further coarsening of the grid becomes impractical as individual sub domain sizes approach unity. At this point the most common solution is to use a bottom solver, such as BiCGStab, to reduce the residual by a fixed factor at the coarsest level. Each iteration of BiCGStab requires multiple global reductions (MPI collectives). As the number of BiCGStab iterations required for convergence grows with problem size, and the time for each collective operation increases with machine scale, bottom solves in large-scale applications can constitute a significant fraction of the overall multigrid solve time. In this paper, we implement, evaluate, and optimize a communication-avoiding s-step formulation of BiCGStab (CABiCGStab for short) as a high-performance, distributed-memory bottom solver for geometric multigrid solvers. This is the first time s-step Krylov subspace methods have been leveraged to improve multigrid bottom solver performance. We use a synthetic benchmark for detailed analysis and integrate the best implementation into BoxLib in order to evaluate the benefit of a s-step Krylov subspace method on the multigrid solves found in the applications LMC and Nyx on up to 32,768 cores on the Cray XE6 at NERSC. Overall, we see bottom solver improvements of up to 4.2x on synthetic problems and up to 2.7x in real applications. This results in as much as a 1.5x improvement in solver performance in real applications.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS2005

Full Multigrid Flow Solver

FMG3D (full multigrid 3 dimensions) is a pilot computer program that solves equations of fluid flow using a finite difference representation on a structured grid. Infrastructure exists for three dimensions but the current implementation treats only two dimensions. Written in Fortran 90, FMG3D takes advantage of the recursive subroutine feature, dynamic memory allocation, and structured-programming constructs of that language. FMG3D supports multi-block grids with three types of block-to-block interfaces: periodic, C-zero, and C-infinity. For all three types, grid points must match at interfaces. For periodic and C-infinity types, derivatives of grid metrics must be continuous at interfaces. The available equation sets are as follows: scalar elliptic equations, scalar convection equations, and the pressure-Poisson formulation of the Navier-Stokes equations for an incompressible fluid. All the equation sets are implemented with nonzero forcing functions to enable the use of user-specified solutions to assist in verification and validation. The equations are solved with a full multigrid scheme using a full approximation scheme to converge the solution on each succeeding grid level. Restriction to the next coarser mesh uses direct injection for variables and full weighting for residual quantities; prolongation of the coarse grid correction from the coarse mesh to the fine mesh uses bilinear interpolation; and prolongation of the coarse grid solution uses bicubic interpolation.

Mineck, Raymond E.↗
DOE OSTI2018

Algebraic multigrid for directed graph Laplacian linear systems (NS‐LAMG)

Summary We propose nonsymmetric lean algebraic multigrid (NS‐LAMG), a new algebraic multigrid algorithm for directed graph Laplacian systems that combines ideas from undirected graph Laplacian multigrid solvers and multigrid algorithms for Markov chain stationary distribution systems. Low‐degree elimination, proposed in LAMG for undirected graphs, is generalized to directed graphs and is a key component of NS‐LAMG. In the setup phase, we propose a simple stationary‐aggregation multigrid algorithms for Markov chain stationary distribution systems solver enhanced by low‐degree elimination to find the right null‐space vector that is used for the intergrid transfer operators. Numerical results show that low‐degree elimination improves performance and that NS‐LAMG outperforms generalized minimal residual method with restart and stable bi‐conjugate gradient method for real‐world, directed graph Laplacian linear systems.

Fox, Alyson↗
NASA NTRS1991

The improved robustness of multigrid elliptic solvers based on multiple semicoarsened grids

Multigrid convergence rates degenerate on problems with stretched grids or anisotropic operators, unless one uses line or plane relaxation. For 3-D problems, only plane relaxation suffices, in general. While line and plane relaxation algorithms are efficient on sequential machines, they are quite awkward and inefficient on parallel machines. A new multigrid algorithm is presented based on the use of multiple coarse grids, that eliminates the need for line or plane relaxation in anisotropic problems. This algorithm was developed and the standard multigrid theory was extended to establish rapid convergence for this class of algorithms. The new algorithm uses only point relaxation, allowing easy and efficient parallel implementation, yet achieves robustness and convergence rates comparable to line and plane relaxation multigrid algorithms. The algorithm described is a variant of Mulder's multigrid algorithm for hyperbolic problems. The latter uses multiple coarse grids to achieve robustness, but is unsuitable for elliptic problems, since its V-cycle convergence rate goes to one as the number of levels increases. The new algorithm combines the contributions from the multiple coarse grid via a local switch, based on the strength of the discrete operator in each coordinate direction.

Naik, Naomi H.↗
NASA NTRS2004

Textbook Multigrid Efficiency for Leading Edge Stagnation

A multigrid solver is defined as having textbook multigrid efficiency (TME) if the solutions to the governing system of equations are attained in a computational work which is a small (less than 10) multiple of the operation count in evaluating the discrete residuals. TME in solving the incompressible inviscid fluid equations is demonstrated for leading- edge stagnation flows. The contributions of this paper include (1) a special formulation of the boundary conditions near stagnation allowing convergence of the Newton iterations on coarse grids, (2) the boundary relaxation technique to facilitate relaxation and residual restriction near the boundaries, (3) a modified relaxation scheme to prevent initial error amplification, and (4) new general analysis techniques for multigrid solvers. Convergence of algebraic errors below the level of discretization errors is attained by a full multigrid (FMG) solver with one full approximation scheme (F.4S) cycle per grid. Asymptotic convergence rates of the F.4S cycles for the full system of flow equations are very fast, approaching those for scalar elliptic equations.

Diskin, Boris↗
NASA NTRS2004

Textbook Multigrid Efficiency for Leading Edge Stagnation

A multigrid solver is defined as having textbook multigrid efficiency (TME) if the solutions to the governing system of equations are attained in a computational work which is a small (less than 10) multiple of the operation count in evaluating the discrete residuals. TME in solving the incompressible inviscid fluid equations is demonstrated for leading-edge stagnation flows. The contributions of this paper include (1) a special formulation of the boundary conditions near stagnation allowing convergence of the Newton iterations on coarse grids, (2) the boundary relaxation technique to facilitate relaxation and residual restriction near the boundaries, (3) a modified relaxation scheme to prevent initial error amplification, and (4) new general analysis techniques for multigrid solvers. Convergence of algebraic errors below the level of discretization errors is attained by a full multigrid (FMG) solver with one full approximation scheme (FAS) cycle per grid. Asymptotic convergence rates of the FAS cycles for the full system of flow equations are very fast, approaching those for scalar elliptic equations.

Diskin, Boris↗
NASA NTRS1984

Vectorized multigrid Poisson solver for the CDC CYBER 205

The full multigrid (FMG) method is applied to the two dimensional Poisson equation with Dirichlet boundary conditions. This has been chosen as a relatively simple test case for examining the efficiency of fully vectorizing of the multigrid method. Data structure and programming considerations and techniques are discussed, accompanied by performance details.

Barkai, D.↗
DOE OSTI2015

Compiler-Directed Transformation for Higher-Order Stencils

As the cost of data movement increasingly dominates performance, developers of finite-volume and finite-difference solutions for partial differential equations (PDEs) are exploring novel higher-order stencils that increase numerical accuracy and computational intensity. This paper describes a new compiler reordering transformation applied to stencil operators that performs partial sums in buffers, and reuses the partial sums in computing multiple results. This optimization has multiple effect son improving stencil performance that are particularly important to higher-order stencils: exploits data reuse, reduces floating-point operations, and exposes efficient SIMD parallelism to backend compilers. We study the benefit of this optimization in the context of Geometric Multigrid (GMG), a widely used method to solvePDEs, using four different Jacobi smoothers built from 7-, 13-, 27-and 125-point stencils. We quantify performance, speedup, andnumerical accuracy, and use the Roofline model to qualify our results. Ultimately, we obtain over 4× speedup on the smoothers themselves and up to a 3× speedup on the multigrid solver. Finally, we demonstrate that high-order multigrid solvers have the potential of reducing total data movement and energy by several orders of magnitude.

97 MATHEMATICS AND COMPUTING↗