SEARCH · Search NASA

Results for “Full Approximation Scheme”

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.

SourceResearch connectionFrom yearThrough year

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

At least 19 records

All sources NASA NTRS DOE OSTI

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.↗

NASA NTRS1985

Multigrid method for nearly singular and slightly indefinite problems

This paper deals with nearly singular, possibly indefinite problems for which the usual multigrid solvers converge very slowly or even diverge. The main difficulty is related to some badly approximated smooth functions which correspond to eigenfunctions with nearly zero eigenvalues. A correction to the usual coarse-grid equations is derived, both in the correction scheme and in the full approximation scheme. The performance of the new algorithm using this correction is essentially as that of usual multigrid for definite problems.

Brandt, A.↗

NASA NTRS1986

Multigrid method for nearly singular and slightly indefinite problems

Brandt, A.↗

DOE OSTI2021

Multilevel Spectral Coarsening for Graph Laplacian Problems with Application to Reservoir Simulation

We extend previously developed two-level coarsening procedures for graph Laplacian problems written in a mixed saddle point form to the fully recursive multilevel case. The resulting hierarchy of discretizations gives rise to a hierarchy of upscaled models, in the sense that they provide approximation in the natural norms (in the mixed setting). This property enables us to utilize them in three applications: (i) as an accurate reduced model, (ii) as a tool in multilevel Monte Carlo simulations (in application to finite volume discretizations), and (iii) for providing a sequence of nonlinear operators in a full approximation scheme for solving nonlinear pressure equations discretized by the conservative two-point flux approximation. Finally, we illustrate the potential of the proposed multilevel technique in all three applications on a number of popular benchmark problems used in reservoir simulation.

multilevel Monte Carlo↗

DOE OSTI2023

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↗

DOE OSTI2022

An aggregation-based nonlinear multigrid solver for two-phase flow and transport in porous media

A nonlinear multigrid solver for two-phase flow and transport in a mixed fractional-flow velocity-pressure-saturation formulation is proposed. The solver, which is under the framework of the full approximation scheme (FAS), extends our previous work on nonlinear multigrid for heterogeneous diffusion problems. The coarse spaces in the multigrid hierarchy are constructed by first aggregating degrees of freedom, and then solving some local flow problems. The mixed formulation and the choice of coarse spaces allow us to assemble the coarse problems without visiting finer levels during the solving phase, which is crucial for the scalability of multigrid methods. Specifically, a natural generalization of the upwind flux can be evaluated directly on coarse levels using the precomputed coarse flux basis vectors. We find that the resulting solver is applicable to problems discretized on general unstructured grids. The performance of the proposed nonlinear multigrid solver in comparison with the standard single level Newton's method is demonstrated through challenging numerical examples. It is observed that the proposed solver is robust for highly nonlinear problems and clearly outperforms Newton's method in the case of high Courant-Friedrichs-Lewy (CFL) numbers.

58 GEOSCIENCES↗

DOE OSTI2024

Multilevel well modeling in aggregation-based nonlinear multigrid for multiphase flow in porous media

A full approximation scheme (FAS) nonlinear multigrid solver for two-phase flow and transport problems driven by wells with multiple perforations is developed here. It is an extension to our previous work on FAS solvers for diffusion and transport problems. The solver is applicable to discrete problems defined on unstructured grids as the coarsening algorithm is aggregation-based and algebraic. To construct coarse basis that can better capture the radial flow near wells, coarse grids in which perforated well cells are not near the coarse-element interface are desired. This is achieved by an aggregation algorithm proposed in this paper that makes use of the location of well cells in the cell-connectivity graph. Numerical examples in which the FAS solver is compared against Newton's method on benchmark problems are given. In particular, for a refined version of the SAIGUP model, the FAS solver is at least 35% faster than Newton's method for time steps with a CFL number greater than 10.

58 GEOSCIENCES↗

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 NTRS1999

An O(Nm(sup 2)) Plane Solver for the Compressible Navier-Stokes Equations

A hierarchical multigrid algorithm for efficient steady solutions to the two-dimensional compressible Navier-Stokes equations is developed and demonstrated. The algorithm applies multigrid in two ways: a Full Approximation Scheme (FAS) for a nonlinear residual equation and a Correction Scheme (CS) for a linearized defect correction implicit equation. Multigrid analyses which include the effect of boundary conditions in one direction are used to estimate the convergence rate of the algorithm for a model convection equation. Three alternating-line- implicit algorithms are compared in terms of efficiency. The analyses indicate that full multigrid efficiency is not attained in the general case; the number of cycles to attain convergence is dependent on the mesh density for high-frequency cross-stream variations. However, the dependence is reasonably small and fast convergence is eventually attained for any given frequency with either the FAS or the CS scheme alone. The paper summarizes numerical computations for which convergence has been attained to within truncation error in a few multigrid cycles for both inviscid and viscous ow simulations on highly stretched meshes.

