Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “preconditioning”

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 1,117 records · Page 62

Domain decomposition in time for PDE-constrained optimization

Here, PDE-constrained optimization problems have a wide range of applications, but they lead to very large and ill-conditioned linear systems, especially if the problems are time dependent. In this paper we outline an approach for dealing with such problems by decomposing them in time and applying an additive Schwarz preconditioner in time, so that we can take advantage of parallel computers to deal with the very large linear systems. We then illustrate the performance of our method on a variety of problems.

97 MATHEMATICS AND COMPUTING↗

Composite matrix construction for structured grid adaptive mesh refinement

Structured-grid adaptive mesh refinement (SAMR) is an approach to mesh generation that supports structured access to data and adaptive mesh refinement for discretized partial differential equations (PDEs). Solution algorithms often require that an inverse of an operator be applied, a system of algebraic equations must be solved, and this process is often the primary computational cost in an application. SAMR is well suited to geometric multigrid solvers, which can be effective, but often do not adapt well to complex geometry including material coefficients. Algebraic multigrid (AMG) is more robust in the face of complex geometry, in both boundary conditions and internal material interfaces. AMG requires a stored matrix linearization of the operator. We discuss an approach, and an implementation in the Chombo block-structured AMR framework, for constructing composite grid matrices from a SAMR hierarchy of grids for use in linear solvers in the PETSc numerical library. We consider a case study with the Chombo-based BISICLES ice sheet modeling application.

97 MATHEMATICS AND COMPUTING↗

Scalable and efficient algorithms for the propagation of uncertainty from data through inference to prediction for large-scale problems, with application to flow of the Antarctic ice sheet

The majority of research on efficient and scalable algorithms in computational science and engineering has focused on the forward problem : given parameter inputs, solve the governing equations to determine output quantities of interest. In contrast, in this paper, we consider the broader question: given a (large-scale) model containing uncertain parameters, (possibly) noisy observational data, and a prediction quantity of interest, how do we construct efficient and scalable algorithms to (1) infer the model parameters from the data (the deterministic inverse problem ), (2) quantify the uncertainty in the inferred parameters (the Bayesian inference problem), and (3) propagate the resulting uncertain parameters through the model to issue predictions with quantified uncertainties (the forward uncertainty propagation problem )? We present efficient and scalable algorithms for this end-to-end, data-to-prediction process under the Gaussian approximation and in the context of modeling the flow of the Antarctic ice sheet and its effect on loss of grounded ice to the ocean. The ice is modeled as a viscous, incompressible, creeping, shear-thinning fluid. The observational data come from satellite measurements of surface ice flow velocity, and the uncertain parameter field to be inferred is the basal sliding parameter, represented by a heterogeneous coefficient in a Robin boundary condition at the base of the ice sheet. The prediction quantity of interest is the present-day ice mass flux from the Antarctic continent to the ocean. We show that the work required for executing this data-to-prediction process—measured in number of forward (and adjoint) ice sheet model solves—is independent of the state dimension, parameter dimension, data dimension, and the number of processor cores. The key to achieving this dimension independence is to exploit the fact that, despite their large size, the observational data typically provide only sparse information on model parameters. This property can be exploited to construct a low rank approximation of the linearized parameter-to-observable map via randomized SVD methods and adjoint-based actions of Hessians of the data misfit functional.

54 ENVIRONMENTAL SCIENCES↗

Multiscale formulation of frictional contact mechanics at the pore scale

Direct numerical simulation (DNS) yields the highest fidelity predictions of mechanical deformation at the pore scale, but is prohibitively expensive for analyzing large or many samples. Discrete element methods (DEM) are an efficient alternative, but are limited to granular media and incapable of estimating or controlling prediction errors. We present a pore-level multiscale method (PLMM) that approximates DNS efficiently and with controllable accuracy. We focus on the linear elastic response of a consolidated geologic porous medium with arbitrary microstructure, heterogeneous mineralogy, containing cracks or defects. PLMM decomposes the solid phase into non-overlapping subdomains, on which local basis functions are constructed. The bases are then coupled with a global interface problem that accounts for slip or stick contact conditions between the subdomains. PLMM produces an initial, but accurate, approximation to DNS that can be iteratively improved. It is amenable to parallelism and allows for different mesh, models, and physics in each subdomain. An algebraic interpretation of PLMM as a preconditioner is also presented to allow non-intrusive implementation into existing solvers. Lastly, this work extends previous developments of PLMM in fluid dynamics to solid mechanics and enables future extensions towards modeling coupled flow and mechanics problems.

42 ENGINEERING↗

A greedy Galerkin method to efficiently select sensors for linear dynamical systems

