Search NASA⌕ Search

SEARCH · Search NASA

Results for “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 91 records · Page 5
All sourcesNASA NTRSDOE OSTI
NASA NTRS1988

Multiple directed graph large-class multi-spectral processor

Numerical analysis techniques for the interpretation of high-resolution imaging-spectrometer data are described and demonstrated. The method proposed involves the use of (1) a hierarchical classifier with a tree structure generated automatically by a Fisher linear-discriminant-function algorithm and (2) a novel multiple-directed-graph scheme which reduces the local maxima and the number of perturbations required. Results for a 500-class test problem involving simulated imaging-spectrometer data are presented in tables and graphs; 100-percent-correct classification is achieved with an improvement factor of 5.

Casasent, David↗
NASA NTRS1991

The role of reliability graph models in assuring dependable operation of complex hardware/software systems

The complexity of computer systems currently being designed for critical applications in the scientific, commercial, and military arenas requires the development of new techniques for utilizing models of system behavior in order to assure 'ultra-dependability'. The complexity of these systems, such as Space Station Freedom and the Air Traffic Control System, stems from their highly integrated designs containing both hardware and software as critical components. Reliability graph models, such as fault trees and digraphs, are used frequently to model hardware systems. Their applicability for software systems has also been demonstrated for software safety analysis and the analysis of software fault tolerance. This paper discusses further uses of graph models in the design and implementation of fault management systems for safety critical applications.

Patterson-Hine, F. A.↗
NASA NTRS1992

A Benes-like theorem for the shuffle-exchange graph

One of the first theorems on permutation routing, proved by V. E. Beness (1965), shows that given a set of source-destination pairs in an N-node butterfly network with at most a constant number of sources or destinations in each column of the butterfly, there exists a set of paths of lengths O(log N) connecting each pair such that the total congestion is constant. An analogous theorem yielding constant-congestion paths for off-line routing in the shuffle-exchange graph is proved here. The necklaces of the shuffle-exchange graph play the same structural role as the columns of the butterfly in Beness' theorem.

Schwabe, Eric J.↗
NASA NTRS1994

Graph-Based Dynamic Assignment Of Multiple Processors

Algorithm-to-architecture mapping model (ATAMM) is strategy minimizing time needed to periodically execute graphically described, data-driven application algorithm on multiple data processors. Implemented as operating system managing flow of data and dynamically assigns nodes of graph to processors. Predicts throughput versus number of processors available to execute given application algorithm. Includes rules ensuring application algorithm represented by graph executed periodically without deadlock and in shortest possible repetition time. ATAMM proves useful in maximizing effectiveness of parallel computing systems.

Hayes, Paul J.↗
NASA NTRS1994

Graphing techniques for materials laboratory using Excel

Engineering technology curricula stress hands on training and laboratory practices in most of the technical courses. Laboratory reports should include analytical as well as graphical evaluation of experimental data. Experience shows that many students neither have the mathematical background nor the expertise for graphing. This paper briefly describes the procedure and data obtained from a number of experiments such as spring rate, stress concentration, endurance limit, and column buckling for a variety of materials. Then with a brief introduction to Microsoft Excel the author explains the techniques used for linear regression and logarithmic graphing.

Kundu, Nikhil K.↗
NASA NTRS1994

A software tool for dataflow graph scheduling

A graph-theoretic design process and software tool is presented for selecting a multiprocessing scheduling solution for a class of computational problems. The problems of interest are those that can be described using a dataflow graph and are intended to be executed repetitively on multiple processors. The dataflow paradigm is very useful in exposing the parallelism inherent in algorithms. It provides a graphical and mathematical model which describes a partial ordering of algorithm tasks based on data precedence.

Jones, Robert L., III↗
NASA NTRS1998

A PVS Graph Theory Library

This paper documents the NASA Langley PVS graph theory library. The library provides fundamental definitions for graphs, subgraphs, walks, paths, subgraphs generated by walks, trees, cycles, degree, separating sets, and four notions of connectedness. Theorems provided include Ramsey's and Menger's and the equivalence of all four notions of connectedness.

Butler, Ricky W.↗
NASA NTRS1996

