Search NASA⌕ Search

SEARCH · Search NASA

Results for “algebraic multigrid (AMG)”

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.

9 records
All sourcesNASA NTRSDOE OSTI
DOE OSTI2024

On Compatible Transfer Operators in Nonsymmetric Algebraic Multigrid

The standard goal for an effective algebraic multigrid (AMG) algorithm is to develop relaxation and coarse-grid correction schemes that attenuate complementary error modes. In the nonsymmetric setting, coarse-grid correction Π will almost certainly be nonorthogonal (and divergent) in any known standard product, meaning ∥Π∥ > 1. This introduces a new consideration, that one wants coarse-grid correction to be as close to orthogonal as possible, in an appropriate norm. In addition, due to nonorthogonality, Π may actually amplify certain error modes that are in the range of interpolation. Relaxation must then not only be complementary to interpolation, but also rapidly eliminate any error amplified by the nonorthogonal correction, or the algorithm may diverge. Here this paper develops analytic formulae on how to construct “compatible” transfer operators in nonsymmetric AMG such that ∥Π∥ = 1 in some standard matrix-induced norm. Discussion is provided on different options for the norm in the nonsymmetric setting, the relation between “ideal” transfer operators in different norms, and insight into the convergence of nonsymmetric reduction-based AMG.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

A two-level GPU-accelerated incomplete LU preconditioner for general sparse linear systems

This paper presents a parallel preconditioning approach based on incomplete LU (ILU) factorizations in the framework of Domain Decomposition (DD) for general sparse linear systems. We focus on distributed memory parallel architectures, specifically, those that are equipped with graphic processing units (GPUs). In addition to block-Jacobi, we present general purpose two-level ILU Schur complement-based approaches, where different strategies are presented to solve the coarse-level reduced system. These strategies are combined with modified ILU methods in the construction of the coarse-level operator, in order to effectively remove smooth errors by targeting an algebraically smooth vector. We leverage available GPU-based sparse matrix kernels to accelerate the setup and the solve phases of the proposed ILU preconditioner. We evaluate the efficiency of the proposed methods as a smoother for algebraic multigrid (AMG) and as a preconditioner for Krylov subspace methods on challenging anisotropic diffusion problems and a collection of general sparse matrices.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1989

Algebraic multigrid methods applied to problems in computational structural mechanics

The development of algebraic multigrid (AMG) methods and their application to certain problems in structural mechanics are described with emphasis on two- and three-dimensional linear elasticity equations and the 'jacket problems' (three-dimensional beam structures). Various possible extensions of AMG are also described. The basic idea of AMG is to develop the discretization sequence based on the target matrix and not the differential equation. Therefore, the matrix is analyzed for certain dependencies that permit the proper construction of coarser matrices and attendant transfer operators. In this manner, AMG appears to be adaptable to structural analysis applications.

Mccormick, Steve↗
DOE OSTI2025

Scalable multilevel Monte Carlo methods exploiting parallel redistribution on coarse levels

Here, we study an element agglomeration coarsening strategy that requires data redistribution at coarse levels when the number of coarse elements becomes smaller than the number of MPI processes used on the finest level. The overall procedure generates coarse elements (general unstructured unions of fine grid elements) within the framework of element-based algebraic multigrid methods (or AMGe) studied previously. The AMGe-generated coarse spaces have the ability to exhibit approximation properties of the same order as the fine-level spaces since by construction they contain the piecewise polynomials of the same order as on the fine level. These approximation properties are key for the successful use of AMGe in multilevel solvers for nonlinear partial differential equations as well as for multilevel Monte Carlo (MLMC) simulations. The ability to coarsen without being constrained by the number of MPI processes, as described in the present paper, allows to improve the scalability of these solvers as well as the overall MLMC method. The paper illustrates this latter fact with detailed scalability study of MLMC simulations applied to model Darcy equations with a stochastic log-normal permeability field.

AMGe↗
DOE OSTI2026

Optimal Transfer Operators in Algebraic Two-Level Methods for Nonsymmetric and Indefinite Problems

