Search NASA⌕ Search

SEARCH · Search NASA

Results for “graph optimization”

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 397 records · Page 22

Noisy evolution of graph-state entanglement

A general method for the study of the entanglement evolution of graph states under the action of Pauli maps was recently proposed in Cavalcanti et al. [Phys. Rev. Lett. 103, 030502 (2009)]. This method is based on lower and upper bounds to the entanglement of the entire state as a function only of the state of a (typically) considerably smaller subsystem undergoing an effective noise process related to the original map. This provides a huge decrease in the size of the matrices involved in the calculation of entanglement in these systems. In the present paper we elaborate on this method in detail and generalize it to other natural situations not described by Pauli maps. Specifically, for Pauli maps we introduce an explicit formula for the characterization of the resulting effective noise. Beyond Pauli maps, we show that the same ideas can be applied to the case of thermal reservoirs at arbitrary temperature. In the latter case, we discuss how to optimize the bounds as a function of the noise strength. We illustrate our ideas with explicit exemplary results for several different graphs and particular decoherence processes. The limitations of the method are also discussed.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

A Synchronization-Avoiding Distance-1 Grundy Coloring Algorithm for Power-Law Graphs

In this paper, we propose a distributed, unordered, label-correcting distance-1 Grundy (vertex) coloring algorithm, namely, Distributed Control (DC) coloring algorithm. Our algorithm eliminates the need for vertex-centric barriers and global synchronization for color refinement, relying only on atomic operations and local termination detection to update vertex color. DC proceeds optimistically, correcting the colors asynchronously as the algorithm progresses and depends on local ordering of tasks to minimize the execution of sub-optimal work. We implement our DC coloring algorithm and the well-known Jones-Plassmann algorithm and compare their performance with 4 different types of standard RMAT graphs and real-world graphs. We show that the elimination of waiting time of global and vertex-centric barriers and investing this time for local ordering leads to improved scaling for graphs with prominent power-law characteristics and densely interconnected local subgraphs.

Firoz, Jesun S.↗

Short-depth QAOA circuits and quantum annealing on higher-order ising models

Abstract We present a direct comparison between QAOA (Quantum Alternating Operator Ansatz), and QA (Quantum Annealing) on 127 qubit problem instances. QAOA with p = 1, 2 rounds is executed on the 127 qubit heavy-hex graph gate-model quantum computer ibm_washington, using on-device grid-searches for angle finding, and QA is executed on two Pegasus-chip D-Wave quantum annealers. The problems are random Ising models whose connectivity matches heavy-hex graphs and the Pegasus graph connectivity, and optionally include hardware-compatible cubic terms ( Z Z Z terms). The QAOA circuits are heavily optimized and of extremely short depth, with a CNOT depth of 6 per round, which allows whole chip usage of the heavy-hex lattice. QAOA and QA are both compared against simulated annealing and the optimal solutions are computed exactly using CPLEX. The noiseless mean QAOA expectation values for p = 1, 2 are computed using classical light-cone based simulations. We find QA outperforms QAOA on the evaluated devices.

127 qubits↗

Quantum speed limits for quantum-information-processing tasks

We derive algebraic bounds on achievable rates for quantum state transfer and entanglement generation in general quantum systems. We apply these bounds to graph-based models of local quantum spin systems to obtain speed limits on these tasks. A comparison to numerical optimal control results for spin chains suggests that unexplored regions of the dynamical landscape may support enhanced performance of key quantum-information-processing tasks.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

MICCO: An Enhanced Multi-GPU Scheduling Framework for Many-Body Correlation Functions

