Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Graph algorithms”

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 505 records · Page 28
All sourcesNASA NTRSDOE OSTI
DOE OSTI2024

Artificial Intelligence/Machine Learning Technology in Power System Applications

The primary purpose of this report is to provide an overview of the advancement in artificial intelligence and machine learning (AI/ML) technologies and their applications in power systems. It offers a foundation for understanding the transformative role of AI/ML in power systems and aims to stimulate further research and development in this area. This report begins with a historical perspective of AI/ML technologies, then explores their advancement to today’s prominence. The document highlights key contributors to the success of AI/ML technologies, including increased computational power, greater data availability, innovative algorithms, and advanced tools. It further introduces various AI/ML techniques, including supervised, unsupervised and reinforcement learning, graph neural networks, and generative AI. It also emphasizes the critical importance of ensuring the safety, security, and trustworthiness of these AI/ML techniques within this sector. The report reviews the recent representative advancements in various power system applications enhanced by AI/ML techniques, underscoring key developments and their transformative impact as evidenced by numerous studies. It also explores both the opportunities and challenges associated with the application of AI/ML technologies to improve power system applications. While the report extensively covers AI/ML applications in power systems, focusing primarily on the technical and operational aspects, it may not thoroughly explore the sociopolitical, economic, and broader regulatory implications of AI/ML integration in power systems. AI/ML techniques hold significant potential for enhancing power system applications; however, they are not omnipotent. It is crucial to acknowledge their limitations and understand that they may not be able to address all challenges in the power system domain. Various factors must be considered that influence the implementation, adoption, and effectiveness of AI/ML solutions, including but not limited to safety, security, transparency, and trustworthiness. Additionally, the incorporation of advanced human–machine interfaces is essential, as it enables humans to validate the effectiveness of AI/ML solutions while remaining actively engaged, fostering trust in AI/ML deployment. Finally, the report summarizes AI/ML research activities supported by the Department of Energy (DOE) Office of Electricity (OE) through the Advanced Grid Modeling (AGM) program. The work aligns with the interests and mission of DOE-OE AGM, with the report serving as a resource for identifying existing progress and for pinpointing future applications within AI/ML that need further exploration and support.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2023

Seven open problems in applied combinatorics

We present and discuss seven different open problems in applied combinatorics. Additionally, the application areas relevant to this compilation include quantum computing, algorithmic differentiation, topological data analysis, iterative methods, hypergraph cut algorithms, and power systems.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1987

Automated problem scheduling and reduction of synchronization delay effects

It is anticipated that in order to make effective use of many future high performance architectures, programs will have to exhibit at least a medium grained parallelism. A framework is presented for partitioning very sparse triangular systems of linear equations that is designed to produce favorable preformance results in a wide variety of parallel architectures. Efficient methods for solving these systems are of interest because: (1) they provide a useful model problem for use in exploring heuristics for the aggregation, mapping and scheduling of relatively fine grained computations whose data dependencies are specified by directed acrylic graphs, and (2) because such efficient methods can find direct application in the development of parallel algorithms for scientific computation. Simple expressions are derived that describe how to schedule computational work with varying degrees of granularity. The Encore Multimax was used as a hardware simulator to investigate the performance effects of using the partitioning techniques presented in shared memory architectures with varying relative synchronization costs.

Saltz, Joel H.↗
NASA NTRS1989

A family of permutations for concurrent factorization of block tridiagonal matrices

The inherent strong seriality of closely coupled systems is circumvented by defining a family of permutations for reordering equation sets whose matrix of coefficients is Hermitian block tridiagonal. The authors show how these permutations can be used to achieve relatively high concurrency in the Cholesky factorization of banded systems at the expense of introducing limited extra computations due to fill-in terms in the factors. Directed graphs are developed for the concurrent factorization of the transformed matrix of coefficients by the Cholesky algorithm. Expressions for speedup and efficiency are derived in terms of parameters of the permutation, set of equations, and machine architecture.

Utku, Senol↗
NASA NTRS2002

An Efficient Scheme for Updating Sparse Cholesky Factors

