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 667 records · Page 37
All sourcesNASA NTRSDOE OSTI
DOE OSTI2021

Probabilistic simulation of quantum circuits using a deep-learning architecture

The fundamental question of how to best simulate quantum systems using conventional computational resources lies at the forefront of condensed matter and quantum computation. It impacts both our understanding of quantum materials and our ability to emulate quantum circuits. Here we present an exact formulation of quantum dynamics via factorized generalized measurements which maps quantum states to probability distributions with the advantage that local unitary dynamics and quantum channels map to local quasistochastic matrices. This representation provides a general framework for using state-of-the-art probabilistic models in machine learning for the simulation of quantum many-body dynamics. Using this framework, we have developed a practical algorithm to simulate quantum circuits using an attention network based on a powerful neural network ansatz responsible for the most recent breakthroughs in natural language processing. We demonstrate our approach by simulating circuits that build Greenberger-Horne-Zeilinger and linear graph states of up to 60 qubits, as well as a variational quantum eigensolver circuit for preparing the ground state of the transverse field Ising model on several system sizes. Our methodology constitutes a modern machine learning approach to the simulation of quantum physics with applicability both to quantum circuits as well as other quantum many-body systems.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2024

Assessing the Feasibility of Bordered Block Diagonal Reordering in Power System Matrices using Fully Convolutional Network

In electromagnetic transient (EMT) simulations for power systems and inverter-based resources (IBRs), the arrangement of states within the system's linear equations, represented by matrix A in Ax=b, is critical. The state ordering in matrix A can highlight distinct characteristics of the system's graph, and identifying an optimal state ordering is crucial for efficient computation. The choice of state ordering, however, is dependent on the solver used, as each solver may perform optimally with different matrix patterns. With a wide array of matrix reordering algorithms available, selecting the most suitable one becomes challenging without insights into the matrix's ideal configuration. To address this, the paper proposes a fully convolutional network (FCN) to evaluate the reordering potential of the A matrix into a bordered block diagonal (BBD) pattern, which is commonly observed in power system and IBR modeling. The FCN's assessment aims to streamline the solver's operation, which in turn could substantially reduce the computational time required to find a solution.

Xia, Qianxue↗
NASA NTRS1989

Generation of precedence relations for mechanical assemblies

Planning of assembly sequences is essential to the manufacturing system design process. Several methodologies have been proposed to represent all the feasible assembly sequences. In this thesis, three algorithms are presented to generate three sets of precedence relations based on all the infeasible assembly tasks, all the infeasible assembly states, and all the feasible assembly sequences, respectively. The equivalence of the resulting sets of precedence relations to the AND/OR graph is established. A new property, the real time property, of a representation of assembly sequences is defined and discussed. A representation of assembly sequences is said to have the real time property, if it is possible to generate the next assembly task by testing locally in the representation, and it will guarantee that the generated assembly task will not lead the assembly sequence to a dead end situation, in which no feasible assembly task can be performed any more. It is shown that the correctness and completeness of one representation can not guarantee the real time property of the representation. It is proven that the directed graph representation and the set of precedence relations based on all the infeasible assembly states have the real time property, while the AND/OR graph representation and the set of precedence relations based on all the infeasible assembly tasks do not have the real time property. Finally in the thesis, the PLEIDEAS system, a PLanning Environment for Integrated DEsign of Assembly Systems, is described and illustrated by an example.

Zhang, Hui↗
NASA NTRS2011

Telemetry and Science Data Software System

