Engineering Papers⌕ Search

SEARCH · Engineering Papers

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 343 records · Page 19
All sourcesNASA NTRSDOE OSTI
DOE OSTI2023

Validation of Microgrid Algorithms using At-Scale Simulation and Emulation Real-Time (ASSERT) Framework

This paper presents a novel framework for validating microgrid algorithms using a At-Scale Simulation and Emulation Real-Time (ASSERT) setup. The proposed universal microgrid validation framework was developed at Advanced Research on Integrated Energy Systems (ARIES) platform at National Renewable Energy Laboratory in Golden, Colorado, USA. As the number of intercommunicating devices grow in power systems, along with more integration of inverter-based resources, developing and validating microgrid operation and control algorithms is becoming complex and time-consuming task. The ASSERT framework is designed to provide a comprehensive, accurate, and efficient solution for validating microgrid algorithms. It combines at-scale simulations and real-time emulation to create a virtual environment that closely mimics the behavior of a physical microgrids which are characteristic of future smart distribution systems, such as: (1) increasing variability in the physical size of new energy technologies; (2) requiring control large numbers of interconnected devices, and (3) integrating diverse technologies that have not previously worked together. The paper describes the technical details of the ASSERT framework, its validation process, and its benefits over traditional validation methods. The framework's ability to validate the performance of various algorithms is demonstrated through a case study, which shows that it can effectively identify the weaknesses of an algorithm and optimize its performance. Overall, the ASSERT framework is a promising tool that can significantly enhance the development and validation of microgrid algorithms, leading to more reliable and efficient microgrid operation.

at-scale↗
DOE OSTI2021

Scaling Out a Combinatorial Algorithm for Discovering Carcinogenic Gene Combinations to Thousands of GPUs

Cancer is a leading cause of death in the US, second only to heart disease. It is primarily a result of a combination of an estimated two-nine genetic mutations (multi-hit combinations). Although a body of research has identified hundreds of cancer-causing genetic mutations, we don’t know the specific combination of mutations responsible for specific instances of cancer for most cancer types. An approximate algorithm for solving the weighted set cover problem was previously adapted to identify combinations of genes with mutations that may be responsible for individual instances of cancer. However, the algorithm’s computational requirement scales exponentially with the number of genes, making it impractical for identifying more than three-hit combinations, even after the algorithm was parallelized and scaled up to a V100 GPU. Since most cancers have been estimated to require more than three hits, we scaled out the algorithm to identify combinations of four or more hits using 1000 nodes (6000 V100 GPUs with ≈48×106 processing cores) on the Summit supercomputer at Oak Ridge National Laboratory. Efficiently scaling out the algorithm required a series of algorithmic innovations and optimizations for balancing an exponentially divergent workload across processors and for minimizing memory latency and inter-node communication. We achieved an average strong scaling efficiency of 90.14% (80.96%–97.96% for 200 to 1000 nodes), compared to a 100 node run, with 84.18% scaling efficiency for 1000 nodes. With experimental validation, the multi-hit combinations identified here could provide further insight into the etiology of different cancer subtypes and provide a rational basis for targeted combination therapy.

Dash, Sajal↗
DOE OSTI2023

Fast Tuning-Free Distributed Algorithm for Solving the Network-Constrained Economic Dispatch

With the increasing penetration of distributed energy resources (DERs) and their participation in the electricity market, it becomes more desirable to apply distributed algorithms for resource allocation in order to address the resulting computational and communicational challenges. Most of the existing distributed algorithms for solving the network-constrained economic dispatch (NCED) problem require the tuning of certain auxiliary parameters. As a result, the robustness of these algorithms against the varieties in DERs is greatly undermined. In this paper, a new distributed algorithm, optimality condition consensus (OCC), is proposed to solve the NCED problem by using distributed power flow (DPF) and ratio consensus as fundamental tools. It inherits the advantages of existing distributed algorithms for the NCED problem but removes the need for parameter tuning to improve performance in practice. In conclusion, the effectiveness of the proposed distributed algorithm in terms of efficiency, scalability, and robustness is demonstrated through detailed case studies.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2020