A key challenge in inverse problems is the selection of sensors to gather the most effective data. In this paper, we consider the problem of inferring the initial condition to a linear dynamical system and develop an efficient control-theoretical approach for greedily selecting sensors. Our method employs a Galerkin projection to reduce the size of the inverse problem, resulting in a computationally efficient algorithm for sensor selection. As a byproduct of our algorithm, we obtain a preconditioner for the inverse problem that enables the rapid recovery of the initial condition. Here, we analyze the theoretical performance of our greedy sensor selection algorithm as well as the performance of the associated preconditioner. Finally, we verify our theoretical results on various inverse problems involving partial differential equations.

97 MATHEMATICS AND COMPUTING↗

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↗

Eigenvalue Solvers for Modeling Nuclear Reactors on Leadership Class Machines

In this paper, three complementary methods have been implemented in the code Denovo that accelerate neutral particle transport calculations with methods that use leadership-class computers fully and effectively: a multigroup block (MG) Krylov solver, a Rayleigh quotient iteration (RQI) eigenvalue solver, and a multigrid in energy (MGE) preconditioner. The MG Krylov solver converges more quickly than Gauss Seidel and enables energy decomposition such that Denovo can scale to hundreds of thousands of cores. RQI should converge in fewer iterations than power iteration (PI) for large and challenging problems. RQI creates shifted systems that would not be tractable without the MG Krylov solver. It also creates ill-conditioned matrices. The MGE preconditioner reduces iteration count significantly when used with RQI and takes advantage of the new energy decomposition such that it can scale efficiently. Each individual method has been described before, but this is the first time they have been demonstrated to work together effectively. The combination of solvers enables the RQI eigenvalue solver to work better than the other available solvers for large reactors problems on leadership-class machines. Using these methods together, RQI converged in fewer iterations and in less time than PI for a full pressurized water reactor core. These solvers also performed better than an Arnoldi eigenvalue solver for a reactor benchmark problem when energy decomposition is needed. The MG Krylov, MGE preconditioner, and RQI solver combination also scales well in energy. Finally, this solver set is a strong choice for very large and challenging problems.

22 GENERAL STUDIES OF NUCLEAR REACTORS↗

A Performance and Energy Study of GPU-Resident Preconditioners for Conjugate Gradient Solvers: In the Context of Existing and Novel Approaches

Optimizing a particular subprogram out of the set of Basic (sparse) Linear Algebra Subprograms (BLAS) for a given architecture is a common topic of research. In applications, however, these BLAS functions rarely appear in isolation; usually, many of them are used together, in various combinations and with varying inputs. As the need to solve a large, sparse linear system is ubiquitous throughout HPC applications, linear solvers constitute a realistic, sufficiently complex and well-defined representative use case for composite BLAS routines. To this end, based on a representative set of matrices drawn from a diverse set of fields, we present a framework to study, from the performance and energy perspective, the efficacy of GPU- resident parallel Conjugate Gradient (CG) linear solver with different preconditioner options, including Gauss-Seidel, Jacobi, and incomplete Cholesky. We also propose a novel GPU-based preconditioner, in which the triangular solves are approximated by an iterative process. The development of this preconditioner was motivated by solving large graph Laplacian linear systems, for which the existing preconditioners either perform slow on GPU-based platforms or are not applicable. We compare the performance of these preconditioners on different hardware accelerator architectures, i.e., AMD MI250X, MI100, Nvidia A100, V100, and Jetson. Our experiments reveal performance trade-offs and provide information on how to select the best strategy for the given linear system, dictated by its properties, and the platform of interest. We demonstrate the application of our novel preconditioner for solving CG and graph Laplacian systems. Overall, the framework can be utilized as a benchmark to guide informed decisions in choosing a specific preconditioner, i.e., whether it is better to rely on the performance of a triangular solver or on the performance of sparse matrix-vector product. Finally, by considering power consumption to solve the linear systems, we report the energy footprint for the solvers.

Preconditioned Conjugate Gradient, GPUs, iterative↗

Parallel Dynamics Simulation Using a Krylov-Schwarz Linear Solution Scheme

Fast dynamics simulation of large-scale power systems is a computational challenge because of the need to solve a large set of stiff, nonlinear differential-algebraic equations at every time step. The main bottleneck in dynamic simulations is the solution of a linear system during each nonlinear iteration of Newton’s method. In this paper, we present a parallel Krylov- Schwarz linear solution scheme that uses the Krylov subspacebased iterative linear solver GMRES with an overlapping restricted additive Schwarz preconditioner. As a result, performance tests of the proposed Krylov-Schwarz scheme for several large test cases ranging from 2,000 to 20,000 buses, including a real utility network, show good scalability on different computing architectures.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Comparative Convergence Analysis of Nonlinear AMLI-Cycle Multigrid

