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 145 records · Page 8
All sourcesNASA NTRSDOE OSTI
NASA NTRS1994

On bottleneck partitioning k-ary n-cubes

Graph partitioning is a topic of extensive interest, with applications to parallel processing. In this context graph nodes typically represent computation, and edges represent communication. One seeks to distribute the workload by partitioning the graph so that every processor has approximately the same workload, and the communication cost (measured as a function of edges exposed by the partition) is minimized. Measures of partition quality vary; in this paper we consider a processor's cost to be the sum of its computation and communication costs, and consider the cost of a partition to be the bottleneck, or maximal processor cost induced by the partition. For a general graph the problem of finding an optimal partitioning is intractable. In this paper we restrict our attention to the class of k-art n-cube graphs with uniformly weighted nodes. Given mild restrictions on the node weight and number of processors, we identify partitions yielding the smallest bottleneck. We also demonstrate by example that some restrictions are necessary for the partitions we identify to be optimal. In particular, there exist cases where partitions that evenly partition nodes need not be optimal.

Nicol, David M.↗
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 OSTI2020

Faster Johnson–Lindenstrauss transforms via Kronecker products

The Kronecker product is an important matrix operation with a wide range of applications in signal processing, graph theory, quantum computing and deep learning. In this work, we introduce a generalization of the fast Johnson–Lindenstrauss projection for embedding vectors with Kronecker product structure, the Kronecker fast Johnson–Lindenstrauss transform (KFJLT). The KFJLT reduces the embedding cost by an exponential factor of the standard fast Johnson–Lindenstrauss transform’s cost when applied to vectors with Kronecker structure, by avoiding explicitly forming the full Kronecker products. Here, we prove that this computational gain comes with only a small price in embedding power: consider a finite set of $p$ points in a tensor product of $d$ constituent Euclidean spaces $\bigotimes _{k=d}^{1}{\mathbb{R}}^{n_k}$, and let $N = \prod _{k=1}^{d}n_k$. With high probability, a random KFJLT matrix of dimension $m \times N$ embeds the set of points up to multiplicative distortion $(1\pm \varepsilon )$ provided $m \gtrsim \varepsilon ^{-2} \, \log ^{2d - 1} (p) \, \log N$. We conclude by describing a direct application of the KFJLT to the efficient solution of large-scale Kronecker-structured least squares problems for fitting the CP tensor decomposition.

Kronecker structure↗
DOE OSTI2024

MassiveGNN: Efficient Training via Prefetching for Massively Connected Distributed Graphs

Graph Neural Networks (GNN) are indispensable in learning from graph-structured data, yet their rising computational costs, especially on massively connected graphs, pose significant challenges in terms of execution performance. To tackle this, distributed-memory solutions such as partitioning the graph to concurrently train multiple replicas of GNNs are in practice. However, approaches requiring a partitioned graph usually suffer from communication overhead and load imbalance, even under optimal partitioning and communication strategies due to irregularities in the neighborhood minibatch sampling. This paper proposes practical trade-offs for improving the sampling and communication overheads for representation learn- ing on distributed graphs (using popular GraphSAGE architecture) by developing a parameterized prefetch and eviction scheme on top of the state-of-the-art Amazon DistDGL distributed GNN framework, demonstrating about 15–40% improvement in end-to-end training performance on the NERSC Perlmutter supercomputer for various OGB datasets.

Machine Leanring, high performance comptuing, grap↗
DOE OSTI2021

Efficient Topology Design Algorithms for Power Grid Stability

The dynamic response of power grids to small disturbances influences their overall stability. This letter examines the effect of network topology on the linearized time-invariant dynamics of electric power systems. The proposed framework utilizes H 2 -norm based stability metrics to study the optimal placement of lines on existing networks as well as the topology design of new networks. The design task is first posed as an NP-hard mixed-integer nonlinear program (MINLP) that is exactly reformulated as a mixed-integer linear program (MILP) using McCormick linearization. To improve computation time, graph-theoretic properties are exploited to derive valid inequalities (cuts) and tighten bounds on the continuous optimization variables. Moreover, a cutting plane generation procedure is put forth that is able to interject the MILP solver and augment additional constraints to the problem on-the-fly. Finally, the efficacy of our approach in designing optimal grid topologies is demonstrated through numerical tests on the IEEE 39-bus network.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2021

