Engineering Papers⌕ Search

SEARCH · Engineering Papers

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 595 records · Page 33

Towards provably efficient quantum algorithms for large-scale machine-learning models

Large machine learning models are revolutionary technologies of artificial intelligence whose bottlenecks include huge computational expenses, power, and time used both in the pre-training and fine-tuning process. In this work, we show that fault-tolerant quantum computing could possibly provide provably efficient resolutions for generic (stochastic) gradient descent algorithms, scaling as $\mathcal{O}$(T 2 x polylog($n$)), where n is the size of the models and T is the number of iterations in the training, as long as the models are both sufficiently dissipative and sparse, with small learning rates. Based on earlier efficient quantum algorithms for dissipative differential equations, we find and prove that similar algorithms work for (stochastic) gradient descent, the primary algorithm for machine learning. In practice, we benchmark instances of large machine learning models from 7 million to 103 million parameters. We find that, in the context of sparse training, a quantum enhancement is possible at the early stage of learning after model pruning, motivating a sparse parameter download and re-upload scheme. Our work shows solidly that fault-tolerant quantum algorithms could potentially contribute to most state-of-the-art, large-scale machine-learning problems.

97 MATHEMATICS AND COMPUTING↗

Exact Gaussian processes for massive datasets via non-stationary sparsity-discovering kernels

Abstract A Gaussian Process (GP) is a prominent mathematical framework for stochastic function approximation in science and engineering applications. Its success is largely attributed to the GP’s analytical tractability, robustness, and natural inclusion of uncertainty quantification. Unfortunately, the use of exact GPs is prohibitively expensive for large datasets due to their unfavorable numerical complexity of $$O(N^3)$$ O ( N 3 ) in computation and $$O(N^2)$$ O ( N 2 ) in storage. All existing methods addressing this issue utilize some form of approximation—usually considering subsets of the full dataset or finding representative pseudo-points that render the covariance matrix well-structured and sparse. These approximate methods can lead to inaccuracies in function approximations and often limit the user’s flexibility in designing expressive kernels. Instead of inducing sparsity via data-point geometry and structure, we propose to take advantage of naturally-occurring sparsity by allowing the kernel to discover—instead of induce—sparse structure. The premise of this paper is that the data sets and physical processes modeled by GPs often exhibit natural or implicit sparsities, but commonly-used kernels do not allow us to exploit such sparsity. The core concept of exact, and at the same time sparse GPs relies on kernel definitions that provide enough flexibility to learn and encode not only non-zero but also zero covariances. This principle of ultra-flexible, compactly-supported, and non-stationary kernels, combined with HPC and constrained optimization, lets us scale exact GPs well beyond 5 million data points.

97 MATHEMATICS AND COMPUTING↗

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↗

Performance of an Astrophysical Radiation Hydrodynamics Code under Scalable Vector Extension Optimization

We present results of a performance study of an astrophysical radiation hydrodynamics code, V2D, on the Arm-based A64FX processor developed by Fujitsu. The code solves sparse linear systems, a task for which the A64FX architecture should be well suited. Here, we performed the performance analysis study on Ookami, an Apollo 80 platform utilizing the A64FX processor. We explored several compilers and performance anal-ysis packages and found the code did not perform as expected under scalable vector extension optimization, suggesting that a “deeper dive” into analyzing the code is worthwhile. However, a simple driver program that exercised basic sparse linear algebra routines used by V2D did show significant speedup with the use of the scalable vector extension optimization. We present the initial results from the study which used V2D on a relatively simple test problem that emphasized the repeated solution of sparse linear systems.

79 ASTRONOMY AND ASTROPHYSICS↗

A Performance and Energy Study of GPU-Resident Preconditioners for Conjugate Gradient Solvers: In the Context of Existing and Novel Approaches

Optimizing a particular subprogram out of the set of Basic (sparse) Linear Algebra Subprograms (BLAS) for a given architecture is a common topic of research. In applications, however, these BLAS functions rarely appear in isolation; usually, many of them are used together, in various combinations and with varying inputs. As the need to solve a large, sparse linear system is ubiquitous throughout HPC applications, linear solvers constitute a realistic, sufficiently complex and well-defined representative use case for composite BLAS routines. To this end, based on a representative set of matrices drawn from a diverse set of fields, we present a framework to study, from the performance and energy perspective, the efficacy of GPU- resident parallel Conjugate Gradient (CG) linear solver with different preconditioner options, including Gauss-Seidel, Jacobi, and incomplete Cholesky. We also propose a novel GPU-based preconditioner, in which the triangular solves are approximated by an iterative process. The development of this preconditioner was motivated by solving large graph Laplacian linear systems, for which the existing preconditioners either perform slow on GPU-based platforms or are not applicable. We compare the performance of these preconditioners on different hardware accelerator architectures, i.e., AMD MI250X, MI100, Nvidia A100, V100, and Jetson. Our experiments reveal performance trade-offs and provide information on how to select the best strategy for the given linear system, dictated by its properties, and the platform of interest. We demonstrate the application of our novel preconditioner for solving CG and graph Laplacian systems. Overall, the framework can be utilized as a benchmark to guide informed decisions in choosing a specific preconditioner, i.e., whether it is better to rely on the performance of a triangular solver or on the performance of sparse matrix-vector product. Finally, by considering power consumption to solve the linear systems, we report the energy footprint for the solvers.