Consider an algebraic two-level method applied to the 𝑛-dimensional linear system 𝐴⁢𝒙 = 𝒃 using fine-space preconditioner (i.e., “relaxation” or “smoother”) 𝑀, with 𝑀 ≈ 𝐴, restriction and interpolation 𝑅 and 𝑃, and algebraic coarse-space operator 𝐴 𝑐 : = 𝑅 ∗ ⁢𝐴⁢𝑃. Then, what are the best possible transfer operators 𝑅 and 𝑃 of a given dimension 𝑛 𝑐 < 𝑛? Brannick et al. [12] showed that when 𝐴 and 𝑀 are Hermitian positive definite (HPD), the optimal interpolation is such that its range contains the 𝑛 𝑐 smallest generalized eigenvectors of the matrix pencil (𝐴, 𝑀). Recently, in Ali et al. [5] we generalized this framework to the non-HPD setting, by considering both right (interpolation) and left (restriction) generalized eigenvectors of (𝐴, 𝑀) and defining corresponding nonsymmetric transfer operators {𝑅#, 𝑃#}. Tight convergence bounds for {𝑅#, 𝑃#} are derived in spectral radius, as well as a proof of pseudo-optimality. Note, {𝑅#, 𝑃#} are typically complex valued, which is not practical for real-valued problems. Here, in this work, we build on [5], first characterizing all inner products in which the coarse-space correction defined by {𝑅#, 𝑃#} is orthogonal. We then develop tight two-level convergence bounds in these norms, and prove that the underlying transfer operators {𝑅#, 𝑃#} are genuinely optimal. As a special case, our theory both recovers and extends the HPD results from [12]. Finally, we show how to construct optimal, real-valued transfer operators in the case of that 𝐴 and 𝑀 are real valued, but are not HPD. Numerical examples arising from a discretized advection-reaction equation, wave-equation, and Stokes equations are used to verify and illustrate the theory.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1993

Layout optimization with algebraic multigrid methods

Finding the optimal position for the individual cells (also called functional modules) on the chip surface is an important and difficult step in the design of integrated circuits. This paper deals with the problem of relative placement, that is the minimization of a quadratic functional with a large, sparse, positive definite system matrix. The basic optimization problem must be augmented by constraints to inhibit solutions where cells overlap. Besides classical iterative methods, based on conjugate gradients (CG), we show that algebraic multigrid methods (AMG) provide an interesting alternative. For moderately sized examples with about 10000 cells, AMG is already competitive with CG and is expected to be superior for larger problems. Besides the classical 'multiplicative' AMG algorithm where the levels are visited sequentially, we propose an 'additive' variant of AMG where levels may be treated in parallel and that is suitable as a preconditioner in the CG algorithm.

Regler, Hans↗
DOE OSTI2026

Multi-physics Preconditioning for Thermally Activated Batteries

Thermal batteries, also known as molten-salt batteries, are single-use reserve power systems activated by pyrotechnic heat generation, which transitions the solid electrolyte into a molten state. The simulation of these batteries relies on multiphysics modeling to evaluate performance and behavior under various conditions. This paper presents advancements in scalable preconditioning strategies for the Thermally Activated Battery Simulator (TABS) tool, enabling efficient solutions to the coupled electrochemical systems that dominate computational costs in thermal battery simulations. We propose a hierarchical block Gauss-Seidel preconditioner implemented through the Teko package in Trilinos, which effectively addresses the challenges posed by tightly coupled physics, including charge transport, porous flow, and species diffusion. The preconditioner leverages scalable subblock solvers, including smoothed aggregation algebraic multigrid (SA-AMG) methods and domain-decomposition techniques, to achieve robust convergence and parallel scalability. Strong and weak scaling studies demonstrate the solver’s ability to handle problem sizes up to 51.3 million degrees of freedom on 2048 processors, achieving near sub-second setup and solve times for the end-to-end electrochemical solve. These advancements significantly improve the computational efficiency and turnaround time of thermal battery simulations, paving the way for higher-resolution models and enabling the transition from 2D axisymmetric to full 3D simulations.

25 ENERGY STORAGE↗
NASA NTRS1987

Algebraic multigrid

The state of the art in algebraic multgrid (AMG) methods is discussed. The interaction between the relaxation process and the coarse grid correction necessary for proper behavior of the solution probes is discussed in detail. Sufficient conditions on relaxation and interpolation for the convergence of the V-cycle are given. The relaxation used in AMG, what smoothing means in an algebraic setting, and how it relates to the existing theory are considered. Some properties of the coarse grid operator are discussed, and results on the convergence of two-level and multilevel convergence are given. Details of an algorithm particularly studied for problems obtained by discretizing a single elliptic, second order partial differential equation are given. Results of experiments with such problems using both finite difference and finite element discretizations are presented.

Ruge, J. W.↗
DOE OSTI2026

Algebraic Multigrid with Filtering: An Efficient Preconditioner for Interior Point Methods in Large-Scale Contact Mechanics Optimization

Large-scale contact mechanics simulations are crucial in many engineering fields such as structural design and manufacturing. In the frictionless case, contact can be modeled by minimizing an energy functional; however, these problems are often nonlinear, nonconvex, and increasingly difficult to solve as mesh resolution increases. In this work, we employ a Newton-based interior-point (IP) filter line-search method, an effective approach for large-scale constrained optimization. While this method converges rapidly, each iteration requires solving a large saddle-point linear system that becomes ill-conditioned as the optimization process converges, largely due to IP treatment of the contact constraints. Such ill-conditioning can hinder solver scalability and increase iteration counts with mesh refinement. Here, to address this, we introduce a novel preconditioner, algebraic multigrid with filtering (AMGF), tailored to the Schur complement of the saddle-point system. Building on the classical AMG solver, commonly used for elasticity, we augment it with a specialized subspace correction that filters near null space components introduced by contact interface constraints. Through theoretical analysis and numerical experiments on a range of linear and nonlinear contact problems, we demonstrate that the proposed solver achieves mesh independent convergence and maintains robustness against the ill-conditioning that notoriously plagues IP methods. These results indicate that AMGF makes contact mechanics simulations more tractable and broadens the applicability of Newton-based IP methods in challenging engineering scenarios. More broadly, AMGF is well suited for problems, optimization or otherwise, where solver performance is limited by a low-dimensional subspace, such as those arising from localized constraints, interface conditions, or model heterogeneities. This makes the method widely applicable beyond contact mechanics and constrained optimization.

Mathematics and Computing↗