Search NASA⌕ Search

SEARCH · Search NASA

Results for “Algorithms.”

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 1,405 records · Page 78

Near-Optimal and Practical Algorithms for Graph Scan Statistics with Connectivity Constraints

One fundamental task in network analysis is detecting “hotspots” or “anomalies” in the network; that is, detecting subgraphs where there is significantly more activity than one would expect given historical data or some baseline process. Scan statistics is one popular approach used for anomalous subgraph detection. This methodology involves maximizing a score function over all connected subgraphs, which is a challenging computational problem. A number of heuristics have been proposed for these problems, but they do not provide any quality guarantees. Here, we propose a framework for designing algorithms for optimizing a large class of scan statistics for networks, subject to connectivity constraints. Our algorithms run in time that scales linearly on the size of the graph and depends on a parameter we call the “effective solution size,” while providing rigorous approximation guarantees. In contrast, most prior methods have super-linear running times in terms of graph size. Extensive empirical evidence demonstrates the effectiveness and efficiency of our proposed algorithms in comparison with state-of-the-art methods. Our approach improves on the performance relative to all prior methods, giving up to over 25% increase in the score. Further, our algorithms scale to networks with up to a million nodes, which is 1–2 orders of magnitude larger than all prior applications.

97 MATHEMATICS AND COMPUTING↗

Neuromorphic Graph Algorithms: Cycle Detection, Odd Cycle Detection, and Max Flow

Neuromorphic computing is poised to become a promising computing paradigm in the post Moore’s law era due to its extremely low power usage and inherent parallelism. Spiking neural networks are the traditional use case for neuromorphic systems, and have proven to be highly effective at machine learning tasks such as control problems. More recently, neuromorphic systems have been applied outside of the arena of machine learning, primarily in the field of graph algorithms. Neuromorphic systems have been shown to perform graph algorithms faster and with lower power consumption than their traditional (GPU/CPU) counterparts, and are hence an attractive option for a co-processing unit in future high performance computing systems, where graph algorithms play a critical role. In this paper, we present a neuromorphic implementation of cycle detection, odd cycle detection, and the Ford-Fulkerson max-flow algorithm. We further evaluate the performance of these implementations using the NEST neuromorphic simulator by using spike counts and simulation time as proxies for energy consumption and run time. In addition to gains inherent in neuromorphic systems, we show that within the neuromorphic implementations early stopping criteria can be implemented to further improve performance.

Kay, Bill↗

A Parallel Ghosting Algorithm for The Flexible Distributed Mesh Database

Critical to the scalability of parallel adaptive simulations are parallel control functions including load balancing, reduced inter-process communication and optimal data decomposition. In distributed meshes, many mesh-based applications frequently access neighborhood information for computational purposes which must be transmitted efficiently to avoid parallel performance degradation when the neighbors are on different processors. This article presents a parallel algorithm of creating and deleting data copies, referred to as ghost copies, which localize neighborhood data for computation purposes while minimizing inter-process communication. The key characteristics of the algorithm are: (1) It can create ghost copies of any permissible topological order in a 1D, 2D or 3D mesh based on selected adjacencies. (2) It exploits neighborhood communication patterns during the ghost creation process thus eliminating all-to-all communication. (3) For applications that need neighbors of neighbors, the algorithm can create n number of ghost layers up to a point where the whole partitioned mesh can be ghosted. Strong and weak scaling results are presented for the IBM BG/P and Cray XE6 architectures up to a core count of 32,768 processors. The algorithm also leads to scalable results when used in a parallel super-convergent patch recovery error estimator, an application that frequently accesses neighborhood data to carry out computation.

Mubarak, Misbah↗

HPC-NMF: A High-Performance Parallel Algorithm for Nonnegative Matrix Factorization

NMF is a useful tool for many applications in different domains such as topic modeling in text mining, background separation in video analysis, and community detection in social networks. Despite its popularity in the data mining community, there is a lack of efficient distributed algorithms to solve the problem for big data sets. We propose a high-performance distributed-memory parallel algorithm that computes the factorization by iteratively solving alternating non-negative least squares (NLS) subproblems for $\WW$ and $\HH$. It maintains the data and factor matrices in memory (distributed across processors), uses MPI for interprocessor communication, and, in the dense case, provably minimizes communication costs (under mild assumptions). As opposed to previous implementation, our algorithm is also flexible: It performs well for both dense and sparse matrices, and allows the user to choose any one of the multiple algorithms for solving the updates to low rank factors $\WW$ and $\HH$ within the alternating iterations.

