Search NASA⌕ Search

SEARCH · Search NASA

Results for “linear system”

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,423 records · Page 79

Reducing Parallel Communication in Algebraic Multigrid through Sparsification

Algebraic multigrid (AMG) is an $\mathcal{O}(n)$ solution process for many large sparse linear systems. A hierarchy of progressively coarser grids which utilize complementary relaxation and interpolation operators is constructed. High-energy error is reduced by relaxation, while low-energy error is mapped to coarse-grid matrices and reduced there. However, large parallel communication costs often limit parallel scalability. Furthermore, as the multigrid hierarchy is formed, each coarse matrix is formed through a triple matrix product. The resulting coarse grids often have significantly more nonzeros per row than the original fine-grid operator, thereby generating high parallel communication costs associated with sparse matrix-vector multiplication (SpMV) on coarse levels. In this paper, we introduce a method that systematically removes entries in coarse-grid matrices after the hierarchy is formed, leading to improved communication costs. We sparsify by removing weakly connected or unimportant entries in the matrix, leading to improved solve time. The main trade-off is that if the heuristic identifying unimportant entries is used too aggressively, then AMG convergence can suffer. To counteract this, the original hierarchy is retained, allowing entries to be reintroduced into the solver hierarchy if convergence is too slow. This enables a balance between communication cost and convergence, as necessary. In this paper we present new algorithms for reducing communication and present a number of computational experiments in support.

97 MATHEMATICS AND COMPUTING↗

AMPS: An Augmented Matrix Formulation for Principal Submatrix Updates with Application to Power Grids

We present an augmented matrix approach to update the solution to a linear system of equations when the coefficient matrix is modified by a few elements within a principal submatrix. This problem arises in the dynamic security analysis of a power grid, where operators need to perform $N-x$ contingency analysis, i.e., determine the state of the system when up to $x$ links from $N$ fail. Our algorithms augment the coefficient matrix to account for the changes in it, and then compute the solution to the augmented system without refactoring the modified matrix. We provide two algorithms, a direct method, and a hybrid direct-iterative method for solving the augmented system. We also exploit the sparsity of the matrices and vectors to accelerate the overall computation. Our algorithms are compared on three power grids with PARDISO, a parallel direct solver, and CHOLMOD, a direct solver with the ability to modify the Cholesky factors of the coefficient matrix. We show that our augmented algorithms outperform PARDISO (by two orders of magnitude), and CHOLMOD (by a factor of up to 5). Further, our algorithms scale better than CHOLMOD as the number of elements updated increases. The solutions are computed with high accuracy. Our algorithms are capable of computing $N-x$ contingency analysis on a $778K$ bus grid, updating a solution with $x=20$ elements in $1.6 \times 10^{-2}$ seconds on an Intel Xeon processor.

Yeung, Yu-Hong↗

A Nonlinear Algebraic Multigrid Framework for the Power Flow Equations

Multigrid is a highly scalable class of methods most often used for solving large linear systems. In this paper we develop a nonlinear algebraic multigrid framework for the power flow equations, a complex quadratic system of the form ${diag}({v})\overline{Y{v}}={s}$, where $Y$ is approximately a complex scalar rotation of a real graph Laplacian. This is a standard problem that needs to be solved repeatedly during power grid simulations. A key difference between our multigrid framework and typical multigrid approaches is the use of a novel multiplicative coarse-grid correction to enable a dynamic multigrid hierarchy. We also develop a new type of smoother that allows one to coarsen together the different types of nodes that appear in power grid simulations. In developing a specific multigrid method, one must make a number of choices that can significantly affect the method's performance, such as how to construct the restriction and interpolation operators, what smoother to use, and how aggressively to coarsen. In this paper, we make simple but reasonable choices that result in a scalable and robust power flow solver. Experiments demonstrate this scalability and show that it is significantly more robust to poor initial guesses than current state-of-the-art solvers.

97 MATHEMATICS AND COMPUTING↗

A Low-Rank Multigrid Method for the Stochastic Steady-State Diffusion Problem

We study a multigrid method for solving large linear systems of equations with tensor product structure here. Such systems are obtained from stochastic finite element discretization of stochastic partial differential equations such as the steady-state diffusion problem with random coefficients. When the variance in the problem is not too large, the solution can be well approximated by a low-rank object. In the proposed multigrid algorithm, the matrix iterates are truncated to low rank to reduce memory requirements and computational effort. The technique is proved convergent with an analytic error bound. Numerical experiments show its effectiveness in solving the Galerkin systems compared to the original multigrid solver, especially when the number of degrees of freedom associated with the spatial discretization is large.

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↗

