Search NASA⌕ Search

SEARCH · Search NASA

Results for “graph problems”

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 91 records · Page 5
All sourcesNASA NTRSDOE OSTI
DOE OSTI2020

Decomposition Algorithms for Scalable Quantum Annealing

The presented python code provides wrapper functions for two decomposition algorithms: One algorithm to decompose Maximum Clique problems and one to decompose Minimum Vertex Cover problems. The functions take as input a networkx graph object, and decompose either problem on the input graph recursively into subproblems such that the optimal solution can be constructed from the optimal solutions of both subproblems. The recursion ends as soon as the subproblems reach a pre-specified size limit by the user, and they can be solved using any method provided in advance by the user as external function. This includes exact solvers or an adiabatic quantum annealer.

Pelofske, Elijah↗
DOE OSTI2026

T-FSM: A Scalable Distributed Task-Based System for Frequent Subgraph Pattern Mining from a Big Graph

Finding frequent subgraph patterns in a big graph is an important problem with many applications such as classifying chemical compounds and building indexes to speed up graph queries. Since this problem is NP-hard, some recent parallel and distributed systems have been developed to accelerate the mining. However, they often have a huge memory cost, very long running time, suboptimal load balancing, poor scale-out capability, and possibly inaccurate results. In this article, we propose an efficient system called T-FSM for parallel mining of frequent subgraph patterns in a big graph. T-FSM supports a new anti-monotonic frequentness measure called Fraction-Score, which is more accurate than the widely used MNI measure. The execution engine of T-FSM supports both intra-machine parallelism and inter-machine parallelism. For intra-machine parallelism, T-FSM adopts a novel task-based execution model to ensure high multithreading concurrency, bounded memory consumption, and effective load balancing. For inter-machine parallelism, T-FSM ensures good scale-out performance with a lightweight pattern rebalancing approach that reduces workload skewness of pattern evaluations among machines. To avoid recomputing the contexts for migrated patterns, we design a novel context cache table to support concurrent and asynchronous requesting and caching of remote context data, which can timely evict and garbage collect used pattern contexts that are no longer needed to keep memory consumption bounded. Extensive experiments show that T-FSM is orders of magnitude faster than existing state-of-the-art parallel systems (more than 10×, 51×, 131×, 55× speedup over ScaleMine, DistGraph, Pangolin and Peregrine, respectively) and distributed systems (more than 42× and 88× over ScaleMine and DistGraph, respectively) for frequent subgraph pattern mining, and it scales out satisfactorily to 512 CPU cores on the Polaris supercomputer at Argonne National Laboratory.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

Parallelization techniques for quantum simulation of fermionic systems

Mapping fermionic operators to qubit operators is an essential step for simulating fermionic systems on a quantum computer. We investigate how the choice of such a mapping interacts with the underlying qubit connectivity of the quantum processor to enable (or impede) parallelization of the resulting Hamiltonian-simulation algorithm. It is shown that this problem can be mapped to a path coloring problem on a graph constructed from the particular choice of encoding fermions onto qubits and the fermionic interactions onto paths. The basic version of this problem is called the weak coloring problem. Taking into account the fine-grained details of the mapping yields what is called the strong coloring problem, which leads to improved parallelization performance. A variety of illustrative analytical and numerical examples are presented to demonstrate the amount of improvement for both weak and strong coloring-based parallelizations. Our results are particularly important for implementation on near-term quantum processors where minimizing circuit depth is necessary for algorithmic feasibility.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

The connection between the chromatic numbers of a hypergraph and its 1-intersection graph

A well known problem from an excellent book of Lovász states that any hypergraph with the property that no pair of hyperedges intersect in exactly one vertex can be properly 2-colored. Motivated by this as well as recent works of Keszegh and of Gyárfás et al. we study the 1-intersection graph of a hypergraph. The 1-intersection graph encodes those pairs of hyperedges in a hypergraph that intersect in exactly one vertex. We prove for k ϵ {2, 4} that all hypergraphs whose 1-intersection graph is k-partite can be properly k-colored.