Kannan, Ramakrishnan↗

Algorithms for Forward and Inverse Problem Solutions in Phase Contrast Tomography

PhaseTorch is a python package that implements algorithms for forward and inverse problem solutions in X-ray phase contrast tomography (XPCT). XPCT is useful to reconstruct the 3D distribution of the refractive index decrement and absorption index of an imaged object. PhaseTorch implements algorithms for simulation, reconstruction, and analysis of XPCT data. PhaseTorch provides algorithms for simulation of XPCT data of an object with known refractive and absorption indices. It contains algorithms for reconstructing the projections of the absorption index and refractive index decrement.

Sridhar, Venkatesh↗

A systematic comparison of genome-scale clustering algorithms

Background: A wealth of clustering algorithms has been applied to gene co-expression experiments. These algorithms cover a broad range of approaches, from conventional techniques such as k-means and hierarchical clustering, to graphical approaches such as k-clique communities, weighted gene co-expression networks (WGCNA) and paraclique. Comparison of these methods to evaluate their relative effectiveness provides guidance to algorithm selection, development and implementation. Most prior work on comparative clustering evaluation has focused on parametric methods. Graph theoretical methods are recent additions to the tool set for the global analysis and decomposition of microarray co-expression matrices that have not generally been included in earlier methodological comparisons. In the present study, a variety of parametric and graph theoretical clustering algorithms are compared using well-characterized transcriptomic data at a genome scale from Saccharomyces cerevisiae. Methods: For each clustering method under study, a variety of parameters were tested. Jaccard similarity was used to measure each cluster’s agreement with every GO and KEGG annotation set, and the highest Jaccard score was assigned to the cluster. Clusters were grouped into small, medium, and large bins, and the Jaccard score of the top five scoring clusters in each bin were averaged and reported as the best average top 5 (BAT5) score for the particular method. Results: Clusters produced by each method were evaluated based upon the positive match to known pathways. This produces a readily interpretable ranking of the relative effectiveness of clustering on the genes. Methods were also tested to determine whether they were able to identify clusters consistent with those identified by other clustering methods. Conclusions: Validation of clusters against known gene classifications demonstrate that for this data, graph-based techniques outperform conventional clustering approaches, suggesting that further development and application of combinatorial strategies is warranted.

59 BASIC BIOLOGICAL SCIENCES↗

Confidentiality-preserving machine learning algorithms for soft-failure detection in optical communication networks

Automated fault management is at the forefront of next-generation optical communication networks. The increase in complexity of modern networks has triggered the need for programmable and software-driven architectures to support the operation of agile and self-managed systems. In these scenarios, the European Telecommunications Standards Institute zero-touch network and service management approach is imperative. The need for machine learning algorithms to process the large volume of telemetry data brings safety concerns as distributed cloud-computing solutions become the preferred approach for deploying reliable communication network automation. This paper’s contribution is twofold. First, we propose a simple yet effective method to guarantee the confidentiality of the telemetry data based on feature scrambling. The method allows the operation of third-party computational services without direct access to the full content of the collected data. Additionally, the effectiveness of four unsupervised machine learning algorithms for soft-failure detection is evaluated when applied to the scrambled telemetry data. The methods are based on factor analysis, principal component analysis, nonlinear principal component analysis, and singular value decomposition. Most dimensionality reduction algorithms have the common property that they can maintain similar levels of fault classification performance while hiding the data structure from unauthorized access. Evaluations of the proposed algorithms demonstrate this capability.

97 MATHEMATICS AND COMPUTING↗

An Empirical Orthogonal Function-Based Algorithm for Estimating Terrestrial Latent Heat Flux from Eddy Covariance, Meteorological and Satellite Observations

