Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Connected Component”

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 19 records
All sourcesNASA NTRSDOE OSTI
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↗
DOE OSTI2020

Sequence optimizations in a high-performance computing environment

Embodiments are directed to techniques to determine dataflow graph instructions comprising one or more pick/switch instruction pairs and generate a reverse static single assignment graph based on the dataflow graph instructions, the reverse static single assignment graph comprising strongly connected components, each of the strongly connected components associated with at least one of the one or more pick/switch instruction pairs. Embodiments also include traversing the reverse static single assignment graph depth-first, and replace pick/switch instructions associated with strongly connected components having configuration values with compound instructions.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Direction-optimizing Label Propagation Framework for Structure Detection in Graphs: Design, Implementation, and Experimental Analysis

Label Propagation is not only a well-known machine learning algorithm for classification but also an effective method for discovering communities and connected components in networks. We propose a new Direction-optimizing Label Propagation Algorithm (DOLPA) framework that enhances the performance of the standard Label Propagation Algorithm (LPA), increases its scalability, and extends its versatility and application scope. As a central feature, the DOLPA framework relies on the use of frontiers and alternates between label push and label pull operations to attain high performance. It is formulated in such a way that the same basic algorithm can be used for finding communities or connected components in graphs by only changing the objective function used. Additionally, DOLPA has parameters for tuning the processing order of vertices in a graph to reduce the number of edges visited and improve the quality of solution obtained. We present the design and implementation of the enhanced algorithm as well as our shared-memory parallelization of it using OpenMP. We also present an extensive experimental evaluation of our implementations using the LFR benchmark and real-world networks drawn from various domains. Compared with an implementation of LPA for community detection available in a widely used network analysis software, we achieve at most five times the F-Score while maintaining similar runtime for graphs with overlapping communities. We also compare DOLPA against an implementation of the Louvain method for community detection using the same LFR-graphs and show that DOLPA achieves about three times the F-Score at just 10% of the runtime. For connected component decomposition, our algorithm achieves orders of magnitude speedups over the basic LP-based algorithm on large-diameter graphs, up to 13.2× speedup over the Shiloach-Vishkin algorithm, and up to 1.6× speedup over Afforest on an Intel Xeon processor using 40 threads.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2026

Dynamic Disruption Resilience in Intermodal Transport Networks: Integrating Flow Weighting and Centrality Measures

Resilient intermodal freight networks are vital for sustaining supply chains amid increasing threats from natural hazards and cyberattacks. Transportation resilience has been widely studied; understanding how random and targeted disruptions affect structural connectivity and functional performance remains a key challenge. To address this, this study evaluates the robustness of the US intermodal freight network, which consists of rail and water modes, using a simulation-based framework that integrates graph-theoretic metrics with flow-weighted centrality measures. Disruption scenarios are examined, including random failures as well as targeted node and edge removals based on static and dynamically updated degree and betweenness centrality. To reflect more realistic conditions, flow-weighted degree centralities (WDC) and partial node degradation are considered. Two resilience indicators are used: (1) the size of the giant connected component to measure structural connectivity; and (2) flow-weighted network efficiency (NE) to assess freight mobility under disruption. The results show that progressively degrading nodes ranked by WDC to 60% of their original functionality causes a sharper decline in normalized NE, for up to approximately 45 affected nodes, than complete failure (100% loss of functionality) applied to nodes targeted by weighted betweenness centrality or selected at random. This highlights how partial degradation of high-tonnage hubs can produce disproportionately large functional losses. The findings emphasize the need for resilience strategies that go beyond network topology to incorporate freight flow dynamics.

42 ENGINEERING↗
DOE OSTI2025

MAGIS-100 Experiment Installation in Shaft

This poster shows the experiment and access system as it will be installed in the MINOS shaft, along with important connecting components such as the atom sources and connection nodes.

Kowalkowski, James B. [Fermilab]↗
DOE OSTI2022

Graph-component approach to defect identification in large atomistic simulations

In this work, the graph-theoretical concept of connected components is employed to extract the evolution of defect configurations in a polycrystalline aluminum structure containing ~8.3 million atoms. This graph-component approach is applied to reveal details of defect formation, transport, and transformation in the polycrystalline Al under large shear deformation. Building upon standard nearest neighbor analysis, graph theory and associated tools are used to reduce the multi-million-atom system into discrete component subgraphs that represent distinct structural defects. This method allows the automated identification, characterization, and tracking of defective regions within large volumes of data representing atomic-scale processes. Such analysis elucidates relationships between external stimuli, such as strain, and defect distributions, which have a large influence on material properties. The Graph Analytics for Large Atomistic Simulations (GALAS) codebase that implements this analysis, together with user guidance, is openly available at https://github.com/pnnl/galas.

36 MATERIALS SCIENCE↗
DOE OSTI2020

