Search NASA⌕ Search

SEARCH · Search NASA

Results for “multigrid solvers”

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 271 records · Page 15

Smoothed aggregation adaptive spectral element-based algebraic multigrid

SAAMGE provides parallel methods for building multilevel hierarchies and solvers that can be used for elliptic equations with highly heterogeneous coefficients. Additionally, hierarchy adaptation is implemented allowing solving multiple problems with close coefficients without rebuilding the hierarchy.

Source record↗

Euler solutions using an implicit multigrid technique

A coarse-grid correction algorithm has been implemented into an implicit upwind Euler solver and tested for transonic airfoil problems. The Euler solver uses split-flux formulation and penta-diagonal scalar equations, respectively, for the explicit and implicit operators. The multigrid sequence starts at the fine grid level, then steps down to each coarse grid level to smooth error components using implicit operators. Estimate of residuals can be obtained by two approaches, which differ in the level where the residuals are collected. Both approaches will lead to a work reduction factor of 12 for a Mach 0.75 flow at 2 degrees incidence on a 65x26 grid. The work reduction factor is found to increase proportional to the number of grid levels.

Li, Chien-Peng↗

Implementation and Optimization of miniGMG - a Compact Geometric Multigrid Benchmark

Multigrid methods are widely used to accelerate the convergence of iterative solvers for linear systems used in a number of different application areas. In this report, we describe miniGMG, our compact geometric multigrid benchmark designed to proxy the multigrid solves found in AMR applications. We explore optimization techniques for geometric multigrid on existing and emerging multicore systems including the Opteron-based Cray XE6, Intel Sandy Bridge and Nehalem-based Infiniband clusters, as well as manycore-based architectures including NVIDIA's Fermi and Kepler GPUs and Intel's Knights Corner (KNC) co-processor. This report examines a variety of novel techniques including communication-aggregation, threaded wavefront-based DRAM communication-avoiding, dynamic threading decisions, SIMDization, and fusion of operators. We quantify performance through each phase of the V-cycle for both single-node and distributed-memory experiments and provide detailed analysis for each class of optimization. Results show our optimizations yield significant speedups across a variety of subdomain sizes while simultaneously demonstrating the potential of multi- and manycore processors to dramatically accelerate single-node performance. However, our analysis also indicates that improvements in networks and communication will be essential to reap the potential of manycore processors in large-scale multigrid calculations.

97 MATHEMATICS AND COMPUTING↗

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↗

Robust parallel iterative solvers for linear and least-squares problems (Final Technical Report)

The primary goal of this project is to study and develop robust iterative methods for solving linear systems of equations and least squares systems. The focus of the Minnesota team is on algorithms development, robustness issues, and on tests and validation of the methods on realistic problems. 1. The project begun with an investigation on how to practically update a preconditioner obtained from an ILU-type factorization, when the coefficient matrix changes. 2. We investigated strategies to improve robustness in parallel preconditioners in a specific case of a PDE with discontinuous coefficients. 3. We explored ways to adapt standard preconditioners for solving linear systems arising from the Helmholtz equation. These are often difficult linear systems to solve by iterative methods. 4. We have also worked on purely theoretical issues related to the analysis of Krylov subspace methods for linear systems. 5. We developed an effective strategy for performing ILU factorizations for the case when the matrix is highly indefinite. The strategy uses shifting in some optimal way. The method was extended to the solution of Helmholtz equations by using complex shifts, yielding very good results in many cases. 6. We addressed the difficult problem of preconditioning sparse systems of equations on GPUs. 7. A by-product of the above work is a software package consisting of an iterative solver library for GPUs based on CUDA. This was made publicly available. It was the first such library that offers complete iterative solvers for GPUs. 8. We considered another form of ILU which blends coarsening techniques from Multigrid with algebraic multilevel methods. 9. We have released a new version on our parallel solver - called pARMS [new version is version 3]. As part of this we have tested the code in complex settings - including the solution of Maxwell and Helmholtz equations and for a problem of crystal growth.10. As an application of polynomial preconditioning we considered the problem of evaluating f(A)v which arises in statistical sampling. 11. As an application to the methods we developed, we tackled the problem of computing the diagonal of the inverse of a matrix. This arises in statistical applications as well as in many applications in physics. We explored probing methods as well as domain-decomposition type methods. 12. A collaboration with researchers from Toulouse, France, considered the important problem of computing the Schur complement in a domain-decomposition approach. 13. We explored new ways of preconditioning linear systems, based on low-rank approximations.