The purpose of our paper is to provide a comprehensive convergence analysis of the nonlinear algebraic multilevel iteration (AMLI)-cycle multigrid (MG) method for symmetric positive definite problems. We show that the nonlinear AMLI-cycle MG method is uniformly convergent, based on classical assumptions for approximation and smoothing properties. Furthermore, under only the assumption that the smoother is convergent, we show that the nonlinear AMLI-cycle method is always better (or not worse) than the respective V-cycle MG method. Finally, numerical experiments are presented to illustrate the theoretical results.

97 MATHEMATICS AND COMPUTING↗

Parallel Auxiliary Space AMG Solver for $H(div)$ Problems

We present a family of scalable preconditioners for matrices arising in the discretization of $H(div)$ problems using the lowest order Raviart--Thomas finite elements. Our approach belongs to the class of “auxiliary space''--based methods and requires only the finite element stiffness matrix plus some minimal additional discretization information about the topology and orientation of mesh entities. Also, we provide a detailed algebraic description of the theory, parallel implementation, and different variants of this parallel auxiliary space divergence solver (ADS) and discuss its relations to the Hiptmair--Xu (HX) auxiliary space decomposition of $H(div)$ [SIAM J. Numer. Anal., 45 (2007), pp. 2483--2509] and to the auxiliary space Maxwell solver AMS [J. Comput. Math., 27 (2009), pp. 604--623]. Finally, an extensive set of numerical experiments demonstrates the robustness and scalability of our implementation on large-scale $H(div)$ problems with large jumps in the material coefficients.

97 MATHEMATICS AND COMPUTING↗

Scalable Preconditioners for Structure Preserving Discretizations of Maxwell Equations in First Order Form

Here, we report multiple physical time-scales can arise in electromagnetic simulations when dissipative effects are introduced through boundary conditions, when currents follow external time-scales, and when material parameters vary spatially. In such scenarios, the time-scales of interest may be much slower than the fastest time-scales supported by the Maxwell equations, therefore making implicit time integration an efficient approach. The use of implicit temporal discretizations results in linear systems in which fast time-scales, which severely constrain the stability of an explicit method, can manifest as so-called stiff modes. This study proposes a new block preconditioner for structure preserving (also termed physics compatible) discretizations of the Maxwell equations in first order form. The intent of the preconditioner is to enable the efficient solution of multiple-time-scale Maxwell type systems. An additional benefit of the developed preconditioner is that it requires only a traditional multigrid method for its subsolves and compares well against alternative approaches that rely on specialized edge-based multigrid routines that may not be readily available. Lastly, results demonstrate parallel scalability at large electromagnetic wave CFL numbers on a variety of test problems.

97 MATHEMATICS AND COMPUTING↗

Scalable Matrix-Free Adaptive Product-Convolution Approximation for Locally Translation-Invariant Operators

We present an adaptive grid matrix-free operator approximation scheme based on a "product-convolution" interpolation of convolution operators. This scheme is appropriate for operators that are locally translation-invariant, even if these operators are high rank or full rank. Such operators arise in Schur complement methods for solving partial differential equations (PDEs), as Hessians in PDE-constrained optimization and inverse problems, as integral operators, as covariance operators, and as Dirichlet-to-Neumann maps. Constructing the approximation requires computing the impulse responses of the operator to point sources centered on nodes in an adaptively refined grid of sample points. A randomized a posteriori error estimator drives the adaptivity. Once constructed, the approximation can be efficiently applied to vectors using the fast Fourier transform. The approximation can be efficiently converted to hierarchical matrix (H-matrix) format, then inverted or factorized using scalable H-matrix arithmetic. The quality of the approximation degrades gracefully as fewer sample points are used, allowing cheap lower quality approximations to be used as preconditioners. Furthermore, this yields an automated method to construct preconditioners for locally translation-invariant Schur complements. We directly address issues related to boundaries and prove that our scheme eliminates boundary artifacts. We test the scheme on a spatially varying blurring kernel, on the nonlocal component of an interface Schur complement for the Poisson operator, and on the data misfit Hessian for an advection dominated advection-diffusion inverse problem. Numerical results show that the scheme outperforms existing methods.

97 MATHEMATICS AND COMPUTING↗

A Relaxed Physical Factorization Preconditioner for Mixed Finite Element Coupled Poromechanics