Calculation of many-body correlation functions is one of the critical kernels utilized in many scientific computing areas, especially in Lattice Quantum Chromodynamics (Lattice QCD). It is formalized as a sum of a large number of contraction terms each of which can be represented by a graph consisting of vertices describing quarks inside a hadron node and edges designating quark propagations at specific time intervals. Due to its computation- and memory-intensive nature, real-world physics systems (e.g., multi-meson or multi-baryon systems) explored by Lattice QCD prefer to leverage multi-GPUs. Different from general graph processing, many-body correlation function calculations show two specific features: a large number of computation-/data-intensive kernels and frequently repeated appearances of original and intermediate data. The former results in expensive memory operations such as tensor movements and evictions. The latter offers data reuse opportunities to mitigate the data-intensive nature of many-body correlation function calculations. However, existing graph-based multi-GPU schedulers cannot capture these data-centric features, thus resulting in a sub-optimal performance for many-body correlation function calculations. To address this issue, this paper presents a multi-GPU scheduling framework, MICCO, to accelerate contractions for correlation functions particularly by taking the data dimension (e.g., data reuse and data eviction) into account. This work first performs a comprehensive study on the interplay of data reuse and load balance, and designs two new concepts: local reuse pattern and reuse bound to study the opportunity of achieving the optimal trade-off between them. Based on this study, MICCO proposes a heuristic scheduling algorithm and a machine-learning-based regression model to generate the optimal setting of reuse bounds. Specifically, MICCO is integrated into a real-world Lattice QCD system, Redstar, for the first time running on multiple GPUs. The evaluation demonstrates MICCO outperforms other state-of-art works, achieving up to 2.25× speedup in synthesized datasets, and 1.49× speedup in real-world correlation functions.

Wang, Qihan↗

Programming Strategies for Irregular Algorithms on the Emu Chick

The Emu Chick prototype implements migratory memory-side processing in a novel hardware system. Rather than transferring large amounts of data across the system interconnect, the Emu Chick moves lightweight thread contexts to near-memory cores before the beginning of each remote memory read. Previous work has characterized the performance of the Chick prototype in terms of memory bandwidth and programming differences from more typical, non-migratory platforms, but there has not yet been an analysis of algorithms on this system. This work evaluates irregular algorithms that could benefit from the lightweight, memory-side processing of the Chick and demonstrates techniques and optimization strategies for achieving performance in sparse matrix-vector multiply operation (SpMV), breadth-first search (BFS), and graph alignment across up to eight distributed nodes encompassing 64 nodelets in the Chick system. We also define and justify relative metrics to compare prototype FPGA-based hardware with established ASIC architectures. The Chick currently supports up to 68x scaling for graph alignment, 80 MTEPS for BFS on balanced graphs, and 50% of measured STREAM bandwidth for SpMV.

Hein, Eric↗

High-Level Synthesis of Irregular Applications: A Case Study on Influence Maximization

The Influence Maximization problem is the problem of identifying a small cohort of actors from a broader population that, when initially activated in a diffusion process, are expected to result in a large number of activations in the population. While the problem is known to be NP-hard, several approximation algorithms have been devised by leveraging its submodular structure. While these algorithms are theoretically efficient, they are computationally very expensive in practice. This work advances the current state-of-the-art parallelization scheme for the IMM algorithm by devising the adoption of custom hardware accelerators implemented on FPGAs by leveraging High Level Synthesis from OpenCL. We study the performance of our proposed approach by exploring optimizations tailored at improving the parallel efficiency of the accelerators and highlight their effects and limitations in accelerating complex graph analytic applications. Our experimental evaluation shows that FPGA acceleration can improve the performance of the LT diffusion model up to 1.72x for the entire application and up to 2.90x for its most important kernel with respect to a CPU only parallel execution. The FPGA acceleration of the LT model shows also a 1.54x reduction in energy consumption when compared to a parallel CPU only run.

Neff, Reece W.↗

Classical symmetries and the Quantum Approximate Optimization Algorithm

Here, we study the relationship between the Quantum Approximate Optimization Algorithm (QAOA) and the underlying symmetries of the objective function to be optimized. Our approach formalizes the connection between quantum symmetry properties of the QAOA dynamics and the group of classical symmetries of the objective function. The connection is general and includes but is not limited to problems defined on graphs. We show a series of results exploring the connection and highlight examples of hard problem classes where a nontrivial symmetry subgroup can be obtained efficiently. In particular, we show how classical objective function symmetries lead to invariant measurement outcome probabilities across states connected by such symmetries, independent of the choice of algorithm parameters or number of layers. To illustrate the power of the developed connection, we apply machine learning techniques toward predicting QAOA performance based on symmetry considerations. We provide numerical evidence that a small set of graph symmetry properties suffices to predict the minimum QAOA depth required to achieve a target approximation ratio on the MaxCut problem, in a practically important setting where QAOA parameter schedules are constrained to be linear and hence easier to optimize.

97 MATHEMATICS AND COMPUTING↗

Finding cycles and trees in sublinear time.

