Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Computational graph”

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 163 records · Page 9
All sourcesNASA NTRSDOE OSTI
NASA NTRSDate not supplied

A Knowledge Graph Framework for Organizing Heterogeneous Datasets for Utilization in Classical and Quantum Computing: Current Challenges and Future Directions

"The escalating impact of climate change induced extreme weather events in urban, suburban, and rural environments demands a rethink of how we have been using the single event-based or use-case-based knowledge graph models. The lack of representation in interaction within environmental variables found in literature led to the development of a novel framework that reflects the true nature of the interconnectedness in our environment. We propose an Environmental Interaction Knowledge Graph (EIKG) framework. This general EIKG framework works as the basis for interconnected environmental events by knitting interrelated events such as hurricanes leading to storm surges, which lead to flood events that could cause mudslides, landslides, etc., The cascading nature of one event leading to another related event in the environment requires an adequate understanding of each event using contextual information before conducting any data-driven analytics. This vision paper showcases how the EIKG:floods, EIKG:wildfire EIKG:landslides, etc, can be derived from a base case framework of EIKG as those individual events are interconnected with some common denominator variables. As an example, the precipitation variable is used in the flood case study as well as in the wildfire case study, as excessive precipitation levels lead to floods, and lack of precipitation leads to droughts and wildfires. We identify the precipitation variable as a “common-denominator-variable” in extreme weather events that play a key role in modeling the environment leading to different extreme weather events based on the variability of that variable (varying values where low precipitation leads to drought, and high values lead to floods). We use the insights gained from EIKG to conduct classical and Quantum Machine Learning (QML) based data analysis on the research questions developed. Our preliminary study shows how the Variational Quantum Classifier (VQC) and Quantum Support Vector Classifier (QSVC) are used along with the classical machine learning models to compare the model accuracies. Our study elaborates on how a quantitative analysis uses state-of-the-art machine learning techniques that include implementing both classical and quantum machine learning models and developing the knowledge graph. The EIKG is used to organize heterogeneous datasets and integrate the relations to case-specific extreme weather events such as floods. The study uses datasets such as county-to-country residential mobility data, socioeconomic datasets from the US Census Bureau, climate and weather-related Earth Observational data from NASA, and critical infrastructure data from the Homeland Infrastructure datasets."

Knowledge Graphs, Quantum Computing, Heterogenous ↗
DOE OSTI2022

Randomized Cholesky Preconditioning for Graph Partitioning Applications

A graph is a mathematical representation of a network; we say it consists of a set of vertices, which are connected by edges. Graphs have numerous applications in various fields, as they can model all sorts of connections, processes, or relations. For example, graphs can model intricate transit systems or the human nervous system. However, graphs that are large or complicated become difficult to analyze. This is why there is an increased interest in the area of graph partitioning, reducing the size of the graph into multiple partitions. For example, partitions of a graph representing a social network might help identify clusters of friends or colleagues. Graph partitioning is also a widely used approach to load balancing in parallel computing. The partitioning of a graph is extremely useful to decompose the graph into smaller parts and allow for easier analysis. There are different ways to solve graph partitioning problems. For this work, we focus on a spectral partitioning method which forms a partition based upon the eigenvectors of the graph Laplacian (details presented in Acer, et. al.). This method uses the LOBPCG algorithm to compute these eigenvectors. LOBPCG can be accelerated by an operator called a preconditioner. For this internship, we evaluate a randomized Cholesky (rchol) preconditioner for its effectiveness on graph partitioning problems with LOBPCG. We compare it with two standard preconditioners: Jacobi and Incomplete Cholesky (ichol). This research was conducted from August to December 2021 in conjunction with Sandia National Laboratories.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

A conservative, consistent, and scalable meshfree mimetic method