The Telemetry and Science Data Software System (TSDSS) was designed to validate the operational health of a spacecraft, ease test verification, assist in debugging system anomalies, and provide trending data and advanced science analysis. In doing so, the system parses, processes, and organizes raw data from the Aquarius instrument both on the ground and while in space. In addition, it provides a user-friendly telemetry viewer, and an instant pushbutton test report generator. Existing ground data systems can parse and provide simple data processing, but have limitations in advanced science analysis and instant report generation. The TSDSS functions as an offline data analysis system during I&T (integration and test) and mission operations phases. After raw data are downloaded from an instrument, TSDSS ingests the data files, parses, converts telemetry to engineering units, and applies advanced algorithms to produce science level 0, 1, and 2 data products. Meanwhile, it automatically schedules upload of the raw data to a remote server and archives all intermediate and final values in a MySQL database in time order. All data saved in the system can be straightforwardly retrieved, exported, and migrated. Using TSDSS s interactive data visualization tool, a user can conveniently choose any combination and mathematical computation of interesting telemetry points from a large range of time periods (life cycle of mission ground data and mission operations testing), and display a graphical and statistical view of the data. With this graphical user interface (GUI), the data queried graphs can be exported and saved in multiple formats. This GUI is especially useful in trending data analysis, debugging anomalies, and advanced data analysis. At the request of the user, mission-specific instrument performance assessment reports can be generated with a simple click of a button on the GUI. From instrument level to observatory level, the TSDSS has been operating supporting functional and performance tests and refining system calibration algorithms and coefficients, in sync with the Aquarius/SAC-D spacecraft. At the time of this reporting, it was prepared and set up to perform anomaly investigation for mission operations preceding the Aquarius/SAC-D spacecraft launch on June 10, 2011.

Bates, Lakesha↗
DOE OSTI2023

Inferring adversarial behaviour in cyber‐physical power systems using a Bayesian attack graph approach

Abstract Highly connected smart power systems are subject to increasing vulnerabilities and adversarial threats. Defenders need to proactively identify and defend new high‐risk access paths of cyber intruders that target grid resilience. However, cyber‐physical risk analysis and defense in power systems often requires making assumptions on adversary behaviour, and these assumptions can be wrong. Thus, this work examines the problem of inferring adversary behaviour in power systems to improve risk‐based defense and detection. To achieve this, a Bayesian approach for inference of the Cyber‐Adversarial Power System (Bayes‐CAPS) is proposed that uses Bayesian networks (BNs) to define and solve the inference problem of adversarial movement in the grid infrastructure towards targets of physical impact. Specifically, BNs are used to compute conditional probabilities to queries, such as the probability of observing an event given a set of alerts. Bayes‐CAPS builds initial Bayesian attack graphs for realistic power system cyber‐physical models. These models are adaptable using collected data from the system under study. Then, Bayes‐CAPS computes the posterior probabilities of the occurrence of a security breach event in power systems. Experiments are conducted that evaluate algorithms based on time complexity, accuracy and impact of evidence for different scales and densities of network. The performance is evaluated and compared for five realistic cyber‐physical power system models of increasing size and complexities ranging from 8 to 300 substations based on computation and accuracy impacts.

Sahu, Abhijeet↗
DOE OSTI2021

Multiscale characterization and representation of variability in ceramic matrix composites

Low density, high strength, and high creep and oxidation resistance properties of ceramic matrix composites (CMCs) make them an ideal choice for use in extreme environments in space and military applications. This paper presents a detailed characterization study of structural and manufacturing flaws in Carbon fiber Silicon-Carbide-Nitride matrix (C/SiNC) CMCs at different length-scales. Energy-dispersive spectroscopy (EDS) is used for the chemical characterization of the material’s elemental constituents. High-resolution multiscale graphs obtained from scanning electron microscope (SEM) and confocal laser scanning microscope (LSM) are used to characterize the distribution and morphology of defects at different length scales. This is followed by the classification and quantification of the common manufacturing defects. An image processing algorithm based on the image segmentation process is developed to quantify the variability of various scale-dependent architectural parameters. Finally, a three-dimensional stochastic representative volume element (SRVE) generation algorithm is developed to provide precise representations of material textures at multiple length scales. The developed algorithm accurately accounts for material features and flaws based on a range of multiscale structural and defects characterization results.

36 MATERIALS SCIENCE↗
NASA NTRS1986

On the structure of parallelism in a highly concurrent PDE solver

A parallel multigrid algorithm for solving elliptic partial differential equations is developed and evaluated. A V-cycle multigrid method is altered to increase the degree of parallelism. A numerical analysis of the resulting concurrent-iteration multigrid algorithm is performed; its architectural implications are considered; highly parallel systems without shared memory are examined (including mesh-connected arrays, mesh-shuffle-connected systems, permutation networks, and direct VLSI embeddings); and the results of numerical experiments are presented in tables and graphs.