97 MATHEMATICS AND COMPUTING↗

Aspects of Solvers for Large-Scale Coupled Problems in Porous Media

This report summarizes solution strategies for discrete systems occurring in the simulation of processes in the subsurface. The focus is on scalable solvers for large and coupled systems. The goal of this work is to enable researchers to select suitable algorithms and parameter settings to efficiently solve their problems. The work provides an overview of existing methods, highlighting their features, potential, and also frequent pitfalls. Numerical examples are provided for single phase flow, density driven flow and poroelasticity.Aspects of multiphase flow are discussed briefly; a detailed discussion of reactive transport is beyond the scope of the article. Future trends are discussed.

97 MATHEMATICS AND COMPUTING↗

Multigrid solution of inviscid transonic flow through rotating blade passages

A fast Euler solver for three dimensional inviscid transonic flow in rotating domains is described. The time dependent Euler equations are discretized spatially with finite volumes, and are advanced temporally with a multiple stage time stepping scheme. A dramatic increase in the rate of convergence for steady solutions is achieved with a multigrid algorithm that employs the multistage scheme as its smoothing procedure. The effectiveness of the multistage scheme as a multigrid driver is enhanced by the utilization of analytically determined combinations of the governing parameters.

Smith, Wayne A.↗

Reducing Communication in Algebraic Multigrid Using Additive Variants

Algebraic multigrid (AMG) has proven to be an effective scalable solver on many high performance computers. However, its increasing communication complexity on coarser levels has shown to seriously impact its performance on computers with high communication cost. Moreover, additive AMG variants provide not only increased parallelism as well as decreased numbers of messages per cycle but also generally exhibit slower convergence. Here we present various new additive variants with convergence rates that are significantly improved compared to the classical additive algebraic multigrid method and investigate their potential for decreased communication, and improved communication-computation overlap, features that are essential for good performance on future exascale architectures.

97 MATHEMATICS AND COMPUTING↗

A matrix-free approach for finite-strain hyperelastic problems using geometric multigrid

This paper investigates matrix-free algorithms for problems in quasi-static finite-strain hyperelasticity. Iterative solvers with matrix-free operator evaluation have emerged as an attractive alternative to sparse matrices in the fluid dynamics and wave propagation communities because they significantly reduce the memory traffic, the limiting factor in classical finite element solvers. Specifically, we study different matrix-free realizations of the finite element tangent operator and determine whether generalized methods of incorporating complex constitutive behavior might be feasible. Furthermore, in order to improve the convergence behavior of iterative solvers, we also propose a method by which to construct level tangent operators and employ them to define a geometric multigrid preconditioner. Additionally, the performance of the matrix-free operator and the geometric multigrid preconditioner is compared to the matrix-based implementation with an algebraic multigrid (AMG) preconditioner on a single node for a representative numerical example of a heterogeneous hyperelastic material in two and three dimensions. We find that matrix-free methods for finite-strain solid mechanics are very promising, outperforming linear matrix-based schemes by two to five times, and that it is possible to develop numerically efficient implementations that are independent of the hyperelastic constitutive law.

42 ENGINEERING↗

FFT, FMM, and multigrid on the road to exascale: Performance challenges and opportunities

FFT, FMM, and multigrid methods are widely used fast and highly scalable solvers for elliptic PDEs. However, emerging large-scale computing systems are introducing challenges in comparison to current petascale computers. Recent efforts (Dongarra et al. 2011) have identified several constraints in the design of exascale software that include massive concurrency, resilience management, exploiting the high performance of heterogeneous systems, energy efficiency, and utilizing the deeper and more complex memory hierarchy expected at exascale. In this paper, we perform a model-based comparison of the FFT, FMM, and multigrid methods in the context of these projected constraints. Finally, we use performance models to offer predictions about the expected performance on upcoming exascale system configurations based on current technology trends.

97 MATHEMATICS AND COMPUTING↗

Performance Models for the Spike Banded Linear System Solver

