Search NASA⌕ Search

SEARCH · Search NASA

Results for “sparse”

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 127 records · Page 7

SU-C-207-03: Optimization of a Collimator-Based Sparse Sampling Technique for Low-Dose Cone-Beam CT

Purpose: In computed tomography (CT) imaging, radiation dose delivered to the patient is one of the major concerns. Sparse-view CT takes projections at sparser view angles and provides a viable option to reducing dose. However, a fast power switching of an X-ray tube, which is needed for the sparse-view sampling, can be challenging in many CT systems. We have earlier proposed a many-view under-sampling (MVUS) technique as an alternative to sparse-view CT. In this study, we investigated the effects of collimator parameters on the image quality and aimed to optimize the collimator design. Methods: We used a bench-top circular cone-beam CT system together with a CatPhan600 phantom, and took 1440 projections from a single rotation. The multi-slit collimator made of tungsten was mounted on the X-ray source for beam blocking. For image reconstruction, we used a total-variation minimization (TV) algorithm and modified the backprojection step so that only the measured data through the collimator slits are to be used in the computation. The number of slits and the reciprocation frequency have been varied and the effects of them on the image quality were investigated. We also analyzed the sampling efficiency: the sampling density and data incoherence in each case. We tested three sets of slits with their number of 6, 12 and 18, each at reciprocation frequencies of 10, 30, 50 and 70 Hz/ro. Results: Consistent results in the image quality have been produced with the sampling efficiency, and the optimum condition was found to be using 12 slits at 30 Hz/ro. As image quality indices, we used the CNR and the detectability. Conclusion: We conducted an experiment with a moving multi-slit collimator to realize a sparse-sampled cone-beam CT. Effects of collimator parameters on the image quality have been systematically investigated, and the optimum condition has been reached.

60 APPLIED LIFE SCIENCES↗

TH-EF-BRA-08: A Novel Technique for Estimating Volumetric Cine MRI (VC-MRI) From Multi-Slice Sparsely Sampled Cine Images Using Motion Modeling and Free Form Deformation

Purpose: To develop a technique to estimate on-board VC-MRI using multi-slice sparsely-sampled cine images, patient prior 4D-MRI, motion-modeling and free-form deformation for real-time 3D target verification of lung radiotherapy. Methods: A previous method has been developed to generate on-board VC-MRI by deforming prior MRI images based on a motion model(MM) extracted from prior 4D-MRI and a single-slice on-board 2D-cine image. In this study, free-form deformation(FD) was introduced to correct for errors in the MM when large anatomical changes exist. Multiple-slice sparsely-sampled on-board 2D-cine images located within the target are used to improve both the estimation accuracy and temporal resolution of VC-MRI. The on-board 2D-cine MRIs are acquired at 20–30frames/s by sampling only 10% of the k-space on Cartesian grid, with 85% of that taken at the central k-space. The method was evaluated using XCAT(computerized patient model) simulation of lung cancer patients with various anatomical and respirational changes from prior 4D-MRI to onboard volume. The accuracy was evaluated using Volume-Percent-Difference(VPD) and Center-of-Mass-Shift(COMS) of the estimated tumor volume. Effects of region-of-interest(ROI) selection, 2D-cine slice orientation, slice number and slice location on the estimation accuracy were evaluated. Results: VCMRI estimated using 10 sparsely-sampled sagittal 2D-cine MRIs achieved VPD/COMS of 9.07±3.54%/0.45±0.53mm among all scenarios based on estimation with ROI-MM-ROI-FD. The FD optimization improved estimation significantly for scenarios with anatomical changes. Using ROI-FD achieved better estimation than global-FD. Changing the multi-slice orientation to axial, coronal, and axial/sagittal orthogonal reduced the accuracy of VCMRI to VPD/COMS of 19.47±15.74%/1.57±2.54mm, 20.70±9.97%/2.34±0.92mm, and 16.02±13.79%/0.60±0.82mm, respectively. Reducing the number of cines to 8 enhanced temporal resolution of VC-MRI by 25% while maintaining the estimation accuracy. Estimation using slices sampled uniformly through the tumor achieved better accuracy than slices sampled non-uniformly. Conclusions: Preliminary studies showed that it is feasible to generate VC-MRI from multi-slice sparsely-sampled 2D-cine images for real-time 3D-target verification. This work was supported by the National Institutes of Health under Grant No. R01-CA184173 and a research grant from Varian Medical Systems.

