Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Multigrid”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

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

At least 19 records
All sourcesNASA NTRSDOE OSTI
DOE OSTI2020

Reducing communication in algebraic multigrid with multi-step node aware communication

Algebraic multigrid (AMG) is often viewed as a scalable [Formula: see text] solver for sparse linear systems. Yet, AMG lacks parallel scalability due to increasingly large costs associated with communication, both in the initial construction of a multigrid hierarchy and in the iterative solve phase. This work introduces a parallel implementation of AMG that reduces the cost of communication, yielding improved parallel scalability. It is common in Message Passing Interface (MPI), particularly in the MPI-everywhere approach, to arrange inter-process communication, so that communication is transported regardless of the location of the send and receive processes. Performance tests show notable differences in the cost of intra- and internode communication, motivating a restructuring of communication. In this case, the communication schedule takes advantage of the less costly intra-node communication, reducing both the number and the size of internode messages. Node-centric communication extends to the range of components in both the setup and solve phase of AMG, yielding an increase in the weak and strong scaling of the entire method.

Computer Science↗
NASA NTRS1994

The algebraic multigrid projection for eigenvalue problems; backrotations and multigrid fixed points

The periods of the theorem for the algebraic multigrid projection (MGP) for eigenvalue problems, and of the multigrid fixed point theorem for multigrid cycles combining MGP with backrotations, are presented. The MGP and the backrotations are central eigenvector separation techniques for multigrid eigenvalue algorithms. They allow computation on coarse levels of eigenvalues of a given eigenvalue problem, and are efficient tools in the computation of eigenvectors.

Costiner, Sorin↗
NASA NTRS1999

Implicit and Multigrid Method for Ideal Multigrid Convergence: Direct Numerical Simulation of Separated Flow Around NACA 0012 Airfoil

Numerical investigation of flow separation over a NACA 0012 airfoil at large angles of attack has been carried out. The numerical calculation is performed by solving the full Navier-Stokes equations in generalized curvilinear coordinates. The second-order LU-SGS implicit scheme is applied for time integration. This scheme requires no tridiagonal inversion and is capable of being completely vectorized, provided the corresponding Jacobian matrices are properly selected. A fourth-order centered compact scheme is used for spatial derivatives. In order to reduce numerical oscillation, a sixth-order implicit filter is employed. Non-reflecting boundary conditions are imposed at the far-field and outlet boundaries to avoid possible non-physical wave reflection. Complex flow separation and vortex shedding phenomenon have been observed and discussed.

Liu, Chao-Qun↗
NASA NTRS1996

Multigrid Methods for Fully Implicit Oil Reservoir Simulation

