Search NASA⌕ Search

SEARCH · Search NASA

Results for “Multigrid methods”

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 631 records · Page 35

A Scalable Multigrid Reduction Framework for Multiphase Poromechanics of Heterogeneous Media

Simulation of multiphase poromechanics involves solving a multiphysics problem in which multiphase flow and transport are tightly coupled with the porous medium deformation. To capture this dynamic interplay, fully implicit methods, also known as monolithic approaches, are usually preferred. The main bottleneck of a monolithic approach is that it requires solution of large linear systems that result from the discretization and linearization of the governing balance equations. Because such systems are nonsymmetric, indefinite, and highly ill-conditioned, preconditioning is critical for fast convergence. Recently, most efforts in designing efficient preconditioners for multiphase poromechanics have been dominated by physics-based strategies. Current state-of-the-art “black-box” solvers such as algebraic multigrid (AMG) are ineffective because they cannot effectively capture the strong coupling between the mechanics and the flow subproblems, as well as the coupling inherent in the multiphase flow and transport process. In this work, we develop an algebraic framework based on multigrid reduction (MGR) that is suited for tightly coupled systems of PDEs. Using this framework, the decoupling between the equations is done algebraically through defining appropriate interpolation and restriction operators. One can then employ existing solvers for each of the decoupled blocks or design a new solver based on knowledge of the physics. We demonstrate the applicability of our framework when used as a “black-box” solver for multiphase poromechanics. Here, we show that the framework is flexible to accommodate a wide range of scenarios, as well as efficient and scalable for large problems.

97 MATHEMATICS AND COMPUTING↗

A scalable, matrix-free multigrid preconditioner for finite element discretizations of heterogeneous Stokes flow

In this paper we describe a computational methodology that is specifically designed for studying three-dimensional geodynamic processes governed by heterogeneous visco-plastic Stokes flow. The method employs a hybrid spatial discretization consisting of a View the MathML sourceQ2-P1disc mixed finite element formulation for the Stokes problem, coupled to a material-point formulation which is used for representing material state and history-dependent variables. The applicability and practicality of this methodology is realized through the development of an efficient, scalable and robust variable viscosity Stokes preconditioner. In this work, these objectives are achieved through exploiting matrix-free operators and a geometric multigrid preconditioner employing hybrid coarse level operators, Chebyshev smoothers and hybrid Krylov coarse level solvers. The robustness and parallel efficiency of this strategy is demonstrated using an idealized geodynamic model. Lastly, we apply the new methodology to study geodynamic models of continental rifting and break-up in order to understand the diverse range of passive continental margins we observe on Earth today

Geodynamics↗

Efficient Preconditioning of a High-Order Solver for Multiple Physics

This work addresses preconditioning approaches for an implicit high-order solver frame-work applied to multiple physics. The solver is based on a space-time spectral element method and matrix-free Newton-Krylov solver developed at NASA over the recent years. Within this context, most preconditioning methods are impractical, as the computational time and memory requirements scale poorly with increasing polynomial orders. To improve computational efficiency, we first describe a novel entity-based Block Jacobi preconditioner for the continuous-Galerkin solution of the linear-elasticity and linear-shell equations. Second, we introduce a multigrid algorithm to further reduce time-to-solution on stiff cases arising from continuous-and discontinuous-Galerkin discretizations. Results obtained on relevant single-physics reference solutions, demonstrate the feasibility of the methods, paving the way for high-order solutions of fully coupled multi-physics problems.

STMD↗

A nonoscillatory shock capturing scheme using flux limited dissipation

A method for modifying the third order dissipative terms by the introduction of flux limiters is proposed. The first order dissipative terms can then be eliminated entirely, and in the case of a scalar conservation law the scheme is converted into a total variation diminishing scheme provided that an appropriate value is chosen for the dissipative coefficient. Particular attention is given to: (1) the treatment of the scalar conservation law; (2) the treatment of the Euler equations for inviscid compressible flow; (3) the boundary conditions; and (4) multistage time stepping and multigrid schemes. Numerical results for transonic flows suggest that a central difference scheme augmented by flux limited dissipative terms can lead to an effective nonoscillatory shock capturing method.

Jameson, A.↗

Algebraic Multigrid Preconditioners for Multiphase Flow in Porous Media

