Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “GRAPH THEORY”

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 109 records · Page 6
All sourcesNASA NTRSDOE OSTI
NASA NTRS2004

Network Theory: A Primer and Questions for Air Transportation Systems Applications

A new understanding (with potential applications to air transportation systems) has emerged in the past five years in the scientific field of networks. This development emerges in large part because we now have a new laboratory for developing theories about complex networks: The Internet. The premise of this new understanding is that most complex networks of interest, both of nature and of human contrivance, exhibit a fundamentally different behavior than thought for over two hundred years under classical graph theory. Classical theory held that networks exhibited random behavior, characterized by normal, (e.g., Gaussian or Poisson) degree distributions of the connectivity between nodes by links. The new understanding turns this idea on its head: networks of interest exhibit scale-free (or small world) degree distributions of connectivity, characterized by power law distributions. The implications of scale-free behavior for air transportation systems include the potential that some behaviors of complex system architectures might be analyzed through relatively simple approximations of local elements of the system. For air transportation applications, this presentation proposes a framework for constructing topologies (architectures) that represent the relationships between mobility, flight operations, aircraft requirements, and airspace capacity, and the related externalities in airspace procedures and architectures. The proposed architectures or topologies may serve as a framework for posing comparative and combinative analyses of performance, cost, security, environmental, and related metrics.

Holmes, Bruce J.↗
DOE OSTI2024

Beyond nothingness in the formation and functional relevance of voids in polymer films

Abstract Voids—the nothingness—broadly exist within nanomaterials and impact properties ranging from catalysis to mechanical response. However, understanding nanovoids is challenging due to lack of imaging methods with the needed penetration depth and spatial resolution. Here, we integrate electron tomography, morphometry, graph theory and coarse-grained molecular dynamics simulation to study the formation of interconnected nanovoids in polymer films and their impacts on permeance and nanomechanical behaviour. Using polyamide membranes for molecular separation as a representative system, three-dimensional electron tomography at nanometre resolution reveals nanovoid formation from coalescence of oligomers, supported by coarse-grained molecular dynamics simulations. Void analysis provides otherwise inaccessible inputs for accurate fittings of methanol permeance for polyamide membranes. Three-dimensional structural graphs accounting for the tortuous nanovoids within, measure higher apparent moduli with polyamide membranes of higher graph rigidity. Our study elucidates the significance of nanovoids beyond the nothingness, impacting the synthesis‒morphology‒function relationships of complex nanomaterials.

36 MATERIALS SCIENCE↗
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 OSTI2024

A General Materials Data Science Framework for Quantitative 2D Analysis of Particle Growth from Image Sequences

Abstract Phase transformations are a challenging problem in materials science, which lead to changes in properties and may impact performance of material systems in various applications. We introduce a general framework for the analysis of particle growth kinetics by utilizing concepts from machine learning and graph theory. As a model system, we use image sequences of atomic force microscopy showing the crystallization of an amorphous fluoroelastomer film. To identify crystalline particles in an amorphous matrix and track the temporal evolution of the particle dispersion, we have developed quantitative methods of 2D analysis. 700 image sequences were analyzed using a neural network architecture, achieving 0.97 pixel-wise classification accuracy as a measure of the correctly classified pixels. The growth kinetics of isolated and impinged particles were tracked throughout time using these image sequences. The relationship between image sequences and spatiotemporal graph representations was explored to identify the proximity of crystallites from each other. The framework enables the analysis of all image sequences without the requirement of sampling for specific particles or timesteps for various materials systems.

36 MATERIALS SCIENCE↗
DOE OSTI2020

De Sitter diagrammar and the resummation of time

Light scalars in inflationary spacetimes suffer from logarithmic infrared divergences at every order in perturbation theory. This corresponds to the scalar field values in different Hubble patches undergoing a random walk of quantum fluctuations, leading to a simple toy “landscape” on superhorizon scales, in which we can explore questions relevant to eternal inflation. However, for a sufficiently long period of inflation, the infrared divergences appear to spoil computability. Some form of renormalization group approach is thus motivated to resum the log divergences of conformal time. Such a resummation may provide insight into De Sitter holography. We present here a novel diagrammatic analysis of these infrared divergences and their resummation. Basic graph theory observations and momen- tum power counting for the in-in propagators allow a simple and insightful determination of the leading-log contributions. One thus sees diagrammatically how the superhorizon sector consists of a semiclassical theory with quantum noise evolved by a first-order, interacting classical equation of motion. This rigorously leads to the “Stochastic Inflation” ansatz developed by Starobinsky to cure the scalar infrared pathology nonperturbatively. Our approach is a controlled approximation of the underlying quantum field theory and is systematically improvable.

