Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “computational linear algebra”

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 163 records · Page 9
All sourcesNASA NTRSDOE OSTI
DOE OSTI2025

Ensemble Simulation Techniques and Fast Randomized Algorithms

The major goals of the project were to develop and analyze new ensemble simulation techniques, including trajectory stratification and preconditioned MCMC techniques, as well as develop fast numerical linear algebra techniques closely related to ensemble simulation ideas. The trajectory stratification techniques involve simulating in parallel short trajectory fragments of a Markov process confined to a specific region of space‐time and then patching together the statistics gathered to assemble estimates of very general dynamical properties. We have also developed this approach for rare event simulation and extended the techniques to applications requiring a more general framework (such as electronic structure calculations). The preconditioned MCMC techniques involve simulating multiple Markov chains in parallel and then using information from the ensemble to speed the mixing of each individual chain. The fast randomized linear algebra methods are motivated by the diffusion Monte Carlo technique, but are applicable to finding the dominant eigenvalue of (almost) general matrices. For most non‐negative matrices, the schemes result in an error (compared to the power method) that is constant in the dimension of the problem. For more general matrices, we see a very clear sublinear cost trend in computational tests.

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗
DOE OSTI2021

Abridged spectral matrix inversion: parametric fitting of X-ray fluorescence spectra following integrative data reduction

Recent improvements in both X-ray detectors and readout speeds have led to a substantial increase in the volume of X-ray fluorescence data being produced at synchrotron facilities. This in turn results in increased challenges associated with processing and fitting such data, both temporally and computationally. Herein an abridging approach is described that both reduces and partially integrates X-ray fluorescence (XRF) data sets to obtain a fivefold total improvement in processing time with negligible decrease in quality of fitting. The approach is demonstrated using linear least-squares matrix inversion on XRF data with strongly overlapping fluorescent peaks. This approach is applicable to any type of linear algebra based fitting algorithm to fit spectra containing overlapping signals wherein the spectra also contain unimportant (non-characteristic) regions which add little (or no) weight to fitted values, e.g. energy regions in XRF spectra that contain little or no peak information.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗
DOE OSTI2021

Porting the Nonlinear Optimization Library HiOp to Accelerator-Based Hardware Architectures

While interior point method has been the centerpiece of nonlinear programming tools used in science and engineering, its reliance on linear solvers that can tackle sparse symmetric indefinite and highly ill-conditioned problems made it difficult to implement it effectively on hardware accelerators. HiOp optimization package attempts to provide an implementation of the interior point method suitable for hardware accelerators by compressing the original sparse problem to produce an underlying linear problem that is dense and of manageable size. Implementations of dense linear solvers are more mature and utilize hardware accelerators better than their sparse counterparts. There is a number of important domain problems, such as optimal power flow analysis for power grids, where the sparse problem can be effectively compressed and deploying dense linear solver within the interior point method can improve performance. Here we describe a portable implementation of HiOp optimization engine, which uses a linear solver from Magma library and runs entirely on hardware accelerators. To compress the problem, HiOp uses customized mixed dense-sparse linear algebra. All HiOp kernels are implemented using Umpire and RAJA portability libraries. We describe details of the implementation and discuss trade-offs between performance, portability and development cost.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Enabling New Flexibility in the SUNDIALS Suite of Nonlinear and Differential/Algebraic Equation Solvers

In recent years, the SUite of Nonlinear and DIfferential/ALgebraic equation Solvers (SUNDIALS) has been redesigned to better enable the use of application-specific and third-party algebraic solvers and data structures. Throughout this work, we have adhered to specific guiding principles that minimized the impact to current users while providing maximum flexibility for later evolution of solvers and data structures. The redesign was done through the addition of new linear and nonlinear solvers classes, enhancements to the vector class, and the creation of modern Fortran interfaces. The vast majority of this work has been performed “behind-the-scenes,” with minimal changes to the user interface and no reduction in solver capabilities or performance. These changes allow SUNDIALS users to more easily utilize external solver libraries and create highly customized solvers, enabling greater flexibility on extreme-scale, heterogeneous computational architectures.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