Multiphase flow is a critical process in a wide range of applications, including carbon sequestration, contaminant remediation, and groundwater management. Typically, this process is modeled by a nonlinear system of partial differential equations derived by considering the mass conservation of each phase (e.g., oil, water), along with constitutive laws for the relationship of phase velocity to phase pressure. In this study, we develop and study efficient solution algorithms for solving the algebraic systems of equations derived from a fully coupled and time-implicit treatment of models of multiphase flow. We explore the performance of several preconditioners based on algebraic multigrid (AMG) for solving the linearized problem, including “black-box” AMG applied directly to the system, a new version of constrained pressure residual multigrid (CPR-AMG) preconditioning, and a new preconditioner derived using an approximate Schur complement arising from the block factorization of the Jacobian. Finally, we show that the new methods are the most robust with respect to problem character, as determined by varying effects of capillary pressures, and we show that the block factorization preconditioner both is efficient and scales optimally with problem size.

97 MATHEMATICS AND COMPUTING↗

A simplified analysis of the multigrid V-cycle as a fast elliptic solver

For special model problems, Fourier analysis gives exact convergence rates for the two-grid multigrid cycle and, for more general problems, provides estimates of the two-grid convergence rates via local mode analysis. A method is presented for obtaining mutigrid convergence rate estimates for cycles involving more than two grids (using essentially the same analysis as for the two-grid cycle). For the simple cast of the V-cycle used as a fast Laplace solver on the unit square, the k-grid convergence rate bounds obtained by this method are sharper than the bounds predicted by the variational theory. Both theoretical justification and experimental evidence are presented.

Decker, Naomi H.↗

On the use of a multigrid-reduction-in-time algorithm for multiscale convergence of turbulence simulations

Simulations of turbulent flow present challenges in terms of accuracy and affordability on modern highly-parallel computer architectures. A multigrid-reduction-in-time algorithm is used to provide a framework for separately evolving different scales of turbulence and for parallelizing the temporal domain, thereby increasing the concurrency. It is hypothesized that the space–time locality of the small scales of turbulence can be used to circumvent difficulties in applying temporal multigrid to flows dominated by inertial physics. For algorithms that fall well short of spectral accuracy (fourth-order is used in this work) attention must be paid to the accuracy of features on scales transferred between multigrid levels. Numerical experiments were performed using implicit large-eddy simulation. Results from applying the approach to an infinite-Reynolds number Taylor–Green flow and a double-shear flow at a Reynolds number of 11650 provide strong evidence that the approach has merit. The multigrid-reduction-in-time framework can be used to parallelize the temporal domain of a high-Reynolds-number turbulent flow and permit independent convergence of different scales. Establishing this foundation allows for future research in reducing the wall-clock time to solve turbulent flows while retaining the same accuracy as sequential solvers. In conclusion, current performance results from parallelizing the temporal domain are not competitive with those from sequential-in-time methods.

97 MATHEMATICS AND COMPUTING↗

Aerodynamic design and optimization in one shot

This paper describes an efficient numerical approach for the design and optimization of aerodynamic bodies. As in classical optimal control methods, the present approach introduces a cost function and a costate variable (Lagrange multiplier) in order to achieve a minimum. High efficiency is achieved by using a multigrid technique to solve for all the unknowns simultaneously, but restricting work on a design variable only to grids on which their changes produce nonsmooth perturbations. Thus, the effort required to evaluate design variables that have nonlocal effects on the solution is confined to the coarse grids. However, if a variable has a nonsmooth local effect on the solution in some neighborhood, it is relaxed in that neighborhood on finer grids. The cost of solving the optimal control problem is shown to be approximately two to three times the cost of the equivalent analysis problem. Examples are presented to illustrate the application of the method to aerodynamic design and constraint optimization.

Ta'asan, Shlomo↗

Fast Computational Algorithms for Partial Differential Equations and Uncertainty Quantifications