ConnectIt: a framework for static and incremental parallel graph connectivity algorithms

Connected components is a fundamental kernel in graph applications. The fastest existing multicore algorithms for solving graph connectivity are based on some form of edge sampling and/or linking and compressing trees. However, many combinations of these design choices have been left unexplored. In this paper, we design the ConnectIt framework, which provides different sampling strategies as well as various tree linking and compression schemes. ConnectIt enables us to obtain several hundred new variants of connectivity algorithms, most of which extend to computing spanning forest. In addition to static graphs, we also extend ConnectIt to support mixes of insertions and connectivity queries in the concurrent setting. We present an experimental evaluation of ConnectIt on a 72-core machine, which we believe is the most comprehensive evaluation of parallel connectivity algorithms to date. Compared to a collection of state-of-the-art static multicore algorithms, we obtain an average speedup of 12.4x (2.36x average speedup over the fastest existing implementation for each graph). Using ConnectIt, we are able to compute connectivity on the largest publicly-available graph (with over 3.5 billion vertices and 128 billion edges) in under 10 seconds using a 72-core machine, providing a 3.1x speedup over the fastest existing connectivity result for this graph, in any computational setting. For our incremental algorithms, we show that our algorithms can ingest graph updates at up to several billion edges per second. To guide the user in selecting the best variants in ConnectIt for different situations, we provide a detailed analysis of the different strategies. Finally, we show how the techniques in ConnectIt can be used to speed up two important graph applications: approximate minimum spanning forest and SCAN clustering.

Computer Science↗
DOE OSTI2020

Low-Frequency Stability Analysis of Inverter-Based Islanded Multiple-Bus AC Microgrids Based on Terminal Characteristics

For system planning of three-phase inverter-based islanded ac microgrids, the low frequency instability issue caused by interactions of inverter droop controllers is a major concern. When internal control information of procured commercial inverters is unknown, impedance-based small-signal stability criteria facilitate prediction of resonances in medium and high frequency ranges, but they usually assume the grid fundamental frequency as constant and thus they are incapable of analyzing the low-frequency oscillation of the fundamental frequency in islanded microgrids. Aiming at solving this issue, this paper proposes two stability analysis methods based on terminal characteristics of inverters and passive connection network including the dynamics of the fundamental frequency for analysis of low-frequency stability in islanded multiple-bus microgrids. Based on the Component Connection Method (CCM) to systematically separate inverters from the passive connection network, a general approach is developed to model the microgrid as a multiple-input-multiple-output (MIMO) negative feedback system in the common system d-q reference frame. By applying the generalized Nyquist stability criterion (GNC) to the return-ratio and return-difference matrices of the MIMO system model, the low-frequency stability related to the fundamental frequency can be analyzed using the measured terminal characteristics of inverters. Finally, analysis and simulation of a 37-bus microgrid verify the effectiveness of the proposed stability analysis methods.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2022

Balancing Impedance and Controllability in Response Reconstruction

One concept in smart dynamic testing is to match the impedance that a component experiences between test and the environment of interest, but this begs the question: how much of an impedance match is needed and could there be too much? In a prior work, the authors performed MIMO testing with a small component connected to various assemblies, each of which had a differing degree of similarity to the actual flight boundary conditions. The results showed that the fidelity of the response at locations away from the control accelerometers was highly sensitive to the impedance. This work presents further case studies to explore these ideas. Subsequent tests are presented for an assembly that presumably matched the impedance even better, and which was also much more flexible, and the results obtained are even worse than when no attention was given to the impedance. Hence, the work presented here suggests that one should seek a balance between 1.) matching the impedance and 2.) improving the controllability of the component of interest. The concepts are explored using both test data of a benchmark component, for which the environment of interest was recorded as the component flew on a sounding rocket.

Shaker Test, Operational Vibration Environment, Su↗
DOE OSTI2020

Low-dimensional de Sitter quantum gravity

We study aspects of Jackiw-Teitelboim (JT) quantum gravity in two-dimensional nearly de Sitter (dS) spacetime, as well as pure de Sitter quantum gravity in three dimensions. These are each theories of boundary modes, which include a reparameterization field on each connected component of the boundary as well as topological degrees of freedom. In two dimensions, the boundary theory is closely related to the Schwarzian path integral, and in three dimensions to the quantization of coadjoint orbits of the Virasoro group. Using these boundary theories we compute loop corrections to the wavefunction of the universe, and investigate gravitational contributions to scattering. Along the way, we show that JT gravity in dS2 is an analytic continuation of JT gravity in Euclidean AdS2, and that pure gravity in dS3 is a continuation of pure gravity in Euclidean AdS3. We define a genus expansion for de Sitter JT gravity by summing over higher genus generalizations of surfaces used in the Hartle-Hawking construction. Assuming a conjecture regarding the volumes of moduli spaces of such surfaces, we find that the de Sitter genus expansion is the continuation of the recently discovered AdS genus expansion. Then both may be understood as coming from the genus expansion of the same double-scaled matrix model, which would provide a non-perturbative completion of de Sitter JT gravity.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2021

