Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Steiner Tree”

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.

11 records
All sourcesNASA NTRSDOE OSTI
DOE OSTI2023

Distributed approximate minimal Steiner trees with millions of seed vertices on billion-edge graphs

In this report, we present a parallel 2-approximation Steiner minimal tree algorithm and its MPI-based distributed implementation. In place of expensive distance computations between all pairs of seed vertices, the solution we employ exploits a cheaper Voronoi cell computation. Our design leverages asynchronous processing and message prioritization to accelerate convergence of distance computations, and harnesses vertex and edge centric processing to offer fast time-to-solution. We demonstrate scalability and performance using real-world graphs with up to 128 billion edges and 512 compute nodes, and show the ability to find Steiner trees with up to one million seed vertices. Using 12 data instances, we present comparison with the state-of-the-art exact solver, SCIP-Jack, and two sequential 2-approximate algorithms. We empirically show that, on average, the total distance of the Steiner tree identified by our solution is 1.1290 times greater than the Steiner minimal tree – well within the theoretical approximation bound of 2.

97 MATHEMATICS AND COMPUTING↗
NASA NTRSDate not supplied

Quantum Distributed Algorithms for Approximate Steiner Trees and Directed Minimum Spanning Trees

We present two algorithms in the Quantum CONGEST- CLIQUE model of distributed computation that succeed with high probability; one for producing an approximately optimal Steiner Tree, and one for producing an exact directed minimum spanning tree, each of which uses O ̃(n1/4) rounds of communication and O ̃(n9/4) messages, achieving a lower asymptotic round and message complexity than any known algorithms in the classical CONGEST-CLIQUE model. At a high level, we achieve these results by combining classical algorithms with fast quantum subroutines. Additionally, we characterize the constants and logarithmic factors involved in our algorithms, as well as related classical algorithms, revealing that advances are needed to render both practical.

quantum computing↗
NASA NTRSDate not supplied

Quantum-Accelerated Distributed Algorithms for Approximate Steiner Trees and Directed Minimum Spanning Trees

We present two algorithms in the Quantum CONGEST-CLIQUE model of distributed computation that succeed with high probability; one for producing an approximately optimal Steiner Tree, and one for producing an exact spanning arborescence of minimum weight, the analog of a Minimum Spanning Tree in a directed graph, each of which uses O~(n^(1/4)) rounds of communication and O~(n^(9/4)) messages, achieving a lower round and message complexity than any known algorithms in the classical CONGEST-CLIQUE model. The CONGEST distributed computational model allows limited-sized messages to be transmitted within a network described by a communication graph of size n in a series of rounds to address a computational problem. The size limitation for such messages isO(log(n)) bits at each edge of the communication graph per round. The communication graph in the CONGEST-CLIQUE model is fully connected. In the Quantum CONGEST-CLIQUE model, at most O(log(n)) classical and quantum bits (qubits) can be communicated across each edge of the communication graph per round. At a high level, we achieve these results by combining classical algorithms with fast quantum subroutines. These speedups further contribute to understanding what problems can be solved more efficiently when we allow quantum communication in this CONGEST-CLIQUE model of distributed computation.

quantum distributed algorithms↗
NASA NTRSDate not supplied

Quantum Distributed Algorithms for Approximate Steiner Trees and Directed Minimum Spanning Trees​

We present two algorithms in the Quantum CONGEST- CLIQUE model of distributed computation that succeed with high probability; one for producing an approximately optimal Steiner Tree, and one for producing an exact directed minimum spanning tree, each of which uses O ̃(n 1/4 ) rounds of communication and O ̃(n 9/4 ) messages, achieving a lower asymptotic round and message complexity than any known algorithms in the classical CONGEST-CLIQUE model. At a high level, we achieve these results by combining classical algorithms with fast quantum subroutines. Additionally, we characterize the constants and logarithmic factors involved in our algorithms, as well as related classical algorithms, revealing that advances are needed to render both practical.

quantum computing↗
NASA NTRSDate not supplied

Quantum-Accelerated Distributed Algorithms for Approximate Steiner Trees and Directed Minimum Spanning Trees