AXI4MLIR: User-Driven Automatic Host Code Generation for Custom AXI-Based Accelerators

Tensor algebra operations represent an important class of algorithms used across many applications, including machine learning, scientific computing, and data analytics. As a result, the efficient generation of custom accelerators for tensor operations has received increased attention. Previous efforts have produced automated tools enabling users to prototype and explore optimized accelerators. However, little effort has been focused on the host-accelerator interaction in these tools. Efficient use of hardware accelerators requires knowledge about the accelerator's capabilities (operations, data formats, and opcode support), the host CPU microarchitecture (e.g., memory hierarchy), the host-accelerator interface, and the application's features (which code regions should be mapped onto an accelerator). Manually rewriting the original applications to facilitate improved custom accelerator mapping is an error-prone and time-consuming endeavor. To cope with this, we propose AXI4MLIR, a new framework to automatically generate and optimize the communication between the host CPU and arbitrary accelerators that implement linear algebra algorithms. AXI4MLIR extends the MLIR compiler framework to automatically generate efficient host-accelerator driver code for accelerators with AXI-based interfaces. Our compiler extensions enable automatic driver code generation while carefully considering the host's memory hierarchy and target accelerator features. To demonstrate the flexibility and utility of AXI4MLIR, we test it with diverse use cases that include different types of accelerators, tiling scenarios, and dataflow schemes. We compare our experimental results to manual implementations of host-accelerator driver code and find that our approach can reduce CPU cache references by 56% and deliver up to a 1.65x speedup.

Bohm Agostini, Nicolas↗
DOE OSTI2023

Fast truncated SVD of sparse and dense matrices on graphics processors

We investigate the solution of low-rank matrix approximation problems using the truncated singular value decomposition (SVD). For this purpose, we develop and optimize graphics processing unit (GPU) implementations for the randomized SVD and a blocked variant of the Lanczos approach. Our work takes advantage of the fact that the two methods are composed of very similar linear algebra building blocks, which can be assembled using numerical kernels from existing high-performance linear algebra libraries. Furthermore, the experiments with several sparse matrices arising in representative real-world applications and synthetic dense test matrices reveal a performance advantage of the block Lanczos algorithm when targeting the same approximation accuracy.

Computer Science↗
DOE OSTI2022

Generalized symmetries of the graviton

We find the set of generalized symmetries associated with the free graviton theory in four dimensions. These are generated by gauge invariant topological operators that violate Haag duality in ring-like regions. As expected from general QFT grounds, we find a set of “electric” and a dual set of “magnetic” topological operators and compute their algebra. To do so, we describe the theory using phase space gauge-invariant electric and magnetic dual variables constructed out of the curvature tensor. Electric and magnetic fields satisfy a set of constraints equivalent to the ones of a stress tensor of a 3d CFT. The constraints give place to a group $\mathbb{R}^{20}$ of topological operators that are charged under space-time symmetries. Finally, we discuss similarities and differences between linearized gravity and tensor gauge theories that have been introduced recently in the context of fractonic systems in condensed matter physics.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2020

Demonstration and performance testing of extreme-resolution simulations with static meshes on Summit (CPU & GPU) for a parked-turbine configuration and an actuator-line (mid-fidelity model) wind farm configuration (ECP-Q4 FY2020 Milestone Report)

The goal of the ExaWind project is to enable predictive simulations of wind farms comprised of many megawatt-scale turbines situated in complex terrain. Predictive simulations will require computational fluid dynamics (CFD) simulations for which the mesh resolves the geometry of the turbines and captures the rotation and large deflections of blades. Whereas such simulations for a single turbine are arguably petascale class, multi-turbine wind farm simulations will require exascale-class resources. The primary physics codes in the ExaWind simulation environment are Nalu-Wind, an unstructured-grid solver for the acoustically incompressible Navier-Stokes equations, AMR-Wind, a block-structured-grid solver with adaptive mesh refinement capabilities, and OpenFAST, a wind-turbine structural dynamics solver. The Nalu-Wind model consists of the mass-continuity Poisson-type equation for pressure and Helmholtz-type equations for transport of momentum and other scalars. For such modeling approaches, simulation times are dominated by linear-system setup and solution for the continuity and momentum systems. For the ExaWind challenge problem, the moving meshes greatly affect overall solver costs as reinitialization of matrices and recomputation of preconditioners is required at every time step. The choice of overset-mesh methodology to model the moving and non-moving parts of the computational domain introduces constraint equations in the elliptic pressure-Poisson solver. The presence of constraints greatly affects the performance of algebraic multigrid preconditioners.

