Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “sparse factorization”

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 91 records · Page 5
All sourcesNASA NTRSDOE OSTI
DOE OSTI2018

A distributed-memory approximation algorithm for maximum weight perfect bipartite matching

We design and implement an efficient parallel approximation algorithm for the problem of maximum weight perfect matching in bipartite graphs, i.e. the problem of finding a set of non-adjacent edges that covers all vertices and has maximum weight. This problem differs from the maximum weight matching problem, for which scalable approximation algorithms are known. It is primarily motivated by finding good pivots in scalable sparse direct solvers before factorization where sequential implementations of maximum weight perfect matching algorithms, such as those available in MC64, are widely used due to the lack of scalable alternatives. To overcome this limitation, we propose a fully parallel distributed memory algorithm that first generates a perfect matching and then searches for weightaugmenting cycles of length four in parallel and iteratively augments the matching with a vertex disjoint set of such cycles. For most practical problems the weights of the perfect matchings generated by our algorithm are very close to the optimum. An efficient implementation of the algorithm scales up to 256 nodes (17,408 cores) on a Cray XC40 supercomputer and can solve instances that are too large to be handled by a single node using the sequential algorithm.

Azad, Ariful↗
DOE OSTI2022

HyKKT: a hybrid direct-iterative method for solving KKT linear systems

Here, we propose a solution strategy for the large indefinite linear systems arising in interior methods for nonlinear optimization. The method is suitable for implementation on hardware accelerators such as graphical processing units (GPUs). The current gold standard for sparse indefinite systems is the LBLT factorization where L is a lower triangular matrix and B is 1×1 or 2×2 block diagonal. However, this requires pivoting, which substantially increases communication cost and degrades performance on GPUs. Our approach solves a large indefinite system by solving multiple smaller positive definite systems, using an iterative solver on the Schur complement and an inner direct solve (via Cholesky factorization) within each iteration. Cholesky is stable without pivoting, thereby reducing communication and allowing reuse of the symbolic factorization. We demonstrate the practicality of our approach on large optimal power flow problems and show that it can efficiently utilize GPUs and outperform LBL T factorization of the full system.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS2000

User's Manual for PCSMS (Parallel Complex Sparse Matrix Solver)

PCSMS (Parallel Complex Sparse Matrix Solver) is a computer code written to make use of the existing real sparse direct solvers to solve complex, sparse matrix linear equations. PCSMS converts complex matrices into real matrices and use real, sparse direct matrix solvers to factor and solve the real matrices. The solution vector is reconverted to complex numbers. Though, this utility is written for Silicon Graphics (SGI) real sparse matrix solution routines, it is general in nature and can be easily modified to work with any real sparse matrix solver. The User's Manual is written to make the user acquainted with the installation and operation of the code. Driver routines are given to aid the users to integrate PCSMS routines in their own codes.

Reddy, C. J.↗
DOE OSTI2020

Multifrontal Non-negative Matrix Factorization

Non-negative matrix factorization (Nmf) is an important tool in high-performance large scale data analytics with applications ranging from community detection, recommender system, feature detection and linear and non-linear unmixing. While traditional Nmf works well when the data set is relatively dense, however, it may not extract sufficient structure when the data is extremely sparse. Specifically, traditional Nmf fails to exploit the structured sparsity of the large and sparse data sets resulting in dense factors. We propose a new algorithm for performing Nmf on sparse data that we call multifrontal Nmf (Mf-Nmf) since it borrows several ideas from the multifrontal method for unconstrained factorization (e.g. LU and QR). We also present an efficient shared memory parallel implementation of Mf-Nmf and discuss its performance and scalability. We conduct several experiments on synthetic and realworld datasets and demonstrate the usefulness of the algorithm by comparing it against standard baselines. We obtain a speedup of 1.2x to 19.5x on 24 cores with an average speed up of 10.3x across all the real world datasets.

Sao, Piyush↗
DOE OSTI2024

Informing forest carbon inventories under the Paris Agreement using ground-based forest monitoring data