We present two algorithms in the Quantum CONGEST-CLIQUE model of distributed computation that succeed with high probability; One for producing an approximately optimal Steiner Tree, and one for producing an exact Minimum Directed Spanning tree. These use O(n1/4) rounds of communication and O(n9/4) messages, leading to a quantum speedup in round and message complexity compared to any known algorithms in the classical CONGEST-CLIQUE model (vs O(n1/3) and O(n7/3)). At a high level, we achieve these results by combining classical algorithms with fast quantum subroutines. Further, these problems can not be sped up in the CONGEST (non-clique) setting, and we characterize the constants involved.

Phillip Kerger↗
DOE OSTI2024

Using phenology to unravel differential soil water use and productivity in a semiarid savanna

Savannas are water-limited ecosystems characterized by two dominant plant types: trees and an understory primarily made up grass. Different phenology and root structures of these plant types complicate how savanna primary productivity responds to changes in water availability. We tested the hypothesis that productivity in savannas is controlled by the temporal and vertical distribution of soil water content (SWC) and differences in growing season length of understory and tree plant functional types. To quantify the relationship between tree, understory, and savanna-wide phenology and productivity, we used PhenoCam and satellite observations surrounding an eddy covariance tower at a semiarid savanna site in Arizona, USA. We distinguished between SWC across two different depth intervals (shallow, <0–30 cm and deep, >30–100 cm). We found that tree greenness increased with SWC at both depths, while understory greenness was only sensitive to the shallower SWC measurements. Onset of ecosystem dormancy, estimated from satellite observations close to the eddy covariance tower, explained more variability in annual gross primary productivity (GPP) than in other phenometrics. Higher SWC led to an extended growing season, caused by delayed dormancy in trees, but the understory showed no evidence of delayed dormancy in wetter periods. We infer that the timing of ecosystem scale dormancy, driven by trees, is important in understanding changes in a savanna's GPP. These findings highlight the important effects of rainfall during the winter. These findings suggest that savanna GPP is conditional on different responses to moisture availability in each of the dominant vegetation components.

54 ENVIRONMENTAL SCIENCES↗
NASA NTRSDate not supplied

Establishing an Urban Heat Exposure Severity Index for Infrastructure Prioritization in Tempe, Arizona, Using NASA Earth Observations and LiDAR

Located on the banks of the Salt River in the Sonoran Desert, Tempe, Arizona, features a semi-arid climate with summer daily maximum temperatures regularly exceeding 37.8°C. Tempe is also subject to the southwestern monsoon season from July-September and the humidity exacerbates the high temperatures. Furthermore, the rapid urbanization experienced in Tempe has resulted in an intensification of the urban heat island. The summer of 2020 shattered the previous record of days exceeding 43.4°C, leading to higher energy and water costs, lower comfort, and increased risk of heat stroke for residents. Recognizing the impacts of extreme heat, the City of Tempe partnered with the Healthy Urban Environments initiative and NASA DEVELOP to identify census tracts that experience a higher mean land surface temperature than the city average. The NASA DEVELOP team used remotely sensed land surface temperature (LST), normalized difference vegetation index (NDVI), normalized difference built-up index (NDBI), normalized difference water index (NDWI), and albedo data calculated from Aqua Moderate Resolution Imaging Spectroradiometer (MODIS) and Landsat 8 Operational Land Imager (OLI) and Thermal Infrared Sensor (TIRS) instruments from 2015 to 2020 to create heat hazard and exposure maps. LiDAR point cloud data, provided by the United States Geological Survey through Arizona State University’s Map and Geospatial Hub, were used to derive 3D buildings, building footprints, and tree point data for a shading analysis of walking paths, roads, and buildings at the census tract level. In situ meteorological measurements including air temperature and humidity were used to compare the macro-scale temperature measurements. The team worked with the City of Tempe to develop a methodology to process available data and identify areas of highest concern for urban heat effects within the city. With these insights, Tempe, Arizona can better address these issues with data-driven information to make decisions regarding heat mitigation and adaptation efforts.

John Dialesandro↗
DOE OSTI2021

Deciphering the source of primary biological aerosol particles: a pollen case study