Graphing Calculator Mini Course

The "Graphing Calculator Mini Course" project provided a mathematically-intensive technologically-based summer enrichment workshop for teachers of American Indian students on the Turtle Mountain Indian Reservation. Eleven such teachers participated in the six-day workshop in summer of 1996 and three Sunday workshops in the academic year. The project aimed to improve science and mathematics education on the reservation by showing teachers effective ways to use high-end graphing calculators as teaching and learning tools in science and mathematics courses at all levels. In particular, the workshop concentrated on applying TI-82's user-friendly features to understand the various mathematical and scientific concepts.

Karnawat, Sunil R.↗
NASA NTRS2002

Graph Partitioning for Parallel Applications in Heterogeneous Grid Environments

The problem of partitioning irregular graphs and meshes for parallel computations on homogeneous systems has been extensively studied. However, these partitioning schemes fail when the target system architecture exhibits heterogeneity in resource characteristics. With the emergence of technologies such as the Grid, it is imperative to study the partitioning problem taking into consideration the differing capabilities of such distributed heterogeneous systems. In our model, the heterogeneous system consists of processors with varying processing power and an underlying non-uniform communication network. We present in this paper a novel multilevel partitioning scheme for irregular graphs and meshes, that takes into account issues pertinent to Grid computing environments. Our partitioning algorithm, called MiniMax, generates and maps partitions onto a heterogeneous system with the objective of minimizing the maximum execution time of the parallel distributed application. For experimental performance study, we have considered both a realistic mesh problem from NASA as well as synthetic workloads. Simulation results demonstrate that MiniMax generates high quality partitions for various classes of applications targeted for parallel execution in a distributed heterogeneous environment.

Bisws, Rupak↗
NASA NTRS1991

Large constraint length high speed viterbi decoder based on a modular hierarchial decomposition of the deBruijn graph

A method of formulating and packaging decision-making elements into a long constraint length Viterbi decoder which involves formulating the decision-making processors as individual Viterbi butterfly processors that are interconnected in a deBruijn graph configuration. A fully distributed architecture, which achieves high decoding speeds, is made feasible by novel wiring and partitioning of the state diagram. This partitioning defines universal modules, which can be used to build any size decoder, such that a large number of wires is contained inside each module, and a small number of wires is needed to connect modules. The total system is modular and hierarchical, and it implements a large proportion of the required wiring internally within modules and may include some external wiring to fully complete the deBruijn graph. pg,14.

Collins, Oliver↗
NASA NTRS1990

Method for concurrent execution of primitive operations by dynamically assigning operations based upon computational marked graph and availability of data

Computationally complex primitive operations of an algorithm are executed concurrently in a plurality of functional units under the control of an assignment manager. The algorithm is preferably defined as a computationally marked graph contianing data status edges (paths) corresponding to each of the data flow edges. The assignment manager assigns primitive operations to the functional units and monitors completion of the primitive operations to determine data availability using the computational marked graph of the algorithm. All data accessing of the primitive operations is performed by the functional units independently of the assignment manager.

Stoughton, John W.↗
NASA NTRS2015

Got Graphs? An Assessment of Data Visualization Tools

Graphs are powerful tools for simplifying complex data. They are useful for quickly assessing patterns and relationships among one or more variables from a dataset. As the amount of data increases, it becomes more difficult to visualize potential associations. Lifetime Surveillance of Astronaut Health (LSAH) was charged with assessing its current visualization tools along with others on the market to determine whether new tools would be useful for supporting NASA's occupational surveillance effort. It was concluded by members of LSAH that the current tools hindered their ability to provide quick results to researchers working with the department. Due to the high volume of data requests and the many iterations of visualizations requested by researchers, software with a better ability to replicate graphs and edit quickly could improve LSAH's efficiency and lead to faster research results.

Schaefer, C. M.↗
NASA NTRS2018

Using a Knowledge Graph to Discover Earth Science Information

Knowledge graphs link key entities within a specific domain to other entities via relationships. Researchers are able to mine these relationships from numerous sources to infer new knowledge. Text extraction from peer-reviewed papers and scientific reports are untapped resources that can be leveraged by knowledge graphs to accelerate scientific discovery.