60 APPLIED LIFE SCIENCES↗

Brief announcement: Hypergraph parititioning for parallel sparse matrix-matrix multiplication

The performance of parallel algorithms for sparse matrix-matrix multiplication is typically determined by the amount of interprocessor communication performed, which in turn depends on the nonzero structure of the input matrices. In this paper, we characterize the communication cost of a sparse matrix-matrix multiplication algorithm in terms of the size of a cut of an associated hypergraph that encodes the computation for a given input nonzero structure. Obtaining an optimal algorithm corresponds to solving a hypergraph partitioning problem. Furthermore, our hypergraph model generalizes several existing models for sparse matrix-vector multiplication, and we can leverage hypergraph partitioners developed for that computation to improve application-specific algorithms for multiplying sparse matrices.

97 MATHEMATICS AND COMPUTING↗

An Efficient Mixed-Mode Representation of Sparse Tensors

The Compressed Sparse Fiber (CSF) representation for sparse tensors is a generalization of the Compressed Sparse Row (CSR) format for sparse matrices. For a tensor with d modes, typical tensor methods such as CANDECOMP/PARAFAC decomposition (CPD) require a sequence of d tensor computations, where efficient memory access with respect to different modes is required for each of them.The straightforward solution is to use d distinct representations of the tensor, with each one being efficient for one of the d computations. However, a d-fold space overhead is often unacceptable in practice, especially with memory-constrained GPUs. In this paper, we present a mixed-mode tensor representation that partitions the tensor’s nonzero elements into disjoint sections, each of which is compressed to create fibers along a different mode. Experimental results on the latest generation of GPU device demonstrate that better performance can be achieved by using the mixed-mode representation, while utilizing only a small fraction of the space required to keep d distinct CSF representations.

Nisa, Israt↗

Elastic-Waveform Inversion with Compressive Sensing for Sparse Seismic Data

Accurate velocity models of compressional- and shear-waves are essential for geothermal reservoir characterization and microseismic imaging. Elastic-waveform inversion of multi-component seismic data can provide high-resolution inversion results of subsurface geophysical properties. However, the method requires seismic data acquired using dense source and receiver arrays. In practice, seismic sources and/or geophones are often sparsely distributed on the surface and/or in a borehole, such as 3D vertical seismic profiling (VSP) surveys. We develop a novel elastic-waveform inversion method with compressive sensing for inversion of sparse seismic data. We employ an alternating-minimization algorithm to solve the optimization problem of our new waveform inversion method. We validate our new method using synthetic VSP data for a geophysical model built using geologic features found at the Raft River enhanced-geothermal-system (EGS) field. We apply our method to synthetic VSP data with a sparse source array and compare the results with those obtained with a dense source array. Our numerical results demonstrate that the velocity models produced with our new method using a sparse source array are almost as accurate as those obtained using a dense source array.

58 GEOSCIENCES↗

Solving the $k$-Sparse Eigenvalue Problem with Reinforcement Learning

We examine the possibility of using a reinforcement learning (RL) algorithm to solve large-scale eigenvalue problems in which the desired the eigenvector can be approximated by a sparse vector with at most k nonzero elements, where k is relatively small compare to the dimension of the matrix to be partially diagonalized. Here, this type of problem arises in applications in which the desired eigenvector exhibits localization properties and in large-scale eigenvalue computations in which the amount of computational resource is limited. When the positions of these nonzero elements can be determined, we can obtain the k-sparse approximation to the original problem by computing eigenvalues of a k × k submatrix extracted from k rows and columns of the original matrix. We review a previously developed greedy algorithm for incrementally probing the positions of the nonzero elements in a k-sparse approximate eigenvector and show that the greedy algorithm can be improved by using an RL method to refine the selection of k rows and columns of the original matrix. We describe how to represent states, actions, rewards and policies in an RL algorithm designed to solve the k-sparse eigenvalue problem and demonstrate the effectiveness of the RL algorithm on two examples originating from quantum many-body physics.

97 MATHEMATICS AND COMPUTING↗

A sparse reconstruction method for the estimation of multi-resolution emission fields via atmospheric inversion