With availability of large-scale parallel platforms comprised of tens-of-thousands of processors and beyond, there is significant impetus for the development of scalable parallel sparse linear system solvers and preconditioners. An integral part of this design process is the development of performance models capable of predicting performance and providing accurate cost models for the solvers and preconditioners. There has been some work in the past on characterizing performance of the iterative solvers themselves. In this paper, we investigate the problem of characterizing performance and scalability of banded preconditioners. Recent work has demonstrated the superior convergence properties and robustness of banded preconditioners, compared to state-of-the-art ILU family of preconditioners as well as algebraic multigrid preconditioners. Furthermore, when used in conjunction with efficient banded solvers, banded preconditioners are capable of significantly faster time-to-solution. Our banded solver, the Truncated Spike algorithm is specifically designed for parallel performance and tolerance to deep memory hierarchies. Its regular structure is also highly amenable to accurate performance characterization. Using these characteristics, we derive the following results in this paper: (i) we develop parallel formulations of the Truncated Spike solver, (ii) we develop a highly accurate pseudo-analytical parallel performance model for our solver, (iii) we show excellent predication capabilities of our model – based on which we argue the high scalability of our solver. Our pseudo-analytical performance model is based on analytical performance characterization of each phase of our solver. These analytical models are then parameterized using actual runtime information on target platforms. An important consequence of our performance models is that they reveal underlying performance bottlenecks in both serial and parallel formulations. All of our results are validated on diverse heterogeneous multiclusters – platforms for which performance prediction is particularly challenging. Finally, we provide predict the scalability of the Spike algorithm using up to 65,536 cores with our model. In this paper we extend the results presented in the Ninth International Symposium on Parallel and Distributed Computing.

Manguoglu, Murat↗

Multigrid convergence of an implicit symmetric relaxation scheme

Multigrid has been applied to an existing three-dimensional compressible Euler solver to accelerate the convergence of the implicit symmetric relaxation scheme. This lower-upper symmetric Gauss-Seidel implicit scheme is shown to be an effective multigrid driver in three-dimensions. A grid refinement study is performed including the effects of large cell aspect ratio meshes. Performance figures of the present multigrid code on Cray computers including the new C90 are presented. A reduction of three orders of of magnitude in the residual for a three-dimensional transonic inviscid flow using 920K grid points is obtained in less than 4 minutes on a Cray C90.

Yoon, Seokkwan↗

A scalable multidimensional fully implicit solver for Hall magnetohydrodynamics

We propose an optimally performant fully implicit algorithm for the Hall magnetohydrodynamics (HMHD) equations based on multigrid-preconditioned Jacobian-free Newton-Krylov methods. HMHD is a challenging system to solve numerically because it supports stiff fast dispersive waves. The preconditioner is formulated using an operator-split approximate block factorization (Schur complement), informed by physics insight. We use a vector-potential formulation (instead of a magnetic field one) to allow a clean segregation of the problematic $\nabla$ x $\nabla$ x operator in the electron Ohm's law subsystem. This segregation allows the formulation of an effective damped block-Jacobi smoother for multigrid. We demonstrate by analysis that our proposed block-Jacobi iteration is convergent and has the smoothing property. The resulting HMHD solver is verified linearly with wave propagation examples, and nonlinearly with the GEM challenge reconnection problem by comparison against another HMHD code. We demonstrate the excellent algorithmic and parallel performance of the algorithm up to 16384 MPI tasks in two dimensions.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Multigrid convergence of an implicit symmetric relaxation scheme

The multigrid method has been applied to an existing three-dimensional compressible Euler solver to accelerate the convergence of the implicit symmetric relaxation scheme. This lower-upper symmetric Gauss-Seidel implicit scheme is shown to be an effective multigrid driver in three dimensions. A grid refinement study is performed including the effects of large cell aspect ratio meshes. Performance figures of the present multigrid code on Cray computers including the new C90 are presented. A reduction of three orders of magnitude in the residual for a three-dimensional transonic inviscid flow using 920 k grid points is obtained in less than 4 min on a Cray C90.

Yoon, Seokkwan↗

Block-Iterative Methods for 3D Constant-Coefficient Stencils on GPUs and Multicore CPUs

Block iterative methods are extremely important as smoothers for multigrid methods, as preconditioners for Krylov methods, and as solvers for diagonally dominant linear systems. Developing robust and efficient smoother algorithms suitable for current and evolving GPU and multicore CPU systems is a significant challenge. We address this issue in the case of constant-coefficient stencils arising in the solution of elliptic partial differential equations on structured 3D uniform and adaptively refined block structured grids. Robust, highly parallel implementations of block Jacobi and chaotic block Gauss-Seidel algorithms with exact inversion of the blocks are developed using different parallelization techniques. Experimental results for NVIDIA Fermi/Kepler GPUs and AMD multicore systems are presented.