79 ASTRONOMY AND ASTROPHYSICS↗
DOE OSTI2020

Symmetry reduction of tensor networks in many-body theory: I. Automated symbolic evaluation of SU(2) algebra

Abstract The ongoing progress in (nuclear) many-body theory is accompanied by an ever-rising increase in complexity of the underlying formalisms used to solve the stationary Schrödinger equation. The associated working equations at play in state-of-the-art ab initio nuclear many-body methods can be analytically reduced with respect to angular-momentum, i.e. SU (2), quantum numbers whenever they are effectively employed in a symmetry-restricted context. The corresponding procedure constitutes a tedious and error-prone but yet an integral part of the implementation of those many-body frameworks. Indeed, this symmetry reduction is a key step to advance modern simulations to higher accuracy since the use of symmetry-adapted tensors can decrease the computational complexity by orders of magnitude. While attempts have been made in the past to automate the (anti-) commutation rules linked to Fermionic and Bosonic algebras at play in the derivation of the working equations, there is no systematic account to achieve the same goal for their symmetry reduction. In this work, the first version of an automated tool performing graph-theory-based angular-momentum reduction is presented. Taking the symmetry-unrestricted expressions of a generic tensor network as an input, the code provides their angular-momentum-reduced form in an error-safe way in a matter of seconds. Several state-of-the-art many-body methods serve as examples to demonstrate the generality of the approach and to highlight the potential impact on the many-body community.

Tichai, A.↗
DOE OSTI2019

Spatially explicit network analysis reveals multi‐species annual cycle movement patterns of sea ducks

Abstract Conservation of long‐distance migratory species poses unique challenges. Migratory connectivity, that is, the extent to which groupings of individuals at breeding sites are maintained in wintering areas, is frequently used to evaluate population structure and assess use of key habitat areas. However, for species with complex or variable annual cycle movements, this traditional bimodal framework of migratory connectivity may be overly simplistic. Like many other waterfowl, sea ducks often travel to specific pre‐ and post‐breeding sites outside their nesting and wintering areas to prepare for migration by feeding extensively and, in some cases, molting their flight feathers. These additional migrations may play a key role in population structure, but are not included in traditional models of migratory connectivity. Network analysis, which applies graph theory to assess linkages between discrete locations or entities, offers a powerful tool for quantitatively assessing the contributions of different sites used throughout the annual cycle to complex spatial networks. We collected satellite telemetry data on annual cycle movements of 672 individual sea ducks of five species from throughout eastern North America and the Great Lakes. From these data, we constructed a multi‐species network model of migratory patterns and site use over the course of breeding, molting, wintering, and migratory staging. Our results highlight inter‐ and intra‐specific differences in the patterns and complexity of annual cycle movement patterns, including the central importance of staging and molting sites in James Bay, the St. Lawrence River, and southern New England to multi‐species annual cycle habitat linkages, and highlight the value of Long‐tailed Ducks ( Calengula haemalis ) as an umbrella species to represent the movement patterns of multiple sea duck species. We also discuss potential applications of network migration models to conservation prioritization, identification of population units, and integrating different data streams.

54 ENVIRONMENTAL SCIENCES↗
DOE OSTI2024

Quantum Simulations of Radiation Damage in a Molecular Polyethylene Analog

Abstract An atomic‐level understanding of radiation‐induced damage in simple polymers like polyethylene is essential for determining how these chemical changes can alter the physical and mechanical properties of important technological materials such as plastics. Ensembles of quantum simulations of radiation damage in a polyethylene analog are performed using the Density Functional Tight Binding method to help bind its radiolysis and subsequent degradation as a function of radiation dose. Chemical degradation products are categorized with a graph theory approach, and occurrence rates of unsaturated carbon bond formation, crosslinking, cycle formation, chain scission reactions, and out‐gassing products are computed. Statistical correlations between product pairs show significant correlations between chain scission reactions, unsaturated carbon bond formation, and out‐gassing products, though these correlations decrease with increasing atom recoil energy. The results present relatively simple chemical descriptors as possible indications of network rearrangements in the middle range of excitation energies. Ultimately, the work provides a computational framework for determining the coupling between nonequilibrium chemistry in polymers and potential changes to macro‐scale properties that can aid in the interpretation of future radiation damage experiments on plastic materials.