Mimetic methods discretize divergence by restricting the Gauss theorem to mesh cells. Because point clouds lack such geometric entities, construction of a compatible meshfree divergence remains a challenge. In this work, we define an abstract Meshfree Mimetic Divergence (MMD) operator on point clouds by contraction of field and virtual face moments. This MMD satisfies a discrete divergence theorem, provides a discrete local conservation principle, and is first-order accurate. We consider two MMD instantiations. The first one assumes a background mesh and uses generalized moving least squares (GMLS) to obtain the necessary field and face moments. This MMD instance is appropriate for settings where a mesh is available but its quality is insufficient for a robust and accurate mesh-based discretization. The second MMD operator retains the GMLS field moments but defines virtual face moments using computationally efficient weighted graph-Laplacian equations. This MMD instance does not require a background grid and is appropriate for applications where mesh generation creates a computational bottleneck. It allows one to trade an expensive mesh generation problem for a scalable algebraic one, without sacrificing compatibility with the divergence operator. We demonstrate the approach by using the MMD operator to obtain a virtual finite-volume discretization of conservation laws on point clouds. Finally, numerical results in the paper confirm the mimetic properties of the method and show that it behaves similarly to standard finite volume methods.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2022

Thermal modeling of directed energy deposition additive manufacturing using graph theory

Purpose: The purpose of this paper is to develop, apply and validate a mesh-free graph theory–based approach for rapid thermal modeling of the directed energy deposition (DED) additive manufacturing (AM) process. Design/methodology/approach: Here, the authors develop a novel mesh-free graph theory–based approach to predict the thermal history of the DED process. Subsequently, the authors validated the graph theory predicted temperature trends using experimental temperature data for DED of titanium alloy parts (Ti-6Al-4V). Temperature trends were tracked by embedding thermocouples in the substrate. The DED process was simulated using the graph theory approach, and the thermal history predictions were validated based on the data from the thermocouples. Findings: The temperature trends predicted by the graph theory approach have mean absolute percentage error of approximately 11% and root mean square error of 23°C when compared to the experimental data. Moreover, the graph theory simulation was obtained within 4 min using desktop computing resources, which is less than the build time of 25 min. By comparison, a finite element–based model required 136 min to converge to similar level of error. Research limitations/implications: This study uses data from fixed thermocouples when printing thin-wall DED parts. In the future, the authors will incorporate infrared thermal camera data from large parts. Practical implications: The DED process is particularly valuable for near-net shape manufacturing, repair and remanufacturing applications. However, DED parts are often afflicted with flaws, such as cracking and distortion. In DED, flaw formation is largely governed by the intensity and spatial distribution of heat in the part during the process, often referred to as the thermal history. Accordingly, fast and accurate thermal models to predict the thermal history are necessary to understand and preclude flaw formation. Originality/value: This paper presents a new mesh-free computational thermal modeling approach based on graph theory (network science) and applies it to DED. The approach eschews the tedious and computationally demanding meshing aspect of finite element modeling and allows rapid simulation of the thermal history in additive manufacturing. Although the graph theory has been applied to thermal modeling of laser powder bed fusion (LPBF), there are distinct phenomenological differences between DED and LPBF that necessitate substantial modifications to the graph theory approach.

42 ENGINEERING↗
DOE OSTI2022

Semantic Property Graph for Scalable Knowledge Graph Analytics

Graphs are a natural and fundamental representation to describe entities, relationships, activities, and evolution of complex systems. Many domains such as communication, citation, procurement, biology, social media, and transportation can be modeled as a set of entities and their relationships. Resource Description Framework (RDF) and Labeled Property Graph (LPG) are two of the most used data models to encode information in a graph. Both models are similar in terms of using basic graph elements such as nodes and edges but differ in terms of the modeling approach, expressibility, serialization, and target applications. RDF is a flexible data exchange model for expressing information about entities but it tends to a have high memory footprint and inefficient storage, which does not make it a natural choice to perform scalable graph analytics. In contrast, LPG has gained traction as a reliable model to perform scalable graph analytic tasks such as sub-graph matching, network alignment, and real-time knowledge graph query. It provides efficient storage, fast traversal, and flexibility to model various real-world domains. At the same time, the LPG lacks the support of a formal knowledge representation such as an ontology to provide automated knowledge inference. We propose Semantic Property Graph (SPG) as a logical projection of reified RDF into the LPG model. SPG continues to use RDF ontology to define the type hierarchy of the projected graph and validate it against a given ontology. We present a framework to convert reified RDF graphs into SPG using two different computing environments. We also present cloud-based graph migration capabilities using Amazon Web Services.