An Algebraic Sparsified Nested Dissection Algorithm Using Low-Rank Approximations

Here, we propose a new algorithm for the fast solution of large, sparse, symmetric positive-definite linear systems, spaND (sparsified Nested Dissection). It is based on nested dissection, sparsification, and low-rank compression. After eliminating all interiors at a given level of the elimination tree, the algorithm sparsifies all separators corresponding to the interiors. This operation reduces the size of the separators by eliminating some degrees of freedom but without introducing any fill-in. This is done at the expense of a small and controllable approximation error. The result is an approximate factorization that can be used as an efficient preconditioner. We then perform several numerical experiments to evaluate this algorithm. We demonstrate that a version using orthogonal factorization and block-diagonal scaling takes fewer CG iterations to converge than previous similar algorithms on various kinds of problems. Furthermore, this algorithm is provably guaranteed to never break down and the matrix stays symmetric positive-definite throughout the process. We evaluate the algorithm on some large problems show it exhibits near-linear scaling. The factorization time is roughly $\mathcal{O}$(N), and the number of iterations grows slowly with N.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

A supernodal all-pairs shortest path algorithm

We show how to exploit graph sparsity in the Floyd-Warshall algorithm for the all-pairs shortest path (Apsp) problem. Floyd-Warshall is an attractive choice for Apsp on high-performing systems due to its structural similarity to solving dense linear systems and matrix multiplication. However, if sparsity of the input graph is not properly exploited, Floyd-Warshall will perform unnecessary asymptotic work and thus may not be a suitable choice for many input graphs. To overcome this limitation, the key idea in our approach is to use the known algebraic relationship between Floyd-Warshall and Gaussian elimination, and import several algorithmic techniques from sparse Cholesky factorization, namely, fill-in reducing ordering, symbolic analysis, supernodal traversal, and elimination tree parallelism. When combined, these techniques reduce computation, improve locality and enhance parallelism. We implement these ideas in an efficient shared memory parallel prototype that is orders of magnitude faster than an efficient multi-threaded baseline Floyd-Warshall that does not exploit sparsity. Our experiments suggest that the Floyd-Warshall algorithm can compete with Dijkstra's algorithm (the algorithmic core of Johnson's algorithm) for several classes sparse graphs.

Sao, Piyush↗
DOE OSTI2021

PAGANI: a parallel adaptive GPU algorithm for numerical integration

We present a new adaptive parallel algorithm for the challenging problem of multi-dimensional numerical integration on massively parallel architectures. Adaptive algorithms have demonstrated the best performance, but efficient many-core utilization is difficult to achieve because the adaptive work-load can vary greatly across the integration space and is impossible to predict a priori. Existing parallel algorithms utilize sequential computations on independent processors, which results in bottlenecks due to the need for data redistribution and processor synchronization. Our algorithm employs a high-throughput approach in which all existing sub-regions are processed and sub-divided in parallel. Repeated sub-region classification and filtering improves upon a brute-force approach and allows the algorithm to make efficient use of computation and memory resources. A CUDA implementation shows orders of magnitude speedup over the fastest open-source CPU method and extends the achievable accuracy for difficult integrands. Our algorithm typically outperforms other existing deterministic parallel methods.

Sakiotis, Ioannis↗
DOE OSTI2025

Pulse: An Outlier Sensitive Downsampling Algorithm For Timeseries Data

Pulse is a downsampling algorithm for timeseries data. Frequently datasets become so large that visualization tools and web browsers cannot effectively render graphics due to memory constraints. Downsampling algorithms are commonly applied to minimize the quantity of data required to visualize important features or trends in the data, but some datasets are composed by distinct enough features and trends that most existing downsampling algorithms fail to preserve them. Pule was developed to downsample timeseries data for galvanostatic stack test data at the Idaho National Laboratory. These datasets were composed by approximately 4 million records, most of them being extremely uniform. However, during relatively brief time periods when the stack test changes state, for example when the test article is powered on, or a load is added, the data produce sparse asymptotes. No existing downsampling algorithm was capable of preserving the sparse asymptotes in electrolysis stack test data. Instead, we develop a downsampling algorithm that preserves important outliers in data, and otherwise aggressively downsamples uniform data. The algorithm has applications in other domains like seismology, in the measurement of earthquakes, or astronomy, in the measurement of quasars or transit photometry.