17 WIND ENERGY↗
DOE OSTI2024

A Provably Accurate Randomized Sampling Algorithm for Logistic Regression

In statistics and machine learning, logistic regression is a widely-used supervised learning technique primarily employed for binary classification tasks. When the number of observations greatly exceeds the number of predictor variables, we present a simple, randomized sampling-based algorithm for logistic regression problem that guarantees high-quality approximations to both the estimated probabilities and the overall discrepancy of the model. Our analysis builds upon two simple structural conditions that boil down to randomized matrix multiplication, a fundamental and well-understood primitive of randomized numerical linear algebra. We analyze the properties of estimated probabilities of logistic regression when leverage scores are used to sample observations, and prove that accurate approximations can be achieved with a sample whose size is much smaller than the total number of observations. To further validate our theoretical findings, we conduct comprehensive empirical evaluations. Overall, our work sheds light on the potential of using randomized sampling approaches to efficiently approximate the estimated probabilities in logistic regression, offering a practical and computationally efficient solution for large-scale datasets.

Chowdhury, Agniva↗
DOE OSTI2024

Solving a class of infinite-dimensional tensor eigenvalue problems by translational invariant tensor ring approximations

Here, we examine a method for solving an infinite-dimensional tensor eigenvalue problem Hx = λx, where the infinite-dimensional symmetric matrix H exhibits a translational invariant structure. We provide a formulation of this type of problem from a numerical linear algebra point of view and describe how a power method applied to e -Ht is used to obtain an approximation to the desired eigenvector. This infinite-dimensional eigenvector is represented in a compact way by a translational invariant infinite Tensor Ring (iTR). Low rank approximation is used to keep the cost of subsequent power iterations bounded while preserving the iTR structure of the approximate eigenvector. We show how the averaged Rayleigh quotient of an iTR eigenvector approximation can be efficiently computed and introduce a projected residual to monitor its convergence. In the numerical examples, we illustrate that the norm of this projected iTR residual can also be used to automatically modify the time step to ensure accurate and rapid convergence of the power method.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

DESC: A stellarator equilibrium solver

In this paper, the new code DESC is presented to solve for fixed-boundary ideal magnetohydrodynamic equilibria in stellarators. The approach directly solves the equilibrium force balance as a system of nonlinear equations in the form f(x) = 0. The independent variables x represent nested magnetic flux surfaces expressed in the inverse representation with toroidal flux coordinates, and the equations f(x) quantify equilibrium force balance errors at discrete points in real space. Discretizing with global Fourier–Zernike basis functions properly treats the magnetic axis and minimizes the number of coefficients needed to describe the flux surfaces. The pseudospectral method provides great flexibility in where the errors are evaluated, and the system of equations is efficiently solved with a Newton–Raphson iteration. Equilibria are computed and compared against VMEC for both axisymmetric and non-axisymmetric examples. The results show fast convergence rates and solutions with low errors throughout the plasma volume.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗
DOE OSTI2020

A supernodal all-pairs shortest path algorithm

We show how to exploit graph sparsity in the Floyd-Warshall algorithm for the all-pairs shortest path (Apsp) problem. Floyd-Warshall is an attractive choice for Apsp on high-performing systems due to its structural similarity to solving dense linear systems and matrix multiplication. However, if sparsity of the input graph is not properly exploited, Floyd-Warshall will perform unnecessary asymptotic work and thus may not be a suitable choice for many input graphs. To overcome this limitation, the key idea in our approach is to use the known algebraic relationship between Floyd-Warshall and Gaussian elimination, and import several algorithmic techniques from sparse Cholesky factorization, namely, fill-in reducing ordering, symbolic analysis, supernodal traversal, and elimination tree parallelism. When combined, these techniques reduce computation, improve locality and enhance parallelism. We implement these ideas in an efficient shared memory parallel prototype that is orders of magnitude faster than an efficient multi-threaded baseline Floyd-Warshall that does not exploit sparsity. Our experiments suggest that the Floyd-Warshall algorithm can compete with Dijkstra's algorithm (the algorithmic core of Johnson's algorithm) for several classes sparse graphs.