Atmospheric inversions are frequently used to estimate fluxes of atmospheric greenhouse gases (e.g., biospheric CO 2 flux fields) at Earth's surface. These inversions typically assume that flux departures from a prior model are spatially smoothly varying, which are then modeled using a multi-variate Gaussian. When the field being estimated is spatially rough, multi-variate Gaussian models are difficult to construct and a wavelet-based field model may be more suitable. Unfortunately, such models are very high dimensional and are most conveniently used when the estimation method can simultaneously perform data-driven model simplification (removal of model parameters that cannot be reliably estimated) and fitting. Such sparse reconstruction methods are typically not used in atmospheric inversions. In this work, we devise a sparse reconstruction method, and illustrate it in an idealized atmospheric inversion problem for the estimation of fossil fuel CO 2 (ffCO 2 ) emissions in the lower 48 states of the USA. Our new method is based on stagewise orthogonal matching pursuit (StOMP), a method used to reconstruct compressively sensed images. Our adaptations bestow three properties to the sparse reconstruction procedure which are useful in atmospheric inversions. We have modified StOMP to incorporate prior information on the emission field being estimated and to enforce non-negativity on the estimated field. Finally, though based on wavelets, our method allows for the estimation of fields in non-rectangular geometries, e.g., emission fields inside geographical and political boundaries. Our idealized inversions use a recently developed multi-resolution (i.e., wavelet-based) random field model developed for ffCO 2 emissions and synthetic observations of ffCO 2 concentrations from a limited set of measurement sites. We find that our method for limiting the estimated field within an irregularly shaped region is about a factor of 10 faster than conventional approaches. It also reduces the overall computational cost by a factor of 2. Further, the sparse reconstruction scheme imposes non-negativity without introducing strong nonlinearities, such as those introduced by employing log-transformed fields, and thus reaps the benefits of simplicity and computational speed that are characteristic of linear inverse problems.

54 ENVIRONMENTAL SCIENCES↗

Image fusion using sparse overcomplete feature dictionaries

Approaches for deciding what individuals in a population of visual system "neurons" are looking for using sparse overcomplete feature dictionaries are provided. A sparse overcomplete feature dictionary may be learned for an image dataset and a local sparse representation of the image dataset may be built using the learned feature dictionary. A local maximum pooling operation may be applied on the local sparse representation to produce a translation-tolerant representation of the image dataset. An object may then be classified and/or clustered within the translation-tolerant representation of the image dataset using a supervised classification algorithm and/or an unsupervised clustering algorithm.

97 MATHEMATICS AND COMPUTING↗

An Asynchronous Task-based Fan-Both Sparse Cholesky Solver

Systems of linear equations arise at the heart of many scientific and engineering applications. Many of these linear systems are sparse; i.e., most of the elements in the coefficient matrix are zero. Direct methods based on matrix factorizations are sometimes needed to ensure accurate solutions. For example, accurate solution of sparse linear systems is needed in shift-invert Lanczos to compute interior eigenvalues. The performance and resource usage of sparse matrix factorizations are critical to time-to-solution and maximum problem size solvable on a given platform. In many applications, the coefficient matrices are symmetric, and exploiting symmetry will reduce both the amount of work and storage cost required for factorization. When the factorization is performed on large-scale distributed memory platforms, communication cost is critical to the performance of the algorithm. At the same time, network topologies have become increasingly complex, so that modern platforms exhibit a high level of performance variability. This makes scheduling of computations an intricate and performance-critical task. In this paper, we investigate the use of an asynchronous task paradigm, one-sided communication and dynamic scheduling in implementing sparse Cholesky factorization (symPACK) on large-scale distributed memory platforms. Our solver symPACK relies on efficient and flexible communication primitives provided by the UPC++ library. Performance evaluation shows good scalability and that symPACK outperforms state-of-the-art parallel distributed memory factorization packages, validating our approach on practical cases.

Jacquelin, Mathias↗

Generic, Sparse Tensor Core for Neural Networks

Sparse neural network attracts more attention for model compression, fast execution, and power reduction. The state-of-the-art designed sparse tensor core for structured and static sparsity, which did not support well for generic or dynamic sparsity. We design a sparse tensor core to support generic sparsity pruning with a novel hybrid and blocked sparse matrix storage format, HB-ELL, which saves computation and storage while keeping the most significant elements, as well as supporting dynamic sparsity for data flow in neural networks. We achieve better performance with preliminary results than the state-of- the-art on an NVIDIA GPU simulator.