We present sublinear-time (randomized) algorithms for finding simple cycles of length at least k {ge} 3 and tree-minors in bounded-degree graphs. The complexity of these algorithms is related to the distance of the graph from being C{sub k}-minor-free (resp., free from having the corresponding tree-minor). In particular, if the graph is far (i.e., {Omega}(1)-far) from being cycle-free, i.e. if one has to delete a constant fraction of edges to make it cycle-free, then the algorithm finds a cycle of polylogarithmic length in time {tilde O}({radical}N), where N denotes the number of vertices. This time complexity is optimal up to polylogarithmic factors. The foregoing results are the outcome of our study of the complexity of one-sided error property testing algorithms in the bounded-degree graphs model. For example, we show that cycle-freeness of N-vertex graphs can be tested with one-sided error within time complexity {tilde O}(poly(1/{epsilon}) {center_dot} {radical}N). This matches the known {Omega}({radical}N) query lower bound, and contrasts with the fact that any minor-free property admits a two-sided error tester of query complexity that only depends on the proximity parameter {epsilon}. For any constant k {ge} 3, we extend this result to testing whether the input graph has a simple cycle of length at least k. On the other hand, for any fixed tree T, we show that T -minor-freeness has a one-sided error tester of query complexity that only depends on the proximity parameter {epsilon}. Our algorithm for finding cycles in bounded-degree graphs extends to general graphs, where distances are measured with respect to the actual number of edges. Such an extension is not possible with respect to finding tree-minors in o({radical}N) complexity.

99 GENERAL AND MISCELLANEOUS↗

Reducing Communication in Graph Neural Network Training

Graph Neural Networks (GNNs) are powerful and flexible neural networks that use the naturally sparse connectivity information of the data. GNNs represent this connectivity as sparse matrices, which have lower arithmetic intensity and thus higher communication costs compared to dense matrices, making GNNs harder to scale to high concurrencies than convolutional or fully-connected neural networks. Here, we introduce a family of parallel algorithms for training GNNs and show that they can asymptotically reduce communication compared to previous parallel GNN training methods. We implement these algorithms, which are based on 1D, 1. 5D, 2D, and 3D sparse-dense matrix multiplication, using torch.distributed on GPU-equipped clusters. Our algorithms optimize communication across the full GNN training pipeline. We train GNNs on over a hundred GPUs on multiple datasets, including a protein network with over a billion edges.

97 MATHEMATICS AND COMPUTING↗

BitGNN: Unlocking the Performance Potential of Binary Graph Neural Networks on GPUs

Graph Neural Networks (GNNs) have shown compelling results in many graph-based learning tasks. They are, however, time-consuming. Recent work has shown a promising direction in improving GNN speed and shrinking the size — network binarization, which binarizes network values and operations. Prior work, however, mainly focused on algorithm designs, leaving it open on how to fully materialize the performance potential. This work fills the gap by proposing techniques to best map binary GNNs and their computations to fit the nature of bit manipulations, optimizations and algorithms to maximize BSpMM kernel efficiency, and solutions to other factors influencing the end-to-end time on GPUs. Results on real-world graphs show that the proposed techniques outperform state of-the-art binary GNN implementations by 21-67× with little accuracy loss.

Chen, Jou-An↗

Surrogate Models for Estimating Failure in Brittle and Quasi-Brittle Materials

In brittle fracture applications, failure paths, regions where the failure occurs and damage statistics, are some of the key quantities of interest (QoI). High-fidelity models for brittle failure that accurately predict these QoI exist but are highly computationally intensive, making them infeasible to incorporate in upscaling and uncertainty quantification frameworks. The goal of this paper is to provide a fast heuristic to reasonably estimate quantities such as failure path and damage in the process of brittle failure. Towards this goal, we first present a method to predict failure paths under tensile loading conditions and low-strain rates. The method uses a k-nearest neighbors algorithm built on fracture process zone theory, and identifies the set of all possible pre-existing cracks that are likely to join early to form a large crack. The method then identifies zone of failure and failure paths using weighted graphs algorithms. We compare these failure paths to those computed with a high-fidelity fracture mechanics model called the Hybrid Optimization Software Simulation Suite (HOSS). A probabilistic evolution model for average damage in a system is also developed that is trained using 150 HOSS simulations and tested on 40 simulations. A non-parametric approach based on confidence intervals is used to determine the damage evolution over time along the dominant failure path. For upscaling, damage is the key QoI needed as an input by the continuum models. This needs to be informed accurately by the surrogate models for calculating effective moduli at continuum-scale. We show that for the proposed average damage evolution model, the prediction accuracy on the test data is more than 90%. In terms of the computational time, the proposed models are ≈ O ( 10 6 ) times faster compared to high-fidelity fracture simulations by HOSS. These aspects make the proposed surrogate model attractive for upscaling damage from micro-scale models to continuum models. We would like to emphasize that the surrogate models are not a replacement of physical understanding of fracture propagation. The proposed method in this paper is limited to tensile loading conditions at low-strain rates. This loading condition corresponds to a dominant fracture perpendicular to tensile direction. The proposed method is not applicable for in-plane shear, out-of-plane shear, and higher strain rate loading conditions.