1-intersection graph of hypergraphs↗
DOE OSTI2022

Improved Distributed-memory Triangle Counting by Exploiting the Graph Structure

Graphs are ubiquitous in modeling complex systems and representing interactions between entities to uncover structural information of the domain. Traditionally, graph analytics workloads are challenging to efficiently scale (both strong and weak cases) on distributed memory due to the irregular memory-access driven nature (with little or no computations) of the methods. The structure of graphs and their relative distribution over the processing elements poses another level of complexity, making it difficult to attain sustainable scalability across platforms. In this paper, we discuss enhancements to TriC, a distributed-memory implementation of graph triangle counting using Message Passing Interface (MPI), which was featured in the 2020 Graph Challenge competition. We have made some incremental enhancements to TriC, primarily adopting a user-defined buffering strategy to overcome the startup problem for large graphs (by fixing the memory for intermediate data), and experimenting with probabilistic data structures such as bloom filter to improve the query response time for assessing edge existence, at the expense of increasing the overall false positive rate. These adjustments have led to a modest improvements in most cases, as compared to the previous version.

Graph Analytics, HPC↗
DOE OSTI2021

Discrete Graph Structure Learning for Forecasting Multiple Time Series

Time series forecasting is an extensively studied subject in statistics, economics, and computer science. Exploration of the correlation and causation among the variables in a multivariate time series shows promise in enhancing the performance of a time series model. When using deep neural networks as forecasting models, we hypothesize that exploiting the pairwise information among multiple (multivariate) time series also improves their forecast. If an explicit graph structure is known, graph neural networks (GNNs) have been demonstrated as powerful tools to exploit the structure. In this work, we propose learning the structure simultaneously with the GNN if the graph is unknown. We cast the problem as learning a probabilistic graph model through optimizing the mean performance over the graph distribution. The distribution is parameterized by a neural network so that discrete graphs can be sampled differentiably through reparameterization. Empirical evaluations show that our method is simpler, more efficient, and better performing than a recently proposed bilevel learning approach for graph structure learning, as well as a broad array of forecasting models, either deep or non-deep learning based, and graph or non-graph based.

Shang, Chao↗
NASA NTRS1990

Solving unstructured grid problems on massively parallel computers

A highly parallel graph mapping technique that enables one to efficiently solve unstructured grid problems on massively parallel computers is presented. Many implicit and explicit methods for solving discretized partial differential equations require each point in the discretization to exchange data with its neighboring points every time step or iteration. The cost of this communication can negate the high performance promised by massively parallel computing. To eliminate this bottleneck, the graph of the irregular problem is mapped into the graph representing the interconnection topology of the computer such that the sum of the distances that the messages travel is minimized. It is shown that using the heuristic mapping algorithm significantly reduces the communication time compared to a naive assignment of processes to processors.

Hammond, Steven W.↗
DOE OSTI2024

Loops of loops expansion in the amplituhedron

We study a novel geometric expansion for scattering amplitudes in the planar sector of $\mathcal{N}$ = 4 super Yang-Mills theory, in the context of the Amplituhedron which reproduces the all-loop integrand as a canonical differential form on the positive geometry. In a paper by Arkani-Hamed, Henn and one of the authors, it was shown that this result can be recast in terms of negative geometries with a certain hierarchy of loops (closed cycles) in the space of loop momenta, represented by lines in momentum twistor space. One can then calculate an all-loop order result in the approximation where only tree graphs in the space of all loops are considered. Furthermore, using differential equation methods, it is possible to calculate and resum integrated expressions and obtain strong coupling results. In this paper, we provide a more general framework for the ‘loops of loops’ expansion and outline a powerful method for the determination of differential forms for higher-order geometries. We solve the problem completely for graphs with one internal cycle, but the method can be used more generally for other geometries.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
NASA NTRS1990

Mapping unstructured grid problems to the connection machine