This project concerned the construction, testing and analysis of computational algorithms for solving parameterized and stochastic partial differential equations. The study and understanding of equations of this type is of fundamental importance in numerous engineering and scientific applications. Examples include simulation of plasma dynamics in models of electric propulsion and nuclear fusion, simulation of multiphase flows, such as the flow of water, gas and oil in reservoirs, and structural analysis of the dependence of structures on materials. Parametrization is used in such settings when properties of the models such as viscosity of fluids or electric resistivity of materials are not precisely understood and instead are treated as random variables. The resulting solutions are themselves random, and having such solutions will enable engineers to use probabilistic methods to assess the likelihood of events, for example, whether a pollutant in a liquid will exceed a limit, and to use such analyses to develop ways to ensure positive outcomes. Construction of accurate (high resolution) computational solutions is expensive, requiring significant computer time and computational resources, and there is need to reduce computational cost to make simulation useful and effective. The aim of the project was to construct algorithms to efficiently compute surrogate solutions to parameterized problems to allow for efficient and accurate simulation. The technical approach used focused on two related strategies, based on rank-reduction methods and reduced-order models. These methods construct surrogate solutions of parameter-dependent models by projection or interpolation into low-dimensional approximation spaces. Cost savings are achieved if the low-dimensional spaces can be identified and constructed efficiently and if the resulting low-dimensional algebraic systems can be solved cheaply. Accomplishments include: Theoretical and empirical demonstration of the effectiveness of fast multigrid solution strategies for computing low-rank representations of parameter-dependent solutions to discrete partial differential equations, including the first proof establishing so-called textbook convergence properties for low-rank methods. Development of efficient solution algorithms for solving nonlinear parameter-dependent partial differential equations used in models of fluid dynamics. Developent of efficient algorithms for low-rank representation of solutions of time-dependent simulations of fluid dynamics using multi-dimensional tensor representations of solutions.

97 MATHEMATICS AND COMPUTING↗

Parallel-In-Time Multigrid with Adaptive Spatial Coarsening for The Linear Advection and Inviscid Burgers Equations

We apply a multigrid reduction-in-time (MGRIT) algorithm to hyperbolic partial differential equations in one spatial dimension. This study is motivated by the observation that sequential time-stepping is a computational bottleneck when attempting to implement highly concurrent algorithms; thus parallel-in-time methods are desirable. MGRIT adds parallelism by using a hierarchy of successively coarser temporal levels to accelerate the solution on the finest level. In the case of explicit time-stepping, spatial coarsening is a suitable approach to ensure that stability conditions are satisfied on all levels, and it may be useful for implicit time-stepping by producing cheaper multigrid cycles. Unfortunately, uniform spatial coarsening results in extremely slow convergence when the wave speed is near zero, even if only locally. We present an adaptive spatial coarsening strategy that addresses this issue for the variable coefficient linear advection equation and the inviscid Burgers equation using first-order explicit or implicit time-stepping methods. Serial numerical results show this method offers significant improvements over uniform coarsening and is convergent for the inviscid Burgers equation with and without shocks. Parallel scaling tests on up to 128K cores indicate that run-time improvements over serial time-stepping strategies are possible when spatial parallelism alone saturates, and that scalability is robust for oscillatory solutions which change on the scale of the grid spacing.

97 MATHEMATICS AND COMPUTING↗

Deploy threading in Nalu solver stack