In this work, we introduce a relaxed physical factorization (RPF) preconditioner for the efficient iterative solution of the linearized algebraic system arising from the mixed finite element discretization of coupled poromechanics equations. The preconditioner is obtained by using a proper factorization of the $3\times3$ block matrix and setting a relaxation parameter $\alpha$. The preconditioner is inspired by the relaxed dimensional factorization introduced by Benzi et al. [J. Comput. Phys., 230 (2011), pp. 6185--6202; Comput. Methods Appl. Mech. Engrg., 300 (2016), pp. 129--145]. A stable algorithm is advanced to compute the optimal value of $\alpha$, along with a lower bound to control the possible ill-conditioning of the $\alpha$ dependent inner blocks. Lastly, numerical experiments in both theoretical benchmarks and real-world applications are presented and discussed to investigate the RPF properties, performance, and robustness.

97 MATHEMATICS AND COMPUTING↗

AIR Algebraic Multigrid for a Space-Time Hybridizable Discontinuous Galerkin Discretization of Advection(-Diffusion)

This article investigates the efficiency, robustness, and scalability of approximate ideal restriction (AIR) algebraic multigrid as a preconditioner in the all-at-once solution of a space-time hybridizable discontinuous Galerkin discretization of advection-dominated flows. The motivation for this study is that the time-dependent advection-diffusion equation can be seen as a “steady” advection-diffusion problem in $(d+1)$-dimensions and AIR has been shown to be a robust solver for steady advection-dominated problems. Numerical examples demonstrate the effectiveness of AIR as a preconditioner for advection-diffusion problems on fixed and time-dependent domains, using both slab-by-slab and all-at-once space-time discretizations, and in the context of uniform and space-time adaptive mesh refinement. A closer look at the geometric coarsening structure that arises in AIR also explains why AIR can provide robust, scalable, space-time convergence on advective and hyperbolic problems, while most multilevel parallel-in-time schemes struggle with such problems.

97 MATHEMATICS AND COMPUTING↗

Constrained Local Approximate Ideal Restriction for Advection-Diffusion Problems

Herein this paper focuses on developing a reduction-based algebraic multigrid (AMG) method that is suitable for solving general (non)symmetric linear systems and is naturally robust from pure advection to pure diffusion. Initial motivation comes from a new reduction-based AMG approach, $\ell \text{AIR}$ (local approximate ideal restriction), that was developed for solving advection-dominated problems. Though this new solver is very effective in the advection-dominated regime, its performance degrades in cases where diffusion becomes dominant. This is consistent with the fact that in general, reduction-based AMG methods tend to suffer from growth in complexity and/or convergence rates as the problem size is increased, especially for diffusion-dominated problems in two or three dimensions. Motivated by the success of $\ell \text{AIR}$ in the advective regime, our aim in this paper is to generalize the AIR framework with the goal of improving the performance of the solver in diffusion-dominated regimes. To do so, we propose a novel way to combine mode constraints as used commonly in energy-minimization AMG methods with the local approximation of ideal operators used in $\ell \text{AIR}$. The resulting constrained $\ell \text{AIR}$ algorithm is able to achieve fast scalable convergence on advective and diffusive problems. In addition, it is able to achieve standard low complexity hierarchies in the diffusive regime through aggressive coarsening, something that was previously difficult for reduction-based methods.

97 MATHEMATICS AND COMPUTING↗

Algebraic Multigrid with Filtering: An Efficient Preconditioner for Interior Point Methods in Large-Scale Contact Mechanics Optimization

Large-scale contact mechanics simulations are crucial in many engineering fields such as structural design and manufacturing. In the frictionless case, contact can be modeled by minimizing an energy functional; however, these problems are often nonlinear, nonconvex, and increasingly difficult to solve as mesh resolution increases. In this work, we employ a Newton-based interior-point (IP) filter line-search method, an effective approach for large-scale constrained optimization. While this method converges rapidly, each iteration requires solving a large saddle-point linear system that becomes ill-conditioned as the optimization process converges, largely due to IP treatment of the contact constraints. Such ill-conditioning can hinder solver scalability and increase iteration counts with mesh refinement. Here, to address this, we introduce a novel preconditioner, algebraic multigrid with filtering (AMGF), tailored to the Schur complement of the saddle-point system. Building on the classical AMG solver, commonly used for elasticity, we augment it with a specialized subspace correction that filters near null space components introduced by contact interface constraints. Through theoretical analysis and numerical experiments on a range of linear and nonlinear contact problems, we demonstrate that the proposed solver achieves mesh independent convergence and maintains robustness against the ill-conditioning that notoriously plagues IP methods. These results indicate that AMGF makes contact mechanics simulations more tractable and broadens the applicability of Newton-based IP methods in challenging engineering scenarios. More broadly, AMGF is well suited for problems, optimization or otherwise, where solver performance is limited by a low-dimensional subspace, such as those arising from localized constraints, interface conditions, or model heterogeneities. This makes the method widely applicable beyond contact mechanics and constrained optimization.

Mathematics and Computing↗