Preconditioned Conjugate Gradient, GPUs, iterative↗

A Flexible Forwarding Scheme to Improve Latency-Bound Irregular P2P Communication in MPI

We propose an algorithm to efficiently perform latency-bound communication scenarios that consist of many small messages. In these parallel scenarios, processes typically pass around a lot of small-sized messages of a few KBs of size. Performing communication operations with P2P MPI routines or collective MPI routines (including neighborhood collectives) in such scenarios may not always yield the optimal results and may not resolve the latency bottleneck. To this end, we develop a regular structure called virtual process topology (VPT) on which the messages can be communicated in a structured and controlled manner. Using parameters of this topology, one can tune the rate of aggression in tackling the latency costs. We demonstrate that our communication algorithm is preferable to MPI P2P and collective routines for latency-bound communication and it can easily be adapted only by replacing calls to MPI routines in a parallel application. We show how to adapt existing topology-aware mapping heuristics to address the volume overhead due to communicating messages on the VPT. Moreover, we propose a novel swap-based mapping heuristic to address this overhead by optimizing the maximum volume handled by a process. Experiments on synthetic communication graphs as well as real-world applications such as parallel Canonical Polyadic sparse tensor decomposition and parallel sparse matrix-dense matrix multiplication show that our approach is a powerful way of overcoming the bottlenecks posed by sparse and latency-bound irregular communication.

communication algorithm↗

Physics-informed neural networks for identification of material properties using standing waves

A metallic structure in its initial stage of failure involves plastic deformation or environmental degradation that changes the elastic modulus and density. This work presents the detection of change in wave velocity (a function of elastic modulus and density) as a system identification problem. A physics-informed neural network (PINN) is proposed to solve the system identification problem. The PINN takes the spatial coordinates of scanning locations and time as inputs and provides the displacement and wave velocity as outputs. The governing partial differential equation of standing waves in a rod is incorporated into the neural network as physics in the form of a loss function. The wave velocity vector is randomly initiated. During the training of the network, physics is used to determine and update the wave velocity target vector from the network’s displacement predictions. The measured data, comprising sparse displacement response on the rod structure, are used to train the PINN. The wave velocity at the sparse locations on the rod is learned from the predicted displacements during the training. Using the predictions of the trained network, the response of free vibration or material property variation can be reconstructed at unscanned locations on the structure to obtain high-resolution maps for full-field imaging to detect and localize the changes caused by plastic deformation. The PINN’s sparse scanning and simultaneous prediction capability during training can lead to high scanning and data-processing speeds. This capability yields a nondestructive evaluation system that can predict the presence of degraded material locations as the structural vibrations are scanned and processed in real time.

Rathod, Vivek↗

Geothermal Fault Zone and Fluid Imaging through Joint Airborne ZTEM and Ground MT Data Inversion Analysis