Wu, Xiaolong↗

symPACK: A GPU-Capable Fan-Out Sparse Cholesky Solver

Sparse symmetric positive definite systems of equations are ubiquitous in scientific workloads and applications. Parallel sparse Cholesky factorization is the method of choice for solving such linear systems. Therefore, the development of parallel sparse Cholesky codes that can efficiently run on today’s large-scale heterogeneous distributed-memory platforms is of vital importance. Modern supercomputers offer nodes that contain a mix of CPUs and GPUs. To fully utilize the computing power of these nodes, scientific codes must be adapted to offload expensive computations to GPUs. We present symPACK, a GPU-capable parallel sparse Cholesky solver that uses one-sided communication primitives and remote procedure calls provided by the UPC++ library. We also utilize the UPC++ "memory kinds" feature to enable efficient communication of GPU-resident data. We show that on a number of large problems, symPACK outperforms comparable state-of-the-art GPU-capable Cholesky factorization codes by up to 14x on the NERSC Perlmutter supercomputer.

Bellavita, Julian↗

Incomplete Sparse Approximate Inverses for Parallel Preconditioning

In this study, we propose a new preconditioning method that can be seen as a generalization of block-Jacobi methods, or as a simplification of the sparse approximate inverse (SAI) preconditioners. The “Incomplete Sparse Approximate Inverses” (ISAI) is in particular efficient in the solution of sparse triangular linear systems of equations. Those arise, for example, in the context of incomplete factorization preconditioning. ISAI preconditioners can be generated via an algorithm providing fine-grained parallelism, which makes them attractive for hardware with a high concurrency level. Finally, in a study covering a large number of matrices, we identify the ISAI preconditioner as an attractive alternative to exact triangular solves in the context of incomplete factorization preconditioning.

97 MATHEMATICS AND COMPUTING↗

Multithreaded sparse matrix-matrix multiplication for many-core and GPU architectures

Sparse matrix-matrix multiplication is a key kernel that has applications in several domains such as scientific computing and graph analysis. Several algorithms have been studied in the past for this foundational kernel. In this work, we develop parallel algorithms for sparse matrix-matrix multiplication with a focus on performance portability across different high performance computing architectures. The performance of these algorithms depend on the data structures used in them. We compare different types of accumulators in these algorithms and demonstrate the performance difference between these data structures. Furthermore, we develop a meta-algorithm, kkSpGEMM, to choose the right algorithm and data structure based on the characteristics of the problem. We show performance comparisons on three architectures and demonstrate the need for the community to develop two phase sparse matrix-matrix multiplication implementations for efficient reuse of the data structures involved.

97 MATHEMATICS AND COMPUTING↗

Toward memory-efficient melt pool monitoring: a classification framework using event-based imaging and sparse sensing technique

Vision sensors like CMOS and CCD cameras are often used for in-process monitoring of melt pools in laser-based additive and welding processes, but they require transferring large amounts of data and computational processing resources. Event-based neuromorphic imagery, on the other hand, detects only the change in pixel intensity, thus potentially reducing the data amount and latency. With an event imager, this study develops a framework for melt pool condition classification, including image construction, time scale selection, optimal pixel selection, and sparse classification, to achieve a highly memory-efficient scheme. These are based on sparse sensing techniques with singular value decomposition (SVD) and QR pivoting, the two fundamental matrix transformations for linear dimensionality reduction. The framework is then validated by classifying a controlled experiment by exciting various mode shapes of liquid gallium pools of varying depths (3, 6, and 8 mm). At 200 pixels, the classifier can reach overall accuracy of 75%, while at 2000 pixels (0.013% of the total possible pixels), the accuracy is nearly 90% (89.86%). At the same number of pixels, random selection can only achieve 46% and 67%, respectively. The memory savings of the sparsely sampled event data compared to a conventional imager is about 500 times. In addition to performance, implementation and limitations of the framework are also discussed.

42 ENGINEERING↗

PASTA: A Parallel Sparse Tensor Algorithm Benchmark Suite

