Search NASA⌕ Search

SEARCH · Search NASA

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 811 records · Page 45

RANS and URANS Application with CFL3D

This case was run using CFL3D, a multi-zone Reynolds-averaged Navier-Stokes code developed at NASA Langley [1]. It solves the thin-layer form of the Navier-Stokes equations in each of the (selected) coordinate directions. It can use 1-to-1, patched, or overset grids, and employs local time step scaling, grid sequencing, and multigrid to accelerate convergence to steady state. In time-accurate mode, CFL3D has the option to employ dual-time stepping with subiterations and multigrid, and it achieves second order temporal accuracy. CFL3D is a finite volume method. It uses third-order upwind-biased spatial differencing on the convective and pressure terms, and second-order differencing on the viscous terms; it is globally second-order spatially accurate. The flux difference-splitting (FDS) method of Roe is employed to obtain fluxes at the cell faces. It is advanced in time with an implicit three-factor approximate factorization method.

Rumsey, C. L.↗

Convergence Acceleration of Runge-Kutta Schemes for Solving the Navier-Stokes Equations

The convergence of a Runge-Kutta (RK) scheme with multigrid is accelerated by preconditioning with a fully implicit operator. With the extended stability of the Runge-Kutta scheme, CFL numbers as high as 1000 can be used. The implicit preconditioner addresses the stiffness in the discrete equations associated with stretched meshes. This RK/implicit scheme is used as a smoother for multigrid. Fourier analysis is applied to determine damping properties. Numerical dissipation operators based on the Roe scheme, a matrix dissipation, and the CUSP scheme are considered in evaluating the RK/implicit scheme. In addition, the effect of the number of RK stages is examined. Both the numerical and computational efficiency of the scheme with the different dissipation operators are discussed. The RK/implicit scheme is used to solve the two-dimensional (2-D) and three-dimensional (3-D) compressible, Reynolds-averaged Navier-Stokes equations. Turbulent flows over an airfoil and wing at subsonic and transonic conditions are computed. The effects of the cell aspect ratio on convergence are investigated for Reynolds numbers between 5:7 x 10(exp 6) and 100 x 10(exp 6). It is demonstrated that the implicit preconditioner can reduce the computational time of a well-tuned standard RK scheme by a factor between four and ten.

Swanson, Roy C., Jr.↗

Progress Towards a Cartesian Cut-Cell Method for Viscous Compressible Flow

We present preliminary development of an approach for simulating high Reynolds number steady compressible flow in two space dimensions using a Cartesian cut-cell finite volume method. We consider both laminar and turbulent flow with both low and high cell Reynolds numbers near the wall. The approach solves the full Navier-Stokes equations in all cells, and uses a wall model to address the resolution requirements near boundaries and to mitigate mesh irregularities in cut cells. We present a quadratic wall model for low cell Reynolds numbers. At high cell Reynolds numbers, the quadratic is replaced with a newly developed analytic wall model stemming from solution of a limiting form of the Spalart-Allmaras turbulence model which features a forward evaluation for flow velocity and exactly matches characteristics of the SA turbulence model in the field. We develop multigrid operators which attain convergence rates similar to inviscid multigrid. Investigations focus on preliminary verification and validation of the method. Flows over flat plates and compressible airfoils show good agreement with both theoretical results and experimental data. Mesh convergence studies on sub- and transonic airfoil flows show convergence of surface pressures with wall spacings as large as approx.0.1% chord. With the current analytic wall model, one or two additional refinements near the wall are required to obtain mesh converged values of skin friction.

Berger, Marsha↗

A Parallel, Fully Coupled, Fully Implicit Solution to Reactive Transport in Porous Media Using the Preconditioned Jacobian-Free Newton-Krylov Method

