Search NASA⌕ Search

SEARCH · Search NASA

Results for “multigrid technique”

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 19 records
All sourcesNASA NTRSDOE OSTI
DOE OSTI2016

Segmental Refinement: A Multigrid Technique for Data Locality

In this paper, we investigate a domain decomposed multigrid technique, termed segmental refinement, for solving general nonlinear elliptic boundary value problems. We extend the method first proposed in 1994 by analytically and experimentally investigating its complexity. We confirm that communication of traditional parallel multigrid is eliminated on fine grids, with modest amounts of extra work and storage, while maintaining the asymptotic exactness of full multigrid. We observe an accuracy dependence on the segmental refinement subdomain size, which was not considered in the original analysis. Finally, we present a communication complexity analysis that quantifies the communication costs ameliorated by segmental refinement and report performance results with up to 64K cores on a Cray XC30.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2014

Segmental Refinement: A Multigrid Technique for Data Locality

We investigate a technique - segmental refinement (SR) - proposed by Brandt in the 1970s as a low memory multigrid method. The technique is attractive for modern computer architectures because it provides high data locality, minimizes network communication, is amenable to loop fusion, and is naturally highly parallel and asynchronous. The network communication minimization property was recognized by Brandt and Diskin in 1994; we continue this work by developing a segmental refinement method for a finite volume discretization of the 3D Laplacian on massively parallel computers. An understanding of the asymptotic complexities, required to maintain textbook multigrid efficiency, are explored experimentally with a simple SR method. A two-level memory model is developed to compare the asymptotic communication complexity of a proposed SR method with traditional parallel multigrid. Performance and scalability are evaluated with a Cray XC30 with up to 64K cores. We achieve modest improvement in scalability from traditional parallel multigrid with a simple SR implementation.

3D Laplacian↗
DOE OSTI2020

A least-squares finite element method based on the Helmholtz decomposition for hyperbolic balance laws

In this paper, a least-squares finite element method for scalar nonlinear hyperbolic balance laws is proposed and studied. The approach is based on a formulation that utilizes an appropriate Helmholtz decomposition of the flux vector and is related to the standard notion of a weak solution. This relationship, together with a corresponding connection to negative-norm least-squares, is described in detail. As a consequence, an important numerical conservation theorem is obtained, similar to the famous Lax–Wendroff theorem. The numerical conservation properties of the method in this paper do not fall precisely in the framework introduced by Lax and Wendroff, but they are similar in spirit as they guarantee that when L 2 convergence holds, the resulting approximations approach a weak solution to the hyperbolic problem. The least-squares functional is continuous and coercive in an H -1 -type norm, but not L 2 -coercive. Nevertheless, the L 2 convergence properties of the method are discussed. Convergence can be obtained either by an explicit regularization of the functional, that provides control of the L 2 norm, or by properly choosing the finite element spaces, providing implicit control of the L 2 norm. Numerical results for the inviscid Burgers equation with discontinuous source terms are shown, demonstrating the L 2 convergence of the obtained approximations to the physically admissible solution. The numerical method utilizes a least-squares functional, minimized on finite element spaces, and a Gauss–Newton technique with nested iteration. Finally, we believe that the linear systems encountered with this formulation are amenable to multigrid techniques and combining the method with adaptive mesh refinement would make this approach an efficient tool for solving balance laws (this is the focus of a future study).

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2017

A compatible high-order meshless method for the Stokes equations with applications to suspension flows

A stable numerical solution of the steady Stokes problem requires compatibility between the choice of velocity and pressure approximation that has traditionally proven problematic for meshless methods. Here in this work, we present a discretization that couples a staggered scheme for pressure approximation with a divergence-free velocity reconstruction to obtain an adaptive, high-order, finite difference-like discretization that can be efficiently solved with conventional algebraic multigrid techniques. We use analytic benchmarks to demonstrate equal-order convergence for both velocity and pressure when solving problems with curvilinear geometries. In order to study problems in dense suspensions, we couple the solution for the flow to the equations of motion for freely suspended particles in an implicit monolithic scheme. The combination of high-order accuracy with fully-implicit schemes allows the accurate resolution of stiff lubrication forces directly from the solution of the Stokes problem without the need to introduce sub-grid lubrication models.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2016

Summary Report: Multigrid for Systems of Elliptic PDEs

We are interested in determining if multigrid can be effectively applied to the system. The conclusion that I seem to be drawn to is that it is impossible to develop a blackbox multigrid solver for these general systems. Analysis of the system of PDEs must be conducted first to determine pre-processing procedures on the continuous problem before applying a multigrid method. Determining this pre-processing is currently not incorporated in black-box multigrid strategies. Nevertheless, we characterize some system features that will make the system more amenable to multigrid approaches, techniques that may lead to more amenable systems, and multigrid procedures that are generally more appropriate for these systems.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2019

