SEARCH · Engineering Papers

Results for “graph algorithm”

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.

SourceResearch connectionFrom yearThrough year

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 145 records · Page 8

All sources NASA NTRS DOE OSTI

DOE OSTI2023

Real-Time Multi-Vehicle Multi-Camera Tracking with Graph-Based Tracklet Features

An essential application in intelligent transportation systems is multi-target multi-camera tracking (MTMCT), where the target’s activity is tracked from different cameras. Although the tracking-by-detection scheme is the primary paradigm in MTMCT, the object association information from the video frames is lost. This is mainly because the multi-camera multi-object matching uses the information from the video frames separately. To solve this problem and leverage this association information, we propose an MTMCT framework, where features are built in the form of a graph and a graph similarity algorithm is used to match multi-camera objects. In this paper, we focus on the real-time scenario, where only the past images are used to match an object. Our method achieves an IDF1 score (the ratio of the number of correctly identified objects to the number of ground truth and average objects) of 0.75 with a rate of 14 frames per second (fps).

Engineering↗

DOE OSTI2022

The public health exposome and pregnancy-related mortality in the United States: a high-dimensional computational analysis

Racial inequities in maternal mortality in the U.S. continue to be stark. The 2015–2018, 4-year total population, county-level, pregnancy-related mortality ratio (PRM; deaths per 100,000 live births; National Center for Health Statistics (NCHS), restricted use mortality file) was linked with the Public Health Exposome (PHE). Using data reduction techniques, 1591 variables were extracted from over 62,000 variables for use in this analysis, providing information on the relationships between PRM and the social, health and health care, natural, and built environments. Graph theoretical algorithms and Bayesian analysis were applied to PHE/PRM linked data to identify latent networks. PHE variables most strongly correlated with total population PRM were years of potential life lost and overall life expectancy. Population-level indicators of PRM were overall poverty, smoking, lack of exercise, heat, and lack of adequate access to food. In this high-dimensional analysis, overall life expectancy, poverty indicators, and health behaviors were found to be the strongest predictors of pregnancy-related mortality. This provides strong evidence that maternal death is part of a broader constellation of both similar and unique health behaviors, social determinants and environmental exposures as other causes of death.

60 APPLIED LIFE SCIENCES↗

DOE OSTI2024

Portable Parallel Algorithms and Frameworks for Exascale Graph Analytics

Graphs (or networks) are a tool used to model the interactions among various entities. Efficiently processing large graphs has recently attracted significant attention due to the applications of graphs in various domains, such as biology, chemistry, and cyber-security. Analyzing the structure and properties of these graphs is an important component of many scientific computing pipelines. With the explosion in the volume of data, graphs have become very large and can contain hundreds of billions of vertices and trillions of edges. Therefore, it is crucial to develop high-performance methods to enable graph analysis to be done quickly and energy-efficiently. Furthermore, these solutions should be highly parallel in order to take advantage of modern parallel machines. However, designing efficient solutions is not enough. With the wide variety of computing environments available, each with different programmability and performance characteristics, it is necessary to develop solutions that are portable in terms of both performance (i.e., provide theoretical guarantees) and programmability (i.e., provide high level abstractions).

97 MATHEMATICS AND COMPUTING↗

NASA NTRS1990

Assembly planning for large truss structures in space

The approach is based on a graph search algorithm. A relational data structure is used to represent a truss structure. There are four types of entities: units, faces, edges, and vertices. There are contain/contained relationships for every pair of entity types, as well as in-contact relationships between faces. A best-first algorithm constitutes the core of the planner. The cost function in the current implementation corresponds to a combination of the rigidity of the intermediate structures and the total distance to be traversed by the agent executing the assembly tasks.

Homem De Mello, L. S.↗

NASA NTRS1991

Validating system-level error recovery for spacecraft

The system-level software onboard a spacecraft is responsible for recovery from communication, thermal, power, and computer-health anomalies that may occur. The recovery must occur without disrupting any critical scientific or engineering activity that is executing at the time of the error. Thus, the error-recovery software may have to execute concurrently with the ongoing acquisition of scientific data or with spacecraft maneuvers. This paper provides a technique by which the rules that constrain the concurrent execution of these processes can be modeled in a graph. An algorithm is described that uses this model to validate that the constraints hold for all concurrent executions of the error-recovery softwave with the softwave that controls the science and engineering events on the spacecraft.

Lutz, Robyn R.↗

NASA NTRS1993

Constraint checking during error recovery

The system-level software onboard a spacecraft is responsible for recovery from communication, power, thermal, and computer-health anomalies that may occur. The recovery must occur without disrupting any critical scientific or engineering activity that is executing at the time of the error. Thus, the error-recovery software may have to execute concurrently with the ongoing acquisition of scientific data or with spacecraft maneuvers. This work provides a technique by which the rules that constrain the concurrent execution of these processes can be modeled in a graph. An algorithm is described that uses this model to validate that the constraints hold for all concurrent executions of the error-recovery software with the software that controls the science and engineering activities of the spacecraft. The results are applicable to a variety of control systems with critical constraints on the timing and ordering of the events they control.

