Search NASA⌕ Search

SEARCH · Search NASA

Results for “Sparse matrix techniques”

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 19 records
All sourcesNASA NTRSDOE OSTI
NASA NTRS1975

Sparse matrix techniques applied to modal analysis of multi-section duct liners

A simplified procedure is presented for analysis of ducts with discretely nonuniform properties. The analysis uses basis functions as the generalized coordinates. The duct eigenfunctions are approximated by finite series of these functions. The emphasis is on solution of the resulting large sparse set of linear equations. Characteristics of sparse matrix algorithms are outlined and some criteria for application are established. Analogies with structural methods are used to illustrate variations which can increase efficiency in generating values for design optimization routines. The effects of basis function selection, number of eigenfunctions and identification and ordering of equations on the sparsity and solution stability are included.

Arnold, W. R.↗
NASA NTRS1994

Solution of matrix equations using sparse techniques

The solution of large systems of matrix equations is key to the solution of a large number of scientific and engineering problems. This talk describes the sparse matrix solver developed at Langley which can routinely solve in excess of 263,000 equations in 40 seconds on one Cray C-90 processor. It appears that for large scale structural analysis applications, sparse matrix methods have a significant performance advantage over other methods.

Baddourah, Majdi↗
NASA NTRS1989

Sparse matrix methods research using the CSM testbed software system

Research is described on sparse matrix techniques for the Computational Structural Mechanics (CSM) Testbed. The primary objective was to compare the performance of state-of-the-art techniques for solving sparse systems with those that are currently available in the CSM Testbed. Thus, one of the first tasks was to become familiar with the structure of the testbed, and to install some or all of the SPARSPAK package in the testbed. A suite of subroutines to extract from the data base the relevant structural and numerical information about the matrix equations was written, and all the demonstration problems distributed with the testbed were successfully solved. These codes were documented, and performance studies comparing the SPARSPAK technology to the methods currently in the testbed were completed. In addition, some preliminary studies were done comparing some recently developed out-of-core techniques with the performance of the testbed processor INV.

Chu, Eleanor↗
DOE OSTI2015

Modeling optical properties of silicon clusters by first principles: From a few atoms to large nanocrystals

Time dependent density functional tight binding (TDDFTB) method is implemented with sparse matrix techniques and improved parallelization algorithms. The method is employed to calculate the optical properties of various Si nanocrystals (NCs). The calculated light absorption spectra of small Si NCs from TDDFTB were found to be comparable with many body perturbation methods utilizing planewave basis sets. For large Si NCs (more than a thousand atoms) that are beyond the reach of conventional approaches, the TDDFTB method is able to produce reasonable results that are consistent with prior experiments. We also employed the method to study the effects of surface chemistry on the optical properties of large Si NCs. We learned that the optical properties of Si NCs can be manipulated with small molecule passivations such as methyl, hydroxyl, amino, and fluorine. In general, the shifts and profiles in the absorption spectra can be tuned with suitably chosen passivants.

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

Disconnected Diagrams in Lattice QCD

In this work, we present state-of-the-art numerical methods and their applications for computing a particular class of observables using lattice quantum chromodynamics (Lattice QCD), a discretized version of the fundamental theory of quarks and gluons. These observables require calculating so called \disconnected diagrams" and are important for understanding many aspects of hadron structure, such as the strange content of the proton. We begin by introducing the reader to the key concepts of Lattice QCD and rigorously define the meaning of disconnected diagrams through an example of the Wick contractions of the nucleon. Subsequently, the calculation of observables requiring disconnected diagrams is posed as the computationally challenging problem of finding the trace of the inverse of an incredibly large, sparse matrix. This is followed by a brief primer of numerical sparse matrix techniques that overviews broadly used methods in Lattice QCD and builds the background for the novel algorithm presented in this work. We then introduce singular value deflation as a method to improve convergence of trace estimation and analyze its effects on matrices from a variety of fields, including chemical transport modeling, magnetohydrodynamics, and QCD. Finally, we apply this method to compute observables such as the strange axial charge of the proton and strange sigma terms in light nuclei. The work in this thesis is innovative for four reasons. First, we analyze the effects of deflation with a model that makes qualitative predictions about its effectiveness, taking only the singular value spectrum as input, and compare deflated variance with different types of trace estimator noise. Second, the synergy between probing methods and deflation is investigated both experimentally and theoretically. Third, we use the synergistic combination of deflation and a graph coloring algorithm known as hierarchical probing to conduct a lattice calculation of light disconnected matrix elements of the nucleon at two different values of the lattice spacing. Finally, we employ these algorithms to do a high-precision study of strange sigma terms in light nuclei; to our knowledge this is the first calculation of its kind from Lattice QCD.