Sao, Piyush↗
DOE OSTI2025

Preserving nonlinear constraints in variational flow filtering data assimilation

Data assimilation aims to estimate the states of a dynamical system by optimally combining sparse and noisy observations of the physical system with uncertain forecasts produced by a computational model. The states of many dynamical systems of interest obey nonlinear physical constraints, and the corresponding dynamics is confined to a certain sub-manifold of the state space. Standard data assimilation techniques applied to such systems yield posterior states lying outside the manifold, violating the physical constraints. This work focuses on particle flow filters which use stochastic differential equations to evolve state samples from a prior distribution to samples from an observation-informed posterior distribution. The variational Fokker-Planck (VFP)—a generic particle flow filtering framework—is extended to incorporate non-linear, equality state constraints in the analysis. To this end, two algorithmic approaches that modify the VFP stochastic differential equation are discussed: (i) VFPSTAB, to inexactly preserve constraints with the addition of a stabilizing drift term, and (ii) VFPDAE, to exactly preserve constraints by treating the VFP dynamics as a stochastic differential-algebraic equation (SDAE). Additionally, an implicit-explicit time integrator is developed to evolve the VFPDAE dynamics. The strength of the proposed approach for constraint preservation in data assimilation is demonstrated on three test problems: the double pendulum, Korteweg-de-Vries, and the incompressible Navier-Stokes equations.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Eigenvectors from Eigenvalues: a survey of a basic identity in linear algebra

If $A$ is an $n \times n$ Hermitian matrix with eigenvalues $\lambda_1(A),\dots,\lambda_n(A)$ and $i,j = 1,\dots,n$, then the $j^{\mathrm{th}}$ component $v_{i,j}$ of a unit eigenvector $v_i$ associated to the eigenvalue $\lambda_i(A)$ is related to the eigenvalues $\lambda_1(M_j),\dots,\lambda_{n-1}(M_j)$ of the minor $M_j$ of $A$ formed by removing the $j^{\mathrm{th}}$ row and column by the formula $$ |v_{i,j}|^2\prod_{k=1;k\neq i}^{n}\left(\lambda_i(A)-\lambda_k(A)\right)=\prod_{k=1}^{n-1}\left(\lambda_i(A)-\lambda_k(M_j)\right)\,.$$ We refer to this identity as the \emph{eigenvector-eigenvalue identity}. Despite the simple nature of this identity and the extremely mature state of development of linear algebra, this identity was not widely known until very recently. In this survey we describe the many times that this identity, or variants thereof, have been discovered and rediscovered in the literature (with the earliest precursor we know of appearing in 1934). We also provide a number of proofs and generalizations of the identity.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Discriminating Quantum States with Quantum Machine Learning

Quantum machine learning (QML) algorithms have obtained great relevance in the machine learning (ML) field due to the promise of quantum speedups when performing basic linear algebra subroutines (BLAS), a fundamental element in most ML algorithms. By making use of BLAS operations, we propose, implement and analyze a quantum k-means (qk-means) algorithm with a low time complexity of O(NKlog(D)I/C) to apply it to the fundamental problem of discriminating quantum states at readout. Discriminating quantum states allows the identification of quantum states |0⟩ and |1⟩ from low-level in-phase and quadrature signal (IQ) data, and can be done using custom ML models. In order to reduce dependency on a classical computer, we use the qk-means to perform state discrimination on the IBMQ Bogota device and managed to find assignment fidelities of up to 98.7% that were only marginally lower than that of the k-means algorithm. We also performed a cross-talk benchmark on the quantum device by applying both algorithms to perform state discrimination on a combination of quantum states and using Pearson Correlation coefficients and assignment fidelities of discrimination results to conclude on the presence of cross-talk on qubits. Evidence shows cross-talk in the (1, 2) and (2, 3) neighboring qubit couples for the analyzed device.