Raghavan had earlier developed the software package DCSPACK which can be used for solving sparse linear systems where the coefficient matrix is symmetric and positive definite (this project was not funded by NASA but by agencies such as NSF). DSCPACK-S is the serial code and DSCPACK-P is a parallel implementation suitable for multiprocessors or networks-of-workstations with message passing using MCI. The main algorithm used is the Cholesky factorization of a sparse symmetric positive positive definite matrix A = LL(T). The code can also compute the factorization A = LDL(T). The complexity of the software arises from several factors relating to the sparsity of the matrix A. A sparse N x N matrix A has typically less that cN nonzeroes where c is a small constant. If the matrix were dense, it would have O(N2) nonzeroes. The most complicated part of such sparse Cholesky factorization relates to fill-in, i.e., zeroes in the original matrix that become nonzeroes in the factor L. An efficient implementation depends to a large extent on complex data structures and on techniques from graph theory to reduce, identify, and manage fill. DSCPACK is based on an efficient multifrontal implementation with fill-managing algorithms and implementation arising from earlier research by Raghavan and others. Sparse Cholesky factorization is typically a four step process: (1) ordering to compute a fill-reducing numbering, (2) symbolic factorization to determine the nonzero structure of L, (3) numeric factorization to compute L, and, (4) triangular solution to solve L(T)x = y and Ly = b. The first two steps are symbolic and are performed using the graph of the matrix. The numeric factorization step is of dominant cost and there are several schemes for improving performance by exploiting the nested and dense structure of groups of columns in the factor. The latter are aimed at better utilization of the cache-memory hierarchy on modem processors to prevent cache-misses and provide execution rates (operations/second) that are close to the peak rates for dense matrix computations. Currently, EPISCOPACY is being used in an application at NASA directed by J. Newman and M. James. We propose the implementation of efficient schemes for updating the LL(T) or LDL(T) factors computed in DSCPACK-S to meet the computational requirements of their project. A brief description is provided in the next section.

Raghavan, Padma↗
DOE OSTI2023

Molecular Hypernetworks for Exploration of Multi-Dimensional Metabolomics Data (Chyper)

Orthogonal separations of data from high-resolution mass spectrometry can provide insight into sample composition and help address the challenge of complete annotation of molecules in untargeted metabolomics. “Molecular networks” (MNs), as used, for example, in the Global Natural Products Social Molecular Networking platform, are an increasingly popular computational strategy for exploring and visualizing molecular relationships and improving annotation. MNs use graph representations to show the relationships between measured multidimensional data features. MNs also show promise for using network science algorithms to automatically identify targets for annotation candidates and to dereplicate features associated to a single molecular identity. However, more advanced methods may better represent the complexity present in samples. Our work aims to increase confidence in annotation propagation by extending molecular network methods to include “molecular hypernetworks” (MHNs), able to natively represent multiway relationships among observations supporting both human and analytical processing. In this paper we first introduce MHNs illustrated with simple examples, and demonstrate how to build them from liquid chromatography- and ion mobility spectrometry- separated MS data. We then describe a method to construct MHNs directly from existing MNs as their “clique reconstructions”, demonstrating their utility by comparing examples of previously published graph-based MNs to their respective MHNs.

59 BASIC BIOLOGICAL SCIENCES↗
DOE OSTI2024

Improved particle-flow event reconstruction with scalable neural networks for current and future particle detectors

Abstract Efficient and accurate algorithms are necessary to reconstruct particles in the highly granular detectors anticipated at the High-Luminosity Large Hadron Collider and the Future Circular Collider. We study scalable machine learning models for event reconstruction in electron-positron collisions based on a full detector simulation. Particle-flow reconstruction can be formulated as a supervised learning task using tracks and calorimeter clusters. We compare a graph neural network and kernel-based transformer and demonstrate that we can avoid quadratic operations while achieving realistic reconstruction. We show that hyperparameter tuning significantly improves the performance of the models. The best graph neural network model shows improvement in the jet transverse momentum resolution by up to 50% compared to the rule-based algorithm. The resulting model is portable across Nvidia, AMD and Habana hardware. Accurate and fast machine-learning based reconstruction can significantly improve future measurements at colliders.

Physics↗
NASA NTRS1987

Computer architecture for efficient algorithmic executions in real-time systems: New technology for avionics systems and advanced space vehicles

Improvements and advances in the development of computer architecture now provide innovative technology for the recasting of traditional sequential solutions into high-performance, low-cost, parallel system to increase system performance. Research conducted in development of specialized computer architecture for the algorithmic execution of an avionics system, guidance and control problem in real time is described. A comprehensive treatment of both the hardware and software structures of a customized computer which performs real-time computation of guidance commands with updated estimates of target motion and time-to-go is presented. An optimal, real-time allocation algorithm was developed which maps the algorithmic tasks onto the processing elements. This allocation is based on the critical path analysis. The final stage is the design and development of the hardware structures suitable for the efficient execution of the allocated task graph. The processing element is designed for rapid execution of the allocated tasks. Fault tolerance is a key feature of the overall architecture. Parallel numerical integration techniques, tasks definitions, and allocation algorithms are discussed. The parallel implementation is analytically verified and the experimental results are presented. The design of the data-driven computer architecture, customized for the execution of the particular algorithm, is discussed.

