Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “graph states”

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 109 records · Page 6
All sourcesNASA NTRSDOE OSTI
DOE OSTI2022

Classical Simulation of Boson Sampling Based on Graph Structure

Boson sampling is a fundamentally and practically important task that can be used to demonstrate quantum supremacy using noisy intermediate-scale quantum devices. In this Letter, we present classical sampling algorithms for single-photon and Gaussian input states that take advantage of a graph structure of a linear-optical circuit. The algorithms’ complexity grows as so-called treewidth, which is closely related to the connectivity of a given linear-optical circuit. Using the algorithms, we study approximated simulations for local Haar-random linear-optical circuits. For equally spaced initial sources, we show that, when the circuit depth is less than the quadratic in the lattice spacing, the efficient simulation is possible with an exponentially small error. Notably, right after this depth, photons start to interfere each other and the algorithms’ complexity becomes subexponential in the number of sources, implying that there is a sharp transition of its complexity. Finally, when a circuit is sufficiently deep enough for photons to typically propagate to all modes, the complexity becomes exponential as generic sampling algorithms. We numerically implement a likelihood test with a recent Gaussian boson sampling experiment and show that the treewidth-based algorithm with a limited treewidth renders a larger likelihood than the experimental data.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
NASA NTRSDate not supplied

Screening of Li-Based Solid Electrolytes Using Bond-Valence Methods and Graph Neural Networks

Li-based solid-state electrolyte (Li-SSE) materials enable safer, all-solid-state batteries but the computational search for candidates with favorable stability and Li-ion conductivity is challenging due to the size of the search space and the cost of evaluating transport properties with ab initio methods. We present a high-throughput screening approach for Li-SSE materials using a combination of bond-valence methods and graph neural networks. We demonstrate the screening approach with a dataset containing tens of thousands of Li-containing compounds. Furthermore, we combine the machine-learning screening procedure with an isovalent substitution scheme to generate and screen additional Li SSE candidates beyond existing databases. Finally, we discuss relative importances of geometric and bond-valence quantities in the training of graph neural networks, providing insight for future modeling of ionic conductivity in Li-SSE materials.

Materials discovery↗
DOE OSTI2023

Dynamic conformational switching underlies TFIIH function in transcription and DNA repair and impacts genetic diseases

Transcription factor IIH (TFIIH) is a protein assembly essential for transcription initiation and nucleotide excision repair (NER). Yet, understanding of the conformational switching underpinning these diverse TFIIH functions remains fragmentary. TFIIH mechanisms critically depend on two translocase subunits, XPB and XPD. To unravel their functions and regulation, we build cryo-EM based TFIIH models in transcription- and NER-competent states. Using simulations and graph-theoretical analysis methods, we reveal TFIIH’s global motions, define TFIIH partitioning into dynamic communities and show how TFIIH reshapes itself and self-regulates depending on functional context. Our study uncovers an internal regulatory mechanism that switches XPB and XPD activities making them mutually exclusive between NER and transcription initiation. By sequentially coordinating the XPB and XPD DNA-unwinding activities, the switch ensures precise DNA incision in NER. Mapping TFIIH disease mutations onto network models reveals clustering into distinct mechanistic classes, affecting translocase functions, protein interactions and interface dynamics.

59 BASIC BIOLOGICAL SCIENCES↗
DOE OSTI2020

Benchmarking materials property prediction methods: the Matbench test set and Automatminer reference algorithm

Abstract We present a benchmark test suite and an automated machine learning procedure for evaluating supervised machine learning (ML) models for predicting properties of inorganic bulk materials. The test suite, Matbench, is a set of 13 ML tasks that range in size from 312 to 132k samples and contain data from 10 density functional theory-derived and experimental sources. Tasks include predicting optical, thermal, electronic, thermodynamic, tensile, and elastic properties given a material’s composition and/or crystal structure. The reference algorithm, Automatminer, is a highly-extensible, fully automated ML pipeline for predicting materials properties from materials primitives (such as composition and crystal structure) without user intervention or hyperparameter tuning. We test Automatminer on the Matbench test suite and compare its predictive power with state-of-the-art crystal graph neural networks and a traditional descriptor-based Random Forest model. We find Automatminer achieves the best performance on 8 of 13 tasks in the benchmark. We also show our test suite is capable of exposing predictive advantages of each algorithm—namely, that crystal graph methods appear to outperform traditional machine learning methods given ~10 4 or greater data points. We encourage evaluating materials ML algorithms on the Matbench benchmark and comparing them against the latest version of Automatminer.

