SEARCH · Engineering Papers

Results for “sparse matrices”

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.

SourceResearch connectionFrom yearThrough year

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 37 records · Page 2

All sources NASA NTRS DOE OSTI

DOE OSTI2022

SparseLU, A Novel Algorithm and Math Library for Sparse LU Factorization

Decomposing sparse matrices into lower and upper triangular matrices (sparse LU factorization) is a key operation in many computational scientific applications. We developed SparseLU, a sparse linear algebra library that implements a new algorithm for LU factorization on general sparse matrices. The new algorithm divides the input matrix into tiles to which OpenMP tasks are created for factorization computation, where only tiles that contain nonzero elements are computed. For comparative performance analysis, we used the reference library SuperLU. Testing was performed on synthetically generated matrices which replicate the conditions of the real-world matrices. SparseLU is able to reach a mean speedup of ~29× compared to SuperLU.

Valero Lara, Pedro↗

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↗

NASA NTRS1992

Large-scale sparse singular value computations

Four numerical methods for computing the singular value decomposition (SVD) of large sparse matrices on a multiprocessor architecture are presented. Lanczos and subspace iteration-based methods for determining several of the largest singular triplets (singular values and corresponding left and right-singular vectors) for sparse matrices arising from two practical applications: information retrieval and seismic reflection tomography are emphasized. The target architectures for implementations are the CRAY-2S/4-128 and Alliant FX/80. The sparse SVD problem is well motivated by recent information-retrieval techniques in which dominant singular values and their corresponding singular vectors of large sparse term-document matrices are desired, and by nonlinear inverse problems from seismic tomography applications which require approximate pseudo-inverses of large sparse Jacobian matrices.

Berry, Michael W.↗

NASA NTRS1992

A performance study of sparse Cholesky factorization on INTEL iPSC/860

The problem of Cholesky factorization of a sparse matrix has been very well investigated on sequential machines. A number of efficient codes exist for factorizing large unstructured sparse matrices. However, there is a lack of such efficient codes on parallel machines in general, and distributed machines in particular. Some of the issues that are critical to the implementation of sparse Cholesky factorization on a distributed memory parallel machine are ordering, partitioning and mapping, load balancing, and ordering of various tasks within a processor. Here, we focus on the effect of various partitioning schemes on the performance of sparse Cholesky factorization on the Intel iPSC/860. Also, a new partitioning heuristic for structured as well as unstructured sparse matrices is proposed, and its performance is compared with other schemes.

Zubair, M.↗

DOE OSTI2020

Reducing Communication in Graph Neural Network Training

Graph Neural Networks (GNNs) are powerful and flexible neural networks that use the naturally sparse connectivity information of the data. GNNs represent this connectivity as sparse matrices, which have lower arithmetic intensity and thus higher communication costs compared to dense matrices, making GNNs harder to scale to high concurrencies than convolutional or fully-connected neural networks. Here, we introduce a family of parallel algorithms for training GNNs and show that they can asymptotically reduce communication compared to previous parallel GNN training methods. We implement these algorithms, which are based on 1D, 1. 5D, 2D, and 3D sparse-dense matrix multiplication, using torch.distributed on GPU-equipped clusters. Our algorithms optimize communication across the full GNN training pipeline. We train GNNs on over a hundred GPUs on multiple datasets, including a protein network with over a billion edges.

97 MATHEMATICS AND COMPUTING↗

NASA NTRS1992

Iterative methods for large scale static analysis of structures on a scalable multiprocessor supercomputer

A parallel Preconditioned Conjugate Gradient (PCG) iterative solver has been developed and implemented on the iPSC-860 scalable hypercube. This new implementation makes use of the Parallel Automated Runtime Toolkit at ICASE (PARTI) primitives to efficiently program irregular communications patterns that exist in general sparse matrices and in particular in the finite element sparse stiffness matrices. The iterative PCG has been used to solve the finite element equations that result from discretizing large scale aerospace structures. In particular, the static response of the High Speed Civil Transport (HSCT) finite element model is solved on the iPSC-860.

Sobh, Nahil Atef↗

DOE OSTI2025

Accelerating GNNs on GPU Sparse Tensor Cores through N:M Sparsity-Oriented Graph Reordering

Recent advancements in GPU hardware support have introduced the capability to leverage N:M sparse patterns for substantial performance gains. Graphs in Graph Neural Networks (GNNs) are typically sparse, but the sparsity is often irregular, not conforming to such sparse patterns. In this paper, we propose a novel graph reordering algorithm, the first of its kind, to reshape irregular graph data into the N:M structured sparse pattern at the tile level, allowing linear-algebra-based graph operations in GNNs to benefit from the N:M sparse hardware. The optimization is lossless, maintaining the accuracy of GNN. It can remove 98-100\% violations of the N:M sparse patterns at the vector level, and increase the proportion of conforming graphs in SuiteSparse collection from 5-9\% to 88.7-93.5\%. On A100 GPUs, the optimization accelerates Sparse Matrix Matrix (SpMM) by up to 43X (2.3X -- 7.5X on average) and speeds up the key graph operations in GNNs on real graphs by as much as 8.6X (3.5X on average).