Gannon, D.↗
NASA NTRS2017

The Quantum Approximation Optimization Algorithm for MaxCut: A Fermionic View

Farhi et al. recently proposed a class of quantum algorithms, the Quantum Approximate Optimization Algorithm (QAOA), for approximately solving combinatorial optimization problems. A level-p QAOA circuit consists of steps in which a classical Hamiltonian, derived from the cost function, is applied followed by a mixing Hamiltonian. The 2p times for which these two Hamiltonians are applied are the parameters of the algorithm. As p increases, however, the parameter search space grows quickly. The success of the QAOA approach will depend, in part, on finding effective parameter-setting strategies. Here, we analytically and numerically study parameter setting for QAOA applied to MAXCUT. For level-1 QAOA, we derive an analytical expression for a general graph. In principle, expressions for higher p could be derived, but the number of terms quickly becomes prohibitive. For a special case of MAXCUT, the Ring of Disagrees, or the 1D antiferromagnetic ring, we provide an analysis for arbitrarily high level. Using a Fermionic representation, the evolution of the system under QAOA translates into quantum optimal control of an ensemble of independent spins. This treatment enables us to obtain analytical expressions for the performance of QAOA for any p. It also greatly simplifies numerical search for the optimal values of the parameters. By exploring symmetries, we identify a lower-dimensional sub-manifold of interest; the search effort can be accordingly reduced. This analysis also explains an observed symmetry in the optimal parameter values. Further, we numerically investigate the parameter landscape and show that it is a simple one in the sense of having no local optima.

quantum algorithm↗
DOE OSTI2020

Optimal D-FACTS Placement in Moving Target Defense Against False Data Injection Attacks

Moving target defense (MTD) is a defense strategy to detect stealthy false data injection (FDI) attacks against the power system state estimation using distributed flexible AC transmission system (D-FACTS) devices. However, existing studies neglect to address a fundamental yet critical issue, i.e., the D-FACTS placement, by assuming that all lines are equipped with D-FACTS devices. Here, to tackle this problem, we first derive analytical necessary conditions and requirements on the D-FACTS placement for a complete MTD. Further, we propose sufficient conditions using a graph theory-based topology analysis to ensure that the MTD under the proposed D-FACTS placement has the maximum rank of its composite matrix, which is indicative of the MTD effectiveness. Based on the analytical conditions, we design D-FACTS placement algorithms by using the minimum number of D-FACTS devices to achieve the maximum MTD effectiveness. A novel MTD-based ACOPF model, in which the reactance of D-FACTS lines is introduced as decision variables, is proposed to find a trade-off between the system loss and the MTD effectiveness. Numerical results on 6-bus, IEEE 14-bus, and IEEE 118-bus systems show the efficacy of MTDs using the proposed D-FACTS placement algorithms in maximizing the composite matrix rank and detecting FDI attacks.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2020

Compare linear-system solver and preconditioner stacks with emphasis on GPU performance and propose phase-2 NGP solver development pathway