Purohit, Sumit↗
NASA NTRS1989

A user-friendly, menu-driven, language-free laser characteristics curves graphing program for desk-top IBM PC compatible computers

A facility was established that uses collected data and feeds it into mathematical models that generate improved data arrays by correcting for various losses, base line drift, and conversion to unity scaling. These developed data arrays have headers and other identifying information affixed and are subsequently stored in a Laser Materials and Characteristics data base which is accessible to various users. The two part data base: absorption - emission spectra and tabulated data, is developed around twelve laser models. The tabulated section of the data base is divided into several parts: crystalline, optical, mechanical, and thermal properties; aborption and emission spectra information; chemical name and formulas; and miscellaneous. A menu-driven, language-free graphing program will reduce and/or remove the requirement that users become competent FORTRAN programmers and the concomitant requirement that they also spend several days to a few weeks becoming conversant with the GEOGRAF library and sequence of calls and the continual refreshers of both. The work included becoming thoroughly conversant with or at least very familiar with GEOGRAF by GEOCOMP Corp. The development of the graphing program involved trial runs of the various callable library routines on dummy data in order to become familiar with actual implementation and sequencing. This was followed by trial runs with actual data base files and some additional data from current research that was not in the data base but currently needed graphs. After successful runs, with dummy and real data, using actual FORTRAN instructions steps were undertaken to develop the menu-driven language-free implementation of a program which would require the user only know how to use microcomputers. The user would simply be responding to items displayed on the video screen. To assist the user in arriving at the optimum values needed for a specific graph, a paper, and pencil check list was made available to use on the trial runs.

Klutz, Glenn↗
DOE OSTI2025

Scalable training of trustworthy and energy-efficient predictive graph foundation models for atomistic materials modeling: a case study with HydraGNN

We present our work on developing and training scalable, trustworthy, and energy-efficient predictive graph foundation models (GFMs) using HydraGNN, a multi-headed graph convolutional neural network architecture. HydraGNN expands the boundaries of graph neural network (GNN) computations in both training scale and data diversity. It abstracts over message passing algorithms, allowing both reproduction of and comparison across algorithmic innovations that define nearest-neighbor convolution in GNNs. This work discusses a series of optimizations that have allowed scaling up the GFMs training to tens of thousands of GPUs on datasets consisting of hundreds of millions of graphs. Our GFMs use multitask learning (MTL) to simultaneously learn graph-level and node-level properties of atomistic structures, such as energy and atomic forces. Using over 154 million atomistic structures for training, we illustrate the performance of our approach along with the lessons learned on two state-of-the-art US Department of Energy (US-DOE) supercomputers, namely the Perlmutter petascale system at the National Energy Research Scientific Computing Center and the Frontier exascale system at Oak Ridge Leadership Computing Facility. The HydraGNN architecture enables the GFM to achieve near-linear strong scaling performance using more than 2000 GPUs on Perlmutter and 16,000 GPUs on Frontier.

97 MATHEMATICS AND COMPUTING↗
NASA NTRSDate not supplied

AstroLoc: An Efficient and Robust Localizer for a Free-flying Robot

We present AstroLoc, an efficient and robust monocular visual-inertial graph-based localization system used by the Astrobee free-flying robots onboard the International Space Station (ISS). We provide a novel localization system that limits the traditionally higher computation times for graph-based localization systems and enables the resource constrained Astrobee robots to benefit from their increased accuracy. We also introduce methods for handling cheirality issues for visual odometry and localization factors that further increase localization robustness. We evaluate the performance of AstroLoc on a dataset of ISS activities and show that it greatly improves pose, velocity, and IMU bias estimation accuracy while efficiently running in a limited computation environment. The source code for AstroLoc is released to the public.

Localization↗
DOE OSTI2023

Integer Sequences from Configurations in the Hausdorff Metric Geometry via Edge Covers of Bipartite Graphs