Accurate estimation of latent heat flux (LE) based on remote sensing data is critical in characterizing terrestrial ecosystems and modeling land surface processes. Many LE products were released during the past few decades, but their quality might not meet the requirements in terms of data consistency and estimation accuracy. Merging multiple algorithms could be an effective way to improve the quality of existing LE products. In this paper, we present a data integration method based on modified empirical orthogonal function (EOF) analysis to integrate the Moderate Resolution Imaging Spectroradiometer (MODIS) LE product (MOD16) and the Priestley-Taylor LE algorithm of Jet Propulsion Laboratory (PT-JPL) estimate. Twenty-two eddy covariance (EC) sites with LE observation were chosen to evaluate our algorithm, showing that the proposed EOF fusion method was capable of integrating the two satellite data sets with improved consistency and reduced uncertainties. Further efforts were needed to evaluate and improve the proposed algorithm at larger spatial scales and time periods, and over different land cover types.

54 ENVIRONMENTAL SCIENCES↗

Proton pulse charge calculation algorithm in Beam Power Limiting System at Spallation Neutron Source

A proton pulse charge calculation algorithm in the Beam Power Limiting System (BPLS) at the Spallation Neutron Source (SNS) was developed and implemented in an FPGA. The algorithm calculates one-minute running average of the pulse charges and issues a fault to the Personal Protection System (PPS) and the Machine Protection System (MPS) when a limit is reached. A bit-accurate model of the algorithm was first developed and tested in Matlab® and then implemented and simulated in VHDL using Vivado® design environment. Finally, the algorithm was verified on a µTCA-based hardware platform.

Bobrek, Miljko [ORNL] (ORCID:0000000332763451)↗

Graupel and Hail Identification Algorithm for the Dual-frequency Precipitation Radar (DPR) on the GPM Core Satellite

Precipitation consists of many types of hydrometeors, such as raindrops, ice crystals, graupel, and hail. Due to their impacts, graupel and hail (GH) have received particular attention in the literature. Global Precipitation Measurement (GPM) dual-frequency radar (DPR) has proved to be a very reliable system for global precipitation retrievals. This paper aims to develop a GH identification algorithm for GPM DPR. This algorithm is constructed using a precipitation type index (PTI) defined for DPR. The PTI is effective in separating hydrometeor types and is calculated using measurements of reflectivity, dual-frequency ratio, and storm top height data. The output of the algorithm is a Boolean product representing the existence of graupel or hail along with the vertical profile for each Ku- and Ka-band matched footprint. Cross validation is performed with the Weather Service Radar (WSR-88D) network over continental United States as well as during the Remote sensing of Electrification, Lightning, and Mesoscale/Microscale Processes with Adaptive Ground Observations (RELAMPAGO) experiment. Evaluation of the GH identification algorithm is performed on a global basis, which illustrates promising comparisons with the global lightning and hail precipitation maps generated using radar and radiometer.

54 ENVIRONMENTAL SCIENCES↗

Direct Evaporative Precooling Model and Analysis: Development and Simulations of an Improved Algorithm for Import into EnergyPlus and Applications to Commercial Buildings in the United States

Evaporative condenser pre-cooling expands the availability of energy saving, cost effective technology options (market engagement) and serves to broaden the range of options in upcoming codes and equipment standards (impacting regulation). Commercially available evaporative pre-coolers provide a low cost retrofit for existing packaged rooftop units, commercial unitary split systems, and air cooled chillers. We map the impact on energy savings and peak energy reduction in three building types (medium office, secondary school, and supermarket) in 16 locations with four levels of pad effectiveness and show the effect for HVAC systems using either refrigerants R22 or R410A (See Section 5.4). EnergyPlus simulations are conducted with an improved algorithm for estimating the condenser pre-cooling wet bulb efficiency. EnergyPlus version 5.0.0 provides an option for a curve-fit form of calculating evaporative cooling efficiency (currently available only for evaporative pads used for space cooling, not condenser precooling). This option requires a large body of empirical data to obtain the 11 parameters required in the polynomial equation and, being a general curve fit, it is also not physically meaningful. Our study departs from this approach by presenting an alternative mathematical model that is physically intuitive, simpler in form, and provides better agreement with manufacturer’s data. In this report, we describe the simpler algorithm and provide the metrics that show how it is an improvement over the algorithm used in EnergyPlus version 5.0.0. We then generate performance values that can be directly input into EnergyPlus for simulations. By this process, we examine the annual and peak energy reductions of three building types (medium office, secondary school and supermarket) in 16 locations within the U.S. These three building types were chosen because they have distinctive loads, zones, and equipment. In addition to performing the requisite calculations, computer algorithms were developed for use with EnergyPlus to simulate the performance of commercial units under a variety of operating parameters. Performance maps were generated and estimated energy savings and peak demand reductions were calculated. Performance curves that were used in these EnergyPlus simulations were shared with the National Renewable Energy Laboratory (NREL) and with the Florida Solar Energy Center (FSEC) for possible inclusion in the next update to EnergyPlus.