Primary biological aerosol particles (PBAPs) are microscopic solids suspended in the atmosphere emitted by biological systems and play critical roles in the atmosphere and at the atmosphere-biosphere interface, impacting human health, climate, and the ecosystem function. Understanding the sources of PBAPs is necessary to decipher the mechanistic interactions between aerosols, climate, and distinct ecosystem components. However, the detection of specific PBAPs in complex ambient aerosol samples is challenging. We performed metabolomics analyses of pollen from three pollinating tree species and ambient samples collected during the peak pollination period of each species. Random Forest and sPLS-DA machine learning methods were employed to evaluate whether metabolic signatures of ambient samples can reveal the source of the main pollen particles present in the atmosphere. Our results suggest that atmospheric eco-metabolomics techniques combined with sophisticated statistical methods can decipher the origin of abundant PBAPs from complex ambient samples. Developing complete libraries containing high-resolution metabolomic fingerprints of the major PBAPs present in the atmosphere would significantly advance future research to accurately understand the role of PBAPs in the atmosphere, ecosystems and human health.

Rivas-Ubach, Albert↗
DOE OSTI2022

Tradeoffs in forest resilience to satellite-based estimates of water and productivity losses

Climate change is expected to intensify the global hydrological cycle via increased evapotranspiration (ET). Changes in ET have important consequences for water-related ecosystem services as well as for forest productivity. Forests play a critical role in ET: active trees sequester carbon at the expense of losing water, yet if they are not active, water remains in the trees, but productivity stalls. Here, we estimated the capacity of forests to recover (resilience) from extreme water or productivity losses based on modeled ET through remote sensing methods across the conterminous USA. Results show there is a spatial tradeoff in resilience to water or productivity losses. Forests were more resilient to water loss in the drier west, and more resilient to productivity loss in the wetter east. Still, resilience was highly heterogeneous across the continent. Projections under climate change indicate both declines and increases of up to 13% in forest resilience, with broad regional trends but high spatial heterogeneity within regions. This study brings crucial satellite-based insights on how water dynamics, and consequentially productivity and water provision in forests, might be impacted by climate change.

54 ENVIRONMENTAL SCIENCES↗
DOE OSTI2020

Molecular understanding of the suppression of new-particle formation by isoprene

Nucleation of atmospheric vapours produces more than half of global cloud condensation nuclei and so has an important influence on climate. Recent studies show that monoterpene ( C 10 H 16 ) oxidation yields highly oxygenated products that can nucleate with or without sulfuric acid. Monoterpenes are emitted mainly by trees, frequently together with isoprene ( C 5 H 8 ), which has the highest global emission of all organic vapours. Previous studies have shown that isoprene suppresses new-particle formation from monoterpenes, but the cause of this suppression is under debate. Here, in experiments performed under atmospheric conditions in the CERN CLOUD chamber, we show that isoprene reduces the yield of highly oxygenated dimers with 19 or 20 carbon atoms – which drive particle nucleation and early growth – while increasing the production of dimers with 14 or 15 carbon atoms. The dimers (termed C 20 and C 15 , respectively) are produced by termination reactions between pairs of peroxy radicals ( RO 2 • ) arising from monoterpenes or isoprene. Compared with pure monoterpene conditions, isoprene reduces nucleation rates at 1.7 nm (depending on the isoprene / monoterpene ratio) and approximately halves particle growth rates between 1.3 and 3.2 nm. However, above 3.2 nm, C 15 dimers contribute to secondary organic aerosol, and the growth rates are unaffected by isoprene. We further show that increased hydroxyl radical ( OH • ) reduces particle formation in our chemical system rather than enhances it as previously proposed, since it increases isoprene-derived RO 2 • radicals that reduce C 20 formation. RO 2 • termination emerges as the critical step that determines the highly oxygenated organic molecule (HOM) distribution and the corresponding nucleation capability. Species that reduce the C 20 yield, such as NO, HO 2 and as we show isoprene, can thus effectively reduce biogenic nucleation and early growth. Therefore the formation rate of organic aerosol in a particular region of the atmosphere under study will vary according to the precise ambient conditions.

54 ENVIRONMENTAL SCIENCES↗