38 RADIATION CHEMISTRY, RADIOCHEMISTRY, AND NUCLEA↗
DOE OSTI2019

The Mathematical Foundations of the Science of Cities

In this chapter, we describe graph-theoretic representations of infrastructure and social processes in urban environments and trace the development of these fields from the perspective of mathematics, social science, and urban planning. We follow the historical development of two different perspectives on cities and urban planning – one in which infrastructure and urban form is the primary focus and another which made people and social processes the primary focus. These perspectives can be traced through their application of concurrently developing mathematical techniques in graph theory, network science, and social network analysis. These different perspectives are now becoming integrated into a more mathematically grounded understanding of cities as coupled social and physical systems, in which the social life of a city shapes and defines the infrastructure that is built and a city’s infrastructure and physical form also shape the lives and communities of its residents.

Brelsford, Christa↗
DOE OSTI2023

Engineering of increased L-Threonine production in bacteria by combinatorial cloning and machine learning

The goal of this study is to develop a general strategy for bacterial engineering using an integrated synthetic biology and machine learning (ML) approach. This strategy was developed in the context of increasing L-threonine production in Escherichia coli ATCC 21277. A set of 16 genes was initially selected based on metabolic pathway relevance to threonine biosynthesis and used for combinatorial cloning to construct a set of 385 strains to generate training data (i.e., a range of L-threonine titers linked to each of the specific gene combinations). Hybrid (regression/classification) deep learning (DL) models were developed and used to predict additional gene combinations in subsequent rounds of combinatorial cloning for increased L-threonine production based on the training data. As a result, E. coli strains built after just three rounds of iterative combinatorial cloning and model prediction generated higher L-threonine titers (from 2.7 g/L to 8.4 g/L) than those of patented L-threonine strains being used as controls (4-5 g/L). Interesting combinations of genes in L-threonine production included deletions of the tdh, metL, dapA, and dhaM genes as well as overexpression of the pntAB, ppc, and aspC genes. Mechanistic analysis of the metabolic system constraints for the best performing constructs offers ways to improve the models by adjusting weights for specific gene combinations. Graph theory analysis of pairwise gene modifications and corresponding levels of L-threonine production also suggests additional rules that can be incorporated into future ML models.

60 APPLIED LIFE SCIENCES↗
DOE OSTI2022

Modified Energy Span Analysis of Catalytic Parallel Pathways and Selectivity

Mechanistic modeling provides vital insights into catalytic reactions. To analyze complex reaction networks with parallel pathways, we leverage the graph theory approach of the Energy Span Model (ESM) to develop a modified energy span analysis (MESA). A new method of cycle plots is proposed to perform reaction pathways analysis visually. We demonstrate this method on two published models: one describing carbon monoxide oxidation and the other simulating ethylene conversion to propanal via hydroformylation or ethane via hydrogenation. Fundamental insights explain kinetic observables, such as a reactant’s negative reaction order. General principles are revealed, such as rate-determining surface species being outside the primary reaction flux cycle and pathway selectivity being a purely kinetic property when reaction conditions are not near equilibrium. Lastly, we demonstrate MESA’s consistency with published microkinetic modeling results, highlighting this technique’s extension of the ESM to heterogeneous catalysts using collision theory to describe adsorption steps and concentration effects.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2024

Structural Properties of [N1888][TFSI] Ionic Liquid: A Small Angle Neutron Scattering and Polarizable Molecular Dynamics Study

In this study, we investigate the quaternary ammonium-based ionic liquid (QAIL), methyltrioctylammonium bis(trifluoromethylsulfonyl)imide, [N 1888 ][TFSI], utilizing small angle neutron scattering (SANS) measurements and polarizable molecular dynamics (MD) simulations to characterize the shortand long-range liquid structure. Scattering structure factors show signatures of three length scales in reciprocal space indicative of alternating polarity (k ~ 0.44 Å –1 ), charge (k ~ 0.75 Å –1 ), and neighboring or adjacent (k ~ 1.46 Å –1 ) domains. Excellent agreement between simulation and experimental scattering structure factors validates various simulation analyses that provide detailed atomistic characterization of the different length scale correlations. The first solvation shell structure is illustrated by obtaining radial, angular, dihedral, and combined distribution functions, where two dominant spatial motifs, N + ···N – and N + ···O – , compete for optimal packing around the polar head of the [N 1888 ] + cation. Intermediate and long-range structures are governed by the balance between local electroneutrality and octyl chain networking, respectively. By computing the charge-correlation structure factor, S ZZ , and the spatial extent of the octyl chain network using graph theory, the bulk-phase structure of [N 1888 ][TFSI] is characterized in terms of electrostatic screening and apolar domain formation length scales.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2020