air conditioner↗

Benchmark Imagery for Assessing Geospatial Semantic Content Extraction Algorithms (Final Report)

Benchmark Imagery for Assessing Geospatial Semantic Content Extraction Algorithms (the “Benchmark Imagery Project”) was a three-year endeavor funded by the Enabling Capabilities (EC) Team of DOE/NNSA’s Office of Proliferation Detection R&D, NA-22, and carried out through a collaborative effort between Los Alamos National Laboratory (LANL) and the Lawrence Livermore National Laboratory (LLNL). The primary objective was to create a set of benchmark imagery for validating algorithms designed to extract semantic content from geospatial images of industrial facilities. The goal was not to develop algorithms; rather, it was to provide information that could be used to do so. The secondary objective was to demonstrate how this information could be used for algorithm validation. This report summarizes the results of the Benchmark Imagery Project.

29 ENERGY PLANNING, POLICY, AND ECONOMY↗

New Design Methods And Algorithms For High Energy-Efficient And Low-cost Distillation Processes

This project sought and successfully answered two big challenges facing the creation of low-energy, cost-effective, zeotropic multi-component distillation processes: first, identification of an efficient search space that includes all the useful distillation configurations and no undesired configurations; second, development of an algorithm to search the space efficiently and generate an array of low-energy options for industrial multi-component mixtures. Such mixtures are found in large-scale chemical and petroleum plants. Commercialization of our results was addressed by building a user interface allowing practical application of our methods for industrial problems by anyone with basic knowledge of distillation for a given problem. We also provided our algorithm to a major U.S. Chemical Company for use by the practitioners. The successful execution of this program has provided methods and algorithms at the disposal of process engineers to readily generate low-energy solutions for a large class of multicomponent distillation problems in a typical chemical and petrochemical plant. In a petrochemical complex, the distillation trains within crude oil processing, hydrotreating units containing alkylation, isomerization, reformer, LPG (liquefied petroleum gas) and NGL (natural gas liquids) processing units can benefit from our results. Effluents from naphtha crackers and ethane-propane crackers typically contain mixtures of methane, ethylene, ethane, propylene, propane, butane and heavier hydrocarbons. We have shown that our systematic search method with a more complete search space, along with the optimization algorithm, has a potential to yield low-energy distillation configurations for all such applications with energy savings up to 50%.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗

Architecture-Aware Algorithms for Scalable Performance and Resilience on Heterogeneous Architectures. Final Report

With the coming end of Moore's law, it has become essential to develop new algorithms and techniques that can provide the performance needed by demanding computational science applications, especially those that are part of the DOE science mission. This work was part of a multi-institution, multi-investigator project that explored several approaches to develop algorithms that would be effective at the extreme scales and with the complex processor architectures that are expected at the end of this decade. The work by this group developed new performance models that have already helped guide the development of highly scalable versions of an algebraic multigrid solver, new programming approaches designed to support numerical algorithms on heterogeneous architectures, and a new, more scalable version of conjugate gradient, an important algorithm in the solution of very large linear systems of equations.

97 MATHEMATICS AND COMPUTING↗

Final Technical Report "Multiscale Simulation Algorithms for Biochemical Systems"