Human interactions with forests have shaped Earth's climate for millennia and will continue to do so as we target net-zero emission goals. Accurately characterizing these climate impacts requires making reliable forest carbon data available for forest monitoring and planning. Here, we develop a semi-automated process for submitting forest carbon measurements from the largest relevant scientific database to the International Panel on Climate Change's Emission Factor Database, which currently has sparse forest carbon data. Building this bridge from scientific research to international policy is an important step towards managing forests in a net-zero motivated future. Humans have been influencing Earth's climate via transformative impacts on forests for millennia, and forests are now recognized as critical to climate change mitigation under the Paris Agreement. The efficacy of climate change mitigation planning and reporting depends on quality data on forest carbon (C) stocks and changes. The Emission Factor Database (EFDB) of the International Panel on Climate Change (IPCC) is intended to be a definitive source for such data, but needs comprehensive and well-documented data to be so. To facilitate submission of forest C estimates from scientific studies to EFDB, we develop and document a process for semi-automated data submission from the Global Forest C database (ForC v4.0), which is the largest compilation of ground-based forest C estimates. We then assess the data currently available through ForC and provide recommendations for improving forest data collection, analysis, and reporting. As of September 2024, ForC contained ~19,286 records potentially relevant to EFDB, 1068 of which had been submitted and posted to EFDB. These represented 19% of the total EFDB records for forest land. Records were unevenly distributed across variables and geographic regions. ForC records (37%) reviewed could not be submitted because the original publication lacked required information. In the future, ground-based forest C estimates should target gaps in the record, and studies should ensure that they report all information necessary for inclusion in EFDB. Given that climate change is rapidly impacting the world's forests, timely reporting of recent estimates will be critical to accurate forest C inventories.

54 ENVIRONMENTAL SCIENCES↗
NASA NTRS2001

Algorithms and Application of Sparse Matrix Assembly and Equation Solvers for Aeroacoustics

An algorithm for symmetric sparse equation solutions on an unstructured grid is described. Efficient, sequential sparse algorithms for degree-of-freedom reordering, supernodes, symbolic/numerical factorization, and forward backward solution phases are reviewed. Three sparse algorithms for the generation and assembly of symmetric systems of matrix equations are presented. The accuracy and numerical performance of the sequential version of the sparse algorithms are evaluated over the frequency range of interest in a three-dimensional aeroacoustics application. Results show that the solver solutions are accurate using a discretization of 12 points per wavelength. Results also show that the first assembly algorithm is impractical for high-frequency noise calculations. The second and third assembly algorithms have nearly equal performance at low values of source frequencies, but at higher values of source frequencies the third algorithm saves CPU time and RAM. The CPU time and the RAM required by the second and third assembly algorithms are two orders of magnitude smaller than that required by the sparse equation solver. A sequential version of these sparse algorithms can, therefore, be conveniently incorporated into a substructuring for domain decomposition formulation to achieve parallel computation, where different substructures are handles by different parallel processors.

Watson, W. R.↗
DOE OSTI2015

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↗
DOE OSTI2022

Graph Partitioning and Sparse Matrix Ordering using Reinforcement Learning and Graph Neural Networks

We present a novel method for graph partitioning, based on reinforcement learning and graph convolutional neural networks. Our approach is to recursively partition coarser representations of a given graph. The neural network is implemented using SAGE graph convolution layers, and trained using an advantage actor critic (A2C) agent. We present two variants, one for finding an edge separator that minimizes the normalized cut or quotient cut, and one that finds a small vertex separator. The vertex separators are then used to construct a nested dissection ordering to permute a sparse matrix so that its triangular factorization will incur less fill-in. The partitioning quality is compared with partitions obtained using METIS and SCOTCH, and the nested dissection ordering is evaluated in the sparse solver SuperLU. Our results show that the proposed method achieves similar partitioning quality as METIS and SCOTCH. Furthermore, the method generalizes across different classes of graphs, and works well on a variety of graphs from the SuiteSparse sparse matrix collection.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2017

CrY2H-seq: a massively multiplexed assay for deep-coverage interactome mapping