The goal of the ExaWind project is to enable predictive simulations of wind farms composed of many MW-scale turbines situated in complex terrain. Predictive simulations will require computational fluid dynamics (CFD) simulations for which the mesh resolves the geometry of the turbines, and captures the rotation and large deflections of blades. Whereas such simulations for a single turbine are arguably petascale class, multi-turbine wind farm simulations will require exascale-class resources. The primary code in the ExaWind project is Nalu, which is an unstructured-grid solver for the acousticallyincompressible Navier-Stokes equations, and mass continuity is maintained through pressure projection. The model consists of the mass-continuity Poisson-type equation for pressure and a momentum equation for the velocity. For such modeling approaches, simulation times are dominated by linear-system setup and solution for the continuity and momentum systems. For the ExaWind challenge problem, the moving meshes greatly affect overall solver costs as re-initialization of matrices and re-computation of preconditioners is required at every time step In this Milestone, we examine the effect of threading on the solver stack performance against flat-MPI results obtained from previous milestones using Haswell performance data full-turbine simulations. Whereas the momentum equations are solved only with the Trilinos solvers, we investigate two algebraic-multigrid preconditioners for the continuity equations: Trilinos/Muelu and HYPRE/BoomerAMG. These two packages embody smoothed-aggregation and classical Ruge-Stiiben AMG methods, respectively. In our FY18 Q2 report, we described our efforts to improve setup and solve of the continuity equations under flat-MPI parallelism. While significant improvement was demonstrated in the solve phase, setup times remained larger than expected. Starting with the optimized settings described in the Q2 report, we explore here simulation performance where OpenMP threading is employed in the solver stack. For Trilinos, threading is acheived through the Kokkos abstraction where, whereas HYPRE/BoomerAMG employs straight OpenMP. We examined results for our mid-resolution baseline turbine simulation configuration (229M DOF). Simulations on 2048 Haswell cores explored the effect of decreasing the number of MPI ranks while increasing the number of threads. Both HYPRE and Trilinos exhibited similar overal solution times, and both showed dramatic increases in simulation time in the shift from MPI ranks to OpenMP threads. This increase is attributed to the large amount of work per MPI rank starting at the single-thread configuration. Decreasing MPI ranks, while increasing threads, may be increasing simulation time due to thread synchronization and start-up overhead contributing to the latency and serial time in the model. These result showed that an MPI+OpenMP parallel decomposition will be more effective as the amount per MPI rank computation per MPI rank decreases and the communication latency increases. This idea was demonstrated in a strong scaling study of our low-resolution baseline model (29M DOF) with the Trilinos-HYPRE configuration. While MPI-only results showed scaling improvement out to about 1536 cores, engaging threading carried scaling improvements out to 4128 cores — roughly 7000 DOF per core. This is an important result as improved strong scaling is needed for simulations to be executed over sufficiently long simulated durations (i.e., for many timesteps). In addition to threading work described above, the team examined solver-performance improvements by exploring communication-overhead in the HYPRE-GMRES implementation through a communicationoptimal- GMRE algorithm (CO-GMRES), and offloading compute-intensive solver actions to GPUs. To those ends, a HYPRE mini-app was allow us to easily test different solver approaches and HYPRE parameter settings without running the entire Nalu code. With GPU acceleration on the Summitdev supercomputer, a 20x speedup was achieved for the overall preconditioner and solver execution time for the mini-app. A study on Haswell processors showed that CO-GMRES provides benefits as one increases MPI ranks.

17 WIND ENERGY↗

An Algebraic Multigrid Solver for Navier-Stokes Problems in the Discrete Second-Order Approximation

An algebraic multigrid scheme is presented for solving the discrete Navier-Stokes equations to second-order accuracy using the defect-correction method. Solutions have been obtained for problems involving both structured and unstructured meshes, with the resolution and resolution grading controlled by global and local mesh refinements. The solver is efficient and robust to the extent that no underrelaxation of variables has been required to ensure convergence, but rates of convergence can be improved with small amounts of underrelaxation of the velocity-pressure coupling. Provided that the computational mesh can resolve the flow field, convergence characteristics are almost mesh independent. Rates of convergence actually improve with refinement, asymptotically approaching mesh independent values. For extremely coarse meshes where dispersive truncation errors would be expected to prevent convergence (or even induce divergence), solutions can still be obtained by using explicit underrelaxation in the iterative cycle.

Webster, R.↗

A Cartesian grid embedded boundary method for solving the Poisson and heat equations with discontinuous coefficients in three dimensions

We present a method for solving Poisson and heat equations with discontinuous coefficients in two- and three-dimensions. It uses a Cartesian cut-cell/embedded boundary method to represent the interface between materials, as described in Johansen and Colella (1998). Matching conditions across the interface are enforced using an approximation to fluxes at the boundary. Overall second order accuracy is achieved, as indicated by an array of tests using non-trivial interface geometries. Both the elliptic and heat solvers are shown to remain stable and efficient for material coefficient contrasts up to 10{sup 6}, thanks in part to the use of geometric multigrid. A test of accuracy when adaptive mesh refinement capabilities are utilized is also performed. An example problem relevant to nuclear reactor core simulation is presented, demonstrating the ability of the method to solve problems with realistic physical parameters.

97 MATHEMATICS AND COMPUTING↗

Discontinuous diffusion synthetic acceleration for S{sub n} transport on 2D arbitrary polygonal meshes