The goal of the ExaWind project is to enable predictive simulations of wind farms comprised of many megawatt-scale turbines situated in complex terrain. Predictive simulations will require computational fluid dynamics (CFD) simulations for which the mesh resolves the geometry of the turbines and captures the rotation and large deflections of blades. Whereas such simulations for a single turbine are arguably petascale class, multi-turbine wind farm simulations will require exascale-class resources. The primary physics codes in the ExaWind project are Nalu-Wind, which is an unstructured-grid solver for the acoustically incompressible Navier-Stokes equations, and OpenFAST, which is a whole-turbine simulation code. The Nalu-Wind model consists of the mass-continuity Poisson-type equation for pressure and a momentum equation for the velocity. For such modeling approaches, simulation times are dominated by linear-system setup and solution for the continuity and momentum systems. For the ExaWind challenge problem, the moving meshes greatly affect overall solver costs as reinitialization of matrices and recomputation of preconditioners is required at every time step. In this report we evaluated GPU-performance baselines for the linear solvers in the Trilinos and hypre solver stacks using two representative Nalu-Wind simulations: an atmospheric boundary layer precursor simulation on a structured mesh, and a fixed-wing simulation using unstructured overset meshes. Both strong-scaling and weak-scaling experiments were conducted on the OLCF supercomputer Summit and similar proxy clusters. We focused on the performance of multi-threaded Gauss-Seidel and two-stage Gauss-Seidel that are extensions of classical Gauss-Seidel; of one-reduce GMRES, a communication-reducing variant of the Krylov GMRES; and algebraic multigrid methods that incorporate the afore-mentioned methods. The team has established that AMG methods are capable of solving linear systems arising from the fixed-wing overset meshes on CPU, a critical intermediate result for ExaWind FY20 Q3 and Q4 milestones. For the fixed-wing strong-scaling study (model with 3M grid-points), the team identified that Nalu-Wind simulations with the new Trilinos and hypre solvers scale to modest GPU counts, maintaining above 70% efficiency up to 6 GPUs. However, there still remain significant bottlenecks to performance: matrix assembly (hypre), AMG setup (hypre and Trilinos) In the weak-scaling experiments (going from 0.4M to 211M gridpoints), it's shown that the solver apply phases are faster on GPUs, but that Nalu-Wind simulation times grow, primarily due to the multigrid-setup process. Finally, based on the report outcomes, we propose a linear solver path-forward for the remainder of the ExaWind project. Near term, the NREL team will continue their work on GPU-based linear-system assembly. They will also investigate how the use of alternatives to the NVIDIA UVM (unified virtual memory) paradigm affects performance. Longer term, the NREL team will evaluate algorithmic performance on other types of accelerators and merge their improvements back to the main hypre repository branch. Near term, the Trilinos team will address performance bottlenecks identified in this milestone, such as implementing a GPU-based segregated momentum solve and reusing matrix graphs across linear-system assembly phases. Longer term, the Trilinos team will do detailed analysis and optimization of multigrid setup.

17 WIND ENERGY↗
DOE OSTI2025

Enabling Efficient Sparse Computations using Linear Algebra Aware Compilers

This project developed the LAPIS compiler framework, built on the Multilevel Intermediate Representation (MLIR), to optimize sparse linear algebra operations and support performance portability across diverse architectures. The main innovation of LAPIS is the Kokkos dialect, which allows for lowering codes from a high productivity language to different architectures in an elegant way. The dialect also allows the conversion of lower-level MLIR code to C++ Kokkos code, facilitating the integration of scientific machine learning (SciML) models into applications. To extend LAPIS for distributed memory architectures, a new partition dialect was created to manage the distribution of sparse tensors and express communication patterns for sparse linear algebra operations. This dialect also supports the distributed execution of operators and includes algorithmic optimizations to minimize communication to improve performance. The project also demonstrates that MLIR can enable effective linear algebra-level optimizations, improving performance on different GPUs for both sparse and dense linear algebra kernels. Key applications of LAPIS include sparse linear algebra and graph kernels, TenSQL, a relational database management solution built on GraphBLAS, and the development of subgraph isomorphism and monomorphism kernels, showcasing performance portability. In summary, the LAPIS framework supports productivity, performance, portability, and distributed memory execution, while also enabling linear algebra-level optimizations that are challenging in traditional programming languages, with successful applications ranging from simple sparse linear algebra to complex graph kernels.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

DOME: Directional medical embedding vectors from Electronic Health Records