Percolated Ionic Aggregate Morphologies and Decoupled Ion Transport in Precise Sulfonated Polymers Synthesized by Ring-Opening Metathesis Polymerization

Here, we describe a set of precise single-ion conducting polymers that form self-assembled percolated ionic aggregates in glassy polymer matrices and have decoupled transport of metal cations. These precise single-ion conductors (SICs), synthesized by a scalable ring-opening metathesis polymerization, consist of a polyethylene backbone with a sulfonated phenyl group pendant on every fifth carbon and are fully neutralized by a counterion X + (Li + , Na + , or Cs + ). Experimental X-ray scattering measurements and fully atomistic molecular dynamics (MD) simulations are in good agreement. The MD simulations show that the ionic groups nanophase separate from the polymer backbone to form percolating ionic aggregates. Using graph theory, we find that within the Li + - and Na + -neutralized polymers the percolated aggregates exhibit planar and ribbon-like configurations at intermediate length scales, while the percolated aggregates within the Cs + -neutralized polymers are more isotropic. Electrical impedance spectroscopy measurements show that the ionic conductivities exhibit Arrhenius behavior, with conductivities of 10 –7 to 10 –6 S/cm at 180 °C. In the MD simulations, the cations move between sulfonate groups in the percolated aggregates, larger ions travel further, and overall cations travel further than the polymer backbones, indicating a decoupled ion-transport mechanism. Thus, the percolated ionic aggregates in these polymers can serve as pathways to facilitate decoupled ion motion through a glassy polymer matrix.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2022

Understanding Metal–Organic Framework Nucleation from a Solution with Evolving Graphs

A mechanistic understanding of metal–organic framework (MOF) synthesis and scale-up remains underexplored due to the complex nature of the interactions of their building blocks. In this work, we investigate the collective assembly of building units at the early stages of MOF nucleation, using MIL-101(Cr) as a prototypical example. Using large-scale molecular dynamics simulations, we observe that the choice of solvent (water and N,N-dimethylformamide), the introduction of ions (Na+ and F–) and the relative populations of MIL-101(Cr) half-secondary building unit (half-SBU) isomers have a strong influence on the cluster formation process. Additionally, the shape, size, nucleation and growth rates, crystallinity, and short and long-range order largely vary depending on the synthesis conditions. We evaluate these properties as they naturally emerge when interpreting the self-assembly of MOF nuclei as the time evolution of an undirected graph. Solution-induced conformational complexity and ionic concentration have a dramatic effect on the morphology of clusters emerging during assembly. While pure solvents lead to the rapid formation of a small number of large clusters, the presence of ions in aqueous solutions results in smaller clusters and slower nucleation. This diversity is captured by the key features of the graph representation. Principle component analysis on graph properties reveals that only a small number of molecular descriptors is needed to deconvolute MOF self-assembly. Furthermore, descriptors such as the average coordination number between half-SBUs and fractal dimension are of particular interest as they can be can be followed experimentally by techniques like by time-resolved spectroscopy. Ultimately, graph theory emerges as an approach that can be used to understand complex processes revealing molecular descriptors accessible by both simulation and experiment.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2025

A Scale‐Adaptive Urban Hydrologic Framework: Incorporating Network‐Level Storm Drainage Pipes Representation