Biochemical systems are inherently multiscale and stochastic. In microscopic systems formed by living cells, the small numbers of reactant molecules can result in dynamical behavior that is discrete and stochastic rather than continuous and deterministic. An analysis tool that respects these dynamical characteristics is the stochastic simulation algorithm (SSA, Gillespie, 1976), a numerical simulation procedure that is essentially exact for chemical systems that are spatially homogeneous or well stirred. Despite recent improvements, as a procedure that simulates every reaction event, the SSA is necessarily inefficient for most realistic problems. There are two main reasons for this, both arising from the multiscale nature of the underlying problem: (1) stiffness, i.e. the presence of multiple timescales, the fastest of which are stable; and (2) the need to include in the simulation both species that are present in relatively small quantities and should be modeled by a discrete stochastic process, and species that are present in larger quantities and are more efficiently modeled by a deterministic differential equation (or at some scale in between). This project has focused on the development of fast and adaptive algorithms, and the fun- damental theory upon which they must be based, for the multiscale simulation of biochemical systems. Areas addressed by this project include: (1) Theoretical and practical foundations for ac- celerated discrete stochastic simulation (tau-leaping); (2) Dealing with stiffness (fast reactions) in an efficient and well-justified manner in discrete stochastic simulation; (3) Development of adaptive multiscale algorithms for spatially homogeneous discrete stochastic simulation; (4) Development of high-performance SSA algorithms.

97 MATHEMATICS AND COMPUTING↗

Advanced Imaging Algorithms for Radiation Imaging Systems

The intent of the proposed work, in collaboration with University of Michigan, is to develop the algorithms that will bring the analysis from qualitative images to quantitative attributes of objects containing SNM. The first step to achieving this is to develop an indepth understanding of the intrinsic errors associated with the deconvolution and MLEM algorithms. A significant new effort will be undertaken to relate the image data to a posited three-dimensional model of geometric primitives that can be adjusted to get the best fit. In this way, parameters of the model such as sizes, shapes, and masses can be extracted for both radioactive and non-radioactive materials. This model-based algorithm will need the integrated response of a hypothesized configuration of material to be calculated many times. As such, both the MLEM and the model-based algorithm require significant increases in calculation speed in order to converge to solutions in practical amounts of time.

Marleau, Peter↗

Final Report: Sublinear Algorithms for In-situ and In-transit Data Analysis at Exascale.

Post-Moore's law scaling is creating a disruptive shift in simulation workflows, as saving the entirety of raw data to persistent storage becomes expensive. We are moving away from a post-process centric data analysis paradigm towards a concurrent analysis framework, in which raw simulation data is processed as it is computed. Algorithms must adapt to machines with extreme concurrency, low communication bandwidth, and high memory latency, while operating within the time constraints prescribed by the simulation. Furthermore, in- put parameters are often data dependent and cannot always be prescribed. The study of sublinear algorithms is a recent development in theoretical computer science and discrete mathematics that has significant potential to provide solutions for these challenges. The approaches of sublinear algorithms address the fundamental mathematical problem of understanding global features of a data set using limited resources. These theoretical ideas align with practical challenges of in-situ and in-transit computation where vast amounts of data must be processed under severe communication and memory constraints. This report details key advancements made in applying sublinear algorithms in-situ to identify features of interest and to enable adaptive workflows over the course of a three year LDRD. Prior to this LDRD, there was no precedent in applying sublinear techniques to large-scale, physics based simulations. This project has definitively demonstrated their efficacy at mitigating high performance computing challenges and highlighted the rich potential for follow-on re- search opportunities in this space.

97 MATHEMATICS AND COMPUTING↗

High-order hydrodynamic algorithms for exascale computing

Hydrodynamic algorithms are at the core of many laboratory missions ranging from simulating ICF implosions to climate modeling. The hydrodynamic algorithms commonly employed at the laboratory and in industry (1) typically lack requisite accuracy for complex multi- material vortical flows and (2) are not well suited for exascale computing due to poor data locality and poor FLOP/memory ratios. Exascale computing requires advances in both computer science and numerical algorithms. We propose to research the second requirement and create a new high-order hydrodynamic algorithm that has superior accuracy, excellent data locality, and excellent FLOP/memory ratios. This proposal will impact a broad range of research areas including numerical theory, discrete mathematics, vorticity evolution, gas dynamics, interface instability evolution, turbulent flows, fluid dynamics and shock driven flows. If successful, the proposed research has the potential to radically transform simulation capabilities and help position the laboratory for computing at the exascale.

97 MATHEMATICS AND COMPUTING↗