Tensor methods have gained increasingly attention from various applications, including machine learning, quantum chemistry, healthcare analytics, social network analysis, data mining, and signal processing, to name a few. Sparse tensors and their algorithms become critical to further improve the performance of these methods and enhance the interpretability of their output. This work presents a sparse tensor algorithm benchmark suite (PASTA) for single- and multi-core CPUs. To the best of our knowledge, this is the first benchmark suite for sparse tensor world. PASTA targets on: 1) helping application users to evaluate different computer systems using its representative computational workloads; 2) providing insights to better utilize existed computer architecture and systems and inspiration for the future design. This benchmark suite will be publicly released.

HPC, sparse tensor, benchmark↗

Underground hydrogen storage leakage detection and characterization based on machine learning of sparse seismic data

Underground hydrogen storage (UHS) is considered as a scalable approach for massive storage and seasonal extraction of hydrogen (H 2 ). Although conventional leakage detection and characterization methods based on time-lapse seismic imaging and inversion generally apply to H 2 leakage detection problem, a high-fidelity yet cost effective geophysics approach is still missing to reliably inform leakage location and properties based on very sparse data. In response, we develop a novel supervised machine learning method to detect and characterize H 2 leakage from UHS. The input to our neural network are sparse time-lapse seismic waveforms, while the output from the neural network includes the spatial location and physical properties of a H 2 leakage. Here, we generate high-quality time-lapse waveforms using the elastic-wave equations to train the neural network. We train and validate our machine learning model and find that it attains high accuracy in using extremely sparse time-lapse seismic data to detect and characterize H 2 leakage. Our investigation is the first systematic study that focuses on applying machine learning to subsurface H 2 leakage detection and characterization and could potentially serve as a cost-effective geophysical tool for underground hydrogen leakage detection and characterization with high fidelity.

08 HYDROGEN↗

Nonlinear sparse Bayesian learning for physics-based models

This paper addresses the issue of overfitting while calibrating unknown parameters of over-parameterized physics-based models with noisy and incomplete observations. Here, a semi-analytical Bayesian framework of nonlinear sparse Bayesian learning (NSBL) is proposed to identify sparsity among model parameters during Bayesian inversion. NSBL offers significant advantages over machine learning algorithm of sparse Bayesian learning (SBL) for physics-based models, such as 1) the likelihood function or the posterior parameter distribution is not required to be Gaussian, and 2) prior parameter knowledge is incorporated into sparse learning (i.e. not all parameters are treated as questionable). NSBL employs the concept of automatic relevance determination (ARD) to facilitate sparsity among questionable parameters through parameterized prior distributions. The analytical tractability of NSBL is enabled by employing Gaussian ARD priors and by building a Gaussian mixture-model approximation of the posterior parameter distribution that excludes the contribution of ARD priors. Subsequently, type-II maximum likelihood is executed using Newton's method whereby the evidence and its gradient and Hessian information are computed in a semi-analytical fashion. We show numerically and analytically that SBL is a special case of NSBL for linear regression models. Subsequently, a linear regression example involving multimodality in both parameter posterior pdf and model evidence is considered to demonstrate the performance of NSBL in cases where SBL is inapplicable. Next, NSBL is applied to identify sparsity among the damping coefficients of a mass-spring-damper model of a shear building frame. These numerical studies demonstrate the robustness and efficiency of NSBL in alleviating overfitting during Bayesian inversion of nonlinear physics-based models.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Accelerated Nano-Optical Imaging through Sparse Sampling

The integration time and signal-to-noise ratio are inextricably linked when performing scanning probe microscopy based on raster scanning. This often yields a large lower bound on the measurement time, for example, in nano-optical imaging experiments performed using a scanning near-field optical microscope (SNOM). Here, in this study, we utilize sparse scanning augmented with Gaussian process regression to bypass the time constraint. We apply this approach to image charge-transfer polaritons in graphene residing on ruthenium trichloride (α-RuCl 3 ) and obtain key features such as polariton damping and dispersion. Critically, nano-optical SNOM imaging data obtained via sparse sampling are in good agreement with those extracted from traditional raster scans but require 11 times fewer sampled points. As a result, Gaussian process-aided sparse spiral scans offer a major decrease in scanning time.

36 MATERIALS SCIENCE↗