Carroll, Chester C.↗
DOE OSTI2023

Trigger Detection for the sPHENIX Experiment via Bipartite Graph Networks with Set Transformer

Trigger (interesting events) detection is crucial to high-energy and nuclear physics experiments because it improves data acquisition efficiency. It also plays a vital role in facilitating the downstream offline data analysis process. The sPHENIX detector, located at the Relativistic Heavy Ion Collider in Brookhaven National Laboratory, is one of the largest nuclear physics experiments on a world scale and is optimized to detect physics processes involving charm and beauty quarks. Furthermore, these particles are produced in collisions involving two proton beams, two gold nuclei beams, or a combination of the two and give critical insights into the formation of the early universe. This paper presents a model architecture for trigger detection with geometric information from two fast silicon detectors. Transverse momentum is introduced as an intermediate feature from physics heuristics. We also prove its importance through our training experiments. Each event consists of tracks and can be viewed as a graph. A bipartite graph neural network is integrated with the attention mechanism to design a binary classification model. Compared with the state-of-the-art algorithm for trigger detection, our model is parsimonious and increases the accuracy and the AUC score by more than 15%.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Using graph neural networks to reconstruct charged pion showers in the CMS High Granularity Calorimeter

A novel method to reconstruct the energy of hadronic showersin the CMS High Granularity Calorimeter (HGCAL) is presented. TheHGCAL is a sampling calorimeter with very fine transverse andlongitudinal granularity. The active media are silicon sensors andscintillator tiles readout by SiPMs and the absorbers are acombination of lead and Cu/CuW in the electromagnetic section, andsteel in the hadronic section. The shower reconstruction method isbased on graph neural networks and it makes use of a dynamicreduction network architecture. It is shown that the algorithm isable to capture and mitigate the main effects that normally hinderthe reconstruction of hadronic showers using classicalreconstruction methods, by compensating for fluctuations in themultiplicity, energy, and spatial distributions of the shower'sconstituents. The performance of the algorithm is evaluated usingtest beam data collected in 2018 prototype of the CMS HGCALaccompanied by a section of the CALICE AHCAL prototype. Thecapability of the method to mitigate the impact of energy leakagefrom the calorimeter is also demonstrated.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗
DOE OSTI2021

Network Based Estimation of Wind Farm Power and Velocity Data Under Changing Wind Direction

This paper describes an estimation algorithm for velocity and power output signals in a wind farm under changing wind direction. A graph-theoretic definition describes the wind farm as a collection of nodes (turbines) and time-varying weighted edges (inter-turbine wake propagation) that change as a function of incoming wind direction. The velocity at each turbine is determined through a discrete input-output model. Changes in wind direction serve as the input and the output is defined in terms of a time-varying weighted adjacency matrix that depends on the time-delay of information propagation between turbines. These delays, which are defined in terms of the advection speed of the wind and the distance between the turbines, capture the delayed effect of wind direction changes on the inter-connectivity of the graph as the wind conditions at the farm inlet propagate through the turbine array. An event-based update framework is employed to capture time-dependent topology changes due to shifts in wind direction. Simulation results for dynamically changing wind inlet directions to a circular wind farm are compared to predictions from both the static and dynamic versions of the FLOw Redirection and Induction in Steady State (FLORIS) model. The approach is shown to enable real-time tracking of dynamic changes to wind farm power output within a framework that can be easily integrated into real-time, horizon-based, control strategies that typically do not account for wind direction changes.

distributed↗
NASA NTRS1991

Enhanced ATAMM for increased throughput performance of multicomputer data flow architectures

The Algorithm To Architecture Mapping Model (ATAMM) is a Petri-net-based model which provides a strategy for periodic execution of a class of real-time algorithms on multicomputer dataflow architectures. The problem domain of particular interest is the execution of large-grained, decision-free algorithms on homogeneous processing elements. Design techniques are discussed and performance measurements are defined. A multiple-graph execution strategy is shown to increase throughput performance. It is shown that the same increase in performance is attainable with minor modifications to the existing ATAMM.

Jones, R. L.↗
NASA NTRS2002

The CORSAIR Turbomachinery Code: Status and Plans

