Search NASA⌕ Search

Engineering topics

Falgout, Robert D.

Publications and source records attributed to Falgout, Robert D..

At least 19 records

Multigrid Reduction in Time for Chaotic Dynamical Systems

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

97 MATHEMATICS AND COMPUTING↗

Fast Multigrid Reduction-in-Time for Advection via Modified Semi-Lagrangian Coarse-Grid Operators

Many iterative parallel-in-time algorithms have been shown to be highly efficient for diffusion-dominated partial differential equations (PDEs) but are inefficient or even divergent when applied to advection-dominated PDEs. We consider the application of the multigrid reduction-in-time (MGRIT) algorithm to linear advection PDEs. Here, the key to efficient time integration with this method is using a coarse-grid operator that provides a sufficiently accurate approximation to the so-called ideal coarse-grid operator. For certain classes of semi-Lagrangian discretizations, we present a novel semi-Lagrangian-based coarse-grid operator that leads to fast and scalable multilevel time integration of linear advection PDEs. The coarse-grid operator is composed of a semi-Lagrangian discretization followed by a correction term, with the correction designed so that the leading-order truncation error of the composite operator is approximately equal to that of the ideal coarse-grid operator. Parallel results show substantial speed-ups over sequential time integration for variable-wave-speed advection problems in one and two spatial dimensions, and using high-order discretizations up to order five. The proposed approach establishes the first practical method that provides small and scalable MGRIT iteration counts for advection problems.

97 MATHEMATICS AND COMPUTING↗

A New Semistructured Algebraic Multigrid Method

Multigrid methods are well suited to large massively parallel computer architectures because they are mathematically optimal and display good parallelization properties. Since current architecture trends are favoring regular compute patterns to achieve high performance, the ability to express structure has become much more important. The hypre software library provides high-performance multigrid preconditioners and solvers through conceptual interfaces, including a semistructured interface that describes matrices primarily in terms of stencils and logically structured grids. This paper presents a new semistructured algebraic multigrid (SSAMG) method built on this interface. The numerical convergence and performance of a CPU implementation of this method are evaluated for a set of semistructured problems. In conclusion, SSAMG achieves significantly better setup times than hypre’s unstructured AMG solvers and comparable convergence. In addition, the new method is capable of solving more complex problems than hypre’s structured solvers.

97 MATHEMATICS AND COMPUTING↗

Parallel Time Integration: An Approaching Paradigm Shift for Scientific Computing

This note argues that parallel-in-time methods will be necessary for doing high-fidelity time-dependent simulations in the future. A “proof” is given to support the argument and to provide a framework for debate. The effect of a parallel-in-time paradigm on scientific computing practice is also discussed.

97 MATHEMATICS AND COMPUTING↗

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↗

Time-periodic steady-state solution of fluid-structure interaction and cardiac flow problems through multigrid-reduction-in-time

In this study, a time-periodic MGRIT algorithm is proposed as a means to reduce the time-to-solution of numerical algorithms by exploiting the time periodicity inherent to many applications in science and engineering. The time-periodic MGRIT algorithm is applied to a variety of linear and nonlinear single- and multiphysics problems that are periodic-in-time. It is demonstrated that the proposed parallel-in-time algorithm can obtain the same time-periodic steady-state solution as sequential time-stepping. It is shown that the required number of MGRIT iterations can be estimated a priori and that the new MGRIT variant can significantly and consistently reduce the time-to-solution compared to sequential time-stepping, irrespective of the number of dimensions, linear or nonlinear PDE models, single-physics or coupled problems and the employed computing resources. The numerical experiments demonstrate that the time-periodic MGRIT algorithm enables a greater level of parallelism yielding faster turnaround, and thus, facilitating more complex and more realistic problems to be solved.

97 MATHEMATICS AND COMPUTING↗

Applying Time-Parallelization to Turbulent Flows

Parallelization of the temporal domain is explored for the solution of turbulent flows. Multigrid reduction-in-time (MGRIT) is used to advance the large-scale fluid dynamics in time sequentially on the coarsest space-time grid but propagate the information in time parallel on all other levels. The goal of this process is to accurately and efficiently resolve the coarse-scale turbulence structure and use that to drive the fine-scales of the turbulent flow. The extra forcing from nonlinear multigrid facilitates the coupling and interaction between fine and coarse scales, through which the multiscale nonlinear physics is properly captured. Adaptive mesh refinement is employed to finely resolve only the regions with strong gradients, which provides further computational efficiency. The underlying computational fluid dynamics solver is a fourth-order finite-volume scheme with the standard 4-stage Runge-Kutta method. An advanced approach is devised and implemented to enable MGRIT to solve highly turbulent flows successfully. Furthermore, the method is applied to solve a Taylor-Green vortex problem and a doubleshear-layer turbulent mixing flow. Results are promising, validating that MGRIT with the filtering approach has the potential to efficiently solve general turbulent flows.