Lutz, Robyn R.↗

NASA NTRS1996

Dataflow Design Tool: User's Manual

The Dataflow Design Tool is a software tool for selecting a multiprocessor scheduling solution for a class of computational problems. The problems of interest are those that can be described with a dataflow graph and are intended to be executed repetitively on a set of identical processors. Typical applications include signal processing and control law problems. The software tool implements graph-search algorithms and analysis techniques based on the dataflow paradigm. Dataflow analyses provided by the software are introduced and shown to effectively determine performance bounds, scheduling constraints, and resource requirements. The software tool provides performance optimization through the inclusion of artificial precedence constraints among the schedulable tasks. The user interface and tool capabilities are described. Examples are provided to demonstrate the analysis, scheduling, and optimization functions facilitated by the tool.

Jones, Robert L., III↗

NASA NTRSDate not supplied

Airspace Research and Development Portfolio Assessment of Urban Air Mobility using Knowledge Graph Data Science

National Aeronautics and Space Administration (NASA) is spearheading an innovative digital engineering approach to integrate, communicate, and facilitate the research of Urban Air Mobility (UAM) operations. The UAM vision is one in which advanced technologies and new operational procedures enable practical and cost-effective air transport as an integrated mode of movement of people and goods throughout metropolitan areas. To safely support UAM operations at scale in the National Airspace System (NAS), NASA’s Air Traffic Management-Exploration (ATM-X) project has been conducting research that evolves the UAM air traffic management system towards a highly automated and operationally flexible system of the future. The complexity of UAM airspace evolution to accommodate the increasing tempo of UAM operations over time is managed through the UAM airspace research roadmap, which is a system engineering approach to the R&D of complex system-of-systems, where system’s interdependencies make it nearly impossible to define requirements for individual elements of the system in isolation. These interdependencies form a knowledge graph (node-link network) with a highly complex structure far beyond the human user’s ability to extract insights for project management’s research portfolio assessment. This study applies advanced data analytics in knowledge graph to the UAM knowledge graph to facilitate the portfolio assessment.

ATM↗

NASA NTRSDate not supplied

Airspace Research and Development Portfolio Assessment of Urban Air Mobility using Knowledge Graph Data Science

ATM↗

DOE OSTI2020

Triangle Counting with Cyclic Distributions

Triangles are the simplest non-trivial subgraphs and triangle counting is used in a number of different applications. The order in which vertices are processed in triangle counting strongly effects the amount of work that needs to be done (and thus the overall performance). Ordering vertices by degree has been shown to be one particularly effective ordering approach. However, for graphs with skewed degree distributions (such as power-law graphs), ordering by degree effects the distribution of work; parallelization must account for this distribution in order to balance work among workers. In this paper we provide an in- depth analysis of the ramifications of degree-based ordering on parallel triangle counting. We present approach for partitioning work in triangle counting, based on cyclic distribution and some surprisingly simple C++ implementations. Experimental results demonstrate the effectiveness of our approach, particularly for power-law (and social network) graphs.

Graph algorithms, parallel algorithms↗

DOE OSTI2020

Performance-Portable and Scalable Algorithms on Sparse/Dense Matrices and Graphs.

Abstract not provided.

Acer, Seher↗

NASA NTRS2000

JavaGenes: Evolving Graphs with Crossover

Genetic algorithms usually use string or tree representations. We have developed a novel crossover operator for a directed and undirected graph representation, and used this operator to evolve molecules and circuits. Unlike strings or trees, a single point in the representation cannot divide every possible graph into two parts, because graphs may contain cycles. Thus, the crossover operator is non-trivial. A steady-state, tournament selection genetic algorithm code (JavaGenes) was written to implement and test the graph crossover operator. All runs were executed by cycle-scavagging on networked workstations using the Condor batch processing system. The JavaGenes code has evolved pharmaceutical drug molecules and simple digital circuits. Results to date suggest that JavaGenes can evolve moderate sized drug molecules and very small circuits in reasonable time. The algorithm has greater difficulty with somewhat larger circuits, suggesting that directed graphs (circuits) are more difficult to evolve than undirected graphs (molecules), although necessary differences in the crossover operator may also explain the results. In principle, JavaGenes should be able to evolve other graph-representable systems, such as transportation networks, metabolic pathways, and computer networks. However, large graphs evolve significantly slower than smaller graphs, presumably because the space-of-all-graphs explodes combinatorially with graph size. Since the representation strongly affects genetic algorithm performance, adding graphs to the evolutionary programmer's bag-of-tricks should be beneficial. Also, since graph evolution operates directly on the phenotype, the genotype-phenotype translation step, common in genetic algorithm work, is eliminated.

Globus, Al↗

DOE OSTI2025

GASP: Gradient-Aware Shortest Path Algorithm for Boundary-Confined 2-Manifold Reeb Graph Visualization