This project has aimed to achieve detailed electrical resistivity resolution at geothermal reservoir scales by combining airborne natural electromagnetic (EM) field surveying (ZTEM) with ground magnetotelluric (MT) measurements to approximate an airborne MT geophysical method. MT alone is relatively expensive and may have permitting challenges in sensitive areas. Airborne ZTEM field data contains only the magnetic field, requires a background assumption, and has been limited to relatively high frequencies, thus suffering uniqueness problems. Based on proto-type 2D simulations, ZTEM ambiguities may be reduced through formal incorporation with possibly sparse ground MT soundings, which we pursued in full 3D for this project. The methodology was tested at the high-temperature Roosevelt Hot Springs geothermal system, Utah, which was considered advantageous given the near total exposure of crystalline reservoir rocks across the project area. ZTEM and ground MT survey data were acquired in 2017, subcontracted to outside parties with which we have worked in the past. These included 80 remote-referenced tensor MT soundings over the Mineral Mountains and adjacent Roosevelt Hot Spring producing geothermal system. These MT stations abut later coverage of a similar number of MT stations taken for the Utah FORGE project providing excellent total data aperture to re-solve structure beneath both project areas better than either set alone. The airborne ZTEM survey covered 704 line kilometers in E-W flight lines with a 250 m line spacing. Although this survey was timed during a maintenance-related shutdown of power production at the Roosevelt Hot Springs, other noise sources difficult to identify but including two high-voltage state-scale transmission lines compromised the ZTEM survey badly leading to unusable responses. Thus, with DOE management concurrence, the project proceeded to emphasize inversion and interpretation of the joint SubTER-FORGE MT data sets with regard to the Roosevelt Hot Springs reservoir recharge and to deep heat sources for both it and the Utah FORGE EGS project area. We also investigated the joint ZTEM-MT sampling concept with data sets from the Eleven Mile Canyon prospect area donated by the U.S. Navy (A. Sabin, PoC). Inversion of the SubTER-FORGE MT data using the HexMT 3D finite element algorithm reveals a large, low-resistivity anomaly extending sub-vertically through the depth range of the crust beneath the western Mineral Mountains. The steep conductive zone connects in the lower crust to a more tabular conductor characteristic of much of the Great Basin that generally is ascribed to current mafic magmatic underplating, hybridization and fluid release. The location of the resolved anomaly relative to the recent (0.5-0.8 Ma) eruptive centers of the Mineral Mountains implicates it as remnants of the magma body which fed these centers. This structure appears to be currently feeding heat and fluids upward into the Roosevelt Hot Springs hydrothermal system, as well as heat laterally to the FORGE project area. Separate and joint inversion models were carried out for the donated Eleven Mile Canyon MT-ZTEM data set to demonstrate concept. ZTEM only inversion showed two main alteration zones in the western portion of the project area known from geological mapping. Joint inversion including an E-W profile of MT soundings sharpened these features considerably. It also resolved in much greater detail the graben related normal faulting structure of the central project area which lies at depths exceeding the sensitivity of ZTEM alone. The sparse number of MT da-ta relative to the ZTEM required upweighting the former by a factor of several, but an exact procedure awaits future research. Our final impression is that sparse MT data can improve resolution of the subsurface over that of ZTEM alone. However, well sampled MT data are to be preferred and offer the simplicity of interpreting just one data type, and possess the superior resolution capability coming with the electric field everywhere, and from their high bandwidth.

15 GEOTHERMAL ENERGY↗

Utilization of satellite-derived cloud cover to improve the estimation of latent heat release in a winter extratropical cyclone

A simple scheme for utilizing satellite cloud pattern information to improve the estimation of parameterized stable and convective latent heat release is proposed and tested for an extratropical cyclone occurring over the United States during January 9-11, 1975. Calculations are done over the standard North American rawinsonde data region and over a sparse data region simulated by ignoring one-third of the original rawinsonde stations. Results indicate 15 percent and 30 percent improvements in latent heating estimates derived from the total and sparse data sets, respectively. A larger improvement was found using the sparse data set because the parameterized latent heat release estimates obtained using these data were poorer than those obtained using the total data set.

Lin, S.-J.↗

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.↗

Carbon balance and productivity of Lemna gibba, a candidate plant for CELSS

The photosynthesis and productivity of Lemna gibba is analyzed for CELSS based plant growth. Net photosynthesis of Lemna gibba is determined as a function of incident photosynthetic photon flux (PPF), with the light coming from above, below, or from both directions. Light from below is about 75 percent as effective as from above when the stand is sparse, but much less so with dense stands. High rates of photosynthesis are measured at 750 micromol / sq m per sec PPF and 1500 micromol/ mol CO2 at densities up to 660 g fresh weight (FW)/ sq m with young cultures. The analysis includes diagrams illustrating the net photosynthesis response to bilateral lighting of a sparse stand of low assimilate Lemna gibba; the effect of stand density on the net photosynthesis response to bilateral lighting of high assimilate Lemna gibba; the net photosynthesis response to ambient CO2 of sparse stands of Lemna gibba; and the time course of net photosynthesis and respiration per unit chamber and per unit dry weight of Lemna gibba.

Gale, J.↗

Experiments with conjugate gradient algorithms for homotopy curve tracking