Elga v.1

SAND2021-4635 O Elga is a software system that provides distributed and elastic computation for temporal graph algorithms. Sandia National Laboratories is a multimission laboratory managed and operated by National Technology & Engineering Solutions of Sandia, LLC, a wholly owned subsidiary of Honeywell International Inc., for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-NA0003525.

Gabert, Kasimir↗
NASA NTRS1973

Aircraft requirements for low/medium density markets

A study was conducted to determine the demand for and the economic factors involved in air transportation in a low and medium density market. The subjects investigated are as follows: (1) industry and market structure, (2) aircraft analysis, (3) economic analysis, (4) field surveys, and (5) computer network analysis. Graphs are included to show the economic requirements and the aircraft performance characteristics.

Ausrotas, R.↗
NASA NTRS1978

Wind shear modeling for aircraft hazard definition

Mathematical models of wind profiles were developed for use in fast time and manned flight simulation studies aimed at defining and eliminating these wind shear hazards. A set of wind profiles and associated wind shear characteristics for stable and neutral boundary layers, thunderstorms, and frontal winds potentially encounterable by aircraft in the terminal area are given. Engineering models of wind shear for direct hazard analysis are presented in mathematical formulae, graphs, tables, and computer lookup routines. The wind profile data utilized to establish the models are described as to location, how obtained, time of observation and number of data points up to 500 m. Recommendations, engineering interpretations and guidelines for use of the data are given and the range of applicability of the wind shear models is described.

Frost, W.↗
NASA NTRS1982

Manifold Insulation for Solar Collectors

Results of computer analysis of effects of various manifold insulation detailed in 23-page report show that if fluid is distributed to and gathered from array of solar collectors by external rather than internal manifold, effectiveness of manifold insulation has major influence on efficiency. Report describes required input data and presents equations that govern computer model. Provides graphs comparing collector efficiencies for representative manifold sizes and insulations.

Source record↗
NASA NTRS1985

Orbits: Computer simulation

In rotating machinery dynamics an orbit (Lissajous curve) represents the dynamic path of the shaft centerline motion during shaft rotation and resulting precession. The orbit can be observed with an oscilloscope connected to XY promixity probes. The orbits can also be simulated by a computer. The software for HP computer simulates orbits for two cases: (1) Symmetric orbit with four frequency components with different radial amplitudes and relative phase angles; and (2) Nonsymmetric orbit with two frequency components with two different vertical/horizontal amplitudes and two different relative phase angles. Each orbit carries a Keyphasor mark (one-per-turn reference). The frequencies, amplitudes, and phase angles, as well as number of time steps for orbit computation, have to be chosen and introduced to the computer by the user. The orbit graphs can be observed on the computer screen.

Muszynska, A.↗
NASA NTRS1990

Potential evapotranspiration and the likelihood of future drought

The possibility that the greenhouse warming predicted by the GISS general-circulation model and other GCMs could lead to severe droughts is investigated by means of numerical simulations, with a focus on the role of potential evapotranspiration E(P). The relationships between precipitation (P), E(P), soil moisture, and vegetation changes in GCMs are discussed; the empirically derived Palmer drought-intensity index and a new supply-demand index (SDDI) based on changes in P - E(P) are described; and simulation results for the period 1960-2060 are presented in extensive tables, graphs, and computer-generated color maps. Simulations with both drought indices predict increasing drought frequency for the U.S., with effects already apparent in the 1990s and a 50-percent frequency of severe droughts by the 2050s. Analyses of arid periods during the Mesozoic and Cenozoic are shown to support the use of the SDDI in GCM drought prediction.

Rind, D.↗
DOE OSTI2026

Navigating Large Chemical Spaces Using Graph Theory and Integer Programming

