Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “spanning 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.

At least 19 records
All sourcesNASA NTRSDOE OSTI
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-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↗
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↗
DOE OSTI2023

A single-tree algorithm to compute the Euclidean minimum spanning tree on GPUs

Computing the Euclidean minimum spanning tree (Emst) is a computationally demanding step of many algorithms. While work-efficient serial and multithreaded algorithms for computing Emst are known, designing an efficient GPU algorithm is challenging due to a complex branching structure, data dependencies, and load imbalances. In this paper, we propose a single-tree $Bor\mathring{u}vka$-based algorithm for computing Emst on GPUs. We use an efficient nearest neighbor algorithm and reduce the number of the required distance calculations by avoiding traversing subtrees with leaf nodes in the same component. The developed algorithms are implemented in a performance portable way using ArborX, an open-source geometric search library based on the Kokkos framework. We evaluate the proposed algorithm on various 2D and 3D datasets, show and compare it with the current state-of-the-art open-source CPU implementations. We demonstrate 4-24 × speedup over the fastest multi-threaded implementation. We prove the portability of our implementation by providing results on a variety of hardware: AMD EPYC 7763, Nvidia A100 and AMD MI250X. We show scalability of the implementation, computing Emst for 37 million 3D cosmological dataset in under a 0.5 second on a single A100 Nvidia GPU.

Prokopenko, Andrey↗
NASA NTRS2005

At-Least Version of the Generalized Minimum Spanning Tree Problem: Optimization Through Ant Colony System and Genetic Algorithms

The At-Least version of the Generalized Minimum Spanning Tree Problem (L-GMST) is a problem in which the optimal solution connects all defined clusters of nodes in a given network at a minimum cost. The L-GMST is NPHard; therefore, metaheuristic algorithms have been used to find reasonable solutions to the problem as opposed to computationally feasible exact algorithms, which many believe do not exist for such a problem. One such metaheuristic uses a swarm-intelligent Ant Colony System (ACS) algorithm, in which agents converge on a solution through the weighing of local heuristics, such as the shortest available path and the number of agents that recently used a given path. However, in a network using a solution derived from the ACS algorithm, some nodes may move around to different clusters and cause small changes in the network makeup. Rerunning the algorithm from the start would be somewhat inefficient due to the significance of the changes, so a genetic algorithm based on the top few solutions found in the ACS algorithm is proposed to quickly and efficiently adapt the network to these small changes.

Janich, Karl W.↗
NASA NTRS1990

Using minimal spanning trees to compare the reliability of network topologies

Graph theoretic methods are applied to compute the reliability for several types of networks of moderate size. The graph theory methods used are minimal spanning trees for networks with bi-directional links and the related concept of strongly connected directed graphs for networks with uni-directional links. A comparison is conducted of ring networks and braided networks. The case is covered where just the links fail and the case where both links and nodes fail. Two different failure modes for the links are considered. For one failure mode, the link no longer carries messages. For the other failure mode, the link delivers incorrect messages. There is a description and comparison of link-redundancy versus path-redundancy as methods to achieve reliability. All the computations are carried out by means of a fault tree program.

Leister, Karen J.↗
DOE OSTI2020

Neuromorphic Graph Algorithms: Extracting Longest Shortest Paths and Minimum Spanning Trees

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. Traditionally speaking, a majority of the use cases for neuromorphic systems have been in the field of machine learning. In order to expand their usability, it is imperative that neuromorphic systems be used for non-machine learning tasks as well. The structural aspects of neuromorphic systems (i.e., neurons and synapses) are similar to those of graphs (i.e., nodes and edges), However, it is not obvious how graph algorithms would translate to their neuromorphic counterparts. In this work, we propose a preprocessing technique that introduces fractional offsets on the synaptic delays of neuromorphic graphs in order to break ties. This technique, in turn, enables two graph algorithms: longest shortest path extraction and minimum spanning trees.

Kay, Bill↗
NASA NTRS2019

Exploring Network-Related Optimization Problems Using Quantum Heuristics

Network-related connectivity optimization problems are underlying a wide range of applications and are also of high computational complexity. We consider studying network optimization problems using two types of quantum heuristics.One is quantum annealing, and the other Quantum Alternating Operator Ansatz, an extension of the Quantum Approximate Optimization Algorithms for gate-model quantum computation, in which a cost-function based unitary and a non-commuting mixing unitary are applied alternately. We present problem mappings for problems of finding the spanning-tree or spanning-graph of a graph that optimizes certain costs, and a variant that further requires the spanning-tree be degree-bounded. With quantum annealing, all constraints are cast into penalty terms in the cost Hamiltonian, and the solution is encoded as the ground state of the Hamiltonian. We provide three mappings to the quadratic unconstrained binary optimization (QUBO) form, compare the resource requirements, and analyze the tradeoffs. For QAOA, we give special focus on the design of mixers based on the constraints presented in the problem, such that the system evolution remains in a subspace of the full Hilbert space where all constraints are satisfied. In the spanning-tree problem, one such hard constraint is that a mixer applied to a spanning-tree needs also be a spanning tree. This involves checking the connectivity of a subgraph, which is a global condition common for most network-related problems. We show how this feature can be efficiently represented in the mixer in a quantum coherent way, based on manipulation of a descendant-matrix and an adjacent matrix. We further develop a mixer for the spanning-graphs based on the spanning-tree mixer.