This viewgraph presentation gives an overview of the CORSAIR turbomachinery code's status and plans. Details are provided on the CORSAIR algorithms, full- and partial-admission turbine simulations, the Simplex turbine, instantaneous Mach number, unsteady pressure admission graphs, variable fluid property RLV-133 simulations, instantaneous entropy function, pumps and inducers, and future plans.

Dorney, Daniel J.↗
DOE OSTI2023

CEGANN: CRYSTAL EDGE GRAPH ATTENTION NEURAL NETWORK

SF-22-156 Machine learning (ML) models and applications in materials design and discovery typically involve the use of feature representations or descriptors followed by a learning algorithm that maps them to user desired properties of interest. Most popular mathematical formulation-based descriptors are not unique across atomic environments and suffer from transferability issues across different application domains and/or material classes. The CEGANN code provides a unified interface to facilitate material characterization across materials across multiple scales (from atomic to mesoscale) and diverse classes of materials ranging from metals oxides, non-metals, and even hierarchical materials such as zeolites and semi ordered materials such as mesophases. CEGANN implements a Graph Attention Network (GAT) type convolution architecture. The details of network architecture can be found in the paper https://doi.org/10.48550/arXiv.2207.10168. The software comes with pretrained examples and dataset for the classification of the following representative systems: (1) Structure-level representation such as space group (2) Structural dimensionality (e.g., bulk, 2D, clusters etc.) (3) Grain boundary identification (4) Nucleation and growth of a zeolite polymorph (5) Characterization of binary mesophases and their phase transitions (6) Growth of ice. The code is written in python programming language.

CHAN, HENRYT↗
DOE OSTI2024

Distribution of centrality measures on undirected random networks via the cavity method

The Katz centrality of a node in a complex network is a measure of the node’s importance as far as the flow of information across the network is concerned. For ensembles of locally tree-like undirected random graphs, this observable is a random variable. Its full probability distribution is of interest but difficult to handle analytically because of its “global” character and its definition in terms of a matrix inverse. Leveraging a fast Gaussian Belief Propagation-Cavity algorithm to solve linear systems on tree-like structures, we show that i) the Katz centrality of a single instance can be computed recursively in a very fast way, and ii) the probability P ( K ) that a random node in the ensemble of undirected random graphs has centrality K satisfies a set of recursive distributional equations, which can be analytically characterized and efficiently solved using a population dynamics algorithm. We test our solution on ensembles of Erdős-Rényi and Scale Free networks in the locally tree-like regime, with excellent agreement. The analytical distribution of centrality for the configuration model conditioned on the degree of each node can be employed as a benchmark to identify nodes of empirical networks with over- and underexpressed centrality relative to a null baseline. We also provide an approximate formula based on a rank- 1 projection that works well if the network is not too sparse, and we argue that an extension of our method could be efficiently extended to tackle analytical distributions of other centrality measures such as PageRank for directed networks in a transparent and user-friendly way.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2020

Scalable Knowledge Graph Analytics at 136 Petaflop/s

We are motivated by newly proposed methods for data mining large-scale corpora of scholarly publications, such as the full biomedical literature, which may consist of tens of millions of papers spanning decades of research. In this setting, analysts seek to discover how concepts relate to one another. They construct graph representations from annotated text databases and then formulate the relationship-mining problem as one of computing all-pairs shortest paths (APSP), which becomes a significant bottleneck. In this context, we present a new high-performance algorithm and implementation of the Floyd-Warshall algorithm for distributed-memory parallel computers accelerated by GPUs, which we call DSNAPSHOT (Distributed Accelerated Semiring All-Pairs Shortest Path). For our largest experiments, we ran DSNAPSHOT on a connected input graph with millions of vertices using 4, 096nodes (24,576GPUs) of the Oak Ridge National Laboratory's Summit supercomputer system. We find DSNAPSHOT achieves a sustained performance of 136×1015 floating-point operations per second (136petaflop/s) at a parallel efficiency of 90% under weak scaling and, in absolute speed, 70% of the best possible performance given our computation (in the single-precision tropical semiring or “min-plus” algebra). Looking forward, we believe this novel capability will enable the mining of scholarly knowledge corpora when embedded and integrated into artificial intelligence-driven natural language processing workflows at scale.

Kannan, Ramakrishnan {ramki}↗
NASA NTRS2002

Distributed topology control algorithm for multihop wireless netoworks

We present a network initialization algorithmfor wireless networks with distributed intelligence. Each node (agent) has only local, incomplete knowledge and it must make local decisions to meet a predefined global objective. Our objective is to use power control to establish a topology based onthe relative neighborhood graph which has good overall performance in terms of power usage, low interference, and reliability.

topology control distributed algorithm wireless ne↗