Gambhir, Arjun↗
NASA NTRS1991

Computing Gravitational Bumps From Repeating-Orbit Data

Iterative, least-squares algorithm efficiently computes estimates of both position errors indicative of irregularities in gravitational field of Earth and trajectory of satellite in orbit repeating along same ground track. Exploits sparse-matrix techniques. Useful in surveying, navigation, and geophysical research. Particularly useful for processing data on trajectory of satellite in low orbit tracked via Global Positioning System (GPS).

Wu, Jiun-Tsong↗
NASA NTRS1997

The Influence of Correlated Crustal Signals in Modelling the Main Geomagnetic Field

Algorithms used in geomagnetic main-field modelling have for the most part treated the noise in the field measurements as if it were white. A major component of the noise consists of the field due to magnetization in the crust and it has been realized for some time that such signals are highly correlated at satellite altitude. Hence approximation by white noise, while of undoubted utility, is of unknown validity. In this paper we study two plausible statistical models for the crustal magnetization, in which the magnetization is a realization of a stationary, isotropic, random process. At a typical satellite altitude the associated fields exhibit significant correlation over ranges as great as 15 deg. or more, which introduces off-diagonal elements into the covariance matrix, elements that have usually been neglected in modelling procedures. Dealing with a full covariance matrix for a large data set would present a formidable computational challenge, but fortunately most of the entries in the covariance matrix are so small that they can be replaced by zeros. The resultant matrix comprises only about 3 per cent non-zero entries and thus we can take advantage of efficient sparse matrix techniques to solve the numerical system. We construct several main-field models based on vertical-component data from a selected 5 deg. by 5 deg. data set derived from the Magsat mission. Models with and without off-diagonal terms are compared.

Rygaard-Hjalsted, C.↗
DOE OSTI2014

Robust parallel iterative solvers for linear and least-squares problems (Final Technical Report)

The primary goal of this project is to study and develop robust iterative methods for solving linear systems of equations and least squares systems. The focus of the Minnesota team is on algorithms development, robustness issues, and on tests and validation of the methods on realistic problems. 1. The project begun with an investigation on how to practically update a preconditioner obtained from an ILU-type factorization, when the coefficient matrix changes. 2. We investigated strategies to improve robustness in parallel preconditioners in a specific case of a PDE with discontinuous coefficients. 3. We explored ways to adapt standard preconditioners for solving linear systems arising from the Helmholtz equation. These are often difficult linear systems to solve by iterative methods. 4. We have also worked on purely theoretical issues related to the analysis of Krylov subspace methods for linear systems. 5. We developed an effective strategy for performing ILU factorizations for the case when the matrix is highly indefinite. The strategy uses shifting in some optimal way. The method was extended to the solution of Helmholtz equations by using complex shifts, yielding very good results in many cases. 6. We addressed the difficult problem of preconditioning sparse systems of equations on GPUs. 7. A by-product of the above work is a software package consisting of an iterative solver library for GPUs based on CUDA. This was made publicly available. It was the first such library that offers complete iterative solvers for GPUs. 8. We considered another form of ILU which blends coarsening techniques from Multigrid with algebraic multilevel methods. 9. We have released a new version on our parallel solver - called pARMS [new version is version 3]. As part of this we have tested the code in complex settings - including the solution of Maxwell and Helmholtz equations and for a problem of crystal growth.10. As an application of polynomial preconditioning we considered the problem of evaluating f(A)v which arises in statistical sampling. 11. As an application to the methods we developed, we tackled the problem of computing the diagonal of the inverse of a matrix. This arises in statistical applications as well as in many applications in physics. We explored probing methods as well as domain-decomposition type methods. 12. A collaboration with researchers from Toulouse, France, considered the important problem of computing the Schur complement in a domain-decomposition approach. 13. We explored new ways of preconditioning linear systems, based on low-rank approximations.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1977

SPAR: Structural-performance analysis and redesign

System of processor programs performs stress, buckling, and vibrational analysis of large linear finite element systems in excess of 50,000 degrees of freedom, while minimizing processing cost, execution time, central memory storage, and secondary data storage requirements. Programs use sparse matrix solution techniques and other computational and data management procedures.

Whetstone, W. D.↗
NASA NTRS1978

Structural performance analysis and redesign

Program performs stress buckling and vibrational analysis of large, linear, finite-element systems in excess of 50,000 degrees of freedom. Cost, execution time, and storage requirements are kept reasonable through use of sparse matrix solution techniques, and other computational and data management procedures designed for problems of very large size.

Whetstone, W. D.↗
NASA NTRS1994

