Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “graph algorithm”

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

Graph Contractions for Calculating Correlation Functions in Lattice QCD

Computing correlation functions for many-particle systems in Lattice QCD is vital to extract nuclear physics observables like the energy spectrum of hadrons such as protons. However, this type of calculation has long been considered to be very challenging and computing-resource intensive because of the complex nature of a hadron composed of quarks with many degrees of freedom. In particular, a correlation function can be calculated through a sum of all possible pairs of quark contractions, each of which is a batched tensor contraction, dictated by Wick's theorem. Because the number of terms of this sum can be very large for any hadronic system of interest, fast evaluation of the sum faces several challenges: an extremely large number of contractions, a huge memory footprint at runtime, and the speed of tensor contractions. In this paper, we present a Lattice QCD analysis software suite, Redstar, which addresses these challenges by utilizing novel algorithmic and software engineering methods targeting modern computing platforms such as many-core CPUs and GPUs. In particular, Redstar represents every term in the sum of a correlation function by a graph, applies efficient graph algorithms to reduce the number of contractions to lower the cost of computations, and minimizes the total memory footprint. Moreover, Redstar carries out the contractions on either CPUs or GPUs utilizing an internal and highly efficient Hadron contraction library. Specifically, we illustrate some important algorithmic optimizations of Redstar, show various key design features of Hadron library, and present the speedup values due to the optimizations along with performance figures for calculating six correlations functions on four computing platforms.

Chen, Jie↗
DOE OSTI2023

Graph Contractions for Calculating Correlation Functions in Lattice QCD

Computing correlation functions for many-particle systems in Lattice QCD is vital to extract nuclear physics observables like the energy spectrum of hadrons such as protons. However, this type of calculation has long been considered to be very challenging and computing-resource intensive because of the complex nature of a hadron composed of quarks with many degrees of freedom. In particular, a correlation function can be calculated through a sum of all possible pairs of quark contractions, each of which is a batched tensor contraction, dictated by Wick's theorem. Because the number of terms of this sum can be very large for any hadronic system of interest, fast evaluation of the sum faces several challenges: an extremely large number of contractions, a huge memory footprint at runtime, and the speed of tensor contractions. In this paper, we present a Lattice QCD analysis software suite, Redstar, which addresses these challenges by utilizing novel algorithmic and software engineering methods targeting modern computing platforms such as many-core CPUs and GPUs. In particular, Redstar represents every term in the sum of a correlation function by a graph, applies efficient graph algorithms to reduce the number of contractions to lower the cost of computations, and minimizes the total memory footprint. Moreover, Redstar carries out the contractions on either CPUs or GPUs utilizing an internal and highly efficient Hadron contraction library. Specifically, we illustrate some important algorithmic optimizations of Redstar, show various key design features of Hadron library, and present the speedup values due to the optimizations along with performance figures for calculating six correlations functions on four computing platforms.

Chen, Jie↗
DOE OSTI2020

Using Graph Edit Distance for Noisy Subgraph Matching of Semantic Property Graphs

The subgraph matching problem is a fundamental problem in graph theory that is known to be NP-complete. In this study, performers were asked to develop algorithms to search for semantic property graphs that were subgraphs of a large knowledge graph. The templates provided contained structural information about the subgraphs and some attributes for each node and edge. There also exists a similarity measure between a set of attribute values that occurs on every node and edge. Algorithms performed well in the case where an exact match existed, but performers were also provided templates that had noise added such that there existed no match in the knowledge graph. Performers were asked to find the closest matches to those noisy subgraphs. To evaluate performance on this task, we developed a version of the graph edit distance algorithm to measure the cost of editing the template graph so that it is isomorphic in structure and attributes to the performer submission.

Ebsch, Christopher L.↗
NASA NTRS1988

Overview and extensions of a system for routing directed graphs on SIMD architectures

Many problems can be described in terms of directed graphs that contain a large number of vertices where simple computations occur using data from adjacent vertices. A method is given for parallelizing such problems on an SIMD machine model that uses only nearest neighbor connections for communication, and has no facility for local indirect addressing. Each vertex of the graph will be assigned to a processor in the machine. Rules for a labeling are introduced that support the use of a simple algorithm for movement of data along the edges of the graph. Additional algorithms are defined for addition and deletion of edges. Modifying or adding a new edge takes the same time as parallel traversal. This combination of architecture and algorithms defines a system that is relatively simple to build and can do fast graph processing. All edges can be traversed in parallel in time O(T), where T is empirically proportional to the average path length in the embedding times the average degree of the graph. Additionally, researchers present an extension to the above method which allows for enhanced performance by allowing some broadcasting capabilities.

Tomboulian, Sherryl↗
DOE OSTI2024

Multi-Agent Graph-Attention Deep Reinforcement Learning for Post-Contingency Grid Emergency Voltage Control