Broad-scale protein–protein interaction mapping is a major challenge given the cost, time, and sensitivity constraints of existing technologies. Here, we present a massively multiplexed yeast two-hybrid method, CrY2H-seq, which uses a Cre recombinase interaction reporter to intracellularly fuse the coding sequences of two interacting proteins and next-generation DNA sequencing to identify these interactions en masse. We applied CrY2H-seq to investigate sparsely annotated Arabidopsis thaliana transcription factors interactions. By performing ten independent screens testing a total of 36 million binary interaction combinations, and uncovering a network of 8,577 interactions among 1,453 transcription factors, we demonstrate CrY2H-seq's improved screening capacity, efficiency, and sensitivity over those of existing technologies. The deep-coverage network resource we call AtTFIN-1 recapitulates one-third of previously reported interactions derived from diverse methods, expands the number of known plant transcription factor interactions by three-fold, and reveals previously unknown family-specific interaction module associations with plant reproductive development, root architecture, and circadian coordination.

59 BASIC BIOLOGICAL SCIENCES↗
DOE OSTI2024

Improved Evaluation of Large Network Matrices for Linear Power Flow Within Optimization Problems

This work presents methods for evaluating the Power Transfer Distribution Factor (PTDF) and Line Outage Distribution Factor (LODF) matrices by employing sparse linear algebra for large-scale computing applications. These matrices play a critical role in many power system applications, such as the Unit Commitment Problem (UC), pre- and post-contingency power flow analysis, and transmission expansion. These matrices are typically dense, which means they require a significant amount of time and memory to be computed for large networks. However, by analyzing the structure of the matrices and their computation method, it is possible to use reduced memory methods based on sparse matrix operations. This paper shows that sparse linear algebra algorithms are faster and require less memory and time than traditional dense approaches. Additionally, we explore the effect of matrix sparsification by eliminating trailing digits on power flow calculations.

large scale↗
DOE OSTI2024

Improved Evaluation of Large Network Matrices for Linear Power Flow Within Optimization Problems: Preprint

This work discusses methods for evaluating the Power Transfer Distribution Factor (PTDF) and Line Outage Distribution Factor (LODF) matrices by employing sparse linear algebra for large-scale computing applications. These matrices are critical in many power systems applications, such as the Unit Commitment Problem (UC), pre- and post-contingency power flow analysis, and transmission expansion. These matrices are typically dense, which means they require a significant amount of time and memory to be computed for large networks. However, by analyzing the structure of the matrices and their computation method, it is possible to use reduced memory methods based on sparse matrix operations. This paper shows that sparse linear algebra algorithms are faster and require less memory and time than traditional dense approaches. Additionally, we explore the effect of matrix sparsification by eliminating trailing digits on power flow calculations.

ENERGY PLANNING, POLICY, AND ECONOMY↗
DOE OSTI2020

LA17-V-InverseRadTransportProblem-PD2Kb. Final Project Report