Thomas, J. L.↗

DOE OSTI2023

Multigrid Reduction in Time for Chaotic Dynamical Systems

As CPU clock speeds have stagnated and high performance computers continue to have ever higher core counts, increased parallelism is needed to take advantage of these new architectures. Traditional serial time-marching schemes can be a significant bottleneck, as many types of simulations require large numbers of time-steps which must be computed sequentially. Parallel-in-time schemes, such as the Multigrid Reduction in Time (MGRIT) method, remedy this by parallelizing across time-steps and have shown promising results for parabolic problems. However, chaotic problems have proved more difficult, since chaotic initial value problems (IVPs) are inherently ill-conditioned. MGRIT relies on a hierarchy of successively coarser time-grids to iteratively correct the solution on the finest time-grid, but due to the nature of chaotic systems, small inaccuracies on the coarser levels can be greatly magnified and lead to poor coarse-grid corrections. Here we introduce a modified MGRIT algorithm based on an existing quadratically converging nonlinear extension to the multigrid Full Approximation Scheme (FAS), as well as a novel time-coarsening scheme. Together, these approaches better capture long-term chaotic behavior on coarse-grids and greatly improve convergence of MGRIT for chaotic IVPs. Further, we introduce a novel low-memory variant of the algorithm for solving chaotic PDEs with MGRIT which not only solves the IVP, but also provides estimates for the unstable Lyapunov vectors of the system. Finally, we provide supporting numerical results for the Lorenz system and demonstrate parallel speedup for the chaotic Kuramoto–Sivashinsky PDE over a significantly longer time-domain than in previous works.

97 MATHEMATICS AND COMPUTING↗

NASA NTRS1996

Application of an Upwind High Resolution Finite-Differencing Scheme and Multigrid Method in Steady-State Incompressible Flow Simulations

The analysis and design of a submarine propulsor requires the ability to predict the characteristics of both laminar and turbulent flows to a higher degree of accuracy. This report presents results of certain benchmark computations based on an upwind, high-resolution, finite-differencing Navier-Stokes solver. The purpose of the computations is to evaluate the ability, the accuracy and the performance of the solver in the simulation of detailed features of viscous flows. Features of interest include flow separation and reattachment, surface pressure and skin friction distributions. Those features are particularly relevant to the propulsor analysis. Test cases with a wide range of Reynolds numbers are selected; therefore, the effects of the convective and the diffusive terms of the solver can be evaluated separately. Test cases include flows over bluff bodies, such as circular cylinders and spheres, at various low Reynolds numbers, flows over a flat plate with and without turbulence effects, and turbulent flows over axisymmetric bodies with and without propulsor effects. Finally, to enhance the iterative solution procedure, a full approximation scheme V-cycle multigrid method is implemented. Preliminary results indicate that the method significantly reduces the computational effort.

NAVIER STOKES EQUATIONS↗

NASA NTRS1997

On Approximate Factorization Schemes for Solving the Full Potential Equation

An approximate factorization scheme based on the AF2 algorithm is presented for solving the three-dimensional full potential equation for the transonic flow about isolated wings. Two spatial discretization variations are presented, one using a hybrid first-order/second-order-accurate scheme and the second using a fully second-order-accurate scheme. The present algorithm utilizes a C-H grid topology to map the flow field about the wing. One version of the AF2 iteration scheme is used on the upper wing surface and another slightly modified version is used on the lower surface. These two algorithm variations are then connected at the wing leading edge using a local iteration technique. The resulting scheme has improved linear stability characteristics and improved time-like damping characteristics relative to previous implementations of the AF2 algorithm. The presentation is highlighted with a grid refinement study and a number of numerical results.

Holst, Terry L.↗

DOE OSTI2021

An experimental comparison of a space-time multigrid method with PFASST for a reaction-diffusion problem

We consider two parallel-in-time approaches applied to a (reaction) diffusion problem, possibly non-linear. In particular, we consider PFASST (Parallel Full Approximation Scheme in Space and Time) and space-time multigrid strategies. For both approaches, we start from an integral formulation of the continuous time dependent problem. Then, a collocation form for PFASST and a discontinuous Galerkin discretization in time for the space-time multi-grid are employed, resulting in the same discrete solution at the time nodes. Strong and weak scaling of both multilevel strategies are compared for varying orders of the temporal discretization. Moreover, we investigate the respective convergence behavior for non-linear problems and highlight quantitative differences in execution times

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2021