Computational Fluid Dynamics↗

Porting hypre to heterogeneous computer architectures: Strategies and experiences

We report that linear systems are occurring in many applications, and solving them can take a large amount of the total simulation time. The high performance library hypre provides a variety of interfaces and linear solvers, including various multigrid methods, that have achieved good scalability on a variety of homogeneous parallel computer architectures. Heterogeneous architectures with nodes that have both CPUs and accelerators provide new challenges, since they require more fine-grained parallelism and reduced data movement between different memories on a single node as well as across nodes. We will discuss our experiences and strategies to port hypre to heterogeneous computers with accelerators, including the design of a new memory model, the use of abstractions, the BoxLoop macros in the structured and semi-structured interfaces, and the restructuring of algebraic multigrid (AMG) into modular components. We present numerical experiments comparing CPU and GPU performance for several test problems.

97 MATHEMATICS AND COMPUTING↗

Optimizing multigrid reduction-in-time and Parareal coarse-grid operators for linear advection

Parallel-in-time methods, such as multigrid reduction-in-time (MGRIT) and Parareal, provide an attractive option for increasing concurrency when simulating time-dependent partial differential equations (PDEs) in modern high-performance computing environments. While these techniques have been very successful for parabolic equations, it has often been observed that their performance suffers dramatically when applied to advection-dominated problems or purely hyperbolic PDEs using standard rediscretization approaches on coarse grids. In this paper, we apply MGRIT or Parareal to the constant-coefficient linear advection equation, appealing to existing convergence theory to provide insight into the typically nonscalable or even divergent behavior of these solvers for this problem. To overcome these failings, we replace rediscretization on coarse grids with improved coarse-grid operators that are computed by applying optimization techniques to approximately minimize error estimates from the convergence theory. Therefore, one of our main findings is that, in order to obtain fast convergence as for parabolic problems, coarse-grid operators should take into account the behavior of the hyperbolic problem by tracking the characteristic curves. Our approach is tested for schemes of various orders using explicit or implicit Runge–Kutta methods combined with upwind-finite-difference spatial discretizations. In all cases, we obtain scalable convergence in just a handful of iterations, with parallel tests also showing significant speed-ups over sequential time-stepping.

97 MATHEMATICS AND COMPUTING↗

A Semi-Algebraic Two Level Solver

We develop a simple semi-algebraic 2-level solver built on traditional multigrid ideas. It is designed to be easily incorporated into existing simulation software. It exhibits good convergence for many classes of challenging problems including discontinuous diffusion, convection- diffusion, and Helmholtz equations. It has built-in structure that makes it simple to generalize in several interesting directions.

97 MATHEMATICS AND COMPUTING↗

Parallel performance of algebraic multigrid domain decomposition

Algebraic multigrid (AMG) is a widely used scalable solver and preconditioner for large-scale linear systems resulting from the discretization of a wide class of elliptic PDEs. While AMG has optimal computational complexity, the cost of communication has become a significant bottleneck that limits its scalability as processor counts continue to grow on modern machines. This article examines the design, implementation, and parallel performance of a novel algorithm, algebraic multigrid domain decomposition (AMG-DD), designed specifically to limit communication. The goal of AMG-DD is to provide a low-communication alternative to standard AMG V-cycles by trading some additional computational overhead for a significant reduction in communication cost. Numerical results show that AMG-DD achieves superior accuracy per communication cost compared with AMG, and speedup over AMG is demonstrated on a large GPU cluster.

97 MATHEMATICS AND COMPUTING↗

A space-time parallel algorithm with adaptive mesh refinement for computational fluid dynamics