36 MATERIALS SCIENCE↗
DOE OSTI2022

Neural Lyapunov Differentiable Predictive Control

We present a learning-based predictive control methodology using the differentiable programming framework with sufficient Lyapunov-based guarantees. The neural Lyapunov differentiable predictive control (NLDPC) learns the policy by constructing a computational graph encompassing the system dynamics, state, and input constraints, and the necessary Lyapunov certification constraints, and thereafter using the automatic differentiation to update the neural policy parameters. In conjunction, our approach jointly learns a Lyapunov function that certifies the regions of state-space with stable dynamics. We also provide an initial condition sampling-based statistical guarantee for the training of NLDPC. Our offline training approach provides a computationally efficient and scalable alternative to classical model predictive control solutions, which now directly comes with Lyapunov based guarantees as shown in this paper. We substantiate the advantages of the proposed approach with simulations to stabilize the double integrator model and on an example of controlling an aircraft model.

Mukherjee, Sayak↗
NASA NTRS1979

Bond graph for modeling valves and switches

Digital graph element represents two-state devices. It can be used in modeling mechanical stops, backlash, and other discontinuities that occur whenever subsystems are connected or disconnected.

Gebben, V. D.↗
NASA NTRS1977

Synchronous meteorological and geostationary operational environmental satellites operational experience

The mode of operation that is of interest in this discussion is a solar array battery load-sharing mode. The battery is loaded for a fraction of a second and then charged, so the cycle is a 100 millisecond load, followed by a 500 millisecond charge. The purpose of the experiment was to evaluate the charge efficiency and the state of charge. Charge/discharge ratio graphs are presented.

Haas, R. J.↗
NASA NTRS1989

Computer-aided boundary delineation of agricultural lands

The National Agricultural Statistics Service of the United States Department of Agriculture (USDA) presently uses labor-intensive aerial photographic interpretation techniques to divide large geographical areas into manageable-sized units for estimating domestic crop and livestock production. Prototype software, the computer-aided stratification (CAS) system, was developed to automate the procedure, and currently runs on a Sun-based image processing system. With a background display of LANDSAT Thematic Mapper and United States Geological Survey Digital Line Graph data, the operator uses a cursor to delineate agricultural areas, called sampling units, which are assigned to strata of land-use and land-cover types. The resultant stratified sampling units are used as input into subsequent USDA sampling procedures. As a test, three counties in Missouri were chosen for application of the CAS procedures. Subsequent analysis indicates that CAS was five times faster in creating sampling units than the manual techniques were.

Cheng, Thomas D.↗
NASA NTRS2003

Robot Acquisition of Active Maps Through Teleoperation and Vector Space Analysis

The work performed under this contract was in the area of intelligent robotics. The problem being studied was the acquisition of intelligent behaviors by a robot. The method was to acquire action maps that describe tasks as sequences of reflexive behaviors. Action maps (a.k.a. topological maps) are graphs whose nodes represent sensorimotor states and whose edges represent the motor actions that cause the robot to proceed from one state to the next. The maps were acquired by the robot after being teleoperated or otherwise guided by a person through a task several times. During a guided task, the robot records all its sensorimotor signals. The signals from several task trials are partitioned into episodes of static behavior. The corresponding episodes from each trial are averaged to produce a task description as a sequence of characteristic episodes. The sensorimotor states that indicate episode boundaries become the nodes, and the static behaviors, the edges. It was demonstrated that if compound maps are constructed from a set of tasks then the robot can perform new tasks in which it was never explicitly trained.

Peters, Richard Alan, II↗
DOE OSTI2025

An automated integrated web-based smart tool for open stope design

The Stability Graph is a widely used tool for the design of open stopes in underground mining. Many users of the Stability Graph still apply this design method manually. Although the manual approach has benefits, using multiple graphs and stability number computation charts for each stope surface is time-consuming, even for the experienced mining engineer. Current practice in the use of the method also limits data sharing. This paper presents a StopeSoft web-based tool for open stope stability prediction that is developed on the basis of the Stability Graph method and is available at openstope.com. StopeSoft incorporates flexibility in terms of Stability Graph options and incorporates additional critical factors often overlooked. As a web-based tool, StopeSoft encourages and makes data sharing possible globally, focused on expanding the database and improving the current limitations of the Stability Graph to provide practical, reliable solutions for mining engineers, consultants, and academics. The StopeSoft automated process facilitates the process of open stope stability prediction, saving time and minimizing potential human errors. Statistical treatment of the data accounts for the variability of input parameters to emphasize the probabilistic nature of the Stability Graph method. The probabilistic interpretation of the stability states of stope surfaces eliminates the false feeling of absolute stope performance based on its location on the Stability Graph , as implied by the deterministic approach.