In this paper, a Diffusion Synthetic Acceleration (DSA) technique applied to the S{sub n} radiation transport equation is developed using Piece-Wise Linear Discontinuous (PWLD) finite elements on arbitrary polygonal grids. The discretization of the DSA equations employs an Interior Penalty technique, as is classically done for the stabilization of the diffusion equation using discontinuous finite element approximations. The penalty method yields a system of linear equations that is Symmetric Positive Definite (SPD). Thus, solution techniques such as Preconditioned Conjugate Gradient (PCG) can be effectively employed. Algebraic MultiGrid (AMG) and Symmetric Gauss–Seidel (SGS) are employed as conjugate gradient preconditioners for the DSA system. AMG is shown to be significantly more efficient than SGS. Fourier analyses are carried out and we show that this discontinuous finite element DSA scheme is always stable and effective at reducing the spectral radius for iterative transport solves, even for grids with high-aspect ratio cells. Numerical results are presented for different grid types: quadrilateral, hexagonal, and polygonal grids as well as grids with local mesh adaptivity.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Petascale solvers for anisotropic PDEs in atmospheric modelling on GPU clusters

Memory bound applications such as solvers for large sparse systems of equations remain a challenge for GPUs. Fast solvers should be based on numerically efficient algorithms and implemented such that global memory access is minimised. To solve systems with trillions ( O ( 10 12 ) ) unknowns the code has to make efficient use of several million individual processor cores on large GPU clusters. We describe the multi-GPU implementation of two algorithmically optimal iterative solvers for anisotropic PDEs which are encountered in (semi-) implicit time stepping procedures in atmospheric modelling. In this application the condition number is large but independent of the grid resolution and both methods are asymptotically optimal, albeit with different absolute performance. In particular, an important constant in the discretisation is the CFL number; only the multigrid solver is robust to changes in this constant. We parallelise the solvers and adapt them to the specific features of GPU architectures, paying particular attention to efficient global memory access. We achieve a performance of up to 0.78 PFLOPs when solving an equation with 0.55 · 10 12 unknowns on 16384 GPUs; this corresponds to about 3% of the theoretical peak performance of the machine and we use more than 40% of the peak memory bandwidth with a Conjugate Gradient (CG) solver. Although the other solver, a geometric multigrid algorithm, has a slightly worse performance in terms of FLOPs per second, overall it is faster as it needs less iterations to converge; the multigrid algorithm can solve a linear PDE with half a trillion unknowns in about one second.

Computer Science↗

A Pressure Based Multigrid Procedure for the Navier-Stokes Equations on Unstructured Grids

We present details and performance of a pressure based multigrid solution procedure for the Navier-Stokes equations discretized on triangular grids. The discretization uses a control volume methodology, with linear inter-nodal variation of the flow variables. The use of the multigrid technique provides rapid and grid-independent rates of convergence. Three model driven cavity flows are computed, and the performance of the method at several grid densities and Reynolds numbers is reported. Representative flow fields characterizing the viscous eddies are also presented.

Jyotsna, R.↗

A Performance Model for Allocating the Parallelism in a Multigrid-in-Time Solver

The traditional way to numerically solve time-dependent problems is to sequentially march through time, solving for one time step and then the next. The parallelism in this approach is limited to the spatial dimension, which is quickly exhausted, causing the gain from using more processors to solve a problem to diminish. One approach to overcome this barrier is to use methods that are parallel in time. These methods have the potential to achieve dramatically better performance compared to time-stepping approaches, but achieving this performance requires carefully choosing the amount of parallelism devoted to space versus the amount devoted to time. Here, we present a performance model that, for a multigrid-in-time solver, makes the decision on when to switch to parallel-in-time and on how much parallelism to devote to space vs. time. In our experiments, the model selects the best parallel configuration in most of our test cases and a configuration close to the best one in all other cases.

97 MATHEMATICS AND COMPUTING↗

Scientific Data Compression for Large Scale Computational Fluid Dynamics (CFD) Simulations

This Cooperative Research and Development Agreement (CRADA) between Oak Ridge National Laboratory (ORNL) and General Electric (GE) investigated methods for reducing the size of large computational fluid dynamics (CFD) simulation datasets using scientific data compression techniques. The work focused on adapting the MultiGrid Adaptive Reduction of Data (MGARD) compression framework and integrating it with high-performance I/O and visualization tools used in CFD workflows. MGARD uses hierarchical multilevel decomposition to enable error-controlled compression of floating-point scientific data while preserving quantities of interest. During the project, MGARD compression was integrated with the ADIOS I/O framework and visualization tools such as ParaView to enable efficient storage, transfer, and analysis of simulation data. The collaboration also explored approaches for improving compression performance for CFD data defined on unstructured meshes. Results demonstrate that scientific data compression can significantly reduce storage requirements and improve data management for large-scale CFD simulations.

97 MATHEMATICS AND COMPUTING↗