Grid emergency voltage control (GEVC) is paramount in electric power systems to improve voltage stability and prevent cascading outages and blackouts in case of contingencies. While most deep reinforcement learning (DRL)-based paradigms perform single agents in a static environment, real-world agents for GEVC are expected to cooperate in a dynamically shifting grid. Moreover, due to high uncertainties from combinatory natures of various contingencies and load consumption, along with the complexity of dynamic grid operation, the data efficiency and control performance of the existing DRL-based methods are challenged. To address these limitations, we propose a multi-agent graph-attention (GATT)-based DRL algorithm for GEVC in multi-area power systems. Here, we develop graph convolutional network (GCN)-based agents for feature representation of the graph-structured voltages to improve the decision accuracy in a data-efficient manner. Furthermore, a cutting-edge attention mechanism concentrates on effective information sharing among multiple agents, synergizing different-sized subnetworks in the grid for cooperative learning. We address several key challenges in the existing DRL-based GEVC approaches, including low scalability and poor stability against high uncertainties. Test results in the IEEE benchmark system verify the advantages of the proposed method over several recent multi-agent DRL-based algorithms.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2020

Online Event Detection in Synchrophasor Data with Graph Signal Processing

Online detection of anomalies is crucial to enhancing the reliability and resiliency of power systems. We propose a novel data-driven online event detection algorithm with synchrophasor data using graph signal processing. In addition to being extremely scalable, our proposed algorithm can accurately capture and leverage the spatio-temporal correlations of the streaming PMU data. This paper also develops a general technique to decouple spatial and temporal correlations in multiple time series. Finally, we develop a unique framework to construct a weighted adjacency matrix and graph Laplacian for product graph. Case studies with real-world, large-scale synchrophasor data demonstrate the scalability and accuracy of our proposed event detection algorithm. Compared to the state-of-the-art benchmark, the proposed method not only achieves higher detection accuracy but also yields higher computational efficiency.

Event detection↗
DOE OSTI2020

Online Event Detection in Synchrophasor Data with Graph Signal Processing

Online detection of anomalies is crucial to enhancing the reliability and resiliency of power systems. We propose a novel data-driven online event detection algorithm with synchrophasor data using graph signal processing. In addition to being extremely scalable, our proposed algorithm can accurately capture and leverage the spatio-temporal correlations of the streaming PMU data. This paper also develops a general technique to decouple spatial and temporal correlations in multiple time series. Finally, we develop a unique framework to construct a weighted adjacency matrix and graph Laplacian for product graph. Case studies with real-world, large-scale synchrophasor data demonstrate the scalability and accuracy of our proposed event detection algorithm. Compared to the state-of-the-art benchmark, the proposed method not only achieves higher detection accuracy but also yields higher computational efficiency.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2021

Impact of graph structures for QAOA on MaxCut

The quantum approximate optimization algorithm (QAOA) is a promising method of solving combinatorial optimization problems using quantum computing. QAOA on the MaxCut problem has been studied extensively on graphs with specific structure; however, little is known about the general performance of the algorithm on arbitrary graphs. Here, we investigate how different graph characteristics correlate with QAOA performance at depths at most three on the MaxCut problem for all connected non-isomorphic graphs with at most eight vertices. Some good predictors of QAOA success relate to graph symmetries, odd cycles, and density. For example, on eight vertex graphs, the average probability for selecting an optimal solution for graphs that contain no odd cycles after three iterations of QAOA is 60.6% compared to 48.2% for those that do. The data generated from these studies are shared in a publicly accessible database to serve as a benchmark for QAOA calculations and experiments. Knowing the relationship between structure and performance can be used to identify classes of combinatorial problems that are likely to exhibit a quantum advantage.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

GraMeR: Gra ph Me ta R einforcement learning for multi-objective influence maximization

Influence maximization (IM) is a combinatorial problem of identifying a subset of seed nodes in a network (graph), which when activated, provide a maximal spread of influence in the network for a given diffusion model and a budget for seed set size. IM has numerous applications such as viral marketing, epidemic control, sensor placement and other network-related tasks. However, its practical uses are limited due to the computational complexity of current algorithms. Recently, deep reinforcement learning has been leveraged to solve IM in order to ease the computational burden. However, there are serious limitations in current approaches, including narrow IM formulation that only consider influence via spread and ignore self-activation, low scalability to large graphs, and lack of generalizability across graph families leading to a large running time for every test network. In this work, we address these limitations through a unique approach that involves: (1) Formulating a generic IM problem as a Markov decision process that handles both intrinsic and influence activations; (2)incorporating generalizability via meta-learning across graph families. There are previous works that combine deep reinforcement learning with graph neural network, but this work solves a more realistic IM problem and incorporates generalizability across graphs via meta reinforcement learning. Extensive experiments are carried out in various standard networks to validate performance of the proposed Graph Meta Reinforcement learning (GraMeR) framework. Finally, the results indicate that GraMeR is multiple orders faster and generic than conventional approaches when applied on small to medium scale graphs.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