Woodruff, Nathan [Idaho National Laboratory (INL),↗
DOE OSTI2022

Automated Identification of Characteristic Droplet Size Distributions in Stratocumulus Clouds Utilizing a Data Clustering Algorithm

Abstract Droplet-level interactions in clouds are often parameterized by a modified gamma fitted to a “global” droplet size distribution. Do “local” droplet size distributions of relevance to microphysical processes look like these average distributions? This paper describes an algorithm to search and classify characteristic size distributions within a cloud. The approach combines hypothesis testing, specifically, the Kolmogorov–Smirnov (KS) test, and a widely used class of machine learning algorithms for identifying clusters of samples with similar properties: density-based spatial clustering of applications with noise (DBSCAN) is used as the specific example for illustration. The two-sample KS test does not presume any specific distribution, is parameter free, and avoids biases from binning. Importantly, the number of clusters is not an input parameter of the DBSCAN-type algorithms but is independently determined in an unsupervised fashion. As implemented, it works on an abstract space from the KS test results, and hence spatial correlation is not required for a cluster. The method is explored using data obtained from the Holographic Detector for Clouds (HOLODEC) deployed during the Aerosol and Cloud Experiments in the Eastern North Atlantic (ACE-ENA) field campaign. The algorithm identifies evidence of the existence of clusters of nearly identical local size distributions. It is found that cloud segments have as few as one and as many as seven characteristic size distributions. To validate the algorithm’s robustness, it is tested on a synthetic dataset and successfully identifies the predefined distributions at plausible noise levels. The algorithm is general and is expected to be useful in other applications, such as remote sensing of cloud and rain properties. Significance Statement A typical cloud can have billions of drops spread over tens or hundreds of kilometers in space. Keeping track of the sizes, positions, and interactions of all of these droplets is impractical, and, as such, information about the relative abundance of large and small drops is typically quantified with a “size distribution.” Droplets in a cloud interact locally, however, so this work is motivated by the question of whether the cloud droplet size distribution is different in different parts of a cloud. A new method, based on hypothesis testing and machine learning, determines how many different size distributions are contained in a given cloud. This is important because the size distribution describes processes such as cloud droplet growth and light transmission through clouds.

54 ENVIRONMENTAL SCIENCES↗
DOE OSTI2022

A Hybrid Bulk Algorithm to Predict Turbulent Fluxes over Dry and Wet Bare Soils

Measurements made in the Columbia River basin (Oregon) in an area of irregular terrain during the second Wind Forecast Improvement Project (WFIP2) field campaign are used to develop an optimized hybrid bulk algorithm to predict the surface turbulent fluxes from readily measured or modeled quantities over dry and wet bare or lightly vegetated soil surfaces. The hybrid (synthetic) algorithm combines (i) an aerodynamic method for turbulent flow, which is based on the transfer coefficients (drag coefficient and Stanton number), roughness lengths, and Monin–Obukhov similarity; and (ii) a modified Priestley–Taylor (P-T) algorithm with physically based ecophysiological constraints, which is essentially based on the surface energy budget (SEB) equation. Soil heat flux in the latter case was estimated from measurements of soil temperature and soil moisture. In the framework of the hybrid algorithm, bulk estimates of the momentum flux and the sensible heat flux are derived from a traditional aerodynamic approach, whereas the latent heat flux (or moisture flux) is evaluated from a modified P-T model. Direct measurements of the surface fluxes (turbulent and radiative) and other ancillary atmospheric/soil parameters made during WFIP2 for different soil conditions (dry and wet) are used to optimize and tune the hybrid bulk algorithm. The bulk flux estimates are validated against the measured eddy-covariance fluxes. We also discuss the SEB closure over dry and wet surfaces at various time scales based on the modeled and measured fluxes. Although this bulk flux algorithm is optimized for the data collected during the WFIP2, a hybrid approach can be used for similar flux-tower sites and field campaigns.

54 ENVIRONMENTAL SCIENCES↗
DOE OSTI2020

ConnectIt: a framework for static and incremental parallel graph connectivity algorithms

Connected components is a fundamental kernel in graph applications. The fastest existing multicore algorithms for solving graph connectivity are based on some form of edge sampling and/or linking and compressing trees. However, many combinations of these design choices have been left unexplored. In this paper, we design the ConnectIt framework, which provides different sampling strategies as well as various tree linking and compression schemes. ConnectIt enables us to obtain several hundred new variants of connectivity algorithms, most of which extend to computing spanning forest. In addition to static graphs, we also extend ConnectIt to support mixes of insertions and connectivity queries in the concurrent setting. We present an experimental evaluation of ConnectIt on a 72-core machine, which we believe is the most comprehensive evaluation of parallel connectivity algorithms to date. Compared to a collection of state-of-the-art static multicore algorithms, we obtain an average speedup of 12.4x (2.36x average speedup over the fastest existing implementation for each graph). Using ConnectIt, we are able to compute connectivity on the largest publicly-available graph (with over 3.5 billion vertices and 128 billion edges) in under 10 seconds using a 72-core machine, providing a 3.1x speedup over the fastest existing connectivity result for this graph, in any computational setting. For our incremental algorithms, we show that our algorithms can ingest graph updates at up to several billion edges per second. To guide the user in selecting the best variants in ConnectIt for different situations, we provide a detailed analysis of the different strategies. Finally, we show how the techniques in ConnectIt can be used to speed up two important graph applications: approximate minimum spanning forest and SCAN clustering.

Computer Science↗
DOE OSTI2022

A Mountaintop View Requires Minimal Sorting: A Faster Contour Tree Algorithm

Consider a scalar field f : M → R, where M is a triangulated simplicial mesh in R d . A level set, or contour, at value v is a connected component of f –1 (v). As v is changed, these contours change topology, merge into each other, or split. Contour trees are concise representations of f that track this contour behavior. The vertices of these trees are the critical points of f, where the gradient is zero. The edges represent changes in the topology of contours. It is a fundamental data structure in data analysis and visualization, and there is significant previous work (both theoretical and practical) on algorithms for constructing contour trees. Suppose M has n vertices, N facets, and t critical points. A classic result of Carr, Snoeyink, and Axen (2000) gives an algorithm that takes O(n log n+Nα(N)) time (where α(·) is the inverse Ackermann function). A further improvement to O(t log t + N) time was given by Chiang et al. All these algorithms involve a global sort of the critical points, a significant computational bottleneck. Unfortunately, lower bounds of Ω(t log t) also exist. We present the first algorithm that can avoid the global sort and has a refined time complexity that depends on the contour tree structure. Intuitively, if the tree is short and fat, we get significant improvements in running time. For a partition of the contour tree into a set of descending paths, P, our algorithm runs in O($\Sigma$ pϵP |p| log |p| + tα(t) + N). This is at most O(t log D + N), where D is the diameter of the contour tree. Moreover, it is O(tα(t) + N) for balanced trees, a significant improvement over the previous complexity. Our algorithm requires numerous ideas: partitioning the contour tree into join and split trees, a local growing procedure to iteratively build contour trees, and the use of heavy path decompositions for the time complexity analysis. There is a crucial use of a family of binomial heaps to maintain priorities, ensuring that any comparison made is between comparable nodes of the contour tree. We also prove lower bounds showing that the $\Sigma$ pϵP |p| log |p| complexity is inherent to computing contour trees.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Development and Validation of Algorithms That Analyze Communicating Thermostat Data to Identify Enclosure Retrofit Opportunities

Annual energy savings of up to $\$ 4$ to $\$ 5$ billion could be achieved nationwide through basic insulation and heating system retrofits of existing homes. However, current utility energy efficiency programs are costly and challenging to scale. Customer acquisition occurs primarily through energy bill mailers, mass media, and online advertising that lack specificity about home-specific retrofit opportunities, expected energy savings, and cost-effectiveness. Specific retrofit opportunities are identified via on-site home energy assessments (HEAs) that are inconvenient to homeowners, expensive, and of variable accuracy. We developed computational algorithms that automatically analyze communicating thermostat (CT) heating data that could be used to increase the customer uptake of insulation and air sealing energy conservation measures (ECMs) by identifying homes with the most significant retrofit opportunities, estimating post-retrofit energy savings, and formulating home-specific outreach. The algorithms are based on an extended second-order grey-box model that characterizes a building’s thermal response using lumped elements, coupled with an empirical model of infiltration that accounts for both wind and stack effects. The basic parameters of the model correspond to actual physical parameters of the home, i.e., the home’s overall R-value of and the building envelope ACH50. Unlike the conventional approach, which estimates model parameters based on the best fit to the observed time-dependent room temperature, our approach derives correlations between the daily heating system runtime and temperature difference (indoor-outdoor) that are more robust to data quality issues in real-world applications. We also used HEA data for algorithm development and validation. With the help of our utility partners, Eversource and National Grid, we obtained data sets for hundreds of Massachusetts homes. For each home, these data sets included three sets of information anonymized by the utility: (1) CT data (HVAC runtime, room temperature, and, for some vendors, outdoor temperature and wind speed) collected by the CT vendor (one of three) over a heating season, (2) HEA report performed by the HEA vendor (same vendor for all homes), (3) Monthly utility gas bills coincident with the CT data (3 to 24 per home, depending on availability). For some homes, we also obtained blower-door test results. Initially, we applied the algorithms developed to homes with a single CT and then extended them to homes with two CTs by using an equivalent home approach. Finally, we developed algorithms for prediction of energy savings and a methodology of comparing our predictions with those generated by HEAs. The main technical results indicate that we can reliably identify homes with insulation and/or air sealing retrofit opportunities and provide accurate savings predictions. Our hypothesis is that the algorithms could be applied to utility energy efficiency programs to identify homes that could realize significant energy savings from insulation and/or air sealing retrofits. This information could then be used to reach out to those homes with highly customized outreach, thereby delivering increased program energy savings and cost-effectiveness. This would: Significantly increase the uptake rate of on-site HEAs, and Significantly increase the fraction of HEAs resulting in ECM implementation. To test these hypotheses, we designed and conducted a randomized controlled trial (RCT). The RCT results suggest that personal messaging leads to a two- to five-fold increase in the HEA uptake rate.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗
DOE OSTI2020

Design, Development and Testing Plan for Energy Efficiency Algorithms Related to Building-Integrated Cooling, Heating, and Power Systems

Building-integrated cooling, heating and power (CHP) systems are more efficient than conventional systems at providing local power and thermal energy, and favorable fuel prices are bound to spur their increased adoption. It is estimated that the total CHP technical potential in the commercial building sector is approximately 76 GW, but only a small fraction of it is actually deployed. Advanced control and monitoring systems that realize the full potential of these CHP systems can transform this capacity into an asset for both the owner and the grid and also accelerate the adoption of these systems in the building sector. However, to realize the full benefit of the CHP systems, we must ensure persistence of energy efficient operations. It has been demonstrated by several studies that as much as 30% of building energy use is wasted. Much of the waste results from the inability to anticipate load variations (design day vs. non-design day operations; diurnal variation of loads), identify improper operation, and efficiently operate, control and maintain building systems. Moreover, many buildings, even those with adequate control infrastructure, lack knowledgeable staff to operate and maintain energy systems. Operators of buildings with CHP systems will constantly need to make tradeoffs (economic dispatch) between onsite power generation and purchasing power, between onsite heat production from distributed generation versus heating/cooling from conventional systems, and different passive and active load management measures. Much of the inefficiency in the current building operations can be eliminated by use of automated performance monitoring (PM), real-time commissioning verification (CxV) and automated fault detection and diagnostic (AFDD) tools. Automation can help system operators make intelligent decisions. Remote and continuous monitoring of system conditions and performance will enable better management and integration of CHP with existing building systems. Continuous PM, real-time CxV and AFDD could alleviate burdens for operations staff, enhance operations and maintenance (O&M), and improve reliability of building and CHP systems. To address the O&M challenges and to provide a means to maximize the rate-of-return of building-integrated CHP systems, the Building Technologies Office (BTO) within the U.S. Department of Energy’s (DOE’s) Office of Energy Efficiency and Renewable Energy (EERE) initiated a project to design, develop, and field test a VOLTTRON™-based supervisory controller and associated open-source algorithms. These algorithms will ensure real-time optimal operation of a building-integrated CHP system, support electric grid reliability, and lead to achieving the goal of a clean, efficient, reliable and affordable next-generation integrated energy systems. This report lists the components for which PM, real-time CxV and AFDD algorithms will be developed, how the algorithms will be tested, and metrics that will be used to validate the algorithms and easy of deployment. Deployment of these algorithms in the field will result in savings reduction in energy consumption of between 10% and 20%.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗
DOE OSTI2023

Comparison of Supervised and Un-Supervised Machine Learning Algorithms for Threat Detection and Scintillator Performance for Radiation Portal Monitoring

Following the events of September 11, 2001, international border crossing have been equipped with radiation portal monitors (RPMs) to identify illicit radioactive material. Polyvinyl toluene (PVT) scintillators are commonly used due to their low cost and reasonable maintainability, however they offer low spectral resolution. Despite the fact that over twenty years has transpired since this event, radioisotopes are still typically identified by hand-crafted classification algorithms, e.g., total counts or energy windowing, and exhibit relatively poor performance in detecting threats at the low false alarm rates required to support the stream of commerce. While some improvement to performance has been realized via the use of supervised machine learning, these classification algorithms typically utilize simulations in lieu of real data due to the sparsity of data for one or more classes. Accordingly, the performance of these algorithms is somewhat less than optimal when examining experiments or simulations with model mismatch. Consequently, in this work, we examine the application of a number of unsupervised machine learning, anomaly detection based algorithms, to circumvent the inverse crime when analyzing spectroscopy data for RPMs. We also compare anomaly detection results with those obtained via the use of supervised classification detection ML algorithms when model mismatch is introduced between the simulated threat items utilized for training/testing. Finally, we compared the performance of the PVT scintillators to those obtained with higher resolution detectors using both anomaly detection and supervised classification algorithms.

98 NUCLEAR DISARMAMENT, SAFEGUARDS, AND PHYSICAL P↗
DOE OSTI2023

Motion Planning Algorithms for Safety and Quantum Computing Efficiency

Motion planning remains a fundamental problem in robotics. Sampling-based algorithms use randomization to allow efficient solutions to this complex problem. As mobile robots and autonomous vehicles become more prevalent in everyday life, motion planning must be applied to increasingly challenging scenarios. Safety has become a paramount concern in motion planning for ensuring robotic applications enrich human lives. To date, many motion planning techniques to increase safety in the face of uncertain and dynamic environments have been developed. This dissertation first addresses distributional safety of Rapidly-Exploring Random Trees (RRT) through our algorithm W-Safe RRT. To acknowledge distributional uncertainty and poor modeling, W-Safe RRT uses the Wasserstein metric to provide a probabilistic bound on the distributional distance between a robot and obstacles. Human-interpretable environmental agent classification allows online safety margin adaptation. We propose and analyze an integrating region method for online classification that increases actor labeling accuracy based on behavioral feature values when compared to state of the art methods. The method performs class assignments based on local maximum likelihood in a created behavioral feature-space, allowing a notion of classification uncertainty. Model-based methods with safety guarantees can quickly become computationally in tractable, especially with multiple agents, higher dimensions, and plentiful unknowns. Sampling based algorithms have been parallelized for computation with multi-core computers and GPUs. We consider the use of quantum algorithms and computers for sampling-based motion planning for the first time. Quantum computing performs operations on superpositions of states and can solve certain problems much more efficiently than classical computers, but introduces previously unseen challenges. With Quantum-RRT, we recast the motion planning problem into a database-search structure and use Quantum Amplitude Amplification to find reachable states in the database with a quadratic performance increase over classical methods. We address two error sources with this method: quantum measurement and quantum oracle errors. We then extend this method to Parallel Quantum-RRT, which uses a manager-worker architecture with multiple parallel quantum workers to increase database search efficiency. We compare algorithm architectures and characterize probabilities of multiple workers finding solutions. Lastly, we test in simulation the quantum algorithms against classical versions in a wide variety of scenarios, concluding that a similar parallelization improvement is to be found in the quantum case as was found in the parallelization of classical RRT.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Revising Apetrei’s bounding volume hierarchy construction algorithm to allow stackless traversal

Stackless traversal is a technique to speed up range queries by avoiding usage of a stack during the tree traversal. One way to achieve that is to transform a given binary tree to store a left child and a skip-connection (also called an escape index). In general, this operation requires an additional tree traversal during the tree construction. For some tree structures, however, it is possible to achieve the same result at a reduced cost. We propose one such algorithm for a GPU hierarchy construction algorithm proposed by Karras in Karras 2012. Furthermore, we show that our algorithm also works with the improved algorithm proposed by Apetrei in Apetrei 2014, despite a different ordering of the internal nodes. We achieve that by modifying Apetrei’s algorithm to restore the original Karras’ ordering of the internal nodes. Using the modified algorithm, we show how to construct a hierarchy suitable for a stackless traversal in a single bottom-up pass.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

Application of the Approximate Bayesian Computation Algorithm to Gamma-Ray Spectroscopy

Radioisotope identification (RIID) algorithms for gamma-ray spectroscopy aim to infer what isotopes are present and in what amounts in test items. RIID algorithms either use all energy channels in the analysis region or only energy channels in and near identified peaks. Because many RIID algorithms rely on locating peaks and estimating each peak’s net area, peak location and peak area estimation algorithms continue to be developed for gamma-ray spectroscopy. This paper shows that approximate Bayesian computation (ABC) can be effective for peak location and area estimation. Algorithms to locate peaks can be applied to raw or smoothed data, and among several smoothing options, the iterative bias reduction algorithm (IBR) is recommended; the use of IBR with ABC is shown to potentially reduce uncertainty in peak location estimation. Extracted peak locations and areas can then be used as summary statistics in a new ABC-based RIID. ABC allows for easy experimentation with candidate summary statistics such as goodness-of-fit scores and peak areas that are extracted from relatively high dimensional gamma spectra with photopeaks (1024 or more energy channels) consisting of count rates versus energy for a large number of gamma energies.

Burr, Tom↗
DOE OSTI2024

Mapping Geothermal Indicator Minerals Using Fusion of Target Detection Algorithms

Mineral mapping from satellite images provides valuable insights into subsurface mineral alteration for geothermal exploration. In previous studies, eight fundamental algorithms were used for mineral mapping utilizing USGS spectra, a collection of reflectance spectra containing samples of minerals, rocks, and soils created by the USGS. We used an ASD FieldSpec 4 Hi-RES NG portable spectrometer to collect spectra for analyzing ASTER images of the Coso Geothermal Field. Then, we established the ground-truth information and the spectral library by analyzing 97 samples. Samples collected from the field were analyzed using the CSIRO TSG (The Spectral Geologist of the Commonwealth Scientific and Industrial Research Organization). Based on the mineralogy study, multiple high-purity spectra of geothermal alteration minerals were selected from collected data, including alunite, chalcedony, hematite, kaolinite, and opal. Eight mineral spectral target detection algorithms were applied to the preprocessed satellite data with a proposed local spectral library. We measured the highest overall accuracy of 87% for alunite, 95% for opal, 83% for chalcedony, 60% for hematite, and 96% for kaolinite out of these eight algorithms. Three, four, five, and eight algorithms were fused to extract mineral alteration with the obtained target detection results. The results prove that the fusion of algorithms gives better results than using individual ones. In conclusion, this paper discusses the significance of evaluating different mapping algorithms. It proposes a robust fusion approach to extract mineral maps as an indicator for geothermal exploration.

Cavur, Mahmut↗