The Hausdorff metric provides a way to measure the distance between nonempty compact sets in $\mathbb{R}^N$, from which we can build a geometry of sets. This geometry is very different than the standard Euclidean geometry and provides many interesting results. In this paper we focus on line segments in this geometry, where pairs of disjoint sets $A$ and $B$ satisfying certain distance conditions have the property that there are exactly $m$ different sets on the line segment $\overline{AB}$ at every distance from $A$, where $m$ can assume many values different than one. We provide new families of sets that generate previously unrecorded integer sequences via these values of $m$ by connecting the values of $m$ to the number of edge coverings of a graph corresponding to the sets $A$ and $B$.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

Dirac traces and the Tutte polynomial

Perturbative calculations involving fermion loops in quantum field theories require tracing over Dirac matrices. A simple way to regulate the divergences that generically appear in these calculations is dimensional regularisation, which has the consequence of replacing 4-dimensional Dirac matrices with d-dimensional counterparts for arbitrary complex values of d. In this work, a connection between traces of d-dimensional Dirac matrices and computations of the Tutte polynomial of associated graphs is proven. The time complexity of computing Dirac traces is analysed by this connection, and improvements to algorithms for computing Dirac traces are proposed.

Renormalization and Regularization↗
DOE OSTI2024

Accelerate microstructure evolution simulation using graph neural networks with adaptive spatiotemporal resolution

Abstract Surrogate models driven by sizeable datasets and scientific machine-learning methods have emerged as an attractive microstructure simulation tool with the potential to deliver predictive microstructure evolution dynamics with huge savings in computational costs. Taking 2D and 3D grain growth simulations as an example, we present a completely overhauled computational framework based on graph neural networks with not only excellent agreement to both the ground truth phase-field methods and theoretical predictions, but enhanced accuracy and efficiency compared to previous works based on convolutional neural networks. These improvements can be attributed to the graph representation, both improved predictive power and a more flexible data structure amenable to adaptive mesh refinement. As the simulated microstructures coarsen, our method can adaptively adopt remeshed grids and larger timesteps to achieve further speedup. The data-to-model pipeline with training procedures together with the source codes are provided.

36 MATERIALS SCIENCE↗
DOE OSTI2021

COVID19 Disease Map, a computational knowledge repository of virus–host interaction mechanisms

We need to effectively combine the knowledge from surging literature with complex datasets to propose mechanistic models of SARS-CoV-2 infection, improving data interpretation and predicting key targets of intervention. Here, we describe a large-scale community effort to build an open access, interoperable and computable repository of COVID-19 molecular mechanisms. The COVID-19 Disease Map (C19DMap) is a graphical, interactive representation of disease-relevant molecular mechanisms linking many knowledge sources. Notably, it is a computational resource for graph-based analyses and disease modelling. To this end, we established a framework of tools, platforms and guidelines necessary for a multifaceted community of biocurators, domain experts, bioinformaticians and computational biologists. The diagrams of the C19DMap, curated from the literature, are integrated with relevant interaction and text mining databases. We demonstrate the application of network analysis and modelling approaches by concrete examples to highlight new testable hypotheses. This framework helps to find signatures of SARS-CoV-2 predisposition, treatment response or prioritisation of drug candidates. Such an approach may help deal with new waves of COVID-19 or similar pandemics in the long-term perspective.

59 BASIC BIOLOGICAL SCIENCES↗
DOE OSTI2022

Matching Complexes of Trees and Applications of the Matching Tree Algorithm

A matching complex of a simple graph G is a simplicial complex with faces given by the matchings of G. The topology of matching complexes is mysterious; there are few graphs for which the homotopy type is known. Marietti and Testa showed that matching complexes of forests are contractible or homotopy equivalent to a wedge of spheres. We study two specific families of trees. For caterpillar graphs, we give explicit formulas for the number of spheres in each dimension and for perfect binary trees we find a strict connectivity bound. We also use a tool from discrete Morse theory called the Matching Tree Algorithm to study the connectivity of honeycomb graphs, partially answering a question raised by Jonsson.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

MLPF: efficient machine-learned particle-flow reconstruction using graph neural networks

