Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “sparse matrix”

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 307 records · Page 17
All sourcesNASA NTRSDOE OSTI
DOE OSTI2020

Towards real-time monitoring: data assimilated time-lapse full waveform inversion for seismic velocity and uncertainty estimation

SUMMARY Rapid development of time-lapse seismic monitoring instrumentations has made it possible to collect dense time-lapse data for tomographically retrieving time-lapse (even continuous) images of subsurface changes. While traditional time-lapse full waveform inversion (TLFWI) algorithms are designed for sparse time-lapse surveys, they lack of effective temporal constraint on time-lapse data, and, more importantly, lack of the uncertainty estimation of the TLFWI results that is critical for further interpretation. Here, we propose a new data assimilation TLFWI method, using hierarchical matrix powered extended Kalman filter (HiEKF) to quantify the image uncertainty. Compared to existing Kalman filter algorithms, HiEKF allows to store and update a data-sparse representation of the cross-covariance matrices and propagate model errors without expensive operations involving covariance matrices. Hence, HiEKF is computationally efficient and applicable to 3-D TLFWI problems. Then, we reformulate TLFWI in the framework of HiEKF (termed hereafter as TLFWI-HiEKF) to predict time-lapse images of subsurface spatiotemporal velocity changes and simultaneously quantify the uncertainty of the inverted velocity changes over time. We demonstrate the validity and applicability of TLFWI–HiEKF with two realistic CO2 monitoring models derived from Frio-II and Cranfield CO2 injection sites, respectively. In both 2-D and 3-D examples, the inverted high-resolution time-lapse velocity results clearly reveal a continuous velocity reduction due to the injection of CO2. Moreover, the accuracy of the model is increasing over time by assimilating more time-lapse data while the standard deviation is decreasing over lapsed time. We expect TLFWI-HiEKF to be equipped with real-time seismic monitoring systems for continuously imaging the distribution of subsurface gas and fluids in the future large-scale CO2 sequestration experiments and reservoir management.

58 GEOSCIENCES↗
DOE OSTI2025

Why Is Attention Sparse In Particle Transformer?

Transformer-based models have achieved state-of-the-art performance in jet tagging at the CERN Large Hadron Collider (LHC), with the Particle Transformer (ParT) representing a leading example of such models. A striking feature of ParT is its sparse, nearly binary, attention structure, raising questions about the origin of this behavior and whether it encodes physically meaningful correlations. In this work, we investigate the source of ParT's sparse attention by comparing models trained on multiple benchmark datasets and examine the relative contributions of the attention term and the physics-inspired interaction matrix before softmax. We find that binary sparsity arises primarily from the attention mechanism itself, with the interaction matrix playing a secondary role. Moreove, we show that ParT is able to identify key jet substructure elements, such as leptons in semileptonic top decays, even without explicit particle identification inputs. These results provide new insight into the interpretability of transformer-based jet taggers and clarify the conditions under which sparse attention patterns emerge in ParT.

Legge, Timothy [UC, San Diego]↗
NASA NTRS1989

Data traffic reduction schemes for Cholesky factorization on asynchronous multiprocessor systems

Communication requirements of Cholesky factorization of dense and sparse symmetric, positive definite matrices are analyzed. The communication requirement is characterized by the data traffic generated on multiprocessor systems with local and shared memory. Lower bound proofs are given to show that when the load is uniformly distributed the data traffic associated with factoring an n x n dense matrix using n to the alpha power (alpha less than or equal 2) processors is omega(n to the 2 + alpha/2 power). For n x n sparse matrices representing a square root of n x square root of n regular grid graph the data traffic is shown to be omega(n to the 1 + alpha/2 power), alpha less than or equal 1. Partitioning schemes that are variations of block assignment scheme are described and it is shown that the data traffic generated by these schemes are asymptotically optimal. The schemes allow efficient use of up to O(n to the 2nd power) processors in the dense case and up to O(n) processors in the sparse case before the total data traffic reaches the maximum value of O(n to the 3rd power) and O(n to the 3/2 power), respectively. It is shown that the block based partitioning schemes allow a better utilization of the data accessed from shared memory and thus reduce the data traffic than those based on column-wise wrap around assignment schemes.