In the inverse radiation transport problem, a radiation signal emanating from an unknown object is used to reconstruct geometric and material parameters of the object , e.g., the mass of special nuclear material (SNM), the isotopic composition of the SNM (e.g., the enrichment of 235U), the thickness of shielding, etc. The inverse radiation transport problem is one of the most fundamental and important in the emergency response mission, and has been addressed in previous NA-22 and NA-42/84 investments by using derivative-free optimization methods. Our project was aimed at (i) consolidating previous work by applying polynomial chaos expansion (PCE) for reducing significantly the number of forward model simulations required by derivative-free optimization methods; (ii) developing a general-purpose framework and stand-alone software for solving the inverse radiation transport problem by applying a new “predictive modeling” methodology (predictive modeling of coupled multi-physics systems, PM_CMPS) which enables the fusing of experimental and computational information; and (iii) developing several benchmarks (for unscattered gamma rays) for demonstrating the quantification of non-Gaussian features (e.g., skewness and kurtosis, which characterize asymmetries and long tails) of response distributions by deterministically and efficiently propagating parameter uncertainties (covariances and higher-order moments, where available) using high-order sensitivities computed by the recently developed comprehensive adjoint sensitivity analysis methodology (C-ASAM). With regard to (i), application of PCE, the most significant accomplishment of this project was an implementation of PCE into INVERSE that significantly reduced computation time for the DiffeRential Evolution Adaptive Metropolis (DREAM) and Differential Evolution (DE) methods. For inverse transport problems with measurements of neutron leakage, neutron multiplication, and neutron-induced gamma-rays, the solution times for the DREAM and DE methods were reduced by factors of 30-300, reducing run times from hours to minutes while maintaining the same accuracy as the standard (non-PCE) DREAM and DE. Speedups were further improved by exploring sparse grid quadrature sets using the Toolkit for Adaptive Stochastic Modeling and Non-Intrusive ApproximatioN (Tasmanian) toolset. An initial exploration of sparse grids indicated that further speedups factors of 5-10 are obtainable. The implementation of PCE in INVERSE is not in a form that users can easily access. With regard to (ii), solving the inverse problem using a predictive modeling paradigm, the most significant accomplishment of this project were the derivation and implementation of adjoint-based second derivatives in neutron and photon transport theory. There are two codes that compute these derivatives. SENSPG computes them for uncollided gamma rays and SENSMG computes them for neutron leakage. SENSMG is open-source code available on github. Other significant accomplishments included a stand-alone code, MULTI-PRED, that implements the predictive modeling paradigm, along with a detailed manual. The code was implemented in the existing INVERSE code for inverse problems, but a head-to-head comparison of inverse methods was not achieved. We also derived and implemented the capability to compute sensitivities for multiplicity measurements into the SENSMG code, and this capability was used in a data assimilation application, but it was not used for solving inverse problems. With regard to (iii), developing benchmarks to demonstrate the importance of high-order sensitivity and uncertainty analysis, the most significant accomplishment of this project were two test problems that showed how important second-order sensitivities are.

07 ISOTOPE AND RADIATION SOURCES↗
DOE OSTI2025

A two-level GPU-accelerated incomplete LU preconditioner for general sparse linear systems

This paper presents a parallel preconditioning approach based on incomplete LU (ILU) factorizations in the framework of Domain Decomposition (DD) for general sparse linear systems. We focus on distributed memory parallel architectures, specifically, those that are equipped with graphic processing units (GPUs). In addition to block-Jacobi, we present general purpose two-level ILU Schur complement-based approaches, where different strategies are presented to solve the coarse-level reduced system. These strategies are combined with modified ILU methods in the construction of the coarse-level operator, in order to effectively remove smooth errors by targeting an algebraically smooth vector. We leverage available GPU-based sparse matrix kernels to accelerate the setup and the solve phases of the proposed ILU preconditioner. We evaluate the efficiency of the proposed methods as a smoother for algebraic multigrid (AMG) and as a preconditioner for Krylov subspace methods on challenging anisotropic diffusion problems and a collection of general sparse matrices.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2017

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↗
DOE OSTI2017

Combining landscape suitability and habitat connectivity to conserve the last surviving population of cheetah in Asia

Abstract Aim The Asiatic cheetah, Acinonyx jubatus venaticus , a critically endangered large felid, has disappeared from vast tracks of its historical range across south‐western Asia. It is currently confined to the arid ecosystems of central Iran for which little is known about its distribution and habitat linkages. We proposed the first evaluation of Asiatic cheetah's distribution and developed models of landscape suitability and connectivity to inform future conservation planning. Location Central Iran. Methods We analysed presence data of a 14‐year‐long cheetah monitoring programme according to environmental and anthropogenic factors, and generated an ensemble model of habitat suitability based on seven species distribution models ( SDM s). We then used the concept of circuit theory and landscape connectivity prioritization ( LCP ) on resultant core habitats and landscape suitability to evaluate potential linkages between core areas. Results Core habitats, that is, the areas hosting the largest continuous suitable habitats for Asiatic cheetahs, covered approximately 49,144 km 2 ( c . 6.3% of the study area). Availability of prey species, avoidance of human‐dominated areas and their infrastructures, and rough landscapes covered with sparse vegetation were the most predictive factors of the core habitats for the last cheetah population in Asia. Although relatively vast, the area of potential core habitats available to cheetahs appeared to be fragmented with limited connectivity between the northern and southern parts of this distribution. Main conclusions Our approach highlights the importance of distribution models to recognize, at a coarse‐scale level, a spatial population structure and habitat suitability characteristics for a large carnivore surviving at very low density. We have identified specific areas of suitable habitat where developing new landscape protection and adaptive conservation management; and improving the safety of important linkages between core habitats are likely to promote the conservation of the last surviving population of cheetah in Asia.