artificial intelligence, graph neural networks↗

DOE OSTI2021

Dynamics of disordered mechanical systems with large connectivity, free probability theory, and quasi-Hermitian random matrices

Disordered mechanical systems with high connectivity represent a limit opposite to the more familiar case of disordered crystals. Individual ions in a crystal are subjected essentially to nearest-neighbor interactions. In contrast, the systems studied in this paper have all their degrees of freedom coupled to each other. Thus, the problem of linearized small oscillations of such systems involves two full positive-definite and non-commuting matrices, as opposed to the sparse matrices associated with disordered crystals. Consequently, the familiar methods for determining the averaged vibrational spectra of disordered crystals, introduced many years ago by Dyson and Schmidt, are inapplicable for highly connected disordered systems. In this paper we apply random matrix theory (RMT) to calculate the averaged vibrational spectra of such systems, in the limit of infinitely large system size. At the heart of our analysis lies a calculation of the average spectrum of the product of two positive definite random matrices by means of free probability theory techniques. We also show that this problem is intimately related with quasi-hermitian random matrix theory (QHRMT), which means that the ‘hamiltonian’ matrix is hermitian with respect to a non-trivial metric. This extends ordinary hermitian matrices, for which the metric is simply the unit matrix. The analytical results we obtain for the spectrum agree well with our numerical results. The latter also exhibit oscillations at the high-frequency band edge, which fit well the Airy kernel pattern. We also compute inverse participation ratios of the corresponding amplitude eigenvectors and demonstrate that they are all extended, in contrast with conventional disordered crystals. Finally, we compute the thermodynamic properties of the system from its spectrum of vibrations. In addition to matrix model analysis, we also study the vibrational spectra of various multi-segmented disordered pendula, as concrete realizations of highly connected mechanical systems. A universal feature of the density of vibration modes, common to both pendula and the matrix model, is that it tends to a non-zero constant at vanishing frequency.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

NASA NTRS1990

SPARSKIT: A basic tool kit for sparse matrix computations

Presented here are the main features of a tool package for manipulating and working with sparse matrices. One of the goals of the package is to provide basic tools to facilitate the exchange of software and data between researchers in sparse matrix computations. The starting point is the Harwell/Boeing collection of matrices for which the authors provide a number of tools. Among other things, the package provides programs for converting data structures, printing simple statistics on a matrix, plotting a matrix profile, and performing linear algebra operations with sparse matrices.

Saad, Youcef↗

NASA NTRS1992

Multivariable frequency domain identification via 2-norm minimization

The author develops a computational approach to multivariable frequency domain identification, based on 2-norm minimization. In particular, a Gauss-Newton (GN) iteration is developed to minimize the 2-norm of the error between frequency domain data and a matrix fraction transfer function estimate. To improve the global performance of the optimization algorithm, the GN iteration is initialized using the solution to a particular sequentially reweighted least squares problem, denoted as the SK iteration. The least squares problems which arise from both the SK and GN iterations are shown to involve sparse matrices with identical block structure. A sparse matrix QR factorization method is developed to exploit the special block structure, and to efficiently compute the least squares solution. A numerical example involving the identification of a multiple-input multiple-output (MIMO) plant having 286 unknown parameters is given to illustrate the effectiveness of the algorithm.

Bayard, David S.↗

DOE OSTI2021

Communication-Avoiding and Memory-Constrained Sparse Matrix-Matrix Multiplication at Extreme Scale

Sparse matrix-matrix multiplication (SpGEMM) is a widely used kernel in various graph, scientific computing and machine learning algorithms. In this paper, we consider SpGEMMs performed on hundreds of thousands of processors generating trillions of nonzeros in the output matrix. Distributed SpGEMM at this extreme scale faces two key challenges: (1) high communication cost and (2) inadequate memory to generate the output. Furthermore, we address these challenges with an integrated communication-avoiding and memory-constrained SpGEMM algorithm that scales to 262,144 cores (more than 1 million hardware threads) and can multiply sparse matrices of any size as long as inputs and a fraction of output fit in the aggregated memory. As we go from 16,384 cores to 262,144 cores on a Cray XC40 supercomputer, the new SpGEMM algorithm runs 10x faster when multiplying large-scale protein-similarity matrices.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2026

Quantum block encoding for one-pair semiseparable matrices