Evaluation of several non-reflecting computational boundary conditions for duct acoustics

Several non-reflecting computational boundary conditions that meet certain criteria and have potential applications to duct acoustics are evaluated for their effectiveness. The same interior solution scheme, grid, and order of approximation are used to evaluate each condition. Sparse matrix solution techniques are applied to solve the matrix equation resulting from the discretization. Modal series solutions for the sound attenuation in an infinite duct are used to evaluate the accuracy of each non-reflecting boundary conditions. The evaluations are performed for sound propagation in a softwall duct, for several sources, sound frequencies, and duct lengths. It is shown that a recently developed nonlocal boundary condition leads to sound attenuation predictions considerably more accurate for short ducts. This leads to a substantial reduction in the number of grid points when compared to other non-reflecting conditions.

Watson, Willie R.↗
NASA NTRS2008

Sparse Regression as a Sparse Eigenvalue Problem

We extend the l0-norm "subspectral" algorithms for sparse-LDA [5] and sparse-PCA [6] to general quadratic costs such as MSE in linear (kernel) regression. The resulting "Sparse Least Squares" (SLS) problem is also NP-hard, by way of its equivalence to a rank-1 sparse eigenvalue problem (e.g., binary sparse-LDA [7]). Specifically, for a general quadratic cost we use a highly-efficient technique for direct eigenvalue computation using partitioned matrix inverses which leads to dramatic x103 speed-ups over standard eigenvalue decomposition. This increased efficiency mitigates the O(n4) scaling behaviour that up to now has limited the previous algorithms' utility for high-dimensional learning problems. Moreover, the new computation prioritizes the role of the less-myopic backward elimination stage which becomes more efficient than forward selection. Similarly, branch-and-bound search for Exact Sparse Least Squares (ESLS) also benefits from partitioned matrix inverse techniques. Our Greedy Sparse Least Squares (GSLS) generalizes Natarajan's algorithm [9] also known as Order-Recursive Matching Pursuit (ORMP). Specifically, the forward half of GSLS is exactly equivalent to ORMP but more efficient. By including the backward pass, which only doubles the computation, we can achieve lower MSE than ORMP. Experimental comparisons to the state-of-the-art LARS algorithm [3] show forward-GSLS is faster, more accurate and more flexible in terms of choice of regularization

Exact Sparse Least Squares (ESLS)↗
NASA NTRS1990

Constraint treatment techniques and parallel algorithms for multibody dynamic analysis