Naik, Vijay K.↗
DOE OSTI2021

Butterfly Factorization Via Randomized Matrix-Vector Multiplications

This paper presents an adaptive randomized algorithm for computing the butterfly factorization of an m × n matrix with m ≈ n provided that both the matrix and its transpose can be rapidly applied to arbitrary vectors. The resulting factorization is composed of O(log n) sparse factors, each containing O(n) nonzero entries. The factorization can be attained using O(n 3/2 log n) computation and O(n log n) memory resources. Furthermore, the proposed algorithm can be implemented in parallel and can apply to matrices with strong or weak admissibility conditions arising from surface integral equation solvers as well as multi-frontal-based finite-difference, finite-element, or finite-volume solvers. A distributed-memory parallel implementation of the algorithm demonstrates excellent scaling behavior.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1984

Algorithms for solving large sparse systems of simultaneous linear equations on vector processors

Very efficient algorithms for solving large sparse systems of simultaneous linear equations have been developed for serial processing computers. These involve a reordering of matrix rows and columns in order to obtain a near triangular pattern of nonzero elements. Then an LU factorization is developed to represent the matrix inverse in terms of a sequence of elementary Gaussian eliminations, or pivots. In this paper it is shown how these algorithms are adapted for efficient implementation on vector processors. Results obtained on the CYBER 200 Model 205 are presented for a series of large test problems which show the comparative advantages of the triangularization and vector processing algorithms.

David, R. E.↗
DOE OSTI2024

Sparsity-Independent Lyapunov Exponent in the Sachdev-Ye-Kitaev Model

The saturation of a recently proposed universal bound on the Lyapunov exponent has been conjectured to signal the existence of a gravity dual. This saturation occurs in the low-temperature limit of the dense Sachdev-Ye-Kitaev (SYK) model, N Majorana fermions with q body ( q > 2 ) infinite-range interactions. We calculate certain out-of-time-order correlators (OTOCs) for N ≤ 64 fermions for a highly sparse SYK model and find no significant dependence of the Lyapunov exponent on sparsity up to near the percolation limit where the Hamiltonian breaks up into blocks. This provides strong support to the saturation of the Lyapunov exponent in the low-temperature limit of the sparse SYK. A key ingredient to reaching N = 64 is the development of a novel quantum spin model simulation library that implements highly optimized matrix-free Krylov subspace methods on graphical processing units. This leads to a significantly lower simulation time as well as vastly reduced memory usage over previous approaches, while using modest computational resources. Strong sparsity-driven statistical fluctuations require both the use of a much larger number of disorder realizations with respect to the dense limit and a careful finite size scaling analysis. The saturation of the bound in the sparse SYK points to the existence of a gravity analog that would enlarge substantially the number of field theories with this feature. Published by the American Physical Society 2024

Physics↗
NASA NTRS1994

Rarefied solids

One important limit to creating low density materials is the objects' own weight. As a solid or colloidal matrix becomes more rarefied, gravity acts destructively to compress its suporting skeleton. We describe experimental results and propose a model which matches the low gravity behavior of rarefied or fractal solids. On parabolic airplane flights, we sought to demonstrate a key component of producing higher surface area fractals. Flight paths were selected to give a range of gravity levels: 0.01 g/g(sub 0) (low), 0.16 g(sub 0) (Lunar), 0.33 g/g(sub 0) (Martian), 1 g/g(sub 0) (Earth) and 1.8 g/g(sub 0) (high) (where g(sub 0) = 980 cm/sq s). Results using the model material of hydrophobic silica indicated that stable agglomeration of such tenuous objects can increase markedly in reduced gravity. Optical characterization revealed that fractal dimension changed directly with varying gravity. As measured by fractal dimension, effective surface area and roughness increased by 40% in low gravity. This finding supports the conclusion that relieving internal weight stresses on delicate aggregates can enhance their overall size (by two orders of magnitude) and internal surface area. We conclude that gravitational restructuring limits the overall size and void content of low-density solids. These sparse colloidal regimes may present new and technologically attractive physics, ranging from improved insulators, liquid-like tension in a 'solid' matrix, and characteristically low conductivities for sound and (8 to 14 micrometers wavelength) infrared radiation.