This work describes a space-time parallel algorithm with space-time adaptive mesh refinement (AMR). AMR with subcycling is added to multigrid reduction-in-time (MGRIT) in order to provide solution efficient adaptive grids with a reduction in work performed on coarser grids. This algorithm is achieved by integrating two software libraries: XBraid (Parallel time integration with multigrid. https://computation.llnl.gov/projects/parallel-timeintegration-multigrid) and Chombo (Chombo software package for AMR applications—design document, 2014). The former is a parallel time integration library using multigrid and the latter is a massively parallel structured AMR library. Employing this adaptive space-time parallel algorithm is Chord (Comput Fluids 123:202–217, 2015), a computational fluid dynamics (CFD) application code for solving compressible fluid dynamics problems. For the same solution accuracy, speedups are demonstrated from the use of space-time parallelization over the time-sequential integration on Couette flow and Stokes’ second problem. On a transient Couette flow case, at least a 1.5× speedup is achieved, and with a time periodic problem, a speedup of up to 13.7× over the time-sequential case is obtained. In both cases, the speedup is achieved by adding processors and exploring additional parallelization in time. The numerical experiments show the algorithm is promising for CFD applications that can take advantage of the time parallelism. Future work will focus on improving the parallel performance and providing more tests with complex fluid dynamics to demonstrate the full potential of the algorithm.

97 MATHEMATICS AND COMPUTING↗

Smoothers for Matrix-Free Algebraic Multigrid Preconditioning of High-Order Finite Elements

We investigate smoothers for use in matrix-free algebraic multigrid (AMG) preconditioning of high-order finite element problems. These AMG preconditioners are matrix-free in the sense that they are built from a related low-order refined finite element problem whose system matrix can be much more rapidly assembled than the high-order problem. Our proposed smoother, which we call distributive relaxation, is more robust to the anisotropy present in many low-order refined meshes which feature a clustering of nodes near the boundaries between high-order finite elements. For solving the low-order refined problem, we show that this new distributive relaxation smoother possesses significantly improved performance compared to more traditional smoothers.

97 MATHEMATICS AND COMPUTING↗

Multigrid-Reduction-in-Time for the Rotating Shallow Water Equations

We consider multilevel time-parallel methods for the numerical solution of the rotating shallow water equations. In particular, the multigrid-reduction-in-time (MGRIT) algorithm is used for the parallel time integration. An asymptotic model is used at the coarse levels while the full model is employed at the finer levels. The asymptotic model is well-suited for highly oscillatory partial differential equations like the rotating shallow water equations because it can accurately and stably take the required large time-steps on coarse levels. Our work exploits the flexibility of the MGRIT algorithm in terms of the number of levels and relaxation schemes to show some computational benefits, especially with respect to FCF-relaxation and data reuse.

97 MATHEMATICS AND COMPUTING↗

Multilevel Convergence Analysis of Multigrid-Reduction-in-Time

This study presents a multilevel convergence framework for multigrid-reduction-in-time (MGRIT) as a generalization of previous two-grid estimates. The framework provides a priori upper bounds on the convergence of MGRIT V- and F-cycles, with different relaxation schemes, by deriving the respective residual and error propagation operators. The residual and error operators are functions of the time-stepping operator, analyzed directly and bounded in the norm, both numerically and analytically. We present various upper bounds of different computational cost and varying sharpness. These upper bounds are complemented by proposing analytic formulae for the approximate convergence factor of V-cycle algorithms that take the number of fine grid time points, the temporal coarsening factors, and the eigenvalues of the time-stepping operator as parameters. The paper concludes with supporting numerical investigations of parabolic (anisotropic diffusion) and hyperbolic (wave equation) model problems. We assess the sharpness of the bounds and the quality of the approximate convergence factors. Observations from these numerical investigations demonstrate the value of the proposed multilevel convergence framework for estimating MGRIT convergence a priori and for the design of a convergent algorithm. We further highlight that observations in the literature are captured by the theory, including that two-level Parareal and multilevel MGRIT with F-relaxation do not yield scalable algorithms and the benefit of a stronger relaxation scheme. An important observation is that with increasing numbers of levels MGRIT convergence deteriorates for the hyperbolic model problem, while constant convergence factors can be achieved for the diffusion equation. The theory also indicates that L-stable Runge--Kutta schemes are more amendable to multilevel parallel-in-time integration with MGRIT than A-stable Runge--Kutta schemes.

97 MATHEMATICS AND COMPUTING↗

A parallel-in-time algorithm for variable step multistep methods

This paper presents a multigrid reduction in time (MGRIT) algorithm for achieving time parallelism using multistep backward difference formula (BDF) methods on variably-spaced temporal grids. This MGRIT approach transforms the linear multistep methods into single step methods applied to groups of time steps. Stability considerations are addressed through lowering of the order on coarse grids. The methods are presented for fixed and variable time step formulations. Furthermore, numerical results show moderate speedups for the heat equation as well as two IEEE power grid test problems characterized by nonlinear differential algebraic equations (DAE) of index 1. The performance of MGRIT with BDF is compared to MGRIT with Runge-Kutta for both the fixed and variable step methods of the same order.

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↗

Special issue: Advanced stencil-code engineering

Here, stencil codes are compute-intensive algorithms, in which data points arranged in a large grid are being recomputed repeatedly from the values of data points in a predefined neighborhood. This fixed neighborhood pattern is called a stencil. Stencils codes see wide-spread use in computing the discrete solutions of partial differential equations and systems composed of such equations.

97 MATHEMATICS AND COMPUTING↗