Computational procedures for kinematic and dynamic analysis of three-dimensional multibody dynamic (MBD) systems are developed from the differential-algebraic equations (DAE's) viewpoint. Constraint violations during the time integration process are minimized and penalty constraint stabilization techniques and partitioning schemes are developed. The governing equations of motion, a two-stage staggered explicit-implicit numerical algorithm, are treated which takes advantage of a partitioned solution procedure. A robust and parallelizable integration algorithm is developed. This algorithm uses a two-stage staggered central difference algorithm to integrate the translational coordinates and the angular velocities. The angular orientations of bodies in MBD systems are then obtained by using an implicit algorithm via the kinematic relationship between Euler parameters and angular velocities. It is shown that the combination of the present solution procedures yields a computationally more accurate solution. To speed up the computational procedures, parallel implementation of the present constraint treatment techniques, the two-stage staggered explicit-implicit numerical algorithm was efficiently carried out. The DAE's and the constraint treatment techniques were transformed into arrowhead matrices to which Schur complement form was derived. By fully exploiting the sparse matrix structural analysis techniques, a parallel preconditioned conjugate gradient numerical algorithm is used to solve the systems equations written in Schur complement form. A software testbed was designed and implemented in both sequential and parallel computers. This testbed was used to demonstrate the robustness and efficiency of the constraint treatment techniques, the accuracy of the two-stage staggered explicit-implicit numerical algorithm, and the speed up of the Schur-complement-based parallel preconditioned conjugate gradient algorithm on a parallel computer.

Chiou, Jin-Chern↗
NASA NTRS1989

Computational architecture for integrated controls and structures design

To facilitate the development of control structure interaction (CSI) design methodology, a computational architecture for interdisciplinary design of active structures is presented. The emphasis of the computational procedure is to exploit existing sparse matrix structural analysis techniques, in-core data transfer with control synthesis programs, and versatility in the optimization methodology to avoid unnecessary structural or control calculations. The architecture is designed such that all required structure, control and optimization analyses are performed within one program. Hence, the optimization strategy is not unduly constrained by cold starts of existing structural analysis and control synthesis packages.

Belvin, W. Keith↗
DOE OSTI2018

Tomographic analysis of tangential viewing cameras (invited)

Many tokamaks now use visible light cameras to observe plasma-wall interactions and integrated line emission. The DIII-D coherence imaging spectroscopy diagnostic cameras image interferograms that encode line integrated velocity. By modeling the 2D camera image pixels as line of sight integrals through an axisymmetric discrete grid, it is possible to do tomographic analysis to determine the local plasma line emissivity and parallel velocity. Approaches to solve the inverse problem posed by these tangential viewing cameras are presented. The inversion begins with calculation of the sparse response matrix that encompasses all the geometry and diagnostic information and reduces the process of image formation to a sparse matrix-vector multiply. Our report includes techniques for determining the detailed geometry of the camera views and methods for handling physical quantities that vary spatially. Additionally, the size of the response matrix has driven the development of capability to distribute the coarse parallel calculation across a heterogeneous cluster of computers on the Energy Sciences Network. Iterative techniques are then used to solve the sparse matrix-vector linear system

47 OTHER INSTRUMENTATION↗
NASA NTRS2002

Effects of Ordering Strategies and Programming Paradigms on Sparse Matrix Computations

The Conjugate Gradient (CG) algorithm is perhaps the best-known iterative technique to solve sparse linear systems that are symmetric and positive definite. For systems that are ill-conditioned, it is often necessary to use a preconditioning technique. In this paper, we investigate the effects of various ordering and partitioning strategies on the performance of parallel CG and ILU(O) preconditioned CG (PCG) using different programming paradigms and architectures. Results show that for this class of applications: ordering significantly improves overall performance on both distributed and distributed shared-memory systems, that cache reuse may be more important than reducing communication, that it is possible to achieve message-passing performance using shared-memory constructs through careful data ordering and distribution, and that a hybrid MPI+OpenMP paradigm increases programming complexity with little performance gains. A implementation of CG on the Cray MTA does not require special ordering or partitioning to obtain high efficiency and scalability, giving it a distinct advantage for adaptive applications; however, it shows limited scalability for PCG due to a lack of thread level parallelism.

Oliker, Leonid↗
DOE OSTI2022

SMALE: Enhancing Scalability of Machine Learning Algorithms on Extreme-Scale Computing Platforms

Deployment and execution of machine learning tasks on extreme-scale computing platforms face several significant technical challenges: 1) High computing cost incurred by dense networks – The computing workload of deep networks with densely-connected topology increases rapidly with the network size, imposing a non-scalable computing model of extreme-scale computing platforms; 2) Non-optimized workload distribution – Many advanced deep learning algorithms, e.g., sparsification and irregular net-work topology, produce very unbalanced workload distribution on extreme-scale computing platforms. The computation efficiency is greatly hindered by the incurred data and computation redundancies as well as long tails of the node with extensive workload; 3) Constraints in data movement and I/O bottle-neck – Inter-node data movement in extreme-scale computing platforms are associated with high energy and latency costs, and subject to the constraints of I/O bandwidth; and 4) Generalization of algorithm realization and acceleration on computing platforms – The large varieties of machine learning algorithms and structures of extreme-scale computing platforms make the derivation of a generalized algorithm realization and acceleration method very challenging, which, however, is the requirement by domain scientists and interested users. We call the above challenges Smale’s Problems in Machine Learning and Understanding for High-Performance Computing Scientific Discovery. The objective of our three-year research project is to develop a holistic innovation set at structure, assembly, and acceleration layers of machine learning algorithms to address the above challenges in algorithm deployment and execution. Three tasks are particularly performed, including: At the algorithm structure level, we investigate the techniques that can structurally sparsify on the topology of deep networks for computing workload reduction. We also study clustering and pruning techniques that can optimize the workload distributions over the extreme-scale computing platforms; At the algorithm assembly level, we derive a unified learning framework for unsupervised transfer learning and dynamic growing capabilities. Novel training methods are also exploited to enhance the training efficiency of the proposed framework; At the algorithm acceleration level, we will develop a series of techniques that can accelerate the computation of sparse matrix operations, which are one of the core executions in deep learning and optimize memory access of the concerned platforms. Our proposed techniques attack the fundamental problems in machine learning algorithms running on extreme-scale computing platforms by vertically integrating the solutions at three closely entangled layers, paving the long-term scaling path of machine learning applications under DOE context. Three tasks corresponding to the above respective research orientations are performed during the three-year project period with our collaborators at ORNL. The outcome of the proposed project is anticipated to form a holistic solution set of novel algorithms and network topologies, efficient training techniques, and fast acceleration methods to promote the computing scalability of the machine learning applications of particular interest to DOE.

97 MATHEMATICS AND COMPUTING↗