(2, 2) Scattering and the celestial torus

Analytic continuation from Minkowski space to (2, 2) split signature spacetime has proven to be a powerful tool for the study of scattering amplitudes. Here we show that, under this continuation, null infinity becomes the product of a null interval with a celestial torus (replacing the celestial sphere) and has only one connected component. Spacelike and timelike infinity are time-periodic quotients of AdS 3 . These three components of infinity combine to an S 3 represented as a toric fibration over the interval. Privileged scattering states of scalars organize into SL(2, $\mathbb{R}$) L ×SL(2, $\mathbb{R}$) R conformal primary wave functions and their descendants with real integral or half-integral conformal weights, giving the normally continuous scattering problem a discrete character.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2021

Charge completeness and the massless charge lattice in F-theory models of supergravity

We prove that, for every 6D supergravity theory that has an F-theory description, the property of charge completeness for the connected component of the gauge group (meaning that all charges in the corresponding charge lattice are realized by massive or massless states in the theory) is equivalent to a standard assumption made in F-theory for how geometry encodes the global gauge theory by means of the Mordell-Weil group of the elliptic fibration. This result also holds in 4D F-theory constructions for the parts of the gauge group that come from sections and from 7-branes. We find that in many 6D F-theory models the full charge lattice of the theory is generated by massless charged states; this occurs for each gauge factor where the associated anomaly coefficient satisfies a simple positivity condition. We describe many of the cases where this massless charge sufficiency condition holds, as well as exceptions where the positivity condition fails, and analyze the related global structure of the gauge group and associated Mordell-Weil torsion in explicit F-theory models.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
DOE OSTI2020

A Quantum-Based Approach to Predict Primary Radiation Damage in Polymeric Networks

Initial atomistic-level radiation damage in chemically reactive materials is thought to induce reaction cascades that can result in undesirable degradation of macroscale properties. Ensembles of quantum-based molecular dynamics (QMD) simulations can accurately predict these cascades, but extracting chemical insights from the many underlying trajectories is a labor-intensive process that can require substantial a priori intuition. We develop here a general and automated graph-based approach to extract all chemically distinct structures sampled in QMD simulations and apply our approach to predict primary radiation damage of polydimethylsiloxane (PDMS), the main constituent of silicones. A postprocessing protocol is developed to identify underlying polymer backbone structures as connected components in QMD trajectories. Furthermore, these backbones form a repository of radiation-damaged structures. A scheme for extracting and updating a library of isomorphically distinct structures is proposed to identify the spanning set and aid chemical interpretation of the repository. The analyses are applied to ensembles of cascade QMD simulations in which the four element types in PDMS are selectively excited in primary knock-on atom events. Our approach reveals a much higher degree of combinatorial complexity in this system than was inferred through radiolysis experiments. Probabilities are extracted for radiation-induced network changes including formation of branch points, carbon linkages, cycles, bond scissions, and carbon uptake into the Si–O siloxane backbone network. The general analysis framework presented here is readily extendable to modeling chemical degradation of other polymers and molecular materials and provides a basis for future quantum-informed multiscale modeling of radiation damage.

36 MATERIALS SCIENCE↗
DOE OSTI2026

Toward the “platinum standard” of quantum chemistry on quantum computers: Perturbative quadruple corrections in unitary coupled cluster theory

We propose a non-iterative, post-hoc correction to the unitary coupled cluster theory with the single, double, and triple excitations (UCCSDT) Ansatz, which considers the leading-order effects of neglected quadruple excitations. We present two ways to derive this correction, henceforth referred to as [Q-6], which leads to an improvement in the correlation energy shown to be truncated to sixth-order in many-body perturbation theory. Furthermore, a comparison between the UCC-based [Q-6] correction proposed in this work and analogous, “platinum standard” quadruple corrections proposed in conventional coupled cluster theory recognizes that [Q-6] is distinct from prior corrections since it is constructed entirely from internally connected components. Although trotterized (t) and full operator variants of UCCSDT exhibit errors in scans of small molecule potential energy surfaces that routinely exceed 1.6 mH, we find that t/UCCSDT[Q-6] is, nevertheless, able to achieve chemical accuracy as measured by the mean unsigned error.

Correlation energy↗
DOE OSTI2021

Morse Theory without Non-Degeneracy

Abstract We describe an extension of Morse theory to smooth functions on compact Riemannian manifolds, without any non-degeneracy assumptions except that the critical locus must have only finitely many connected components.

Mathematics↗