Modeling large multicomponent reactive transport systems in porous media is particularly challenging when the governing partial differential algebraic equations (PDAEs) are highly nonlinear and tightly coupled due to complex nonlinear reactions and strong solution-media interactions. Here we present a preconditioned Jacobian-Free Newton-Krylov (JFNK) solution approach to solve the governing PDAEs in a fully coupled and fully implicit manner. A well-known advantage of the JFNK method is that it does not require explicitly computing and storing the Jacobian matrix during Newton nonlinear iterations. Our approach further enhances the JFNK method by utilizing physics-based, block preconditioning and a multigrid algorithm for efficient inversion of the preconditioner. This preconditioning strategy accounts for self- and optionally, cross-coupling between primary variables using diagonal and off-diagonal blocks of an approximate Jacobian, respectively. Numerical results are presented demonstrating the efficiency and massive scalability of the solution strategy for reactive transport problems involving strong solution-mineral interactions and fast kinetics. We found that the physics-based, block preconditioner significantly decreases the number of linear iterations, directly reducing computational cost; and the strongly scalable algebraic multigrid algorithm for approximate inversion of the preconditioner leads to excellent parallel scaling performance.

97 MATHEMATICS AND COMPUTING↗

miniGMG

miniGMG is a compact geometric multigrid (MG benchmark designed to proxy the performance characteristics of the solves found in adaptive mesh refinement multigrid (AMR MG) applications. It solves the equation a*alpha*u - b div beta grad u = f on a large cubical domain using cell-centered values and periodic boundaries. a and b are scalar constants, alpha and beta are space varying constants, f is the right hand side, and u is the solution. The cubical domain is divided into cubical subdomains which are distributed across the supercomputer. The righthand side f is generated from a continuous function for u. Thus, one can solve this linear system of equations and verify the error properties of the discrete solution u by comparing to a sampling of the continuous u. miniGMG implements both v- and f- cycles, as well as two constant coeffficient discretications of the equation above (one 27pt 2nd order, and one 13pt 4th order). In both cases, the (embedded) v-cycles are truncated when a subdomain reaces 4^3, 2^3, or 1^3 cells (a u-cycle). The multigrd solver then swtiches to one of seven coarse grid (bottom) solves. relaxation, BiCGStab, CABiCGStab, TelescopingCABiCGStab, CG, or CACG. The code exploits two forms of communication-avoiding. The first is exemplified by the referenced SC'12 paper in which DRAM data movment is avoided when smoothing. The second, described in the IPDPS'14 paper avoids collectives in a bottom solve (the CA bottom solves). There are a number of implementations of the operators for both CPUs and NVIDIA GPUs. The CPUs have been optimized to exploit a wavefront approach to communication-avoiding. The GPU versions include a number of optimized and tunable implementations. The code has been demonstrated to scale to 46K nodes on the BGQ Mira (750K cores), 9K nodes on Edison (111K cores), and 14K GPUs on Titan (37M cuda cores). It thus acts as a scalable testbed for a wide range of computer science and applied math research. Nominally, one invokes the benchmark as ./run b x y z alpha beta gamma Each subdomain is (2^b)^3 cells Each MPI process receives a x-by-y-by-z collection of subdomains. There are alpha*beta*gamma total MPI processes For correctness (a cubical domain), *alpha==y*beta==z*gamma.

Williams, Sameul↗

Approximate Inverse Chain Preconditioner: Iteration Count Case Study for Spectral Support Solvers

As the growing availability of computational power slows, there has been an increasing reliance on algorithmic advances. However, faster algorithms alone will not necessarily bridge the gap in allowing computational scientists to study problems at the edge of scientific discovery in the next several decades. Often, it is necessary to simplify or precondition solvers to accelerate the study of large systems of linear equations commonly seen in a number of scientific fields. Preconditioning a problem to increase efficiency is often seen as the best approach; yet, preconditioners which are fast, smart, and efficient do not always exist. Following the progress of [1], we present a new preconditioner for symmetric diagonally dominant (SDD) systems of linear equations. These systems are common in certain PDEs, network science, and supervised learning among others. Based on spectral support graph theory, this new preconditioner builds off of the work of [2], computing and applying a V-cycle chain of approximate inverse matrices. This preconditioner approach is both algebraic in nature as well as hierarchically-constrained depending on the condition number of the system to be solved. Due to its generation of an Approximate Inverse Chain of matrices, we refer to this as the AIC preconditioner. We further accelerate the AIC preconditioner by utilizing precomputations to simplify setup and multiplications in the con-text of an iterative Krylov-subspace solver. While these iterative solvers can greatly reduce solution time, the number of iterations can grow large quickly in the absence of good preconditioners. Initial results for the AIC preconditioner have shown a very large reduction in iteration counts for SDD systems as compared to standard preconditioners such as Incomplete Cholesky (ICC) and Multigrid (MG). We further show significant reduction in iteration counts against the more advanced Combinatorial Multigrid (CMG) preconditioner. We have further developed no-fill sparsification techniques to ensure that the computational cost of applying the AIC preconditioner does not grow prohibitively large as the depth of the V-cycle grows for systems with larger condition numbers. Our numerical results have shown that these sparsifiers maintain the sparsity structure of our system while also displaying significant reductions in iteration counts.1 2

97 MATHEMATICS AND COMPUTING↗

Approximate Inverse Chain Preconditioner: Iteration Count Case Study for Spectral Support Solvers

As the growing availability of computational power slows, there has been an increasing reliance on algorithmic advances. However, faster algorithms alone will not necessarily bridge the gap in allowing computational scientists to study problems at the edge of scientific discovery in the next several decades. Often, it is necessary to simplify or precondition solvers to accelerate the study of large systems of linear equations commonly seen in a number of scientific fields. Preconditioning a problem to increase efficiency is often seen as the best approach; yet, preconditioners which are fast, smart, and efficient do not always exist. Following the progress of [1], we present a new preconditioner for symmetric diagonally dominant (SDD) systems of linear equations. These systems are common in certain PDEs, network science, and supervised learning among others. Based on spectral support graph theory, this new preconditioner builds off of the work of [2], computing and applying a V-cycle chain of approximate inverse matrices. This preconditioner approach is both algebraic in nature as well as hierarchically-constrained depending on the condition number of the system to be solved. Due to its generation of an Approximate Inverse Chain of matrices, we refer to this as the AIC preconditioner. We further accelerate the AIC preconditioner by utilizing precomputations to simplify setup and multiplications in the con-text of an iterative Krylov-subspace solver. While these iterative solvers can greatly reduce solution time, the number of iterations can grow large quickly in the absence of good preconditioners. Initial results for the AIC preconditioner have shown a very large reduction in iteration counts for SDD systems as compared to standard preconditioners such as Incomplete Cholesky (ICC) and Multigrid (MG). We further show significant reduction in iteration counts against the more advanced Combinatorial Multigrid (CMG) preconditioner. We have further developed no-fill sparsification techniques to ensure that the computational cost of applying the AIC preconditioner does not grow prohibitively large as the depth of the V-cycle grows for systems with larger condition numbers. Our numerical results have shown that these sparsifiers maintain the sparsity structure of our system while also displaying significant reductions in iteration counts.1 2

97 MATHEMATICS AND COMPUTING↗

On the scalability of the Albany/FELIX first-order Stokes approximation ice sheet solver for large-scale simulations of the Greenland and Antarctic ice sheets

We examine the scalability of the recently developed Albany/FELIX finite-element based code for the first-order Stokes momentum balance equations for ice flow. We focus our analysis on the performance of two possible preconditioners for the iterative solution of the sparse linear systems that arise from the discretization of the governing equations: (1) a preconditioner based on the incomplete LU (ILU) factorization, and (2) a recently-developed algebraic multigrid (AMG) preconditioner, constructed using the idea of semi-coarsening. A strong scalability study on a realistic, high resolution Greenland ice sheet problem reveals that, for a given number of processor cores, the AMG preconditioner results in faster linear solve times but the ILU preconditioner exhibits better scalability. A weak scalability study is performed on a realistic, moderate resolution Antarctic ice sheet problem, a substantial fraction of which contains floating ice shelves, making it fundamentally different from the Greenland ice sheet problem. Here, we show that as the problem size increases, the performance of the ILU preconditioner deteriorates whereas the AMG preconditioner maintains scalability. This is because the linear systems are extremely ill-conditioned in the presence of floating ice shelves, and the ill-conditioning has a greater negative effect on the ILU preconditioner than on the AMG preconditioner.

54 ENVIRONMENTAL SCIENCES↗

Constrained Local Approximate Ideal Restriction for Advection-Diffusion Problems

Herein this paper focuses on developing a reduction-based algebraic multigrid (AMG) method that is suitable for solving general (non)symmetric linear systems and is naturally robust from pure advection to pure diffusion. Initial motivation comes from a new reduction-based AMG approach, $\ell \text{AIR}$ (local approximate ideal restriction), that was developed for solving advection-dominated problems. Though this new solver is very effective in the advection-dominated regime, its performance degrades in cases where diffusion becomes dominant. This is consistent with the fact that in general, reduction-based AMG methods tend to suffer from growth in complexity and/or convergence rates as the problem size is increased, especially for diffusion-dominated problems in two or three dimensions. Motivated by the success of $\ell \text{AIR}$ in the advective regime, our aim in this paper is to generalize the AIR framework with the goal of improving the performance of the solver in diffusion-dominated regimes. To do so, we propose a novel way to combine mode constraints as used commonly in energy-minimization AMG methods with the local approximation of ideal operators used in $\ell \text{AIR}$. The resulting constrained $\ell \text{AIR}$ algorithm is able to achieve fast scalable convergence on advective and diffusive problems. In addition, it is able to achieve standard low complexity hierarchies in the diffusive regime through aggressive coarsening, something that was previously difficult for reduction-based methods.

97 MATHEMATICS AND COMPUTING↗

Scaled ILU Smoothers for Navier-Stokes Pressure Projection

Incomplete LU (ILU) smoothers are effective in the algebraic multigrid (AMG) V-cycle for reducing high-frequency components of the error. However, the requisite direct triangular solves are comparatively slow on GPUs. Previous work has demonstrated the advantages of Jacobi iteration as an alternative to direct solution of these systems. Depending on the threshold and fill-level parameters chosen, the factors can be highly nonnormal and Jacobi is unlikely to converge in a low number of iterations. We demonstrate that row scaling can reduce the departure from normality, allowing us to replace the inherently sequential solve with a rapidly converging Richardson iteration. There are several advantages beyond the lower compute time. Scaling is performed locally for a diagonal block of the global matrix because it is applied directly to the factor. Further, an ILUT Schur complement smoother maintains a constant GMRES iteration count as the number of MPI ranks increases, and thus parallel strong-scaling is improved. Our algorithms have been incorporated into hypre, and we demonstrate improved time to solution for linear systems arising in the Nalu-Wind and PeleLM pressure solvers. For large problem sizes, GMRES+AMG executes at least five times faster when using iterative triangular solves compared with direct solves on massively parallel GPUs.

algebraic multigrid↗

Estimating posterior quantity of interest expectations in a multilevel scalable framework

Scalable approaches for uncertainty quantification are necessary for characterizing prediction confidence in large-scale subsurface flow simulations with uncertain permeability. To this end we explore a multilevel Monte Carlo approach for estimating posterior moments of a particular quantity of interest, where we employ an element-agglomerated algebraic multigrid (AMG) technique to generate the hierarchy of coarse spaces with guaranteed approximation properties for both the generation of spatially correlated random fields and the forward simulation of Darcy's law to model subsurface flow. In both these components (sampling and forward solves), we exploit solvers that rely on state-of-the-art scalable AMG. To illustrate the applicability of this approach, numerical tests are performed on two 3D examples-a unit cube and an egg-shaped domain with an irregular boundary-where the scalability of each simulation as well as the scalability of the overall algorithm are demonstrated.

97 MATHEMATICS AND COMPUTING↗

Multilevel-in-width training for deep neural network regression

A common challenge in regression is that for many problems, the degrees of freedom required for a high-quality solution also allows for overfitting. Regularization is a class of strategies that seek to restrict the range of possible solutions so as to discourage overfitting while still enabling good solutions, and different regularization strategies impose different types of restrictions. In this paper, we present a multilevel regularization strategy that constructs and trains a hierarchy of neural networks, each of which has layers that are wider versions of the previous network's layers. Here, we draw intuition and techniques from the field of Algebraic Multigrid (AMG), traditionally used for solving linear and nonlinear systems of equations, and specifically adapt the Full Approximation Scheme (FAS) for nonlinear systems of equations to the problem of deep learning. Training through V-cycles then encourage the neural networks to build a hierarchical understanding of the problem. We refer to this approach as multilevel-in-width to distinguish from prior multilevel works which hierarchically alter the depth of neural networks. The resulting approach is a highly flexible framework that can be applied to a variety of layer types, which we demonstrate with both fully connected and convolutional layers. We experimentally show with PDE regression problems that our multilevel training approach is an effective regularizer, improving the generalize performance of the neural networks studied.

97 MATHEMATICS AND COMPUTING↗

A Scalable Interior‐Point Gauss–Newton Method for PDE‐Constrained Optimization With Bound Constraints

Here, we present a scalable approach to solve a class of partial differential equation (PDE)‐constrained optimization problems with bound constraints. This approach utilizes a robust full‐space interior‐point (IP)‐Gauss–Newton optimization method. To cope with the poorly‐conditioned IP‐Gauss–Newton saddle‐point linear systems that need to be solved approximately, once per optimization step, we propose two spectrally related preconditioners. These preconditioners leverage the limited informativeness of data in regularized PDE‐constrained optimization problems. A block Gauss–Seidel preconditioner is proposed for the GMRES‐based solution of the IP‐Gauss–Newton linear systems. It is shown, for a large‐class of PDE‐ and bound‐constrained optimization problems, that the spectrum of the block Gauss–Seidel preconditioned IP‐Gauss–Newton matrix is asymptotically independent of discretization and is not impacted by the ill‐conditioning that notoriously plagues interior‐point methods. We exploit symmetry of the IP‐Gauss–Newton linear systems and propose a regularization and log‐barrier Hessian preconditioner for the preconditioned conjugate gradient (PCG)‐based solution of the equivalent IP‐Gauss–Newton–Schur complement linear systems. The eigenvalues of the block Gauss–Seidel preconditioned IP‐Gauss–Newton matrix, that are not equal to one, are identical to the eigenvalues of the regularization and log‐barrier Hessian preconditioned Schur complement matrix. The scalability of the approach is demonstrated on two example problems. The numerical solution of these optimization problems is shown to require a discretization independent number of IP‐Gauss–Newton linear solves. Furthermore, the linear systems are solved in a discretization and IP ill‐conditioning independent number of preconditioned Krylov subspace iterations. The parallel scalability of the preconditioner, achieved via algebraic multigrid component solvers when applicable, and the aforementioned algorithmic scalability permits a parallel scalable means to compute solutions of a large class of PDE‐ and bound‐constrained problems.

PDE-constrained optimization↗

Multilevel Preconditioners for Reaction-Diffusion Problems with Discontinuous Coefficients

In this study, we extend some of the multilevel convergence results obtained by Xu and Zhu, to the case of second order linear reaction-diffusion equations. Specifically, we consider the multilevel preconditioners for solving the linear systems arising from the linear finite element approximation of the problem, where both diffusion and reaction coefficients are piecewise-constant functions. We discuss in detail the influence of both the discontinuous reaction and diffusion coefficients to the performance of the classical BPX and multigrid V-cycle preconditioner.

97 MATHEMATICS AND COMPUTING↗

Integral boundary conditions in phase field models

Modeling the chemical, electric and thermal transport as well as phase transitions and the accompanying mesoscale microstructure evolution within a material in an electronic device setting involves the solution of partial differential equations often with integral boundary conditions. Employing the familiar Poisson equation describing the electric potential evolution in a material exhibiting insulator to metal transitions, we exploit a special property of such an integral boundary condition, and we properly formulate the variational problem and establish its well-posedness. Next, we compare our method with the commonly-used Lagrange multiplier method that can also handle such boundary conditions. Numerical experiments demonstrate that our new method achieves optimal convergence rate in contrast to the conventional Lagrange multiplier method. Furthermore, the linear system derived from our method is symmetric positive definite, and can be efficiently solved by Conjugate Gradient method with algebraic multigrid preconditioning.

97 MATHEMATICS AND COMPUTING↗

Extinction conditions of a premixed flame in a channel

A local refinement method is used to numerically predict the propagation and extinction conditions of a premixed flame in a channel considering a thermodiffusive model. A local refinement method is employed because of the numerous length scales that characterize this phenomenon. The time integration is self adaptive and the solution is based on a multigrid method using a zonal mesh refinement in the flame reaction zone. The objective is to determine the conditions of extinction which are characterized by the flame structure and its properties. We are interested in the following properties: the curvature of the flame, its maximum temperature, its speed of propagation and the distance separating the flame from the wall. We analyze the influence of heat losses at the wall through the thermal conductivity of the wall and the nature of the fuel characterized by the Lewis number of the mixture. This investigation allows us to identify three propagation regimes according to heat losses at the wall and to the channel radius. The results show that there is an intermediate value of the radius for which the flame can bend and propagate provided that its curvature does not exceed a certain limit value. Indeed, small values of the radius will choke the flame and extinguish it. The extinction occurs if the flame curvature becomes too small. Furthermore, this study allows us to predict the limiting values of the heat loss coefficient at extinction as well as the critical value of the channel radius above which the premixed flame may propagate without extinction. A dead zone of length 2-4 times the flame thickness appears between the flame and the wall for a Lewis number (Le) between 0.8 and 2. For small values of Le, local extinctions are observed. (author)

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

A robust fourth-order finite-difference discretization for the strongly anisotropic transport equation in magnetized plasmas

We propose a second-order temporally implicit, fourth-order-accurate spatial discretization scheme for the strongly anisotropic heat transport equation characteristic of hot, fusion-grade plasmas. Following Du Toit et al. (2018), the scheme transforms mixed-derivative diffusion fluxes (which are responsible for the lack of a discrete maximum principle) into nonlinear advective fluxes, amenable to nonlinear-solver-friendly monotonicity-preserving limiters. The scheme enables accurate multi-dimensional heat transport simulations with up to seven orders of magnitude of heat-transport-coefficient anisotropies with low cross-field numerical error pollution and excellent algorithmic performance, with the number of linear iterations scaling very weakly with grid resolution and grid anisotropy, and scaling with the square-root of the implicit timestep. We propose a multigrid preconditioning strategy based on a lower-order approximation that renders the scheme efficient and scalable under grid refinement. Several numerical tests are presented that display the expected spatial convergence rates and strong algorithmic performance, including fully nonlinear magnetohydrodynamics simulations of kink instabilities in a Bennett pinch in 2D helical geometry and of ITER in 3D toroidal geometry.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

Fast solvers for tokamak fluid models with PETSc

Multigrid (MG) is widely recognized as a highly effective solver for the model problem, the Laplacian, but textbook MG fails on most problems of interest. MG methods have been applied to complex, real-world applications with careful consideration of the physical model and discretization. In this work we develop the first step in applying MG methods to science and engineering relevant magnetohydrodynamics (MHD) tokamak models in the M3D-C1 (https://m3dc1.pppl.gov) fusion energy science code. The semi-implicit time integrator in M3D-C1 is composed of many linear solves. The implicit advance of the momentum equation is the most challenging and is the focus of this work. The current production solver in M3D-C1 is a block Jacobi (BJ) preconditioner within a Krylov solver, where blocks group degrees of freedom on planes of constant toroidal coordinate. BJ convergence degrades as the number of planes increases due to the spectral properties of the matrix preconditioned with BJ. The partially magnetic field-aligned, regular toroidal grid structure in M3D-C1 is amenable to semi-coarsening geometric MG in the toroidal direction. This paper develops such a solver and demonstrates competitive performance on a runaway electron model of a SPARC (https://cfs.energy/technology/sparc) disruption, and superior robustness on a stellarator model on which the BJ solver fails to converge.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