Decomposition Algorithms for Solving NP-hard Problems on a Quantum Annealer

NP-hard problems such as the maximum clique or minimum vertex cover problems, two of Karp’s 21 NP-hard problems, have several applications in computational chemistry, biochemistry and computer network security. Adiabatic quantum annealers can search for the optimum value of such NP-hard optimization problems, given the problem can be embedded on their hardware. However, this is often not possible due to certain limitations of the hardware connectivity structure of the annealer. This paper studies a general framework for a decomposition algorithm for NP-hard graph problems aiming to identify an optimal set of vertices. Our generic algorithm allows us to recursively divide an instance until the generated subproblems can be embedded on the quantum annealer hardware and subsequently solved. Furthermore, the framework is applied to the maximum clique and minimum vertex cover problems, and we propose several pruning and reduction techniques to speed up the recursive decomposition. The performance of both algorithms is assessed in a detailed simulation study.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

Heterogeneous Graph Neural Network for identifying hadronically decayed tau leptons at the High Luminosity LHC

Here, we present a new algorithm that identifies reconstructed jets originating from hadronic decays of tau leptons against those from quarks or gluons. No tau lepton reconstruction algorithm is used. Instead, the algorithm represents jets as heterogeneous graphs with tracks and energy clusters as nodes and trains a Graph Neural Network to identify tau jets from other jets. Different attributed graph representations and different GNN architectures are explored. We propose to use differential track and energy cluster information as node features and a heterogeneous sequentially-biased encoding for the inputs to final graph-level classification.

47 OTHER INSTRUMENTATION↗
NASA NTRSDate not supplied

Formalization of the Bellman-Ford Algorithm for Airspace Applications

This paper describes the formal verification of one of the most well-known algorithms for finding the shortest path between all vertices in a directed graph, namely the Bellman-Ford algorithm. This formal verification, performed in the Prototype Verification System (PVS), is motivated by two applications in the aerospace domain which use the algorithm for path planning. The first is a pre-flight calculation that uses an adapted version of Bellman-Ford to find a route intended to maximize GNSS availability throughout the flight. The second is a more traditional application intended to find the shortest path between an autonomous aircraft's current position and a goal waypoint, while avoiding regions of space specified by geofences. A novel aspect of this formal verification effort is the inclusion of two distinct models of computation for the algorithm, one being a traditional serial computation, and the other being an explicitly parallel computation. The ability to use parallel computation in the Bellman-Ford algorithm is in fact why it was chosen over other traditionally more performant algorithms, especially for the GNSS application, where the size of the graph makes a purely serial computation infeasible.

formal verification↗
NASA NTRS2022

A Unifying View of Estimation and Control Using Belief Propagation With Application to Path Planning

The use of estimation techniques on stochastic models to solve control problems is an emerging paradigm that falls under the rubric of Active Inference (AI) and Control as Inference (CAI). In this work, we use probability propagation on factor graphs to show that various algorithms proposed in the literature can be seen as specific composition rules in a factor graph. We show how this unified approach, presented both in probability space and in log of the probability space, provides a very general framework that includes the Sum-product, the Max-product, Dynamic programming and mixed Reward/Entropy criteria-based algorithms. The framework also expands algorithmic design options that lead to new smoother or sharper policy distributions. We propose original recursions such as: a generalized Sum/Max-product algorithm, a Smooth Dynamic programming algorithm and a modified versions of the Reward/Entropy algorithm. The discussion is carried over with reference to a path planning problem where the recursions that arise from various cost functions, although they may appear similar in scope, bear noticeable differences. We provide a comprehensive table of composition rules and a comparison through simulations, first on a synthetic small grid with a single goal with obstacles, and then on a grid extrapolated from a real-world scene with multiple goals and a semantic map.

Francesco A. N. Palmieri↗
NASA NTRSDate not supplied

Cooperative Clustering Techniques For Space Network Scalability

Routing in the space internet must face many unique challenges - from unplanned disconnections and interruptions to predictable intermittent connectivity due to high network mobility and long propagation delays. NASA’s current approach to such routing is Contact Graph Routing (CGR), using a graph formed of prescheduled communication contacts to compute routes through the network. While this approach manages to tackle issues of connectivity and propagation delays, it is a global approach that requires continuous knowledge of the entire network. In a potential future Solar Space Internet (SSI) such an approach on its own cannot scale to large networks with thousands of members. In this paper we propose clustering as a solution to CGR scalability. Clustering has been used in many networking problems as a way to subdivide the network and allow for localized routing and better scalability. Using techniques from graph theory and game theory, we explore various existing clustering algorithms and adapt them to the Contact Graph Routing setting. We propose a way to combine multiple algorithms to create a Delay Tolerant Clustering Protocol (DTCP). In addition, we explore the underlying networking mechanisms such as multicast, neighbor discovery, and software defined networking that may be used to enable DTCP.