Ahmadi, Mohsen↗
DOE OSTI2016

Bacteria increase arid-land soil surface temperature through the production of sunscreens

Soil surface temperature, an important driver of terrestrial biogeochemical processes, depends strongly on soil albedo, which can be significantly modified by factors such as plant cover. In sparsely vegetated lands, the soil surface can be colonized by photosynthetic microbes that build biocrust communities. Here we use concurrent physical, biochemical and microbiological analyses to show that mature biocrusts can increase surface soil temperature by as much as 10 °C through the accumulation of large quantities of a secondary metabolite, the microbial sunscreen scytonemin, produced by a group of late-successional cyanobacteria. Scytonemin accumulation decreases soil albedo significantly. Such localized warming has apparent and immediate consequences for the soil microbiome, inducing the replacement of thermosensitive bacterial species with more thermotolerant forms. In conclusion, these results reveal that not only vegetation but also microorganisms are a factor in modifying terrestrial albedo, potentially impacting biosphere feedbacks on past and future climate, and call for a direct assessment of such effects at larger scales.

59 BASIC BIOLOGICAL SCIENCES↗
DOE OSTI2026

Development of a Framework and Methodology for an Advanced Reactor Materials Environmental Effects Design Guide

Advanced non-light-water reactor components may operate at elevated temperature while experiencing cyclic loading, significant neutron irradiation, and exposure to reactor coolant. ASME Boiler and Pressure Vessel Code, Section III, Division 5, provides design rules for elevated-temperature service but does not include specific procedures to account for environmental effects on material properties. This report develops an initial framework and methodology for an Environmental Effects Design Guide (EEDG) focused on neutron irradiation; coolant-environment effects are reserved for future work. The proposed approach treats irradiation as a property-based overlay on the existing Division 5 design process, with two routes: a sparse-data route applying two reduction factors — FCR on creep-rupture strength and FF on fatigue life — for the creep-fatigue evaluations that typically control the design of advanced high-temperature reactor components, and a fuller framework developing the property-to-rule chain across the four Division 5 checks (primary load, strain limits and ratcheting, creep-fatigue, and buckling), together with swelling and weldments as scope items. Both routes are scoped by an in-pile qualification that restricts the use of post-irradiation-examination-derived properties in regimes where an in-pile mechanism could control the design outcome. Illustrative outputs derived on a compiled annealed Type 316 database — FCR ≈ 0.78–0.86 and FF ≈ 0.4 — demonstrate the calculation method within that specific dataset. The framework is an initial, testable design-rule concept; it identifies a practical path for preliminary design evaluations under sparse data and the material data and testing needed to develop the framework further.

Barua, Bipul (ORCID:0000000247184113)↗
DOE OSTI2017

Non-Intrusive Energy Disaggregation Using Non-Negative Matrix Factorization With Sum-to-k Constraint

Energy disaggregation or non-intrusive load monitoring addresses the issue of extracting device-level energy consumption information by monitoring the aggregated signal at one single measurement point without installing meters on each individual device. Energy disaggregation can be formulated as a source separation problem, where the aggregated signal is expressed as linear combination of basis vectors in a matrix factorization framework. In this paper, an approach based on Sum-to-k constrained non-negative matrix factorization (S2K-NMF) is proposed. By imposing the sum-to-k constraint and the non-negative constraint, S2K-NMF is able to effectively extract perceptually meaningful sources from complex mixtures. The strength of the proposed algorithm is demonstrated through two sets of experiments: Energy disaggregation in a residential smart home; and heating, ventilating, and air conditioning components energy monitoring in an industrial building testbed maintained at the Oak Ridge National Laboratory. Furthermore, extensive experimental results demonstrate the superior performance of S2K-NMF as compared to state-of-the-art decomposition-based disaggregation algorithms.

42 ENGINEERING↗