There are algorithms for finding zeros or fixed points of nonlinear systems of equations that are globally convergent for almost all starting points, i.e., with probability one. The essence of all such algorithms is the construction of an appropriate homotopy map and then tracking some smooth curve in the zero set of this homotopy map. HOMPACK is a mathematical software package implementing globally convergent homotopy algorithms with three different techniques for tracking a homotopy zero curve, and has separate routines for dense and sparse Jacobian matrices. The HOMPACK algorithms for sparse Jacobian matrices use a preconditioned conjugate gradient algorithm for the computation of the kernel of the homotopy Jacobian matrix, a required linear algebra step for homotopy curve tracking. Here, variants of the conjugate gradient algorithm are implemented in the context of homotopy curve tracking and compared with Craig's preconditioned conjugate gradient method used in HOMPACK. The test problems used include actual large scale, sparse structural mechanics problems.

Irani, Kashmira M.↗

Vision based obstacle detection and grouping for helicopter guidance

Electro-optical sensors can be used to compute range to objects in the flight path of a helicopter. The computation is based on the optical flow/motion at different points in the image. The motion algorithms provide a sparse set of ranges to discrete features in the image sequence as a function of azimuth and elevation. For obstacle avoidance guidance and display purposes, these discrete set of ranges, varying from a few hundreds to several thousands, need to be grouped into sets which correspond to objects in the real world. This paper presents a new method for object segmentation based on clustering the sparse range information provided by motion algorithms together with the spatial relation provided by the static image. The range values are initially grouped into clusters based on depth. Subsequently, the clusters are modified by using the K-means algorithm in the inertial horizontal plane and the minimum spanning tree algorithms in the image plane. The object grouping allows interpolation within a group and enables the creation of dense range maps. Researchers in robotics have used densely scanned sequence of laser range images to build three-dimensional representation of the outside world. Thus, modeling techniques developed for dense range images can be extended to sparse range images. The paper presents object segmentation results for a sequence of flight images.

Sridhar, Banavar↗

The red edge in arid region vegetation: 340-1060 nm spectra

The remote sensing study of vegetated regions of the world has typically been focused on the use of broad-band vegetation indices such as NDVI. Various modifications of these indices have been developed in attempts to minimize the effect of soil background, e.g., SAVI, or to reduce the effect of the atmosphere, e.g., ARVI. Most of these indices depend on the so-called 'red edge,' the sharp transition between the strong absorption of chlorophyll pigment in visible wavelengths and the strong scattering in the near-infrared from the cellular structure of leaves. These broadband indices tend to become highly inaccurate as the green canopy cover becomes sparse. The advent of high spectral resolution remote sensing instrument such as the Airborne Visible and Infrared Imaging Spectrometer (AVIRIS) has allowed the detection of narrow spectral features in vegetation and there are reports of detection of the red edge even for pixels with very low levels of green vegetation cover by Vane et al. and Elvidge et al., and to characterize algal biomass in coastal areas. Spectral mixing approaches similar to those of Smith et al. can be extended into the high spectral resolution domain allowing for the analysis of more endmembers, and potentially, discrimination between material with narrow spectral differences. Vegetation in arid regions tends to be sparse, often with small leaves such as the creosote bush. Many types of arid region vegetation spend much of the year with their leaves in a senescent state, i.e., yellow, with lowered chlorophyll pigmentation. The sparseness of the leaves of many arid region plants has the dual effect of lowering the green leaf area which can be observed and of allowing more of the sub-shrub soil to be visible which further complicates the spectrum of a region covered with arid region vegetation. Elvidge examined the spectral characteristics of dry plant materials showing significant differences in the region of the red edge and the diagnostic ligno-cellulose absorptions at 2090 nm and 2300 nm. Ray et al. detected absorption at 2100 nm in AVIRIS spectra of an abandoned field known to be covered by a great deal of dead plant litter. In order to better study arid region vegetation remote sensing data, it is necessary to better characterize the reflectance spectra of in situ, living, arid region plants.

Ray, Terrill W.↗

A Shifted Block Lanczos Algorithm 1: The Block Recurrence

In this paper we describe a block Lanczos algorithm that is used as the key building block of a software package for the extraction of eigenvalues and eigenvectors of large sparse symmetric generalized eigenproblems. The software package comprises: a version of the block Lanczos algorithm specialized for spectrally transformed eigenproblems; an adaptive strategy for choosing shifts, and efficient codes for factoring large sparse symmetric indefinite matrices. This paper describes the algorithmic details of our block Lanczos recurrence. This uses a novel combination of block generalizations of several features that have only been investigated independently in the past. In particular new forms of partial reorthogonalization, selective reorthogonalization and local reorthogonalization are used, as is a new algorithm for obtaining the M-orthogonal factorization of a matrix. The heuristic shifting strategy, the integration with sparse linear equation solvers and numerical experience with the code are described in a companion paper.

Grimes, Roger G.↗