Scaling Structured Multigrid to 500K+ Cores Through Coarse-Grid Redistribution

The effcient solution of sparse, linear systems resulting from the discretization of partial differential equations is crucial to the performance of many physics-based simulations. The algorithmic optimality of multilevel approaches for common discretizations makes them a good candidate for an efficient parallel solver. Yet, modern architectures for high-performance computing systems continue to challenge the parallel scalability of multilevel solvers. While algebraic multigrid methods are robust for solving a variety of problems, the increasing importance of data locality and cost of data movement in modern architectures motivates the need to carefully exploit structure in the problem. Robust logically structured variational multigrid methods, such as Black Box Multigrid (BoxMG), maintain structure throughout the multigrid hierarchy. This avoids indirection and increased coarse- grid communication costs typical in parallel algebraic multigrid. Nevertheless, the parallel scalability of structured multigrid is challenged by coarse-grid problems where the overhead in communication dominates computation. In this paper, an algorithm is introduced for redistributing coarse-grid problems through incremental agglomeration. Guided by a predictive performance model, this algorithm provides robust redistribution decisions for structured multilevel solvers. A two-dimensional diffusion problem is used to demonstrate the significant gain in performance of this algorithm over the previous approach that used agglomeration to one processor. In addition, the parallel scalability of this approach

97 MATHEMATICS AND COMPUTING↗

Unified Geometric Multigrid Algorithm for Hybridized High-Order Finite Element Methods

In this paper, we consider a standard elliptic partial differential equation and propose a geometric multigrid algorithm based on Dirichlet-to-Neumann (DtN) maps for hybridized high-order finite element methods. The proposed unified approach is applicable to any locally conservative hybridized finite element method including multinumerics with different hybridized methods in different parts of the domain. For these methods, the linear system involves only the unknowns residing on the mesh skeleton, and constructing intergrid transfer operators is therefore not trivial. The key to our geometric multigrid algorithm is the physics-based energy-preserving intergrid transfer operators which depend only on the fine scale DtN maps. Thanks to these operators, we completely avoid upscaling of parameters and no information regarding subgrid physics is explicitly required on coarse meshes. Moreover, our algorithm is agglomeration-based and can straightforwardly handle unstructured meshes. We perform extensive numerical studies with hybridized mixed methods, hybridized discontinuous Galerkin methods, weak Galerkin methods, and hybridized versions of interior penalty discontinuous Galerkin methods on a range of elliptic problems including subsurface flow through highly heterogeneous porous media. We compare the performance of different smoothers and analyze the effect of stabilization parameters on the scalability of the multigrid algorithm.

97 MATHEMATICS AND COMPUTING↗

Computationally Efficient Decompositions of Oblique Projection Matrices

Oblique projection matrices arise in problems in weighted least squares, signal processing, and optimization. While these matrices can be potentially very large, their low-rank structure can be exploited for efficient computation. Here, we propose fast and scalable algorithms for computing their eigendecomposition and singular value decomposition (SVD). Numerical experiments that compare our proposed approaches to existing methods, including randomized SVD, are presented. In addition, we test their accuracy on linear systems from equality constrained optimization problems.

97 MATHEMATICS AND COMPUTING↗

KKT Preconditioners for PDE-Constrained Optimization with the Helmholtz Equation

This paper considers preconditioners for the linear systems that arise from optimal control and inverse problems involving the Helmholtz equation. Specifically, we explore an all-at-once approach. The main contribution centers on the analysis of two block preconditioners. Variations of these preconditioners have been proposed and analyzed in prior works for optimal control problems where the underlying partial differential equation is a Laplace-like operator. In this paper, we extend some of the prior convergence results to Helmholtz-based optimization applications. Our analysis examines situations where control variables and observations are restricted to subregions of the computational domain. We prove that solver convergence rates do not deteriorate as the mesh is refined or as the wavenumber increases. More specifically, for one of the preconditioners we prove accelerated convergence as the wavenumber increases. Additionally, in situations where the control and observation subregions are disjoint, we observe that solver convergence rates have a weak dependence on the regularization parameter. We give a partial analysis of this behavior. We illustrate the performance of the preconditioners on control problems motivated by acoustic testing.

97 MATHEMATICS AND COMPUTING↗

Sparse Approximate Multifrontal Factorization with Butterfly Compression for High-Frequency Wave Equations