Abstract Below‐ground urban stormwater networks (BUSNs) significantly influence urban flood dynamics, yet their representation at the watershed or larger scales remains challenging. We introduce a scalable urban hydrologic framework that centers on a novel network‐level BUSN representation, balancing the needs for physical basis, parameter parsimony, and computational efficiency. Our framework conceptualizes an urban watershed into four interacting zones: hillslopes (natural), storm‐sewersheds (urban), a sub‐network channel (tributaries), and a main channel. We develop an innovative Graph Theory‐based algorithm to derive network‐level BUSN parameters from publicly available datasets, enabling efficient, scalable parameterization. We demonstrate this framework's applicability at nine representative watersheds in the Houston metropolitan region, USA, with urban imperviousness ranging from 0% to 64% and drainage areas ranging from 24 to 302 . Our model achieves satisfying computational efficiency, completing hourly time step simulations for 18 years in less than 5 sec per watershed on a standard PC. Validation against observed daily streamflow confirms that the model can capture small‐to‐large flood peaks and seasonal and annual water balance over these watersheds. Comparisons with the National Water Model show better performance in predicting flood peaks and overall water balance, underscoring the promises of our new framework for urban hydrologic modeling at large scales. Furthermore, analysis reveals nonlinear relationships between BUSNs' designed capacities and flood reduction effects. Our approach bridges the gap between detailed hydraulic and large‐scale hydrologic models, providing a valuable tool for urban flood prediction and management across broader spatial and temporal scales.

54 ENVIRONMENTAL SCIENCES↗
DOE OSTI2022

Chemical crystallography by serial femtosecond X-ray diffraction

Abstract Inorganic–organic hybrid materials represent a large share of newly reported structures, owing to their simple synthetic routes and customizable properties 1 . This proliferation has led to a characterization bottleneck: many hybrid materials are obligate microcrystals with low symmetry and severe radiation sensitivity, interfering with the standard techniques of single-crystal X-ray diffraction 2,3 and electron microdiffraction 4–11 . Here we demonstrate small-molecule serial femtosecond X-ray crystallography (smSFX) for the determination of material crystal structures from microcrystals. We subjected microcrystalline suspensions to X-ray free-electron laser radiation 12,13 and obtained thousands of randomly oriented diffraction patterns. We determined unit cells by aggregating spot-finding results into high-resolution powder diffractograms. After indexing the sparse serial patterns by a graph theory approach 14 , the resulting datasets can be solved and refined using standard tools for single-crystal diffraction data 15–17 . We describe the ab initio structure solutions of mithrene (AgSePh) 18–20 , thiorene (AgSPh) and tethrene (AgTePh), of which the latter two were previously unknown structures. In thiorene, we identify a geometric change in the silver–silver bonding network that is linked to its divergent optoelectronic properties 20 . We demonstrate that smSFX can be applied as a general technique for structure determination of beam-sensitive microcrystalline materials at near-ambient temperature and pressure.

36 MATERIALS SCIENCE↗
DOE OSTI2022

Active learning of chemical reaction networks via probabilistic graphical models and Boolean reaction circuits

Discerning networks of many reactions among multiple interconverting species is challenging. Here, we present a reaction network identification methodology. Our methodology enumerates all stoichiometrically and chemically feasible reactions and requires statistical evidence from effluent concentrations for the inclusion or exclusion of each from the reaction network, contrasting with the commonly seen incremental approach and other work of relying heavily upon chemical intuition and assuming the reactions occurring. Using graph theory alongside an active learning design of experiments that propose maximally informative feeds, we identify the underlying reaction network with minimal laboratory runs. Here, we introduce chemistry-probabilistic graphical modeling and Boolean reaction circuits to statistically quantify which reactions occur from effluent concentrations. Our methodology accurately discerns active reactions, as showcased upon a laboratory network of cross-ketonization of furoic and lauric acid and validated upon simulated networks of thermal and CO 2 -assisted ethane dehydrogenation.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2021

Systematic planning of moving target defence for maximising detection effectiveness against false data injection attacks in smart grid

Abstract Moving target defence (MTD) has been gaining traction to thwart false data injection attacks against state estimation (SE) in the power grid. MTD actively perturbs the reactance of transmission lines equipped with distributed flexible AC transmission system (D‐FACTS) devices to falsify the attacker's knowledge about the system configuration. However, the existing literature has not systematically studied what influences the detection effectiveness of MTD and how it can be improved based on the topology analysis. These problems are tackled here from the perspective of an MTD plan in which the D‐FACTS placement is determined. We first exploit the relation between the rank of the composite matrix and the detecting effectiveness. Then, we rigorously derive upper and lower bounds on the attack detecting probability of MTDs with a given rank of the composite matrix. Furthermore, we analyse existing planning methods and highlight the importance of bus coverage by D‐FACTS devices. To improve the detection effectiveness, we propose a novel graph theory–based planning algorithm to retain the maximum rank of the composite matrix while covering all necessary buses. Comparative results on multiple systems show the high detecting effectiveness of the proposed algorithm in both DC‐ and AC‐SE.

24 POWER TRANSMISSION AND DISTRIBUTION↗