Wang, Zhihui↗
NASA NTRS2019

Study network-related optimization problems using quantum alternating optimization ansatz

Network-related connectivity optimization problems are underlying a wide range of applications and are also of high computational complexity. We consider studying network optimization problems using two types of quantum heuristics. One is quantum annealing, and the other Quantum Alternating Operator Ansatz, an extension of the Quantum Approximate Optimization Algorithms for gate-model quantum computation, in which a cost-function based unitary and a non-commuting mixing unitary are applied alternately. We present problem mappings for problems of finding the spanning-tree or spanning-graph of a graph that optimizes certain costs, and a variant that further requires the spanning-tree be degree-bounded. With quantum annealing, all constraints are cast into penalty terms in the cost Hamiltonian, and the solution is encoded as the ground state of the Hamiltonian. We provide three mappings to the quadratic unconstrained binary optimization (QUBO) form, compare the resource requirements, and analyze the tradeoffs. For QAOA, we give special focus on the design of mixers based on the constraints presented in the problem, such that the system evolution remains in a subspace of the full Hilbert space where all constraints are satisfied. In the spanning-tree problem, one such hard constraint is that a mixer applied to a spanning-tree needs also be a spanning tree. This involves checking the connectivity of a subgraph, which is a global condition common for most network-related problems. We show how this feature can be efficiently represented in the mixer in a quantum coherent way, based on manipulation of a descendant-matrix and an adjacent matrix. We further develop a mixer for the spanning-graphs based on the spanning-tree mixer.

Zhihui Wang↗
DOE OSTI2021

An automated procedure built on MTEX for reconstructing deformation twin hierarchies from electron backscattered diffraction datasets of heavily twinned microstructures

Here we present a set of algorithms built on the MTEX and MATLAB graph toolboxes for automatic reconstruction of deformation twin hierarchies from Electron Backscatter Diffraction (EBSD) datasets with a focus on developing methods for heavily twinned microstructures (twin fractions >0.5). The algorithms address key issues arising at large strains, mainly: missing twin relationships, grouping of heavily deformed grain fragments into families of similar orientation originating from a single initial grain, identification of parent fragments for large twin volume fractions, and classification of families having twin relationships with multiple families. To facilitate the development of these algorithms, large-grained ultra-high purity α-Ti deformed in compression along two directions is investigated. Graphs are utilized to handle non-local geometric merging and to represent relationships throughout the reconstruction process. When determining if a grain fragment is from the undeformed microstructure, the combined metrics of the fragment's orientation volume fraction in the initial texture and the directed graph centrality measure of out-closeness (the number of nodes reached in a graph from a given node) are essential. To address automation in reconstructing the sequence of twinning and relating fragments originating from a single grain in the initial microstructure, the twin family tree is formulated as a minimum spanning tree emanating from the initial grain family. A scheme constructing the distances associated with twin relationship comprising the spanning tree is developed, and a novel quasi-directional Prim spanning tree algorithm is used to determine the twin family tree. The procedure is demonstrated to significantly improve the level of automation in reconstructing twin hierarchies in heavily twinned microstructure compared to other methodologies in literature. The procedure can readily be applied to analyses of twinning in metals, as well as provide an approach for routinely extracting twin statistics at larger deformation levels than previously possible. Significantly, the procedure is demonstrated to be capable of identifying third generation twinning in α-Ti microstructures.

36 MATERIALS SCIENCE↗
DOE OSTI2022

Scalable access to shared files in a distributed system

Logic may pre-populate cache of compute nodes allocated to a user's session. Logic may access an image file of a global filesystem, the image file to comprise a first set of one or more files associated with a user session and a second set of one or more files upon which execution of the first set will depend. Logic may store the image file in local data storage of each compute node of a spanning tree of compute nodes allocated for the user session. Logic may unpack the image file based on the data. Logic may configure the local environment of each compute node in the spanning tree to identify a location in local memory of each of the files. And logic may initiate execution of a local filesystem service in each of the compute nodes of the spanning tree.

Oganezov, Alexander↗
DOE OSTI2024

PANDORA: A Parallel Dendrogram Construction Algorithm for Single Linkage Clustering on GPU