Quantum block encoding (QBE) is a crucial step in the development of most quantum algorithms, as it provides an embedding of a given matrix into a suitable larger unitary matrix. Historically, the development of efficient techniques for QBE has mostly focused on sparse matrices; less effort has been devoted to data-sparse (e.g., rank-structured) matrices. In this work we examine a particular case of rank structure, namely, one-pair semiseparable matrices. We present a new block encoding approach that relies on a suitable factorization of the given matrix as the product of triangular and diagonal factors. To encode the matrix, the algorithm needs $2\log(N)+7$ ancillary qubits. Assuming that the data input oracles can be implemented with polylogarithmic depth, or that a QRAM input model is available, our proposed method requires $\mathcal{O}({\rm polylog} (N))$ time and has an error of $\mathcal{O}(N^2)$, where $N$ is the matrix size.

Antonioli, Giacomo [Pisa U.; CERN] (ORCID:00090000↗

NASA NTRS1975

An interactive graphics package for the automatic node renumbering of finite element matrices

An interactive graphics software package which allows users to display the non-zero structure of large sparse symmetric materials was described and methods used to implement it as a portable FORTRAN callable subroutine were summarized. In particular, the system permits the display of the resulting matrix after reordering the rows and columns, with the reordering scheme either defined by the user or automatically generated by the program with the aim of reducing matrix bandwidth and profile. Although the primary application of the package has been to the finite element analysis of structures, it is equally well suited to the many other areas of engineering and science which use sparse matrices.

Boisvert, R. F.↗

NASA NTRS1977

Matrix computations in MACSYMA

Facilities built into MACSYMA for manipulating matrices with numeric or symbolic entries are described. Computations will be done exactly, keeping symbols as symbols. Topics discussed include how to form a matrix and create other matrices by transforming existing matrices within MACSYMA; arithmetic and other computation with matrices; and user control of computational processes through the use of optional variables. Two algorithms designed for sparse matrices are given. The computing times of several different ways to compute the determinant of a matrix are compared.

Wang, P. S.↗

NASA NTRS1985

Supercomputing on massively parallel bit-serial architectures

Research on the Goodyear Massively Parallel Processor (MPP) suggests that high-level parallel languages are practical and can be designed with powerful new semantics that allow algorithms to be efficiently mapped to the real machines. For the MPP these semantics include parallel/associative array selection for both dense and sparse matrices, variable precision arithmetic to trade accuracy for speed, micro-pipelined train broadcast, and conditional branching at the processing element (PE) control unit level. The preliminary design of a FORTRAN-like parallel language for the MPP has been completed and is being used to write programs to perform sparse matrix array selection, min/max search, matrix multiplication, Gaussian elimination on single bit arrays and other generic algorithms. A description is given of the MPP design. Features of the system and its operation are illustrated in the form of charts and diagrams.

Iobst, Ken↗

NASA NTRS1989

Sparse Gaussian elimination with controlled fill-in on a shared memory multiprocessor

It is shown that in sparse matrices arising from electronic circuits, it is possible to do computations on many diagonal elements simultaneously. A technique for obtaining an ordered compatible set directly from the ordered incompatible table is given. The ordering is based on the Markowitz number of the pivot candidates. This technique generates a set of compatible pivots with the property of generating few fills. A novel heuristic algorithm is presented that combines the idea of an order-compatible set with a limited binary tree search to generate several sets of compatible pivots in linear time. An elimination set for reducing the matrix is generated and selected on the basis of a minimum Markowitz sum number. The parallel pivoting technique presented is a stepwise algorithm and can be applied to any submatrix of the original matrix. Thus, it is not a preordering of the sparse matrix and is applied dynamically as the decomposition proceeds. Parameters are suggested to obtain a balance between parallelism and fill-ins. Results of applying the proposed algorithms on several large application matrices using the HEP multiprocessor (Kowalik, 1985) are presented and analyzed.

Alaghband, Gita↗

DOE OSTI2023

Feeder Power Disaggregation: A Data-Efficient Matrix Completion Approach: Preprint

This paper presents a data-driven algorithm for the feeder power disaggregation problem in distribution systems. Leveraging spatio-temporal power patterns in residential homes, residential power is discomposed into three components: sparse-switching loads, periodic loads, and photovoltaic generation, using two sparse matrices and a rank-one matrix. The matrix completion process is data-efficient because of the matrix sparsity and low rankness, along with the use of power system models. The proposed approach is tested using real-world residential datasets on a 33-bus distribution system, demonstrating accurate power disaggregation with efficient matrix completion.

distribution system↗

DOE OSTI2023

Feeder Power Disaggregation: A Data-Efficient Matrix Completion Approach

This paper presents a data-driven algorithm for the feeder power disaggregation problem in distribution systems. Leveraging spatio-temporal power patterns in residential homes, residential power is discomposed into three components: sparse-switching loads, periodic loads, and photovoltaic (PV) generation, which are characterized through the design of two sparse matrices and a low-rank matrix. The matrix completion process is data-efficient because of the matrix sparsity and low rankness, along with the use of power system models. The proposed approach is tested using real-world residential data set on a 33-bus distribution system, demonstrating accurate power disaggregation with efficient matrix completion.

distribution system↗