Multilevel Training of Neural Networks

MTNN is a software library for applying multilevel algorithms on training neural networks. Based on PyTorch, it is designed to be an extensible framework to enable researchers to implement multilevel training algorithms on a variety of neural network models. This release includes a culmination of preliminary work in applying the multilevel Full Approximation Scheme technique on fully connected and convolutional neural networks to solve PDE problems (pending publication submission).

Li, Ruipeng↗

DOE OSTI2023

SUHMO: an adaptive mesh refinement SUbglacial Hydrology MOdel v1.0

Abstract. Water flowing under ice sheets and glaciers can have a strong influence on ice dynamics, particularly through pressure changes, suggesting that a comprehensive ice sheet model should include the effect of basal hydrology. Modeling subglacial hydrology remains a challenge, however, mainly due to the range of spatial and temporal scales involved – from subglacial channels to vast subglacial lakes. Additionally, networks of subglacial drainage channels dynamically evolve over time. To address some of these challenges, we have developed an adaptive mesh refinement (AMR) model based on the Chombo software framework. We extend the model proposed by Sommers et al. (2018) with a small but significant change to accommodate the transition from unresolved to resolved flow features. We handle the strong nonlinearities present in the equations by resorting to an efficient nonlinear full approximation scheme multigrid (FAS-MG) algorithm. We outline the details of the algorithm and present convergence analysis results demonstrating its good performance. Additionally, we present results validating our approach, using test cases from the Subglacial Hydrology Model Intercomparison Project (SHMIP) (de Fleurian et al., 2018). We finish by presenting a more complex, 100 km-by-100 km synthetic test case with peaks and valleys that we use to investigate the effective pressure distribution as the number of AMR levels increases. These preliminary results suggest that a minimum spatial resolution is needed to properly capture channel features, but additional work is required to precisely quantify this and its impact on accurately modeling the coupled ice sheet–hydrology system. The efficiency of our approach, relying on localized refinement, is also demonstrated. Future work will include coupling the SUbglacial Hydrology MOdel (SUHMO) with the BISICLES AMR ice sheet model (Cornford et al., 2013), both built on the same numerical framework.

58 GEOSCIENCES↗

NASA NTRS1986

Implicit multigrid algorithms for the three-dimensional flux split Euler equations

The full approximation scheme multigrid method is applied to several implicit flux-split algorithms for solving the three-dimensional Euler equations in a body fitted coordinate system. Each uses a variation of approximate factorization and is implemented in a finite volume formulation. The algorithms are all vectorizable with little or no scalar computations required. The flux vectors are split into upwind components using both the splittings of Steger-Warming and Van Leer. Results comparing pressure distributions with experimental data using both splitting types are shown. The stability and smoothing rate of each of the schemes are examined using a Fourier analysis of the complete system of equations. Results are presented for three-dimensional subsonic, transonic, and supersonic flows which demonstrate substantially improved convergence rates with the multigrid algorithm. The influence of using both a V-cycle and a W-cycle on the convergence is examined. Using the multigrid method on both subsonic and transonic wing calculations, the final lift coefficient is obtained to within 0.1 percent of its final value in a few as 15 cycles for a mesh with over 210,000 points. A spectral radius of 0.89 is achieved for both subsonic and transonic flow over the ONERA M6 wing while a spectral radius of 0.83 is obtained for supersonic flow over an analytically defined forebody. Results compared with experiment for all cases show good agreement.

Anderson, W. K.↗

NASA NTRS1988

Three-dimensional multigrid algorithms for the flux-split Euler equations

The Full Approximation Scheme (FAS) multigrid method is applied to several implicit flux-split algorithms for solving the three-dimensional Euler equations in a body fitted coordinate system. Each of the splitting algorithms uses a variation of approximate factorization and is implemented in a finite volume formulation. The algorithms are all vectorizable with little or no scalar computation required. The flux vectors are split into upwind components using both the splittings of Steger-Warming and Van Leer. The stability and smoothing rate of each of the schemes are examined using a Fourier analysis of the complete system of equations. Results are presented for three-dimensional subsonic, transonic, and supersonic flows which demonstrate substantially improved convergence rates with the multigrid algorithm. The influence of using both a V-cycle and a W-cycle on the convergence is examined.

Anderson, W. Kyle↗