Multilevel Techniques for Compression and Reduction of Scientific Data---The Multivariate Case

We develop a technique for multigrid adaptive reduction of data (MGARD). Special attention is given to the case of tensor product grids, where our approach permits the use of nonuniformly spaced grids in each direction, which can prove problematic for many types of data reduction methods. An important feature of our approach is the provision of guaranteed, computable bounds on the loss incurred by the reduction of the data. Many users are leery of lossy algorithms and will only consider using them provided that numerical bounds on the pointwise difference between the original and the reduced datasets are given. Accordingly, we develop techniques for bounding the loss measured in the $L^{\infty}(\Omega)$ norm, and we show that these bounds are realistic in the sense that they do not significantly overestimate the actual loss. Here, the resulting loss indicators are used to guide the adaptive reduction of the data so that the reduced dataset meets a user-prescribed tolerance or memory constraint. Illustrative numerical examples, including the reduction of data arising from the simulation of a nonlinear reaction-diffusion problem, a turbulent channel flow, and a climate simulation, are provided.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2016

Multigrid Reduction in Time for Nonlinear Parabolic Problems

The need for parallel-in-time is being driven by changes in computer architectures, where future speed-ups will be available through greater concurrency, but not faster clock speeds, which are stagnant.This leads to a bottleneck for sequential time marching schemes, because they lack parallelism in the time dimension. Multigrid Reduction in Time (MGRIT) is an iterative procedure that allows for temporal parallelism by utilizing multigrid reduction techniques and a multilevel hierarchy of coarse time grids. MGRIT has been shown to be effective for linear problems, with speedups of up to 50 times. The goal of this work is the efficient solution of nonlinear problems with MGRIT, where efficient is defined as achieving similar performance when compared to a corresponding linear problem. As our benchmark, we use the p-Laplacian, where p = 4 corresponds to a well-known nonlinear diffusion equation and p = 2 corresponds to our benchmark linear diffusion problem. When considering linear problems and implicit methods, the use of optimal spatial solvers such as spatial multigrid imply that the cost of one time step evaluation is fixed across temporal levels, which have a large variation in time step sizes. This is not the case for nonlinear problems, where the work required increases dramatically on coarser time grids, where relatively large time steps lead to worse conditioned nonlinear solves and increased nonlinear iteration counts per time step evaluation. This is the key difficulty explored by this paper. We show that by using a variety of strategies, most importantly, spatial coarsening and an alternate initial guess to the nonlinear time-step solver, we can reduce the work per time step evaluation over all temporal levels to a range similar with the corresponding linear problem. This allows for parallel scaling behavior comparable to the corresponding linear problem.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2017

Multigrid Reduction in Time for Nonlinear Parabolic Problems: A Case Study

The need for parallelism in the time dimension is being driven by changes in computer architectures, where performance increases are now provided through greater concurrency, not faster clock speeds. This creates a bottleneck for sequential time marching schemes because they lack parallelism in the time dimension. Multigrid reduction in time (MGRIT) is an iterative procedure that allows for temporal parallelism by utilizing multigrid reduction techniques and a multilevel hierarchy of coarse time grids. MGRIT has been shown to be effective for linear problems, with speedups of up to 50 times. The goal of this work is the efficient solution of nonlinear problems with MGRIT, where efficiency is defined as achieving similar performance when compared to an equivalent linear problem. The benchmark nonlinear problem is the p-Laplacian, where p=4 corresponds to a well-known nonlinear diffusion equation and p=2 corresponds to the standard linear diffusion operator, our benchmark linear problem. The key difficulty encountered is that the nonlinear time-step solver becomes progressively more expensive on coarser time levels as the time-step size increases. To overcome such difficulties, multigrid research has historically targeted an accumulated body of experience regarding how to choose an appropriate solver for a specific problem type. To that end, this paper develops a library of MGRIT optimizations and modifications, most important an alternate initial guess for the nonlinear time-step solver and delayed spatial coarsening, that will allow many nonlinear parabolic problems to be solved with parallel scaling behavior comparable to the corresponding linear problem.

parareal↗
DOE OSTI2020

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↗
DOE OSTI2023

Scalable DPG multigrid solver for Helmholtz problems: A study on convergence

This paper presents a scalable multigrid preconditioner targeting large-scale systems arising from discontinuous Petrov–Galerkin (DPG) discretizations of high-frequency wave operators. This work is built on previously developed multigrid preconditioning techniques of Petrides and Demkowicz (Comput. Math. Appl. 87 (2021) pp. 12–26) and extends the convergence results from $\mathscr{O}$(10 7 ) degrees of freedom (DOFs) to $\mathscr{O}$(10 9 ) DOFs using a new scalable parallel MPI/OpenMP implementation. Novel contributions of this paper include an alternative definition of coarse-grid systems based on restriction of fine-grid operators, yielding superior convergence results. In the uniform refinement setting, a detailed convergence study is provided, demonstrating h and p robust convergence and linear scaling with respect to the wave frequency. Finally, the paper concludes with numerical results on hp -adaptive simulations including a large-scale seismic modeling benchmark problem with high material contrast.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2018