We present a highly parallel graph mapping technique that enables one to solve unstructured grid problems on massively parallel computers. Many implicit and explicit methods for solving discretizated partial differential equations require each point in the discretization to exchange data with its neighboring points every time step or iteration. The time spent communicating can limit the high performance promised by massively parallel computing. To eliminate this bottleneck, we map the graph of the irregular problem to the graph representing the interconnection topology of the computer such that the sum of the distances that the messages travel is minimized. We show that, in comparison to a naive assignment of processors, our heuristic mapping algorithm significantly reduces the communication time on the Connection Machine, CM-2.

Hammond, Steven W.↗
DOE OSTI2021

The Patterson function as auto-hologram and graph enables the direct solution to the phase problem for coherently illuminated atomistic structures

Abstract The coherent Patterson function, derived from the coherent scattering intensities from N atoms, can be described as an auto-holographic image, i.e., the superposition of N -holographic images in which each atom serves as the source of a different reference wave, and as a mathematical graph of the unknown structure. These insights indicate that the unknown structure is significantly over-determined by the inherent information content in a Patterson function by a factor of ( N − 1)/2 (for non-degenerate structures), independent of dimensionality. However, we also show that the ability to resolve the distinct features in the Patterson function depends strongly on details of the experimental design (data range, sampling frequency, and dimensionality). This re-interpretation suggests that the coherent Patterson function provides a natural context for describing the information content in coherent scattering, reveals that there is no inherent phase problem for coherently illuminated pointwise structures, and enables the design of an algorithm which retrieves the structure directly from the Patterson function, without using error metric minimization.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
NASA NTRS1987

A system for routing arbitrary directed graphs on SIMD architectures

There are many problems which can be described in terms of directed graphs that contain a large number of vertices where simple computations occur using data from connecting vertices. A method is given for parallelizing such problems on an SIMD machine model that is bit-serial and uses only nearest neighbor connections for communication. Each vertex of the graph will be assigned to a processor in the machine. Algorithms are given that will be used to implement movement of data along the arcs of the graph. This architecture and algorithms define a system that is relatively simple to build and can do graph processing. All arcs can be transversed in parallel in time O(T), where T is empirically proportional to the diameter of the interconnection network times the average degree of the graph. Modifying or adding a new arc takes the same time as parallel traversal.

Tomboulian, Sherryl↗
DOE OSTI2024

Physics-informed heterogeneous graph neural networks for DC blocker placement

The threat of geomagnetic disturbances (GMDs) to the reliable operation of the bulk energy system has spurred the development of effective strategies for mitigating their impacts. One such approach involves placing transformer neutral blocking devices, which interrupt the path of geomagnetically induced currents (GICs) to limit their impact. The high cost of these devices and the sparsity of transformers that experience high GICs during GMD events, however, calls for a sparse placement strategy that involves high computational cost. To address this challenge, we developed a physics-informed heterogeneous graph neural network (PIHGNN) for solving the graph-based dc-blocker placement problem. Our approach combines a heterogeneous graph neural network (HGNN) with a physics-informed neural network (PINN) to capture the diverse types of nodes and edges in ac/dc networks and incorporates the physical laws of the power grid. We train the PIHGNN model using a surrogate power flow model and validate it using case studies. Results demonstrate that PIHGNN can effectively and efficiently support the deployment of GIC dc-current blockers, ensuring the continued supply of electricity to meet societal demands. Furthermore, our approach has the potential to contribute to the development of more reliable and resilient power grids capable of withstanding the growing threat that GMDs pose.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2025

Analyzing the Quantum Approximate Optimization Algorithm: Ansätze, Symmetries, and Lie Algebras