In this paper we consider the simultaneous flow of oil and water in reservoir rock. This displacement process is modeled by two basic equations: the material balance or continuity equations and the equation of motion (Darcy's law). For the numerical solution of this system of nonlinear partial differential equations there are two approaches: the fully implicit or simultaneous solution method and the sequential solution method. In the sequential solution method the system of partial differential equations is manipulated to give an elliptic pressure equation and a hyperbolic (or parabolic) saturation equation. In the IMPES approach the pressure equation is first solved, using values for the saturation from the previous time level. Next the saturations are updated by some explicit time stepping method; this implies that the method is only conditionally stable. For the numerical solution of the linear, elliptic pressure equation multigrid methods have become an accepted technique. On the other hand, the fully implicit method is unconditionally stable, but it has the disadvantage that in every time step a large system of nonlinear algebraic equations has to be solved. The most time-consuming part of any fully implicit reservoir simulator is the solution of this large system of equations. Usually this is done by Newton's method. The resulting systems of linear equations are then either solved by a direct method or by some conjugate gradient type method. In this paper we consider the possibility of applying multigrid methods for the iterative solution of the systems of nonlinear equations. There are two ways of using multigrid for this job: either we use a nonlinear multigrid method or we use a linear multigrid method to deal with the linear systems that arise in Newton's method. So far only a few authors have reported on the use of multigrid methods for fully implicit simulations. Two-level FAS algorithm is presented for the black-oil equations, and linear multigrid for two-phase flow problems with strong heterogeneities and anisotropies is studied. Here we consider both possibilities. Moreover we present a novel way for constructing the coarse grid correction operator in linear multigrid algorithms. This approach has the advantage in that it preserves the sparsity pattern of the fine grid matrix and it can be extended to systems of equations in a straightforward manner. We compare the linear and nonlinear multigrid algorithms by means of a numerical experiment.

Molenaar, J.↗
NASA NTRS1999

Large-Scale Parallel Viscous Flow Computations using an Unstructured Multigrid Algorithm

The development and testing of a parallel unstructured agglomeration multigrid algorithm for steady-state aerodynamic flows is discussed. The agglomeration multigrid strategy uses a graph algorithm to construct the coarse multigrid levels from the given fine grid, similar to an algebraic multigrid approach, but operates directly on the non-linear system using the FAS (Full Approximation Scheme) approach. The scalability and convergence rate of the multigrid algorithm are examined on the SGI Origin 2000 and the Cray T3E. An argument is given which indicates that the asymptotic scalability of the multigrid algorithm should be similar to that of its underlying single grid smoothing scheme. For medium size problems involving several million grid points, near perfect scalability is obtained for the single grid algorithm, while only a slight drop-off in parallel efficiency is observed for the multigrid V- and W-cycles, using up to 128 processors on the SGI Origin 2000, and up to 512 processors on the Cray T3E. For a large problem using 25 million grid points, good scalability is observed for the multigrid algorithm using up to 1450 processors on a Cray T3E, even when the coarsest grid level contains fewer points than the total number of processors.

Mavriplis, Dimitri J.↗
NASA NTRS1989

Multigrid calculation of three-dimensional turbomachinery flows

Research was performed in the general area of computational aerodynamics, with particular emphasis on the development of efficient techniques for the solution of the Euler and Navier-Stokes equations for transonic flows through the complex blade passages associated with turbomachines. In particular, multigrid methods were developed, using both explicit and implicit time-stepping schemes as smoothing algorithms. The specific accomplishments of the research have included: (1) the development of an explicit multigrid method to solve the Euler equations for three-dimensional turbomachinery flows based upon the multigrid implementation of Jameson's explicit Runge-Kutta scheme (Jameson 1983); (2) the development of an implicit multigrid scheme for the three-dimensional Euler equations based upon lower-upper factorization; (3) the development of a multigrid scheme using a diagonalized alternating direction implicit (ADI) algorithm; (4) the extension of the diagonalized ADI multigrid method to solve the Euler equations of inviscid flow for three-dimensional turbomachinery flows; and also (5) the extension of the diagonalized ADI multigrid scheme to solve the Reynolds-averaged Navier-Stokes equations for two-dimensional turbomachinery flows.

Caughey, David A.↗
NASA NTRS1993

The multigrid preconditioned conjugate gradient method

A multigrid preconditioned conjugate gradient method (MGCG method), which uses the multigrid method as a preconditioner of the PCG method, is proposed. The multigrid method has inherent high parallelism and improves convergence of long wavelength components, which is important in iterative methods. By using this method as a preconditioner of the PCG method, an efficient method with high parallelism and fast convergence is obtained. First, it is considered a necessary condition of the multigrid preconditioner in order to satisfy requirements of a preconditioner of the PCG method. Next numerical experiments show a behavior of the MGCG method and that the MGCG method is superior to both the ICCG method and the multigrid method in point of fast convergence and high parallelism. This fast convergence is understood in terms of the eigenvalue analysis of the preconditioned matrix. From this observation of the multigrid preconditioner, it is realized that the MGCG method converges in very few iterations and the multigrid preconditioner is a desirable preconditioner of the conjugate gradient method.

Tatebe, Osamu↗
NASA NTRS1995

Convergence acceleration of the Proteus computer code with multigrid methods

This report presents the results of a study to implement convergence acceleration techniques based on the multigrid concept in the two-dimensional and three-dimensional versions of the Proteus computer code. The first section presents a review of the relevant literature on the implementation of the multigrid methods in computer codes for compressible flow analysis. The next two sections present detailed stability analysis of numerical schemes for solving the Euler and Navier-Stokes equations, based on conventional von Neumann analysis and the bi-grid analysis, respectively. The next section presents details of the computational method used in the Proteus computer code. Finally, the multigrid implementation and applications to several two-dimensional and three-dimensional test problems are presented. The results of the present study show that the multigrid method always leads to a reduction in the number of iterations (or time steps) required for convergence. However, there is an overhead associated with the use of multigrid acceleration. The overhead is higher in 2-D problems than in 3-D problems, thus overall multigrid savings in CPU time are in general better in the latter. Savings of about 40-50 percent are typical in 3-D problems, but they are about 20-30 percent in large 2-D problems. The present multigrid method is applicable to steady-state problems and is therefore ineffective in problems with inherently unstable solutions.

Demuren, A. O.↗
NASA NTRS2004

Agglomeration Multigrid for an Unstructured-Grid Flow Solver

An agglomeration multigrid scheme has been implemented into the sequential version of the NASA code USM3Dns, tetrahedral cell-centered finite volume Euler/Navier-Stokes flow solver. Efficiency and robustness of the multigrid-enhanced flow solver have been assessed for three configurations assuming an inviscid flow and one configuration assuming a viscous fully turbulent flow. The inviscid studies include a transonic flow over the ONERA M6 wing and a generic business jet with flow-through nacelles and a low subsonic flow over a high-lift trapezoidal wing. The viscous case includes a fully turbulent flow over the RAE 2822 rectangular wing. The multigrid solutions converged with 12%-33% of the Central Processing Unit (CPU) time required by the solutions obtained without multigrid. For all of the inviscid cases, multigrid in conjunction with an explicit time-stepping scheme performed the best with regard to the run time memory and CPU time requirements. However, for the viscous case multigrid had to be used with an implicit backward Euler time-stepping scheme that increased the run time memory requirement by 22% as compared to the run made without multigrid.

Frink, Neal↗
DOE OSTI2022

Parallel Multigrid in Time and Space for Extreme-Scale Computational Science: Chaotic and Hyperbolic Problems

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 stateof-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, we take inspiration from the Least Squares Shadowing (LSS by Wang) approach for solving chaotic problems. Here, an optimization approach is able to find “well-conditioned” shadow trajectories/solutions to the original “ill-conditioned” chaotic problem. Thus, the new multigrid methods researched here also arise in an optimization context.

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 OSTI2023

Parallel Algebraic Multigrid for Fusion and Higher-Order PDEs

Multigrid methods play a key role in large-scale scientific simulation because they are among the fastest and most scalable approaches for solving the underlying sparse linear systems of equations that arise from a wide array of Partial Differential Equation (PDE) discretizations. Algebraic multigrid (AMG) is a special type of multigrid method that depends only on the description of the linear system, giving it better portability and broader applicability than geometric multigrid, as it requires no explicit knowledge of the problem geometry. Even though these methods are widely used today, there are still applications where further development is needed. In this report, we focus on PDEs with higher-order terms (e.g., fourth order), concentrating on a PDE that arises in tokamak edge plasma simulations (a tokamak is a machine that confines a plasma using magnetic fields and is believed to be the leading plasma confinement concept for future fusion power plants). General multigrid relaxes a linear system on coarser grids and reverses this process with interpolation, but standard AMG methods struggle with the aforementioned higher-order PDEs. We investigate cyclic coarsening and interpolation heuristics, as well as new iterative approximation methods of refining the solution at each grid to improve the existing multigrid approach. To this end, we ensure that these techniques are transferable to a parallelized setting with LLNL’s supercomputers.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1996

Multiple Coarse Grid Multigrid Methods for Solving Elliptic Problems

In this paper we describe some classes of multigrid methods for solving large linear systems arising in the solution by finite difference methods of certain boundary value problems involving Poisson's equation on rectangular regions. If parallel computing systems are used, then with standard multigrid methods many of the processors will be idle when one is working at the coarsest grid levels. We describe the use of Multiple Coarse Grid MultiGrid (MCGMG) methods. Here one first constructs a periodic set of equations corresponding to the given system. One then constructs a set of coarse grids such that for each grid corresponding to the grid size h there are four grids corresponding to the grid size 2*h. Multigrid operations such as restriction of residuals and interpolation of corrections are done in parallel at each grid level. For suitable choices of the multigrid operators the MCGMG method is equivalent to the Parallel Superconvergent MultiGrid (PSMG) method of Frederickson and McBryan. The convergence properties of MCGMG methods can be accurately analyzed using spectral methods.

Xiao, Shengyou↗
NASA NTRS2011

A Critical Study of Agglomerated Multigrid Methods for Diffusion

Agglomerated multigrid techniques used in unstructured-grid methods are studied critically for a model problem representative of laminar diffusion in the incompressible limit. The studied target-grid discretizations and discretizations used on agglomerated grids are typical of current node-centered formulations. Agglomerated multigrid convergence rates are presented using a range of two- and three-dimensional randomly perturbed unstructured grids for simple geometries with isotropic and stretched grids. Two agglomeration techniques are used within an overall topology-preserving agglomeration framework. The results show that multigrid with an inconsistent coarse-grid scheme using only the edge terms (also referred to in the literature as a thin-layer formulation) provides considerable speedup over single-grid methods but its convergence deteriorates on finer grids. Multigrid with a Galerkin coarse-grid discretization using piecewise-constant prolongation and a heuristic correction factor is slower and also grid-dependent. In contrast, grid-independent convergence rates are demonstrated for multigrid with consistent coarse-grid discretizations. Convergence rates of multigrid cycles are verified with quantitative analysis methods in which parts of the two-grid cycle are replaced by their idealized counterparts.

Nishikawa, Hiroaki↗
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 OSTI2019

Efficient Operator-Coarsening Multigrid Schemes for Local Discontinuous Galerkin Methods

An efficient hp-multigrid scheme is presented for local discontinuous Galerkin (LDG) discretizations of elliptic problems, formulated around the idea of separately coarsening the underlying discrete gradient and divergence operators. We show that traditional multigrid coarsening of the primal formulation leads to poor and suboptimal multigrid performance, whereas coarsening of the flux formulation leads to essentially optimal convergence and is equivalent to a purely geometric multigrid method. The resulting operator-coarsening schemes do not require the entire mesh hierarchy to be explicitly built, thereby obviating the need to compute quadrature rules, lifting operators, and other mesh-related quantities on coarse meshes. We show that good multigrid convergence rates are achieved in a variety of numerical tests on two-dimensional and three-dimensional uniform and adaptive Cartesian grids, as well as for curved domains using implicitly defined meshes and for multiphase elliptic interface problems with complex geometry. Extensions, e.g., to non-LDG discretizations and fully unstructured meshes, are briefly discussed.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

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 parallel-in-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 further researched and improved (including with a new relaxation method inspired by on Least Squares Shadowing (LSS)) and explored for more complicated problems.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1981

Multigrid solvers on parallel computers

Massively parallel computers, as considered in this investigation, are not yet available. However, a large-scale parallel computer cannot usefully be designed before the hypothetical algorithms which will employ it are studied. Most of the studies of parallel partial differential equations (PDE) solvers are based on solution techniques much slower (on sequential machines) than multigrid methods. Multigrid methods are highly parallelizable. Each of their processes can simultaneously be performed at all grid points. The present investigation is concerned with a preliminary exploration of the potential of multigrid, or, more generally, Multi-Level Adaptive Techniques (MLAT) on computers with many processors. Basic processes are considered, taking into account coarse-grid approximation, relaxation, coarse-grid corrections, full multigrid algorithms, nonlinear problems and eigenvalue problems, fine-to-coarse correction, and chains of problems. Details of parallel multigrid processing are also examined.

Brandt, A.↗