A non-intrusive parallel-in-time approach for simultaneous optimization with unsteady PDEs

This paper presents a non-intrusive framework for integrating existing unsteady partial differential equation (PDE) solvers into a parallel-in-time simultaneous optimization algorithm. The time-parallelization is provided by the non-intrusive software library XBraid [Parallel multigrid in time, software available at http://llnl.gov/casc/xbraid], which applies an iterative multigrid reduction technique to the time domain of existing time-marching schemes for solving unsteady PDEs. Its general user-interface has been extended in [S. Günther, N.R. Gauger, and J.B. Schroder, A non-intrusive parallel-in-time adjoint solver with the XBraid library, Comput. Vis. Sci. 19 (2018), pp. 85–95. Available at arXiv, math.OC/1705.00663] for computing adjoint sensitivities such that gradients of output quantities with respect to design changes can be computed parallel-in-time alongside with the primal PDE solution. In this paper, the primal and adjoint XBraid iterations are embedded into a simultaneous optimization framework, namely the One-shot method. In this method, design updates towards optimality are employed after each state and adjoint update such that optimality and feasibility of the design and the PDE solution are reached simultaneously. Finally, the time-parallel optimization method is validated on an advection-dominated flow control problem which shows significant speedup over a classical time-serial optimization algorithm.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

Multigrid Reduction in Time for Chaotic and Hyperbolic Problems (Final Report)

The coming massive parallelism of exascale computing presents a pressing challenge for the many DOE simulations of time-dependent partial differential equations (PDEs), which typically use traditional sequential time stepping methods. Since this traditional approach is inherently serial, it presents a sequential bottleneck when moving to exascale computing, because future performance gains will come through greater concurrency, not faster clock speeds. Thus, the goal of this work is to research parallelism in time, i.e., methods that compute multiple time values simultaneously, not sequentially. The focus will be on hyperbolic and chaotic problems of interest to DOE, with the goal of enabling scalable simulations of time-dependent hyperbolic and chaotic problems on future architectures. The chosen methodology for solving these problems parallel-in-time is multigrid, because multigrid (when it works) is a powerful, optimal, and scalable solver for discretized PDEs. Multigrid is already commonly used in many DOE simulations for scalably and optimally solving space-only PDE problems. The areas of hyperbolic and chaotic problems are chosen because of their relevance to problems of programmatic interest to DOE. However, these problems are also well-known to be difficult for parallelin-time methods, with the most common method, parareal, diverging in many cases. The current state-of-the-art for parallel-in-time at LLNL is the multigrid reduction in time (MGRIT) XBraid package, which also struggles for such problems, while still showing some improvement over parareal. In summary, new methods are needed for an efficient parallel-in-time scheme for hyperbolic and chaotic problems, and this work shall research promising new multigrid methods in this area. In particular, this work shall continue researching the directions from the current collaboration with Dr. Falgout, which are laid out in the work Toward Parallel in Time for Chaotic Dynamical Systems and showed the first known results of a parallel-in-time speedup for a chaotic problem. This work outlines two key improvements to XBraid for chaotic problems, the so-called “theta” and “delta-correction” methods. Here, these two improvements will be implemented in a high-performance but general way in XBraid and explored for more complicated problems. We will additionally research, as time allows, improvements to these techniques, as well as multigrid relaxation techniques based on Least Squares Shadowing (LSS by Wang) and a nonintrusive block tridiagonal solver based on MGRIT, called TriMGRIT.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2018

A Scalable Preconditioner for a Primal Discontinuous Petrov--Galerkin Method

In this work, we show how a scalable preconditioner for the primal discontinuous Petrov--Galerkin (DPG) method can be developed using existing algebraic multigrid (AMG) preconditioning techniques. The stability of the DPG method gives a norm equivalence which allows us to exploit existing AMG algorithms and software. We show how these algebraic preconditioners can be applied directly to a Schur complement system arising from the DPG method. One of our intermediate results shows that a generic stable decomposition implies a stable decomposition for the Schur complement. This justifies the application of algebraic solvers directly to the interface degrees of freedom. Combining such results, we obtain the first massively scalable algebraic preconditioner for the DPG system.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2017

Numerical Multilevel Upscaling for Incompressible Flow in Reservoir Simulation: An Element-Based Algebraic Multigrid (AMGe) Approach

Here, we study the application of a finite element numerical upscaling technique to the incompressible two-phase porous media total velocity formulation. Specifically, an element-agglomeration-based algebraic multigrid (AMGe) technique with improved approximation properties is used, for the first time, to generate upscaled and accurate coarse systems for the reservoir simulation equations. The upscaling technique is applied to both the mixed system for velocity and pressure and to the hyperbolic transport equations, providing fully upscaled systems. By introducing additional degrees of freedom associated with nonplanar interfaces between agglomerates, the coarse velocity space has guaranteed approximation properties. The employed AMGe technique provides coarse spaces with desirable local mass conservation and stability properties analogous to the original pair of Raviart--Thomas and piecewise discontinuous polynomial spaces, resulting in strong mass conservation for the upscaled systems. Due to the guaranteed approximation properties and the generic nature of the AMGe method, recursive multilevel upscaling is automatically obtained. Furthermore, this technique works for both structured and unstructured meshes. Multiscale mixed finite elements exhibit accuracy for general unstructured meshes but do not in general lead to nested hierarchy of spaces. Multiscale multilevel mimetic finite differences generate nested spaces but lack the adaptivity of the flux representation on coarser levels that the proposed AMGe approach offers. Thus, the proposed approach can be seen as a rigorous bridge that merges the best properties of these two existing methods. The accuracy and stability of the studied multilevel AMGe upscaling technique is demonstrated on two challenging test cases.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2017

On the Preconditioning of a Newton-Krylov Solver for a High-Order reconstructed Discontinuous Galerkin Discretization of All-Speed Compressible Flow with Phase Change for Application in Laser-Based Additive Manufacturing

This dissertation focuses on the development of a fully-implicit, high-order compressible ow solver with phase change. The work is motivated by laser-induced phase change applications, particularly by the need to develop large-scale multi-physics simulations of the selective laser melting (SLM) process in metal additive manufacturing (3D printing). Simulations of the SLM process require precise tracking of multi-material solid-liquid-gas interfaces, due to laser-induced melting/ solidi cation and evaporation/condensation of metal powder in an ambient gas. These rapid density variations and phase change processes tightly couple the governing equations, requiring a fully compressible framework to robustly capture the rapid density variations of the ambient gas and the melting/evaporation of the metal powder. For non-isothermal phase change, the velocity is gradually suppressed through the mushy region by a variable viscosity and Darcy source term model. The governing equations are discretized up to 4th-order accuracy with our reconstructed Discontinuous Galerkin spatial discretization scheme and up to 5th-order accuracy with L-stable fully implicit time discretization schemes (BDF2 and ESDIRK3-5). The resulting set of non-linear equations is solved using a robust Newton-Krylov method, with the Jacobian-free version of the GMRES solver for linear iterations. Due to the sti nes associated with the acoustic waves and thermal and viscous/material strength e ects, preconditioning the GMRES solver is essential. A robust and scalable approximate block factorization preconditioner was developed, which utilizes the velocity-pressure (vP) and velocity-temperature (vT) Schur complement systems. This multigrid block reduction preconditioning technique converges for high CFL/Fourier numbers and exhibits excellent parallel and algorithmic scalability on classic benchmark problems in uid dynamics (lid-driven cavity ow and natural convection heat transfer) as well as for laser-induced phase change problems in 2D and 3D.

42 ENGINEERING↗
DOE OSTI2018

Algebraic multigrid preconditioners for two-phase flow in porous media with phase transitions [Algebraic multigrid preconditioners for multiphase flow in porous media with phase transitions]

Multiphase flow is a critical process in a wide range of applications, including oil and gas recovery, carbon sequestration, and contaminant remediation. Numerical simulation of multiphase flow requires solving of a large, sparse linear system resulting from the discretization of the partial differential equations modeling the flow. In the case of multiphase multicomponent flow with miscible effect, this is a very challenging task. The problem becomes even more difficult if phase transitions are taken into account. A new approach to handle phase transitions is to formulate the system as a nonlinear complementarity problem (NCP). Unlike in the primary variable switching technique, the set of primary variables in this approach is fixed even when there is phase transition. Not only does this improve the robustness of the nonlinear solver, it opens up the possibility to use multigrid methods to solve the resulting linear system. The disadvantage of the complementarity approach, however, is that when a phase disappears, the linear system has the structure of a saddle point problem and becomes indefinite, and current algebraic multigrid (AMG) algorithms cannot be applied directly. In this study, we explore the effectiveness of a new multilevel strategy, based on the multigrid reduction technique, to deal with problems of this type. We demonstrate the effectiveness of the method through numerical results for the case of two-phase, two-component flow with phase appearance/disappearance. In conclusion, we also show that the strategy is efficient and scales optimally with problem size.

02 PETROLEUM↗
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↗