The quantum approximate optimization algorithm (QAOA) has been proposed as a method to obtain approximate solutions for combinatorial optimization tasks. In this work, we study the underlying algebraic properties of three QAOA ansätze for the maximum-cut problem on connected graphs, while focusing on the generated Lie algebras as well as their invariant subspaces. Specifically, we analyze the standard QAOA ansatz as well as the orbit and multiangle ansätze. We are able to fully characterize the Lie algebras of the multiangle ansatz across arbitrary connected graphs, finding that they only fall into one of just six families. Aside from the cycle and path graphs, the Lie dimensions for every graph are exponentially large in the system size, meaning that multiangle ansätze are extremely prone to exhibiting barren plateaus. Then, a similar quasi-graph-independent Lie-algebraic characterization beyond the multiangle ansatz is impeded as the circuit exhibits additional “hidden” symmetries besides those naturally arising from a certain parity-superselection operator and all automorphisms of the considered graph. Disregarding the “hidden” symmetries, we can upper bound the dimensions of the orbit and the standard Lie algebras, and the dimensions of the associated invariant subspaces are determined via explicit character formulas. To finish, we conjecture that (for most graphs) the standard Lie algebras have only components that are either exponential or that grow, at most, polynomially with the system size. This would imply that the QAOA is either prone to barren plateaus or classically simulable. More generally, our work provides a symmetry framework and tools to analyze any desired variational quantum algorithm.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2021

Structural Controllability Assessment for Inverter-Based Microgrids

Enhanced inverter-based controls are considered for microgrids, which use additional actuation beyond a droop-like term. Shaping of the microgrid’s small-signal dynamics using such enhanced controls is posed as a structural controllability problem. A graph-theoretic characterization of structural controllability is obtained, in terms of the concept of zero-forcing sets.Two benchmark test systems are used to illustrate the selection of locations where enhanced controls should be applied, based on the graph-theoretic analysis. These examples indicate that small-signal characteristics can be shaped using a relatively small number of enhanced controls

microgrids, zero-forcing, structural controlabilit↗
NASA NTRS1991

Operationally Efficient Propulsion System Study (OEPPS)

A description is presented, through view graphs, of the problems encountered in today's launch vehicles and how these problems have adversely affected the ability to achieve serviceability, reliability, and operability. The need is emphasized to recognize and understand the operations problems and the effort that must be made to avoid them in future designs. Technology areas that will enhance operations requirements are also presented.

Wong, G. S.↗
NASA NTRS1988

Learning dominance relations in combinatorial search problems

Dominance relations commonly are used to prune unnecessary nodes in search graphs, but they are problem-dependent and cannot be derived by a general procedure. The authors identify machine learning of dominance relations and the applicable learning mechanisms. A study of learning dominance relations using learning by experimentation is described. This system has been able to learn dominance relations for the 0/1-knapsack problem, an inventory problem, the reliability-by-replication problem, the two-machine flow shop problem, a number of single-machine scheduling problems, and a two-machine scheduling problem. It is considered that the same methodology can be extended to learn dominance relations in general.

Yu, Chee-Fen↗
DOE OSTI2023

Graph Sparsification by Approximate matrix Multiplication

Graphs arising in statistical problems, signal processing, large networks, combinatorial optimization, and data analysis are often dense, which causes both computational and storage bottlenecks. One way of sparsifying a weighted graph, while sharing the same vertices as the original graph but reducing the number of edges, is through spectral sparsification. We study this problem through the perspective of RandNLA. Specifically, we utilize randomized matrix multiplication to give a clean and simple analysis of how sampling according to edge weights gives a spectral approximation to graph Laplacians, without requiring spectral information. Through the CR–MM algorithm, we attain a simple and computationally efficient sparsifier whose resulting Laplacian estimate is unbiased and of minimum variance. Here, we define a new notion of additive spectral sparsifiers, which has not been considered in the literature.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1990

Assembly, disassembly and repair of large truss structures in space

This paper addresses the problem of planning assembly, disassembly and repair sequences for large truss structures in space. First, the AND/OR graph representation scheme for mechanical assemblies is reviewed and extended to truss structures. The assembly, disassembly and repair sequence planning problem is then formulated as a graph search problem using assembly's AND/OR graph and appropriate cost functions. The general search problem, which is known to be exponential, is simplified by taking advantage of the symmetries that exist in truss structures. General cost functions for truss assembly are discussed.

Desai, Rajiv S.↗