Motivation: The increasing availability of Electronic Health Record (EHR) systems has created enormous potential for translational research. Recent developments in representation learning techniques have led to effective large-scale representations of EHR concepts along with knowledge graphs that empower downstream EHR studies. However, most existing methods require training with patient-level data, limiting their abilities to expand the training with multi-institutional EHR data. On the other hand, scalable approaches that only require summary-level data do not incorporate temporal dependencies between concepts. Methods: We introduce a DirectiOnal Medical Embedding (DOME) algorithm to encode temporally directional relationships between medical concepts, using summary-level EHR data. Specifically, DOME first aggregates patient-level EHR data into an asymmetric co-occurrence matrix. Then it computes two Positive Pointwise Mutual Information (PPMI) matrices to correspondingly encode the pairwise prior and posterior dependencies between medical concepts. Following that, a joint matrix factorization is performed on the two PPMI matrices, which results in three vectors for each concept: a semantic embedding and two directional context embeddings. They collectively provide a comprehensive depiction of the temporal relationship between EHR concepts. Results: We highlight the advantages and translational potential of DOME through three sets of validation studies. First, DOME consistently improves existing direction-agnostic embedding vectors for disease risk prediction in several diseases, for example achieving a relative gain of 5.5% in the area under the receiver operating characteristic (AUROC) for lung cancer. Second, DOME excels in directional drug-disease relationship inference by successfully differentiating between drug side effects and indications, correspondingly achieving relative AUROC gain over the state-of-the-art methods by 10.8% and 6.6%. Finally, DOME effectively constructs directional knowledge graphs, which distinguish disease risk factors from comorbidities, thereby revealing disease progression trajectories. The source codes are provided at https://github.com/celehs/Directional-EHRembedding.

60 APPLIED LIFE SCIENCES↗
DOE OSTI2024

Retrieving Top-k Hyperedge Triplets: Models and Applications

Complex systems frequently exhibit multi-way, rather than pairwise, interactions. These group interactions can- not be faithfully modeled as collections of pairwise interactions using graphs and instead require hypergraphs. However, methods that analyze hypergraphs directly, rather than via lossy graph reductions, remain limited. Hypergraph motifs hold promise in this regard, as motif patterns serve as building blocks for larger group interactions which are inexpressible by graphs. Recent work has focused on categorizing and counting hypergraph motifs based on the existence of nodes in hyperedge intersection regions. Here, we argue that the relative sizes of hyperedge inter- sections within motifs contain varied and valuable information. We propose a suite of efficient algorithms for finding top-k triplets of hyperedges based on optimizing the sizes of these intersection patterns. This formulation uncovers interesting local patterns of interaction, finding hyperedge triplets that either (1) are the least similar with each other, (2) have the highest pairwise but not groupwise correlation, or (3) are the most similar with each other. We formalize this as a combinatorial optimization problem and design efficient algorithms based on filtering hyperedges. Our comprehensive experimental evaluation shows that the resulting hyperedge triplets yield insightful information on real-world hypergraphs. Our approach is also orders of magnitude faster than a naive baseline implementation.

hypergraphs, motifs, Combinatorial Algorithms↗
NASA NTRS2013

Contact Graph Routing Enhancements Developed in ION for DTN

The Interplanetary Overlay Network (ION) software suite is an open-source, flight-ready implementation of networking protocols including the Delay/Disruption Tolerant Networking (DTN) Bundle Protocol (BP), the CCSDS (Consultative Committee for Space Data Systems) File Delivery Protocol (CFDP), and many others including the Contact Graph Routing (CGR) DTN routing system. While DTN offers the capability to tolerate disruption and long signal propagation delays in transmission, without an appropriate routing protocol, no data can be delivered. CGR was built for space exploration networks with scheduled communication opportunities (typically based on trajectories and orbits), represented as a contact graph. Since CGR uses knowledge of future connectivity, the contact graph can grow rather large, and so efficient processing is desired. These enhancements allow CGR to scale to predicted NASA space network complexities and beyond. This software improves upon CGR by adopting an earliest-arrival-time cost metric and using the Dijkstra path selection algorithm. Moving to Dijkstra path selection also enables construction of an earliest- arrival-time tree for multicast routing. The enhancements have been rolled into ION 3.0 available on sourceforge.net.

Segui, John S.↗
NASA NTRS2017

QSPIN: A High Level Java API for Quantum Computing Experimentation