Navigating and analyzing large chemical spaces are necessary to accelerate the design and discovery of new molecules and chemical processes. In this work, we introduce a computational framework that integrates graph theory and integer programming to enable the efficient navigation of large chemical spaces. Our framework represents the chemical space as a graph, wherein nodes represent molecules and edges represent the degree of similarity or connectivity based on domain-specific information. Using the graph representation, we identify representative molecules by computing the so-called minimum dominating set (MDS), which in our context is the minimum set of molecules that is connected to all other molecules. We present a suite of solution strategies for the MDS problem including heuristic and rigorous integer programming (IP) approaches. We show that these approaches allow us to capture physicochemical properties and domain-specific logic and constraints, facilitating the identification of molecules with the target properties. We demonstrate the effectiveness of the proposed approach by navigating the chemical space of per- and polyfluoroalkyl substances (PFAS); this comprises approximately 15,000 molecular structures. We compare our framework against traditional dimensionality reduction and clustering methods such as t-SNE and K-means clustering.

Chemical structure↗
NASA NTRS1992

Software For Generating Graphs And Charts

Common Graphics Library (CGL) computer program designed to enable users to generate graphs and charts of quality sufficient for publication or optical projection. Quickly and easily generates linear, logarithmic, bar, pie, and composite charts. Features of linear charts include automatic scaling, increasing or decreasing numerical axes, and character axes. Features of pie charts include segment labels, exploded segments, and chart keys. One of general features, horizontal or vertical orientation of figures. Written in ANSI FORTRAN 77.

Hammond, Dana P.↗
NASA NTRS1991

A graph theoretic approach to scene matching

The ability to match two scenes is a fundamental requirement in a variety of computer vision tasks. A graph theoretic approach to inexact scene matching is presented which is useful in dealing with problems due to imperfect image segmentation. A scene is described by a set of graphs, with nodes representing objects and arcs representing relationships between objects. Each node has a set of values representing the relations between pairs of objects, such as angle, adjacency, or distance. With this method of scene representation, the task in scene matching is to match two sets of graphs. Because of segmentation errors, variations in camera angle, illumination, and other conditions, an exact match between the sets of observed and stored graphs is usually not possible. In the developed approach, the problem is represented as an association graph, in which each node represents a possible mapping of an observed region to a stored object, and each arc represents the compatibility of two mappings. Nodes and arcs have weights indicating the merit or a region-object mapping and the degree of compatibility between two mappings. A match between the two graphs corresponds to a clique, or fully connected subgraph, in the association graph. The task is to find the clique that represents the best match. Fuzzy relaxation is used to update the node weights using the contextual information contained in the arcs and neighboring nodes. This simplifies the evaluation of cliques. A method of handling oversegmentation and undersegmentation problems is also presented. The approach is tested with a set of realistic images which exhibit many types of sementation errors.

Ranganath, Heggere S.↗
NASA NTRS2006

International Space Station Centrifuge Rotor Models A Comparison of the Euler-Lagrange and the Bond Graph Modeling Approach

The assembly and operation of the International Space Station (ISS) require extensive testing and engineering analysis to verify that the Space Station system of systems would work together without any adverse interactions. Since the dynamic behavior of an entire Space Station cannot be tested on earth, math models of the Space Station structures and mechanical systems have to be built and integrated in computer simulations and analysis tools to analyze and predict what will happen in space. The ISS Centrifuge Rotor (CR) is one of many mechanical systems that need to be modeled and analyzed to verify the ISS integrated system performance on-orbit. This study investigates using Bond Graph modeling techniques as quick and simplified ways to generate models of the ISS Centrifuge Rotor. This paper outlines the steps used to generate simple and more complex models of the CR using Bond Graph Computer Aided Modeling Program with Graphical Input (CAMP-G). Comparisons of the Bond Graph CR models with those derived from Euler-Lagrange equations in MATLAB and those developed using multibody dynamic simulation at the National Aeronautics and Space Administration (NASA) Johnson Space Center (JSC) are presented to demonstrate the usefulness of the Bond Graph modeling approach for aeronautics and space applications.

Nguyen, Louis H.↗