Noever, D. A.↗
DOE OSTI2023

MFiX: Fractional-Step Method Implementation

A comprehensive, multiphase computational fluid dynamics (CFD) simulation solves several coupled transport equations including continuity, momentum, species, and energy. Chemical reactions further couple these equations through heats of reaction and rates of formation of products and rates of destruction of reactants. A fractional-step method separates changes attributed to chemical reactions from transport phenomena like convection and diffusion. When the governing equations are split into the transport and reacting components, efficient and independent methodologies can be exploited to solve the different systems. Specifically, discretization of field variable transport equations results in large, sparse matrices which are loosely coupled. These systems are solved in succession using iterative techniques that take advantage of the matrix structure. In contrast, chemical reactions tightly couple field variables locally within the domain (e.g., within a single computational cell) resulting in low dimensional but dense, nonlinear systems that are better solved using direct integration techniques.

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

Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices

Many standard linear algebra problems can be solved on a quantum computer by using recently developed quantum linear algebra algorithms that make use of block encodings and quantum eigenvalue/singular value transformations. A block encoding embeds a properly scaled matrix of interest A in a larger unitary transformation U that can be decomposed into a product of simpler unitaries and implemented efficiently on a quantum computer. Although quantum algorithms can potentially achieve exponential speedup in solving linear algebra problems compared to the best classical algorithm, such a gain in efficiency ultimately hinges on our ability to construct an efficient quantum circuit for the block encoding of A, which is difficult in general, and not trivial even for well structured sparse matrices. Here, in this paper, we give a few examples on how efficient quantum circuits can be explicitly constructed for some well structured sparse matrices and discuss a few strategies used in these constructions. We also provide implementations of these quantum circuits in MATLAB.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1985

Multiprocessor sparse L/U decomposition with controlled fill-in

Generation of the maximal compatibles of pivot elements for a class of small sparse matrices is studied. The algorithm involves a binary tree search and has a complexity exponential in the order of the matrix. Different strategies for selection of a set of compatible pivots based on the Markowitz criterion are investigated. The competing issues of parallelism and fill-in generation are studied and results are provided. A technque for obtaining an ordered compatible set directly from the ordered incompatible table is given. This technique generates a set of compatible pivots with the property of generating few fills. A new hueristic algorithm is then proposed that combines the idea of an ordered compatible set with a limited binary tree search to generate several sets of compatible pivots in linear time. Finally, an elimination set to reduce the matrix is selected. Parameters are suggested to obtain a balance between parallelism and fill-ins. Results of applying the proposed algorithms on several large application matrices are presented and analyzed.

Alaghband, G.↗
NASA NTRS2019

Electromagnetic Scattering by Discrete Random Media. III: The Vector Radiative Transfer Equation

A vector radiative transfer equation with an additional source term typical of dense media is obtained. The analysis includes (i) the derivation of an integral equation for the correlation matrix of the exciting field coefficients accounting for the correlation between the particles, (ii) the derivation of an integral representation for the specific coherency dyadicin terms of this matrix, and (iii) the simplification of the integral equation for the correlation matrix and of the integral representation for the specific coherency dyadic by employing a series of approximations which are characteristic of sparse media.

Adrian Doicu↗
NASA NTRS2002

Bench top interferometric test bed for LISA

Adaptive optics systems with Shack-Hartmann wavefront sensors require reconstruction of the atmospheric phase error from slope measurements, with every sensor in the array being used in the computation of each actuator command. This fully populated reconstruction matrix can result in a significant computational burden for adaptive optics systems with large numbers of actuators. A method for generating sparse wavefront reconstruction matrices for adaptive optics is proposed. The method exploits the relevance of nearby slope measurements for control of an individual actuator, and relies upon the limited extent of the influence function for a zonal deformable mirror. Relying only on nearby sensor information can significantly reduce the calculation time for wavefront reconstruction. In addition, a hierarchic controller is proposed to recover some of the global wavefront information. The performance of these sparse wavefront reconstruction matrices was evaluated in simulation, and tested on the Palomar Adaptive Optics System. This paper will present some initial results from the simulations and experiments.