36 MATERIALS SCIENCE↗

Trust from the past: Bayesian Personalized Ranking based Link Prediction in Knowledge Graphs

Estimating the confidence for a link is a critical task for Knowledge Graph construction. Link prediction, or predicting the likelihood of a link in a knowledge graph based on prior state is a key research direction within this area. We propose a Latent Feature Embedding based link recommendation model for prediction task and utilize Bayesian Personalized Ranking based optimization technique for learning models for each predicate. Experimental results on large-scale knowledge bases such as YAGO2 show that our approach achieves substantially higher performance than several state-of-art approaches. Furthermore, we also study the performance of the link prediction algorithm in terms of topological properties of the Knowledge Graph and present a linear regression model to reason about its expected level of accuracy.

knowledge graphs↗

Understanding the Hierarchy of Dense Subgraphs in Stationary and Temporally Varying Setting

Graphs are widely used to model relationships in a wide variety of domains such as sociology, bioinformatics, infrastructure, the WWW, to name a few. One of the key observations is that while real-world graphs are often globally sparse, they are locally dense. In other words, the average degree is often quite small (say at most 10 in a million vertex graph), but vertex neighborhoods are often dense. Finding dense subgraphs is a critical aspect of graph mining It has been used for finding communities and spam link farms in web graphs, graph visualization, real-time story identification, DNA motif detection in biological networks, finding correlated genes, epilepsy prediction, finding price value motifs in financial data, graph compression, distance query indexing, and increasing the throughput of social networking site servers. However, most standard formulations of this problem (like clique, quasi-clique, k-densest subgraph) are NP-hard. Furthermore, current dense subgraph finding algorithms usually optimize some objective, and only find a few such subgraphs without providing any structural relations, whereas the goal is rarely to find the "true optimum," but to identify many (if not all) dense substructures, understand their distribution in the graph, and ideally determine relationships among them. In this project, we first aim to devise algorithms and provide 3 implementations with nice visualizations to find the hierarchy between dense subgraphs, and then understand the structure of the hierarchy to gain more insight on the hidden patterns in real-world networks. Another important aspects in graph analysis is the temporal nature of networks. Networks evolve over time and in many applications data arrives at a high velocity, and thus it is important to design algorithms that can process data efficiently. We report three main results towards identifying dense structures in large evolving graphs. First, we will show how the hierarchical connectedness structure can be maintained efficiently, where connectedness is defined by increasing levels of connectivity strength. Next, we present dense structure can be identified in bipartite graphs without building projection graphs. And finally, we present a new method for peeling algorithms This new approach avoids sequential nature of peeling algorithms and is amenable to parallelization, which is crucial for processing high velocity data.

97 MATHEMATICS AND COMPUTING↗

Guiding Architects in Selecting Architectural Evolution Alternatives

Although there exist methods and tools to support architecture evolution, the derivation and evaluation of alternative evolution paths are realized manually. In this paper, we introduce an approach, where architecture specification is converted to a graph representation. Based on this representation, we automatically generate possible evolution paths, evalute quality attributes for different architecture configurations, and optimize the selection of a particular path accordingly. We illustrate our approach by modeling the software architecture evolution of a crisis management system.

99 GENERAL AND MISCELLANEOUS↗

Perfecting one-loop BCJ numerators in SYM and supergravity