QSPIN is a high level Java language API for experimentation in QC models used in the calculation of Ising spin glass ground states and related quadratic unconstrained binary optimization (QUBO) problems. The Java API is intended to facilitate research in advanced QC algorithms such as hybrid quantum-classical solvers, automatic selection of constraint and optimization parameters, and techniques for the correction and mitigation of model and solution errors. QSPIN includes high level solver objects tailored to the D-Wave quantum annealing architecture that implement hybrid quantum-classical algorithms [Booth et al.] for solving large problems on small quantum devices, elimination of variables via roof duality, and classical computing optimization methods such as GPU accelerated simulated annealing and tabu search for comparison. A test suite of documented NP-complete applications ranging from graph coloring, covering, and partitioning to integer programming and scheduling are provided to demonstrate current capabilities.

Quantu↗
NASA NTRSDate not supplied

Biological Research and Space Health Enabled by Machine Learning to Support Deep Space Missions

A key science goal of the NASA “Moon to Mars” campaign is to understand how biology responds to the Lunar, Martian, and deep space environments in order to advance fundamental knowledge and support human space missions. Through artificial intelligence (AI) and machine learning (ML), a paradigm shift has begun in space biosciences and engineered astronaut health systems, to enable Earth-independence and mission operations autonomy. We describe current AI/ML methods to support 1) fundamental biology, 2) in situ analytics, 3) high performance computing, 4) automated science, 5) self-driving labs, 6) remote data management, 7) integrated mission biomonitoring, and 8) a Precision Space Health system. AI/ML approaches that can be integrated to support these domains include active learning, explainable AI, adaptive learning, causal inference, knowledge graphs, federated learning, transfer learning, and large language models. Finally, we present results from several current ML projects that are underway in the space biology field to address key challenges of small sample n, high feature count, heterogeneity, and sparse data. These include 1) connecting omics to phenotypic data using an ensemble model to infer causality of rodent liver health disruption, 2) usage of explainable ML to interrogate muscular underpinnings of muscle atrophy, 3) ML models analyzing and determining directed acyclic graphs of human health risk leveraging rodent bone datasets, 4) usage of large pre-trained models connecting biomedical knowledgebases with small spaceflight datasets to understand gene-to-gene interactions, and 5) a suite of benchmarked open science datasets enabling programmers to identify best algorithms to answer space biology questions.

space biology↗
DOE OSTI2020

Automated Adversary Emulation for Cyber-Physical Systems via Reinforcement Learning

Adversary emulation is an offensive exercise that provides a comprehensive assessment of a system’s resilience against cyber attacks. However, adversary emulation is typically a manual process, making it costly and hard to deploy in cyber-physical systems (CPS) with complex dynamics, vulnerabilities, and operational uncertainties. In this paper, we develop an automated, domain-aware approach to adversary emulation for CPS. We formulate a Markov Decision Process (MDP) model to determine an optimal attack sequence over a hybrid attack graph with cyber (discrete) and physical (continuous) components and related physical dynamics. We apply model-based and model-free reinforcement learning (RL) methods to solve the discrete-continuous MDP in a tractable fashion. As a baseline, we also develop a greedy attack algorithm and compare it with the RL procedures. We summarize our findings through a numerical study on sensor deception attacks in buildings to compare the performance and solution quality of the proposed algorithms.

Bhattacharya, Arnab↗
DOE OSTI2022

Skew-Symmetric adjacency matrices for clustering directed graphs

Graph clustering methods often critically rely on the symmetry of graph matrices. Developing analogous methods for digraphs often proves more challenging, because digraph matrices are typically asymmetric and not orthogonally diagonalizable. However, researchers have recently proposed several complex-valued Hermitian digraph matrices. In particular, one such representation has been utilized as an input to an algorithm for finding imbalanced cuts. In this work, we establish an algebraic relationship between this matrix and an associated real-valued matrix. We show using this real-valued matrix for imbalanced cut-finding algorithms is not only sufficient but advantageous. Our algorithm uses less memory and asymptotically less computation while provably preserving solution quality. We also show our method can be easily implemented using standing computational building blocks, possesses better numerical properties, and loans itself to a natural interpretation via an objective function relaxation argument. We empirically demonstrate these advantages on real world data sets and show how our algorithm can uncover meaningful cluster structure.

Hayashi, Koby↗