In this work, we present a fast and approximate multifrontal solver for large-scale sparse linear systems arising from finite-difference, finite-volume or finite-element discretization of high-frequency wave equations. The proposed solver leverages the butterfly algorithm and its hierarchical matrix extension for compressing and factorizing large frontal matrices via graph-distance guided entry evaluation or randomized matrix-vector multiplication-based schemes. Complexity analysis and numerical experiments demonstrate $\mathcal{O}(N\log^2 N)$ computation and $\mathcal{O}(N)$ memory complexity when applied to an $N\times N$ sparse system arising from 3D high-frequency Helmholtz and Maxwell problems.

97 MATHEMATICS AND COMPUTING↗

Learning Optimal Multigrid Smoothers via Neural Networks

Multigrid methods are one of the most efficient techniques for solving large sparse linear systems arising from partial differential equations (PDEs) and graph Laplacians from machine learning applications. One of the key components of multigrid is smoothing, which aims at reducing high-frequency errors on each grid level. However, finding optimal smoothing algorithms is problem-dependent and can impose challenges for many problems. In this paper, we propose an efficient adaptive framework for learning optimized smoothers from operator stencils in the form of convolutional neural networks (CNNs). Here, the CNNs are trained on small-scale problems from a given type of PDEs based on a supervised loss function derived from multigrid convergence theories and can be applied to large-scale problems of the same class of PDEs. Numerical results on anisotropic rotated Laplacian problems and variable coefficient diffusion problems demonstrate improved convergence rates and solution time compared with classical hand-crafted relaxation methods.

97 MATHEMATICS AND COMPUTING↗

A Probabilistic Scheme for Semilinear Nonlocal Diffusion Equations with Volume Constraints

This work presents a probabilistic scheme for solving semilinear nonlocal diffusion equations with volume constraints and integrable kernels. The nonlocal model of interest is defined by a time-dependent semilinear partial integro-differential equation (PIDE), in which the integro-differential operator consists of both local convection-diffusion and nonlocal diffusion operators. Here, our numerical scheme is based on the direct approximation of the nonlinear Feynman–Kac formula that establishes a link between nonlinear PIDEs and stochastic differential equations. The exploitation of the Feynman–Kac representation avoids solving dense linear systems arising from nonlocal operators. Compared with existing stochastic approaches, our method can achieve first-order convergence after balancing the temporal and spatial discretization errors, which is a significant improvement of existing probabilistic/stochastic methods for nonlocal diffusion problems. Error analysis of our numerical scheme is established. The effectiveness of our approach is shown in two numerical examples. The first example considers a three-dimensional nonlocal diffusion equation to numerically verify the error analysis results. The second example presents a physics problem motivated by the study of heat transport in magnetically confined fusion plasmas.

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↗

Modifying the Asynchronous Jacobi Method for Data Corruption Resilience

Moving scientific computation from high-performance computing (HPC) and cloud computing (CC) environments to devices on the edge, i.e., physically near instruments of interest, has received tremendous interest in recent years. Such edge computing environments can operate on data in situ, offering enticing benefits over data aggregation to HPC and CC facilities that include avoiding costs of transmission, increased data privacy, and real-time data analysis. Because of the inherent unreliability of edge computing environments, new fault-tolerant approaches must be developed before the benefits of edge computing can be realized. Motivated by algorithm-based fault tolerance, a variant of the asynchronous Jacobi (ASJ) method is developed that achieves resilience to data corruption by rejecting solution approximations from neighbor devices according to a bound derived from convergence theory. Numerical results on a two-dimensional Poisson problem show that the new rejection criterion, along with a novel approximation to the shortest path length on which the criterion depends, restores convergence for the ASJ variant in the presence of certain types data corruption. Numerical results are obtained for when the singular values in the analytic bound are approximated. Additional linear systems are also explored, one with a more dense sparsity pattern and one that includes advection. All results indicate that successful resilience to data corruption depends on whether the bound tightens fast enough to reject corrupted data before the iteration evolution deviates significantly from that predicted by the convergence theory defining the bound. This observation generalizes to future work on algorithm-based fault tolerance for other asynchronous algorithms, including upcoming approaches that leverage Krylov subspaces.

97 MATHEMATICS AND COMPUTING↗

An Adaptive Newton-Based Free-Boundary Grad–Shafranov Solver