This paper introduces Pandora, a parallel algorithm for computing dendrograms, the hierarchical cluster trees for single linkage clustering (SLC). Current parallel approaches construct dendrograms by partitioning a minimum spanning tree and removing edges. However, they struggle with skewed, hard-to-parallelize real-world dendrograms. Consequently, computing dendrograms is the sequential bottleneck in HDBSCAN*[21], a popular SLC variant. Pandora uses recursive tree contraction to address this limitation. Pandora contracts nodes to construct progressively smaller trees. It computes the smallest contracted dendrogram and expands it by inserting contracted edges. This recursive strategy is highly parallel, skew-independent, work-optimal, and well-suited for GPUs and multicores. We develop a performance portable implementation of Pandora in Kokkos[31] and evaluate its performance on multicore CPUs and multi-vendor GPUs (e.g., Nvidia, AMD) for dendrogram construction in HDBSCAN*. Multithreaded Pandora is 2.2x faster than the current best-multithreaded implementation. Our GPU version achieves 6-20x speedup on AMD GPUs and 10-37x on NVIDIA GPUs over multithreaded Pandora. Pandora removes HDBSCAN*’s sequential bottleneck, greatly boosting efficiency, particularly with GPUs.

Sao, Piyush↗
NASA NTRS1993

Experimental evaluation of the certification-trail method

Certification trails are a recently introduced and promising approach to fault-detection and fault-tolerance. A comprehensive attempt to assess experimentally the performance and overall value of the method is reported. The method is applied to algorithms for the following problems: huffman tree, shortest path, minimum spanning tree, sorting, and convex hull. Our results reveal many cases in which an approach using certification-trails allows for significantly faster overall program execution time than a basic time redundancy-approach. Algorithms for the answer-validation problem for abstract data types were also examined. This kind of problem provides a basis for applying the certification-trail method to wide classes of algorithms. Answer-validation solutions for two types of priority queues were implemented and analyzed. In both cases, the algorithm which performs answer-validation is substantially faster than the original algorithm for computing the answer. Next, a probabilistic model and analysis which enables comparison between the certification-trail method and the time-redundancy approach were presented. The analysis reveals some substantial and sometimes surprising advantages for ther certification-trail method. Finally, the work our group performed on the design and implementation of fault injection testbeds for experimental analysis of the certification trail technique is discussed. This work employs two distinct methodologies, software fault injection (modification of instruction, data, and stack segments of programs on a Sun Sparcstation ELC and on an IBM 386 PC) and hardware fault injection (control, address, and data lines of a Motorola MC68000-based target system pulsed at logical zero/one values). Our results indicate the viability of the certification trail technique. It is also believed that the tools developed provide a solid base for additional exploration.

Sullivan, Gregory F.↗
DOE OSTI2025

Graph-Theoretic Approaches to Quantifying Power System Resiliency

Although gaining growing importance, the subject of power system resiliency still lacks a commonly acknowledged metric. As a contribution to solving this complication, in this paper we leverage the concepts of spanning trees and Fiedler value from graph theory to propose two topology-based indices for quantifying the resiliency of power systems. The proposed indices require least information and may be applied to any other flow network, such as water or gas pipeline networks.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2025

Enabling Real-Time Communication in Multi-Agent Systems: A Graph Neural Network Based Approach

Global connectivity enables effective coordination in Multi-Agent Systems (MAS). Solving these connection problems under hardware constraints is an NP-hard non-Euclidean Degree Constrained Minimum Spanning Tree (DCMST) problem. Prior MAS controllers coordinate team movement for task completion and collision avoidance; some considering Line-of-Sight (LOS) maintenance but prioritizing flexibility over guarantees. Evolutionary Algorithms (EA) have been shown to find good solutions for DCMST, but their performance degrades with larger populations required to support a large MAS. We present a method based on edge graph attention networks, trained offline to reduce online computation times. Empirical comparisons with greedy polynomial-time solvers and EA show that our method leverages latent graph information to consistently find constraint-satisfying solutions in less time.

connectivity maintenance↗
NASA NTRS1984

Augmenting computer networks

Three methods of augmenting computer networks by adding at most one link per processor are discussed: (1) A tree of N nodes may be augmented such that the resulting graph has diameter no greater than 4log sub 2((N+2)/3)-2. Thi O(N(3)) algorithm can be applied to any spanning tree of a connected graph to reduce the diameter of that graph to O(log N); (2) Given a binary tree T and a chain C of N nodes each, C may be augmented to produce C so that T is a subgraph of C. This algorithm is O(N) and may be used to produce augmented chains or rings that have diameter no greater than 2log sub 2((N+2)/3) and are planar; (3) Any rectangular two-dimensional 4 (8) nearest neighbor array of size N = 2(k) may be augmented so that it can emulate a single step shuffle-exchange network of size N/2 in 3(t) time steps.

Bokhari, S. H.↗