Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Multigrid”

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
DOE OSTI2020

Multilevel Convergence Analysis of Multigrid-Reduction-in-Time

This study presents a multilevel convergence framework for multigrid-reduction-in-time (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.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Tuning Multigrid Methods with Robust Optimization and Local Fourier Analysis

Local Fourier analysis is a useful tool for predicting and analyzing the performance of many efficient algorithms for the solution of discretized PDEs, such as multigrid and domain decomposition methods. The crucial aspect of local Fourier analysis is that it can be used to minimize an estimate of the spectral radius of a stationary iteration, or the condition number of a preconditioned system, in terms of a symbol representation of the algorithm. In practice, this is a “minimax” problem, minimizing with respect to solver parameters the appropriate measure of work, which involves maximizing over the Fourier frequency. Often, several algorithmic parameters may be determined by local Fourier analysis in order to obtain efficient algorithms. Analytical solutions to minimax problems are rarely possible beyond simple problems; the status quo in local Fourier analysis involves grid sampling, which is prohibitively expensive in high dimensions. In this paper, we propose and explore optimization algorithms to solve these problems efficiently. Finally, several examples, with known and unknown analytical solutions, are presented to show the effectiveness of these approaches.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Monolithic Multigrid Methods for Magnetohydrodynamics

The magnetohydrodynamics equations model a wide range of plasma physics applications and are characterized by a nonlinear system of partial differential equations that strongly couples a charged fluid with the evolution of electromagnetic fields. After discretization and linearization, the resulting system of equations is generally difficult to solve due to the coupling between variables and the heterogeneous coefficients induced by the linearization process. In this paper, we investigate multigrid preconditioners for this system based on specialized relaxation schemes that properly address the system structure and coupling. Here, three extensions of Vanka relaxation are proposed and applied to problems with up to 170 million degrees of freedom and fluid and magnetic Reynolds numbers up to 400 for stationary problems and up to 20,000 for time-dependent problems.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

AIR Algebraic Multigrid for a Space-Time Hybridizable Discontinuous Galerkin Discretization of Advection(-Diffusion)

This article investigates the efficiency, robustness, and scalability of approximate ideal restriction (AIR) algebraic multigrid as a preconditioner in the all-at-once solution of a space-time hybridizable discontinuous Galerkin discretization of advection-dominated flows. The motivation for this study is that the time-dependent advection-diffusion equation can be seen as a “steady” advection-diffusion problem in $(d+1)$-dimensions and AIR has been shown to be a robust solver for steady advection-dominated problems. Numerical examples demonstrate the effectiveness of AIR as a preconditioner for advection-diffusion problems on fixed and time-dependent domains, using both slab-by-slab and all-at-once space-time discretizations, and in the context of uniform and space-time adaptive mesh refinement. A closer look at the geometric coarsening structure that arises in AIR also explains why AIR can provide robust, scalable, space-time convergence on advective and hyperbolic problems, while most multilevel parallel-in-time schemes struggle with such problems.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

Fast Multigrid Reduction-in-Time for Advection via Modified Semi-Lagrangian Coarse-Grid Operators

Many iterative parallel-in-time algorithms have been shown to be highly efficient for diffusion-dominated partial differential equations (PDEs) but are inefficient or even divergent when applied to advection-dominated PDEs. We consider the application of the multigrid reduction-in-time (MGRIT) algorithm to linear advection PDEs. Here, the key to efficient time integration with this method is using a coarse-grid operator that provides a sufficiently accurate approximation to the so-called ideal coarse-grid operator. For certain classes of semi-Lagrangian discretizations, we present a novel semi-Lagrangian-based coarse-grid operator that leads to fast and scalable multilevel time integration of linear advection PDEs. The coarse-grid operator is composed of a semi-Lagrangian discretization followed by a correction term, with the correction designed so that the leading-order truncation error of the composite operator is approximately equal to that of the ideal coarse-grid operator. Parallel results show substantial speed-ups over sequential time integration for variable-wave-speed advection problems in one and two spatial dimensions, and using high-order discretizations up to order five. The proposed approach establishes the first practical method that provides small and scalable MGRIT iteration counts for advection problems.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

A Fast Algebraic Multigrid Solver and Accurate Discretization for Highly Anisotropic Heat Flux I: Open Field Lines

We present a novel solver technique for the anisotropic heat flux equation, aimed at the high level of anisotropy seen in magnetic confinement fusion plasmas. Such problems pose two major challenges: (i) discretization accuracy and (ii) efficient implicit linear solvers. We simultaneously address each of these challenges by constructing a new finite element discretization with excellent accuracy properties, tailored to a novel solver approach based on algebraic multigrid (AMG) methods designed for advective operators. We pose the problem in a mixed formulation, introducing the directional temperature gradient as an auxiliary variable. The temperature and auxiliary fields are discretized in a scalar discontinuous Galerkin space with upwinding principles used for discretizations of advection. We demonstrate the proposed discretization’s superior accuracy over other discretizations of anisotropic heat flux, achieving error 1000x smaller for anisotropy ratio of 10 9 , for closed field lines. The block matrix system is reordered and solved in an approach where the two advection operators are inverted using AMG solvers based on approximate ideal restriction, which is particularly efficient for upwind discontinuous Galerkin discretizations of advection. To ensure that the advection operators are nonsingular, in this paper we restrict ourselves to considering open (acyclic) magnetic field lines for the linear solvers. We demonstrate fast convergence of the proposed iterative solver in highly anisotropic regimes where other diffusion-based AMG methods fail.

97 MATHEMATICS AND COMPUTING↗
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 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↗
DOE OSTI2021

Multigrid reduction in time with Richardson extrapolation

The advent of exascale computing will leave many users with access to more computational resources than they can simultaneously use, e.g., billion-way parallelism. In particular, this is true for time-dependent simulations that limit parallelism to the spatial domain. One method to add parallelism in time to existing simulation codes and thus take advantage of ever larger compute resources is Multigrid Reduction in Time (MGRIT). The goal is to achieve a smaller time-to-solution through parallelism in time. In this paper, MGRIT is enhanced with Richardson extrapolation in a cost-efficient way to produce a parallel-in-time method with improved accuracy. Overall, this leads to a large improvement in the accuracy per computational cost of MGRIT.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Basic elements for simulations of standard-model physics with quantum annealers: Multigrid and clock states

Here, we explore the potential of D-Wave's quantum annealers for computing some of the basic components required for quantum simulations of standard model physics. By implementing a basic multigrid (including “zooming”) and specializing Feynman-clock algorithms, D-Wave's Advantage is used to study harmonic and anharmonic oscillators relevant for lattice scalar field theories and effective field theories, the time evolution of a single plaquette of SU(3) Yang-Mills lattice gauge field theory, and the dynamics of flavor entanglement in four-neutrino systems.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2020

Multigrid-Reduction-in-Time for the Rotating Shallow Water Equations

We consider multilevel time-parallel methods for the numerical solution of the rotating shallow water equations. In particular, the multigrid-reduction-in-time (MGRIT) algorithm is used for the parallel time integration. An asymptotic model is used at the coarse levels while the full model is employed at the finer levels. The asymptotic model is well-suited for highly oscillatory partial differential equations like the rotating shallow water equations because it can accurately and stably take the required large time-steps on coarse levels. Our work exploits the flexibility of the MGRIT algorithm in terms of the number of levels and relaxation schemes to show some computational benefits, especially with respect to FCF-relaxation and data reuse.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

Smoothers for Matrix-Free Algebraic Multigrid Preconditioning of High-Order Finite Elements

We investigate smoothers for use in matrix-free algebraic multigrid (AMG) preconditioning of high-order finite element problems. These AMG preconditioners are matrix-free in the sense that they are built from a related low-order refined finite element problem whose system matrix can be much more rapidly assembled than the high-order problem. Our proposed smoother, which we call distributive relaxation, is more robust to the anisotropy present in many low-order refined meshes which feature a clustering of nodes near the boundaries between high-order finite elements. For solving the low-order refined problem, we show that this new distributive relaxation smoother possesses significantly improved performance compared to more traditional smoothers.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Time-periodic steady-state solution of fluid-structure interaction and cardiac flow problems through multigrid-reduction-in-time

In this study, a time-periodic MGRIT algorithm is proposed as a means to reduce the time-to-solution of numerical algorithms by exploiting the time periodicity inherent to many applications in science and engineering. The time-periodic MGRIT algorithm is applied to a variety of linear and nonlinear single- and multiphysics problems that are periodic-in-time. It is demonstrated that the proposed parallel-in-time algorithm can obtain the same time-periodic steady-state solution as sequential time-stepping. It is shown that the required number of MGRIT iterations can be estimated a priori and that the new MGRIT variant can significantly and consistently reduce the time-to-solution compared to sequential time-stepping, irrespective of the number of dimensions, linear or nonlinear PDE models, single-physics or coupled problems and the employed computing resources. The numerical experiments demonstrate that the time-periodic MGRIT algorithm enables a greater level of parallelism yielding faster turnaround, and thus, facilitating more complex and more realistic problems to be solved.

97 MATHEMATICS AND COMPUTING↗