58 GEOSCIENCES↗
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 OSTI2024

Streaming Matching and Edge Cover in Practice

Graph algorithms with polynomial space and time requirements often become infeasible for massive graphs with billions of edges or more. State-of-the-art approaches therefore employ approximate serial, parallel, and distributed algorithms to tackle these challenges. However, such approaches require storing the entire graph in memory and thus need access to costly computing resources such as clusters and supercomputers. In this paper, we present practical streaming approaches for solving massive graph problems using limited memory for two prototypical graph problems: maximum weighted matching and minimum weighted edge cover. For matching, we conduct a thorough computational study on two of the semi-streaming algorithms including a recent breakthrough result that achieves a $1/(2+\varepsilon)$-approximation of the weight while using $O( n \log W /\epsilon)$ memory (here $n$ is the number of vertices and $W$ is the maximum edge weight), designed by Paz and Schwartzman [SODA, 2017]. Empirically, we show that the semi-streaming algorithms produce matchings whose weight is close to the best $1/2$-approximate offline algorithm while requiring less time and an order-of-magnitude less memory. For minimum weighted edge cover, we develop three novel semi-streaming algorithms. Two of these algorithms require a single pass through the input graph, require $O(n \log n)$ memory, and provide a 2-approximation guarantee on the objective. We also leverage a relationship between approximate maximum weighted matching and approximate minimum weighted edge cover to develop a two-pass $3/2+\epsilon$-approximate algorithm with the memory requirement of Paz and Schwartzman's semi-streaming matching algorithm. These streaming approaches are compared against the state-of-the-art 3/2-approximate offline algorithm. The semi-streaming matching and the novel edge cover algorithms proposed in this paper can process graphs with several billions of edges in under 30 minutes using 6 GB of memory, which is at least an order of magnitude improvement from the offline (non-streaming) algorithms. For the largest graph, the best alternative offline parallel approximation algorithm (GPA+ROMA) could not finish in three hours even while employing hundreds of processors and 1 TB of memory. We also demonstrate an application of the semi-streaming algorithm by computing a matching using linearly bounded memory on item intersection graphs derived from three machine learning datasets, whereas the existing offline algorithms could not complete on one of these datasets since their memory requirements exceeded 1TB.

Ferdous, S M.↗
NASA NTRS1993

Simulator for heterogeneous dataflow architectures

A new simulator is developed to simulate the execution of an algorithm graph in accordance with the Algorithm to Architecture Mapping Model (ATAMM) rules. ATAMM is a Petri Net model which describes the periodic execution of large-grained, data-independent dataflow graphs and which provides predictable steady state time-optimized performance. This simulator extends the ATAMM simulation capability from a heterogenous set of resources, or functional units, to a more general heterogenous architecture. Simulation test cases show that the simulator accurately executes the ATAMM rules for both a heterogenous architecture and a homogenous architecture, which is the special case for only one processor type. The simulator forms one tool in an ATAMM Integrated Environment which contains other tools for graph entry, graph modification for performance optimization, and playback of simulations for analysis.

Malekpour, Mahyar R.↗
DOE OSTI2021

On the use of neural networks for energy reconstruction in high-granularity calorimeters

We contrasted the performance of deep neural networks — Convolutional Neural Network (CNN) and Graph Neural Network (GNN) — to current state of the art energy regression methods in a finely 3D-segmented calorimeter simulated by GEANT4. This comparative benchmark gives us some insight to assess the particular latent signals neural network methods exploit to achieve superior resolution. A CNN trained solely on a pure sample of pions achieved substantial improvement in the energy resolution for both single pions and jets over the conventional approaches. It maintained good performance for electron and photon reconstruction. We also used the Graph Neural Network (GNN) with edge convolution to assess the importance of timing information in the shower development for improved energy reconstruction. We implement a simple simulation based correction to the energy sum derived from the fraction of energy deposited in the electromagnetic shower component. This serves as an approximate dual-readout analogue for our benchmark comparison. Although this study does not include the simulation of detector effects, such as electronic noise, the margin of improvement seems robust enough to suggest these benefits will endure in real-world application. We also find reason to infer that the CNN/GNN methods leverage latent features that concur with our current understanding of the physics of calorimeter measurement.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
NASA NTRS1994