97 MATHEMATICS AND COMPUTING↗

Adjoint Algorithm for CAD-Based Shape Optimization Using a Cartesian Method

Adjoint solutions of the governing flow equations are becoming increasingly important for the development of efficient analysis and optimization algorithms. A well-known use of the adjoint method is gradient-based shape optimization. Given an objective function that defines some measure of performance, such as the lift and drag functionals, its gradient is computed at a cost that is essentially independent of the number of design variables (geometric parameters that control the shape). More recently, emerging adjoint applications focus on the analysis problem, where the adjoint solution is used to drive mesh adaptation, as well as to provide estimates of functional error bounds and corrections. The attractive feature of this approach is that the mesh-adaptation procedure targets a specific functional, thereby localizing the mesh refinement and reducing computational cost. Our focus is on the development of adjoint-based optimization techniques for a Cartesian method with embedded boundaries.12 In contrast t o implementations on structured and unstructured grids, Cartesian methods decouple the surface discretization from the volume mesh. This feature makes Cartesian methods well suited for the automated analysis of complex geometry problems, and consequently a promising approach to aerodynamic optimization. Melvin et developed an adjoint formulation for the TRANAIR code, which is based on the full-potential equation with viscous corrections. More recently, Dadone and Grossman presented an adjoint formulation for the Euler equations. In both approaches, a boundary condition is introduced to approximate the effects of the evolving surface shape that results in accurate gradient computation. Central to automated shape optimization algorithms is the issue of geometry modeling and control. The need to optimize complex, "real-life" geometry provides a strong incentive for the use of parametric-CAD systems within the optimization procedure. In previous work, we presented an effective optimization framework that incorporates a direct-CAD interface. In this work, we enhance the capabilities of this framework with efficient gradient computations using the discrete adjoint method. We present details of the adjoint numerical implementation, which reuses the domain decomposition, multigrid, and time-marching schemes of the flow solver. Furthermore, we explain and demonstrate the use of CAD in conjunction with the Cartesian adjoint approach. The final paper will contain a number of complex geometry, industrially relevant examples with many design variables to demonstrate the effectiveness of the adjoint method on Cartesian meshes.

Nemec, Marian↗

Final Report on Subcontract B591217: Multigrid Methods for Systems of PDEs

Progress is summarized in the following areas of study: (1) Compatible relaxation; (2) Improving aggregation-based MG solver performance - variable cycle; (3) First Order System Least Squares (FOSLS) for LQCD; (4) Auxiliary space preconditioners; (5) Bootstrap algebraic multigrid; and (6) Practical applications of AMG and fast auxiliary space preconditioners.

97 MATHEMATICS AND COMPUTING↗

Scalable smoothing strategies for a geometric multigrid method for the immersed boundary equations

The immersed boundary (IB) method is a widely used approach to simulating fluid-structure interaction (FSI). Although explicit versions of the IB method can suffer from severe time step size restrictions, these methods remain popular because of their simplicity and generality. In prior work (Guy et al., Adv Comput Math, 2015), some of us developed a geometric multigrid preconditioner for a stable semi-implicit IB method under Stokes flow conditions; however, this solver methodology used a Vanka-type smoother that presented limited opportunities for parallelization. This work extends this Stokes-IB solver methodology by developing smoothing techniques that are suitable for parallel implementation. Specifically, we demonstrate that an additive version of the Vanka smoother can yield an effective multigrid preconditioner for the Stokes-IB equations, and we introduce an efficient Schur complement-based smoother that is also shown to be effective for the Stokes-IB equations. We investigate the performance of these solvers for a broad range of material stiffnesses, both for Stokes flows and flows at nonzero Reynolds numbers, and for thick and thin structural models. We show here that linear solver performance degrades with increasing Reynolds number and material stiffness, especially for thin interface cases. Nonetheless, the proposed approaches promise to yield effective solution algorithms, especially at lower Reynolds numbers and at modest-to-high elastic stiffnesses.

97 MATHEMATICS AND COMPUTING↗