Reeb graphs are an important tool for abstracting and representing the topological structure of a function defined on a manifold. We have identified three properties for faithfully representing Reeb graphs in a visualization: they should be constrained to the boundary, compact, and aligned with the function gradient. Existing algorithms for drawing Reeb graphs are agnostic to or violate these properties. In this paper, we introduce an algorithm to generate Reeb graph visualizations, called GASP, that is cognizant of these properties, thereby producing visualizations that are more representative of the underlying data. To demonstrate the improvements, the resulting Reeb graphs are evaluated both qualitatively and quantitatively against the geometric barycenter algorithm, using its implementation available in the Topology ToolKit (TTK), a widely adopted tool for calculating and visualizing Reeb graphs.

Rahman, Sefat [University of Utah]↗

DOE OSTI2020

On the Feasibility of Using Reduced-Precision Tensor Core Operations for Graph Analytics

Today’s data-driven analytics and machine learning workload have been largely driven by the General-PurposeGraphics Processing Units (GPGPUs). To accelerate dense matrix multiplications on the GPUs, Tensor Core Units (TCUs) have been introduced in recent years. In this paper, we study linear-algebra-based and vertex-centric algorithms for various graph kernels on the GPUs with an objective of applying this new hardware feature to graph applications. We identify the potential stages in these graph kernels that can be executed on the Tensor Core Units. In particular, we leverage the reformulation of the reduction and scan operations in terms of matrix multiplication [1]on the TCUs. We demonstrate that executing these operations on the TCUs, available inside different graph kernels, can assist in establishing an end-to-end pipeline on the GPGPUs without depending on hand-tuned external libraries and still can deliver comparable performance for various graph analytics.

Graph algorithms, GPU computing↗

DOE OSTI2020

OpenGraphGym: A Parallel Reinforcement Learning Framework for Graph Optimization Problems

This paper presents an open-source, parallel AI environment (named OpenGraphGym) to facilitate the application of reinforcement learning (RL) algorithms to address combinatorial graph optimization problems. This environment incorporates a basic deep reinforcement learning method, and several graph embeddings to capture graph features, it also allows users to rapidly plug in and test new RL algorithms and graph embeddings for graph optimization problems. This new open-source RL framework is targeted at achieving both high performance and high quality of the computed graph solutions. This RL framework forms the foundation of several ongoing research directions, including 1) benchmark works on different RL algorithms and embedding methods for classic graph problems; 2) advanced parallel strategies for extreme-scale graph computations, as well as 3) performance evaluation on real-world graph solutions.

Zheng, Weijian↗

NASA NTRS1993

A dataflow analysis tool for parallel processing of algorithms

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 a set of identical parallel processors. Typical applications include signal processing and control law problems. Graph analysis techniques are introduced and shown to effectively determine performance bounds, scheduling constraints, and resource requirements. The software tool is shown to facilitate the application of the design process to a given problem.

Jones, Robert L., III↗

NASA NTRS1990

Partitioning sparse matrices with eigenvectors of graphs

The problem of computing a small vertex separator in a graph arises in the context of computing a good ordering for the parallel factorization of sparse, symmetric matrices. An algebraic approach for computing vertex separators is considered in this paper. It is shown that lower bounds on separator sizes can be obtained in terms of the eigenvalues of the Laplacian matrix associated with a graph. The Laplacian eigenvectors of grid graphs can be computed from Kronecker products involving the eigenvectors of path graphs, and these eigenvectors can be used to compute good separators in grid graphs. A heuristic algorithm is designed to compute a vertex separator in a general graph by first computing an edge separator in the graph from an eigenvector of the Laplacian matrix, and then using a maximum matching in a subgraph to compute the vertex separator. Results on the quality of the separators computed by the spectral algorithm are presented, and these are compared with separators obtained from other algorithms for computing separators. Finally, the time required to compute the Laplacian eigenvector is reported, and the accuracy with which the eigenvector must be computed to obtain good separators is considered. The spectral algorithm has the advantage that it can be implemented on a medium-size multiprocessor in a straightforward manner.

Pothen, Alex↗

DOE OSTI2020

Parallel algorithms for finding connected components using linear algebra

Finding connected components is one of the most widely used operations on a graph. Optimal serial algorithms for the problem have been known for half a century, and many competing parallel algorithms have been proposed over the last several decades under various different models of parallel computation. This paper presents a class of parallel connected-component algorithms designed using linear-algebraic primitives. These algorithms are based on a PRAM algorithm by Shiloach and Vishkin and can be designed using standard GraphBLAS operations. Here, we demonstrate two algorithms of this class, one named LACC for Linear Algebraic Connected Components, and the other named FastSV which can be regarded as LACC’s simplification. With the support of the highly-scalable Combinatorial BLAS library, LACC and FastSV outperform the previous state-of-the-art algorithm by a factor of up to 12x for small to medium scale graphs. For large graphs with more than 50B edges, LACC and FastSV scale to 4K nodes (262K cores) of a Cray XC40 supercomputer and outperform previous algorithms by a significant margin. This remarkable performance is accomplished by (1) exploiting sparsity that was not present in the original PRAM algorithm formulation, (2) using high-performance primitives of Combinatorial BLAS, and (3) identifying hot spots and optimizing them away by exploiting algorithmic insights.

97 MATHEMATICS AND COMPUTING↗