Task scheduling in dataflow computer architectures

Dataflow computers provide a platform for the solution of a large class of computational problems, which includes digital signal processing and image processing. Many typical applications are represented by a set of tasks which can be repetitively executed in parallel as specified by an associated dataflow graph. Research in this area aims to model these architectures, develop scheduling procedures, and predict the transient and steady state performance. Researchers at NASA have created a model and developed associated software tools which are capable of analyzing a dataflow graph and predicting its runtime performance under various resource and timing constraints. These models and tools were extended and used in this work. Experiments using these tools revealed certain properties of such graphs that require further study. Specifically, the transient behavior at the beginning of the execution of a graph can have a significant effect on the steady state performance. Transformation and retiming of the application algorithm and its initial conditions can produce a different transient behavior and consequently different steady state performance. The effect of such transformations on the resource requirements or under resource constraints requires extensive study. Task scheduling to obtain maximum performance (based on user-defined criteria), or to satisfy a set of resource constraints, can also be significantly affected by a transformation of the application algorithm. Since task scheduling is performed by heuristic algorithms, further research is needed to determine if new scheduling heuristics can be developed that can exploit such transformations. This work has provided the initial development for further long-term research efforts. A simulation tool was completed to provide insight into the transient and steady state execution of a dataflow graph. A set of scheduling algorithms was completed which can operate in conjunction with the modeling and performance tools previously developed. Initial studies on the performance of these algorithms were done to examine the effects of application algorithm transformations as measured by such quantities as number of processors, time between outputs, time between input and output, communication time, and memory size.

Katsinis, Constantine↗
DOE OSTI2022

Do graph neural networks learn traditional jet substructure?

At the CERN LHC, the task of jet tagging, whose goal is to infer the origin of a jet given a set of final-state particles, is dominated by machine learning methods. Graph neural networks have been used to address this task by treating jets as point clouds with underlying, learnable, edge connections between the particles inside. We explore the decision-making process for one such state-of-the-art network, ParticleNet, by looking for relevant edge connections identified using the layerwise-relevance propagation technique. As the model is trained, we observe changes in the distribution of relevant edges connecting different intermediate clusters of particles, known as subjets. The resulting distribution of subjet connections is different for signal jets originating from top quarks, whose subjets typically correspond to its three decay products, and background jets originating from lighter quarks and gluons. This behavior indicates that the model is using traditional jet substructure observables, such as the number of prongs -- energetic particle clusters -- within a jet, when identifying jets.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
NASA NTRS2010

Graph-Based Path-Planning for Titan Balloons

A document describes a graph-based path-planning algorithm for balloons with vertical control authority and little or no horizontal control authority. The balloons are designed to explore celestial bodies with atmospheres, such as Titan, a moon of Saturn. The algorithm discussed enables the balloon to achieve horizontal motion using the local horizontal winds. The approach is novel because it enables the balloons to use arbitrary wind field models. This is in contrast to prior approaches that used highly simplified wind field models, such as linear, or binary, winds. This new approach works by discretizing the space in which the balloon operates, and representing the possible states of the balloon as a graph whose arcs represent the time taken to move from one node to another. The approach works with arbitrary wind fields, by looking up the wind strength and direction at every node in the graph from an arbitrary wind model. Having generated the graph, search techniques such as Dijkstra s algorithm are then used to find the set of vertical actuation commands that takes the balloon from the start to the goal in minimum time. In addition, the set of reachable locations on the moon or planet can be determined.

Blackmore, Lars James↗
DOE OSTI2022

Progress toward a universal biomedical data translator

Clinical, biomedical, and translational science has reached an inflection point in the breadth and diversity of available data and the potential impact of such data to improve human health and well-being. However, the data are often siloed, disorganized, and not broadly accessible due to discipline-specific differences in terminology and representation. To address these challenges, the Biomedical Data Translator Consortium has developed and tested a pilot knowledge graph-based “Translator” system capable of integrating existing biomedical data sets and “translating” those data into insights intended to augment human reasoning and accelerate translational science. Having demonstrated feasibility of the Translator system, the Translator program has since moved into development, and the Translator Consortium has made significant progress in the research, design, and implementation of an operational system. Herein, we describe the current system’s architecture, performance, and quality of results. We apply Translator to several real-world use cases developed in collaboration with subject-matter experts. Finally, we discuss the scientific and technical features of Translator and compare those features to other state-of-the-art, biomedical graph-based question-answering systems.

60 APPLIED LIFE SCIENCES↗