Freitag, Brian↗
NASA NTRSDate not supplied

Planning for Compilation of a Quantum Algorithm for Graph Coloring

Recently, the problem of compiling general quantum algorithms for implementation on near-term quantum processors has been introduced to the AI community. Previous work demonstrated that temporal planning is an attractive approach for part of this compilation task, specifically, the routing of circuits that implement the Quantum Alternating Operator Ansatz (QAOA) applied to theMaxCut problem on a quantum processor architecture. In this paper, we extend the earlier work to route circuits that implement QAOAfor Graph Coloring problems. QAOA for coloring requires execution of more, and more complex, operations on the chip, which makes routing a more challenging problem. We evaluate the approach on state-of-the-art hardware architectures from leading quantum computing companies. Additionally, we investigate applying the planning approach to qubit initialization as well as routing. Our empirical evaluation shows that temporal planning compares well to reasonable analytic upper bounds [20], and that solving qubit initialization with a classical planner generally helps temporal planners in finding shorter-makespan compilations for QAOA for Graph Coloring.These advances suggest that temporal planning can be an effective approach for more complex quantum computing algorithms and architectures.

Minh Do↗
NASA NTRS2018

Evaluation of Opportunistic Contact Graph Routing in Random Mobility Environments

Routing in networks where nodes move randomly is particularly challenging due their potentially unpredictable, and rapidly changing topology. Several routing algorithms have been presented in the literature to address the needs of such networks, most of them implementing variants of controlled network flooding in the hope of successful data delivery. In this note, we compare the results of previous routing algorithms with Opportunistic Contact Graph Routing (OCGR), an enhanced version of Contact Graph Routing (CGR) that is suitable for networks where contacts cannot always be scheduled ahead of time. To perform the benchmark, we simulate a network of nodes moving in a certain space according to the Random Waypoint Mobility Model, and then take measurements of bundle delivery probabilty and overhead ratio as metrics of performance and cost respectively. Through this exercise, we demonstrate that the performance of OCGR is highly dependent on the type of network under consideration (e.g. very sparse vs. densely connected) and the assumed mobility model.

Burleigh, Scott↗
NASA NTRSDate not supplied

Creating a knowledge graph to connect scientific publications and datasets for improving discovery of GES DISC’s data and services

The NASA Goddard Earth Sciences Data and Information Services Center (GES DISC) archives and distributes to the public hundreds of Earth Science data collections. These collections are used in research, resulting in thousands of scientific papers published each year. As new users come to GES DISC for the data, it is important for them to understand how these data were used in the prior research. For this we are creating the Knowledge Graph that connects research paper citation and the data collection metadata. The relationships created in the graph have potential for the Web applications that utilize this information to directly connect the paper research to the GES DISC datasets and services. We will demonstrate these relationships using the Web application prototype.

Nathaniel Ross Crosby↗
NASA NTRS2021

Predicting the Functional State of Protein Kinases Using Interpretable Graph Neural Networks

Kinases are a family of proteins that function as molecular switches, regulating several essential cellular activities such as cell proliferation. Dysfunctional kinases are implicated in several types of cancers and hence they are actively pursued as drug targets. Given the vast number of complex kinase structures that are available in the protein data bank (PDB), there is a necessity to develop methodologies that can identify structurally important moieties of the kinases in an automated fashion, for such techniques can be instrumental in identifying novel drug targets. In this work, we develop a graph neural network (GNN) based deep learning framework for classifying the functionally active and inactive states of a large set of eukaryotic protein kinases, making use of their 3D structure from the PDB. We show that GNN based machine learning models can classify protein states with an accuracy greater than 97%. We further use the GNN models to automatically identify regions of the kinases that are important for its function. For this purpose, Gradient-weighted Class Activation Mapping (Grad-CAM) was implemented on the protein graphs. Remarkably, Grad-CAM consistently identifies the highly conserved DFG motif as the most important part of the protein across the entire kinome, without any prior input. Other regions of the hydrophobic core such as the HRD motif were also identified by the interpretable GNN framework, consistent with the literature. We discuss the significance of each of these regions in detail.

Ashwin Ravichandran↗