We take a major step towards computing D-dimensional one-loop amplitudes in general gauge theories, compatible with the principles of unitarity and the color-kinematics duality. For n-point amplitudes with either supersymmetry multiplets or generic non-supersymmetric matter in the loop, simple all-multiplicity expressions are obtained for the maximal cuts of kinematic numerators of n-gon diagrams. At n = 6, 7 points with maximal supersymmetry, we extend the cubic-diagram numerators to encode all contact terms, and thus solve the long-standing problem of simultaneously realizing the following properties: color-kinematics duality, manifest locality, optimal power counting of loop momenta, quadratic rather than linearized Feynman propagators, compatibility with double copy as well as all graph symmetries. Color-kinematics dual representations with similar properties are presented in the half-maximally supersymmetric case at n = 4, 5 points. The resulting gauge-theory integrands and their supergravity counterparts obtained from the double copy are checked to reproduce the expected ultraviolet divergences.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗

Stakeholder-guided holistic, Adaptive Framework for enhancing community Energy Resilience (SAFER) (Final Technical Report)

The Stakeholder-guided holistic, Adaptive Framework for enhancing community Energy Resilience (SAFER) project advances resilience science and engineering by addressing challenges in rural Kansas communities where aging infrastructure, extreme weather, and socioeconomic disparities heighten vulnerability to energy disruptions. Traditional approaches often focus on technical performance while overlooking community concerns and priorities. SAFER responds by integrating community perspectives with advanced analytical frameworks to create a holistic model for measuring and improving resilience. Project objectives included developing novel resilience metrics, advancing modeling frameworks that capture interdependencies across infrastructures, and embedding community-centric indicators directly into planning processes for distributed energy resources. The key technical innovations included the creation of self-organizing map (SOM)-based indices for objective resilience quantification, hetero-functional graph theory (HFGT) models linking power, water, transportation, and community assets, and graph neural network (GNN) tools for identifying critical nodes in complex systems. Community-centric energy planning was demonstrated through optimal siting and sizing of (photovoltaic) PV and battery storage, ensuring resilience enhancements also addressed energy burden and energy insecurity. SAFER engaged community partners in Dodge City and Ford County through surveys, focus groups, and workshops, generating more than 600 responses that established baseline measures of energy burden, financial insecurity, and willingness-to-pay to avoid outages. This data, organized in terms of a community capitals framework, informed the development of weighted reliability indices that better reflect community costs than traditional utility metrics. SAFER’s GNN-based critical node identification framework identified expert-labelled critical nodes with over 99% accuracy, while also uncovering additional functionalities essential for proactive resilience planning. The project’s models demonstrated that optimal PV and storage deployment could improve resilience indices by over 11 percent, with dispatch strategies further enhancing outcomes, confirming both the technical effectiveness and economic feasibility of these approaches. Through its combined emphasis on rigorous modeling, community-focused planning, and community engagement, SAFER advances the state of resilience research while delivering direct benefits to rural communities. The project provides tools, guidelines, and resilience heatmaps that help utilities, local governments, and residents better anticipate disruptions, prioritize investments, and strengthen the capacity to withstand and recover from energy-related hazards. Furthermore, the developed HFG and GNN frameworks are designed for transferability, allowing them to be adapted for resilience planning in other communities with minimal retraining. This inductive learning capability provides a scalable pathway to extend the SAFER project’s impact. Thus, creating a foundation for a nationally applicable model of infrastructure resilience. Additionally, the HFG can also be extended to include other FEMA community lifelines.

14 SOLAR ENERGY↗

Finding Your Niche: An Evolutionary Approach to HPC Topologies

Traditional interconnection network design approaches focus on building general network topologies by optimizing the bisection bandwidth or minimizing the network’s diameter to reduce the maximum distance between any two nodes, thus amortizing the overall execution time of the HPC workloads. While such network topologies may accommodate a wide variety of applications in general, this may result in sub-optimal performance for many frequently-executed or dynamic workloads. In this paper, instead of focusing on designing an all-encompassing, general-purpose network topology, we develop a methodology to design customized network interconnects, evolved by “finding” the optimal topologies for a particular target workload given by its communication and contention profiles. To this end, we implement a Genetic Algorithm (GA)-based approach for network topology design tailored to improve the overall execution time of a particular workload of interest. We conducted extensive experiments with well-known motifs in physics-based workloads (Sweep3D and FFT), as well as with a representative graph application (MiniVite), using the well-known Structural Simulation Toolkit (SST) Macroscale Element Library (SST/macro) simulator for network interconnect evaluation. We demonstrate that our genetic algorithm-based approach is robust enough to find the underlying optimal topology of a particular workload.

network interconnects, graph search, meta-heuristi↗