In general-purpose particle detectors, the particle-flow algorithm may be used to reconstruct a comprehensive particle-level view of the event by combining information from the calorimeters and the trackers, significantly improving the detector resolution for jets and the missing transverse momentum. In view of the planned high-luminosity upgrade of the CERN Large Hadron Collider (LHC), it is necessary to revisit existing reconstruction algorithms and ensure that both the physics and computational performance are sufficient in an environment with many simultaneous proton–proton interactions (pileup). Machine learning may offer a prospect for computationally efficient event reconstruction that is well-suited to heterogeneous computing platforms, while significantly improving the reconstruction quality over rule-based algorithms for granular detectors. We introduce MLPF, a novel, end-to-end trainable, machine-learned particle-flow algorithm based on parallelizable, computationally efficient, and scalable graph neural network optimized using a multi-task objective on simulated events. We report the physics and computational performance of the MLPF algorithm on a Monte Carlo dataset of top quark–antiquark pairs produced in proton–proton collisions in conditions similar to those expected for the high-luminosity LHC. The MLPF algorithm improves the physics response with respect to a rule-based benchmark algorithm and demonstrates computationally scalable particle-flow reconstruction in a high-pileup environment.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2024

Generating Euler Diagrams Through Combinatorial Optimization

Abstract Can a given set system be drawn as an Euler diagram? We present the first method that correctly decides this question for arbitrary set systems if the Euler diagram is required to represent each set with a single connected region. If the answer is yes, our method constructs an Euler diagram. If the answer is no, our method yields an Euler diagram for a simplified version of the set system, where a minimum number of set elements have been removed. Further, we integrate known wellformedness criteria for Euler diagrams as additional optimization objectives into our method. Our focus lies on the computation of a planar graph that is embedded in the plane to serve as the dual graph of the Euler diagram. Since even a basic version of this problem is known to be NP‐hard, we choose an approach based on integer linear programming (ILP), which allows us to compute optimal solutions with existing mathematical solvers. For this, we draw upon previous research on computing planar supports of hypergraphs and adapt existing ILP building blocks for contiguity‐constrained spatial unit allocation and the maximum planar subgraph problem. To generate Euler diagrams for large set systems, for which the proposed simplification through element removal becomes indispensable, we also present an efficient heuristic. We report on experiments with data from MovieDB and Twitter. Over all examples, including 850 non‐trivial instances, our exact optimization method failed only for one set system to find a solution without removing a set element. However, with the removal of only a few set elements, the Euler diagrams can be substantially improved with respect to our wellformedness criteria.

Computer Science↗
NASA NTRS1986

A formal definition of data flow graph models

In this paper, a new model for parallel computations and parallel computer systems that is based on data flow principles is presented. Uninterpreted data flow graphs can be used to model computer systems including data driven and parallel processors. A data flow graph is defined to be a bipartite graph with actors and links as the two vertex classes. Actors can be considered similar to transitions in Petri nets, and links similar to places. The nondeterministic nature of uninterpreted data flow graphs necessitates the derivation of liveness conditions.

Kavi, Krishna M.↗
DOE OSTI2021

EXAGRAPH: Graph and combinatorial methods for enabling exascale applications

Combinatorial algorithms in general and graph algorithms in particular play a critical enabling role in numerous scientific applications. However, the irregular memory access nature of these algorithms makes them one of the hardest algorithmic kernels to implement on parallel systems. With tens of billions of hardware threads and deep memory hierarchies, the exascale computing systems in particular pose extreme challenges in scaling graph algorithms. The codesign center on combinatorial algorithms, ExaGraph, was established to design and develop methods and techniques for efficient implementation of key combinatorial (graph) algorithms chosen from a diverse set of exascale applications. Algebraic and combinatorial methods have a complementary role in the advancement of computational science and engineering, including playing an enabling role on each other. In this paper, we survey the algorithmic and software development activities performed under the auspices of ExaGraph from both a combinatorial and an algebraic perspective. In particular, we detail our recent efforts in porting the algorithms to manycore accelerator (GPU) architectures. We also provide a brief survey of the applications that have benefited from the scalable implementations of different combinatorial algorithms to enable scientific discovery at scale. We believe that several applications will benefit from the algorithmic and software tools developed by the ExaGraph team.

97 MATHEMATICS AND COMPUTING↗