LISA↗
DOE OSTI2026

A GPU-based compressible combustion solver for applications exhibiting disparate space and time scales

High-speed chemically active flows pose significant computational challenges due to their disparate space and time scales, with stiff chemistry often dominating simulation time. While modern scientific computing programs achieve exascale performance by leveraging graphics processing units (GPUs), existing GPU-based compressible combustion solvers face critical limitations in memory management, load balancing, and handling the highly localized nature of chemical reactions. To this end, we present a high-performance compressible reacting flow solver built on the AMReX framework and optimized for multi-GPU settings. Here, our approach addresses three GPU performance bottlenecks: memory access patterns through column-major storage optimization, computational workload variability via a bulk-sparse integration strategy for chemical kinetics, and multi-GPU load distribution for adaptive mesh refinement applications. The solver adapts existing matrix-based chemical kinetics formulations to multi-grid contexts. Using representative combustion applications, including 2D and 3D detonations and a 3D jet-in-crossflow configuration, we demonstrate 1.4–5× performance improvements over initial implementations on an in-house cluster of NVIDIA H100 GPUs, and near-ideal weak scaling on the Frontier supercomputer (Oak Ridge Leadership Computing Facility) with up to 1024 AMD Instinct MI250X GPUs. Roofline analysis reveals substantial improvements in arithmetic intensity for both convection (∼ 10 ×) and chemistry (∼ 4 ×) routines, confirming efficient utilization of GPU memory bandwidth and computational resources.

42 ENGINEERING↗
NASA NTRS1985

Iterative solution of large, sparse linear systems on a static data flow architecture - Performance studies

The applicability of static data flow architectures to the iterative solution of sparse linear systems of equations is investigated. An analytic performance model of a static data flow computation is developed. This model includes both spatial parallelism, concurrent execution in multiple PE's, and pipelining, the streaming of data from array memories through the PE's. The performance model is used to analyze a row partitioned iterative algorithm for solving sparse linear systems of algebraic equations. Based on this analysis, design parameters for the static data flow architecture as a function of matrix sparsity and dimension are proposed.

Reed, D. A.↗
DOE OSTI2024

MAGMA: Enabling exascale performance with accelerated BLAS and LAPACK for diverse GPU architectures

MAGMA (Matrix Algebra for GPU and Multicore Architectures) is a pivotal open-source library in the landscape of GPU-enabled dense and sparse linear algebra computations. With a repertoire of approximately 750 numerical routines across four precisions, MAGMA is deeply ingrained in the DOE software stack, playing a crucial role in high-performance computing. Notable projects such as ExaConstit, HiOP, MARBL, and STRUMPACK, among others, directly harness the capabilities of MAGMA. In addition, the MAGMA development team has been acknowledged multiple times for contributing to the vendors’ numerical software stacks. Looking back over the time of the Exascale Computing Project (ECP), we highlight how MAGMA has adapted to recent changes in modern HPC systems, especially the growing gap between CPU and GPU compute capabilities, as well as the introduction of low precision arithmetic in modern GPUs. We also describe MAGMA’s direct impact on several ECP projects. Maintaining portable performance across NVIDIA and AMD GPUs, and with current efforts toward supporting Intel GPUs, MAGMA ensures its adaptability and relevance in the ever-evolving landscape of GPU architectures.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1995

A Hybrid Finite Element Method for Axisymmetric Waveguide fed Horns

A new method for finding radiation patterns and the reflection coefficients associated with an axisymmetric waveguide fed horn is presented. The approach is based on a hybrid finite element method (FEM) wherein the electromagnetic fields in the FEM region are coupled to the fields outside by two surface integral equations. Because of the local nature of the FEM, this formalism allows for the presence of inhomogeneities to be included in the problem domain. The matrix equation which results from the application of this method is shown to be complex-symmetric. It is, furthermore, diagonally dominant and sparse. Comparisons of calculated and measured data for two different horns show good agreement.

Hybrid↗