Equilibria in magnetic confinement devices result from force balancing between the Lorentz force and the plasma pressure gradient. In an axisymmetric configuration like a tokamak, such an equilibrium is described by an elliptic equation for the poloidal magnetic flux, commonly known as the Grad–Shafranov equation. It is challenging to develop a scalable and accurate free-boundary Grad–Shafranov solver, since it is a fully nonlinear optimization problem that simultaneously solves for the magnetic field coil current outside the plasma to control the plasma shape. In this work, we develop a Newton-based free-boundary Grad–Shafranov solver using adaptive finite elements and preconditioning strategies. The free-boundary interaction leads to the evaluation of a domain-dependent nonlinear form of which its contribution to the Jacobian matrix is achieved through shape calculus. The optimization problem aims to minimize the distance between the plasma boundary and specified control points while satisfying two nontrivial constraints, which correspond to the nonlinear finite element discretization of the Grad–Shafranov equation and a constraint on the total plasma current involving a nonlocal coupling term. The linear system is solved by a block factorization, and AMG is called for subblock elliptic operators. The unique contributions of this work include the treatment of a global constraint, preconditioning strategies, nonlocal reformulation, and the implementation of adaptive finite elements. Furthermore, it is found that the resulting Newton solver is robust, successfully reducing the nonlinear residual to 1e-6 and lower in a small handful of iterations while addressing the challenging case to find a Taylor state equilibrium where conventional Picard-based solvers fail to converge.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

Optimal Transfer Operators in Algebraic Two-Level Methods for Nonsymmetric and Indefinite Problems

Consider an algebraic two-level method applied to the 𝑛-dimensional linear system 𝐴⁢𝒙 = 𝒃 using fine-space preconditioner (i.e., “relaxation” or “smoother”) 𝑀, with 𝑀 ≈ 𝐴, restriction and interpolation 𝑅 and 𝑃, and algebraic coarse-space operator 𝐴 𝑐 : = 𝑅 ∗ ⁢𝐴⁢𝑃. Then, what are the best possible transfer operators 𝑅 and 𝑃 of a given dimension 𝑛 𝑐 < 𝑛? Brannick et al. [12] showed that when 𝐴 and 𝑀 are Hermitian positive definite (HPD), the optimal interpolation is such that its range contains the 𝑛 𝑐 smallest generalized eigenvectors of the matrix pencil (𝐴, 𝑀). Recently, in Ali et al. [5] we generalized this framework to the non-HPD setting, by considering both right (interpolation) and left (restriction) generalized eigenvectors of (𝐴, 𝑀) and defining corresponding nonsymmetric transfer operators {𝑅#, 𝑃#}. Tight convergence bounds for {𝑅#, 𝑃#} are derived in spectral radius, as well as a proof of pseudo-optimality. Note, {𝑅#, 𝑃#} are typically complex valued, which is not practical for real-valued problems. Here, in this work, we build on [5], first characterizing all inner products in which the coarse-space correction defined by {𝑅#, 𝑃#} is orthogonal. We then develop tight two-level convergence bounds in these norms, and prove that the underlying transfer operators {𝑅#, 𝑃#} are genuinely optimal. As a special case, our theory both recovers and extends the HPD results from [12]. Finally, we show how to construct optimal, real-valued transfer operators in the case of that 𝐴 and 𝑀 are real valued, but are not HPD. Numerical examples arising from a discretized advection-reaction equation, wave-equation, and Stokes equations are used to verify and illustrate the theory.

97 MATHEMATICS AND COMPUTING↗

A Distributed-Memory Package for Dense Hierarchically Semi-Separable Matrix Computations Using Randomization

In this paper, we present a distributed-memory library for computations with dense structured matrices. A matrix is considered structured if its off-diagonal blocks can be approximated by a rank-deficient matrix with low numerical rank. Here, we use Hierarchically Semi-Separable (HSS) representations. Such matrices appear in many applications, for example, finite-element methods, boundary element methods, and so on. Exploiting this structure allows for fast solution of linear systems and/or fast computation of matrix-vector products, which are the two main building blocks of matrix computations. The compression algorithm that we use, that computes the HSS form of an input dense matrix, relies on randomized sampling with a novel adaptive sampling mechanism. We discuss the parallelization of this algorithm and also present the parallelization of structured matrix-vector product, structured factorization, and solution routines. The efficiency of the approach is demonstrated on large problems from different academic and industrial applications, on up to 8,000 cores. Finally, this work is part of a more global effort, the STRUctured Matrices PACKage (STRUMPACK) software package for computations with sparse and dense structured matrices. Hence, although useful on their own right, the routines also represent a step in the direction of a distributed-memory sparse solver.

98 NUCLEAR DISARMAMENT, SAFEGUARDS, AND PHYSICAL P↗