Quiroga, David↗
DOE OSTI2024

QuTree: A tree tensor network package

Here we present QuTree, a C++ library for tree tensor network approaches. QuTree provides class structures for tensors, tensor trees, and related linear algebra functions that facilitate the fast development of tree tensor network approaches such as the multilayer multiconfigurational time-dependent Hartree approach or the density matrix renormalization group approach and its various extensions. We investigate the efficiency of relevant tensor and tensor network operations and show that the overhead for managing the network structure is negligible, even in cases with a million leaves and small tensors. QuTree focuses on providing simple, high-level routines while retaining easy access to the backend to facilitate novel developments. We demonstrate the capabilities of the package by computing the eigenstates of coupled harmonic oscillator Hamiltonians and performing random circuit simulations on a virtual quantum computer.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2024

A graphics processing unit accelerated sparse direct solver and preconditioner with block low rank compression

We present the GPU implementation efforts and challenges of the sparse solver package STRUMPACK. The code is made publicly available on github with a permissive BSD license. STRUMPACK implements an approximate multifrontal solver, a sparse LU factorization which makes use of compression methods to accelerate time to solution and reduce memory usage. Multiple compression schemes based on rank-structured and hierarchical matrix approximations are supported, including hierarchically semi-separable, hierarchically off-diagonal butterfly, and block low rank. Here, in this paper, we present the GPU implementation of the block low rank (BLR) compression method within a multifrontal solver. Our GPU implementation relies on highly optimized vendor libraries such as cuBLAS and cuSOLVER for NVIDIA GPUs, rocBLAS and rocSOLVER for AMD GPUs and the Intel oneAPI Math Kernel Library (oneMKL) for Intel GPUs. Additionally, we rely on external open source libraries such as SLATE (Software for Linear Algebra Targeting Exascale), MAGMA (Matrix Algebra on GPU and Multi-core Architectures), and KBLAS (KAUST BLAS). SLATE is used as a GPU-capable ScaLAPACK replacement. From MAGMA we use variable sized batched dense linear algebra operations such as GEMM, TRSM and LU with partial pivoting. KBLAS provides efficient (batched) low rank matrix compression for NVIDIA GPUs using an adaptive randomized sampling scheme. The resulting sparse solver and preconditioner runs on NVIDIA, AMD and Intel GPUs. Interfaces are available from PETSc, Trilinos and MFEM, or the solver can be used directly in user code. We report results for a range of benchmark applications, using the Perlmutter system from NERSC, Frontier from ORNL, and Aurora from ALCF. For a high frequency wave equation on a regular mesh, using 32 Perlmutter compute nodes, the factorization phase of the exact GPU solver is about 6.5× faster compared to the CPU-only solver. The BLR-enabled GPU solver is about 13.8× faster than the CPU exact solver. For a collection of SuiteSparse matrices, the STRUMPACK exact factorization on a single GPU is on average 1.9× faster than NVIDIA’s cuDSS solver.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

PyAMG: Algebraic Multigrid Solvers in Python

PyAMG is a Python package of algebraic multigrid (AMG) solvers and supporting tools for approximating the solution to large, sparse linear systems of algebraic equations, Ax = b, where A is an n × n sparse matrix. Sparse linear systems arise in a range of problems in science, from fluid flows to solid mechanics to data analysis. While the direct solvers available in SciPy’s sparse linear algebra package (scipy.sparse.linalg) are highly efficient, in many cases iterative methods are preferred due to overall complexity. However, the iterative methods in SciPy, such as CG and GMRES, often require an efficient preconditioner in order to achieve a lower complexity. Preconditioning is a powerful tool whereby the conditioning of the linear system and convergence rate of the iterative method are both dramatically improved. PyAMG constructs multigrid solvers for use as a preconditioner in this setting. A summary of multigrid and algebraic multigrid solvers can be found in Olson (2015a), in Olson (2015b), and in Falgout (2006); a detailed description can be found in Briggs et al. (2000) and Trottenberg et al. (2001).

97 MATHEMATICS AND COMPUTING↗