Applications of Data Assimilation to Analysis of the Ocean on Large Scales

It is commonplace to begin talks on this topic by noting that oceanographic data are too scarce and sparse to provide complete initial and boundary conditions for large-scale ocean models. Even considering the availability of remotely-sensed data such as radar altimetry from the TOPEX and ERS-1 satellites, a glance at a map of available subsurface data should convince most observers that this is still the case. Data are still too sparse for comprehensive treatment of interannual to interdecadal climate change through the use of models, since the new data sets have not been around for very long. In view of the dearth of data, we must note that the overall picture is changing rapidly. Recently, there have been a number of large scale ocean analysis and prediction efforts, some of which now run on an operational or at least quasi-operational basis, most notably the model based analyses of the tropical oceans. These programs are modeled on numerical weather prediction. Aside from the success of the global tide models, assimilation of data in the tropics, in support of prediction and analysis of seasonal to interannual climate change, is probably the area of large scale ocean modeling and data assimilation in which the most progress has been made. Climate change is a problem which is particularly suited to advanced data assimilation methods. Linear models are useful, and the linear theory can be exploited. For the most part, the data are sufficiently sparse that implementation of advanced methods is worthwhile. As an example of a large scale data assimilation experiment with a recent extensive data set, we present results of a tropical ocean experiment in which the Kalman filter was used to assimilate three years of altimetric data from Geosat into a coarsely resolved linearized long wave shallow water model. Since nonlinear processes dominate the local dynamic signal outside the tropics, subsurface dynamical quantities cannot be reliably inferred from surface height anomalies. Because of its potential for large scale synoptic coverage of the deep ocean, acoustic travel time data should be a natural complement to satellite altimetry. Satellite data give us vertical integrals associated with thermodynamic and dynamic processes.

Miller, Robert N.↗

Integrated Tail Buffet Loads on the F/A-18

The unsteady pressures acting on the vertical tails of a full-scale F/A-18 fighter aircraft were studied to gain a better understanding of tail-buffet loads that frequently occur on fighter aircraft operating at high angles-of-attack. Data for the study were acquired during two test entries in the 80- by 120-Foot Wind Tunnel wherein the aircraft was tested at wind speeds up to 100 knots and at angles-of-attack from 20deg to 40deg. For the purposes of this paper, the primary difference between the two tests is that, during the first wind-tunnel entry, the pressure transducers were more sparsely spaced and covered less of the fin than during the second entry. In addition to a brief description of the spectral analysis methods used for the unsteady aerodynamic pressures and loads, an analysis of the effects of sensor density on estimating integrated loads is presented. It was found that the integrated loads determined from sparse sensor arrays are significantly higher than actual loads. However, a modest increase in the number of sensors can greatly reduce the error and a method for correcting load estimates from sparse sensor arrays is also suggested. The results for the time-averaged, power-spectral analysis are then presented for the tail-fin bending moments. Power spectra are presented for the aircraft at zero sideslip over an angle-of-attack range from 20deg to 40deg and for the aircraft at an angle-of-attack of 30deg over a sideslip range from -16deg to 16deg. Since the aircraft was equipped with a removable leading-edge extension (LEX) fence to reduce tail-buffet loads, the tail-fin bending moment loads are also presented for that configuration. The LEX fence is shown to significantly reduce bending moment loads over a broad range frequencies, for all the aircraft attitudes presented.

Meyn, Larry A.↗

A Method for Optimizing Non-Axisymmetric Liners for Multimodal Sound Sources

Central processor unit times and memory requirements for a commonly used solver are compared to that of a state-of-the-art, parallel, sparse solver. The sparse solver is then used in conjunction with three constrained optimization methodologies to assess the relative merits of non-axisymmetric versus axisymmetric liner concepts for improving liner acoustic suppression. This assessment is performed with a multimodal noise source (with equal mode amplitudes and phases) in a finite-length rectangular duct without flow. The sparse solver is found to reduce memory requirements by a factor of five and central processing time by a factor of eleven when compared with the commonly used solver. Results show that the optimum impedance of the uniform liner is dominated by the least attenuated mode, whose attenuation is maximized by the Cremer optimum impedance. An optimized, four-segmented liner with impedance segments in a checkerboard arrangement is found to be inferior to an optimized spanwise segmented liner. This optimized spanwise segmented liner is shown to attenuate substantially more sound than the optimized uniform liner and tends to be more effective at the higher frequencies. The most important result of this study is the discovery that when optimized, a spanwise segmented liner with two segments gives attenuations equal to or substantially greater than an optimized axially segmented liner with the same number of segments.

Watson, W. R.↗