Delay Tolerant Networking↗
DOE OSTI2023

Integrated Land Suitability Assessment for Depots Siting in a Sustainable Biomass Supply Chain

A sustainable biomass supply chain would require not only an effective and fluid transportation system with a reduced carbon footprint and costs, but also good soil characteristics ensuring durable biomass feedstock presence. Unlike existing approaches that fail to account for ecological factors, this work integrates ecological as well as economic factors for developing sustainable supply chain development. For feedstock to be sustainably supplied, it necessitates adequate environmental conditions, which need to be captured in supply chain analysis. Using geospatial data and heuristics, we present an integrated framework that models biomass production suitability, capturing the economic aspect via transportation network analysis and the environmental aspect via ecological indicators. Production suitability is estimated using scores, considering both ecological factors and road transportation networks. These factors include land cover/crop rotation, slope, soil properties (productivity, soil texture, and erodibility factor) and water availability. This scoring determines the spatial distribution of depots with priority to fields scoring the highest. Two methods for depot selection are presented using graph theory and a clustering algorithm to benefit from contextualized insights from both and potentially gain a more comprehensive understanding of biomass supply chain designs. Graph theory, via the clustering coefficient, helps determine dense areas in the network and indicate the most appropriate location for a depot. Clustering algorithm, via K-means, helps form clusters and determine the depot location at the center of these clusters. An application of this innovative concept is performed on a case study in the US South Atlantic, in the Piedmont region, determining distance traveled and depot locations, with implications on supply chain design. The findings from this study show that a more decentralized depot-based supply chain design with 3depots, obtained using the graph theory method, can be more economical and environmentally friendly compared to a design obtained from the clustering algorithm method with 2 depots. In the former, the distance from fields to depots totals 801,031,476 miles, while in the latter, it adds up to 1,037,606,072 miles, which represents about 30% more distance covered for feedstock transportation.

29 ENERGY PLANNING, POLICY, AND ECONOMY↗
DOE OSTI2022

Examination of Haines Jump in Microfluidic Experiments via Evolution Graphs and Interface Tracking

This work examines a type of rapid pore-filling event in multiphase flow through permeable media that is better known as Haines Jump. While existing microfluidic experiments on Haines Jump mostly seek to maintain quasi-steady states through very low bulk flow rates over long periods of time, this work explores the combined use of a highly structured microscale transport network, high-speed fluorescent microscopy, displacement front segmentation algorithms, and a tracking algorithm to build evolution graphs that track displacement fronts as they evolve through high-speed video recording. The resulting evolution graph allows the segmentation of a high-speed recording in both space and time, potentially facilitating topology-cognitive computation on the transport network. Occurrences of Haines Jump are identified in the microfluidic displacement experiments and their significance in bulk flow rates is qualitatively analyzed. The bulk flow rate has little effect on the significance of Haines Jump during merging and splitting, but large bulk flow rates may obscure small bursts at the narrowest part of the throat.

permeable media↗
DOE OSTI2025

ScaWL: Scaling k-WL (Weisfeiler-Lehman) Algorithms in Memory and Performance on Shared and Distributed-Memory Systems

The k-dimensional Weisfeiler-Lehman (k-WL) algorithm—developed as an efficient heuristic for testing if two graphs are isomorphic—is a fundamental kernel for node embedding in the emerging field of graph neural networks. Unfortunately, the k-WL algorithm has exponential storage requirements, limiting the size of graphs that can be handled. This work presents a novel k-WL scheme with a storage requirement orders of magnitude lower while maintaining the same accuracy as the original k-WL algorithm. Due to the reduced storage requirement, our scheme allows for processing much bigger graphs than previously possible on a single compute node. For even bigger graphs, we provide the first distributed-memory implementation. Our k-WL scheme also has significantly reduced communication volume and offers high scalability. Our experimental results demonstrate that our approach is significantly faster and has superior scalability compared to five other implementations employing state-of-the-art techniques.

algorithims↗
DOE OSTI2021

Quantum Algorithm for Approximating Maximum Independent Sets

We present a quantum algorithm for approximating maximum independent sets of a graph based on quantum non-Abelian adiabatic mixing in the sub-Hilbert space of degenerate ground states, which generates quantum annealing in a secondary Hamiltonian. For both sparse and dense random graphs G , numerical simulation suggests that our algorithm on average finds an independent set of size close to the maximum size α ( G ) in low polynomial time. The best classical algorithms, by contrast, produce independent sets of size about half of α ( G ) in polynomial time.

Physics↗