Search NASA⌕ Search

SEARCH · Search NASA

Results for “connected components”

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

Automatic partitioning of unstructured grids into connected components

This paper presents two partitioning schemes that guarantee connected components given a connected initial grid. Connected components are important for convergence of methods such as domain decomposition or multigrid. For many of the grids tested, the schemes produce partitions as good (in terms of number of cut edges) or better than spectral partitioning and require only modest computational resources. This paper describes the two schemes in detail and presents comparison results from a number of two and three dimensional unstructured grids.

Dagum, Leonardo↗

Symbolic Computation of Strongly Connected Components Using Saturation

Finding strongly connected components (SCCs) in the state-space of discrete-state models is a critical task in formal verification of LTL and fair CTL properties, but the potentially huge number of reachable states and SCCs constitutes a formidable challenge. This paper is concerned with computing the sets of states in SCCs or terminal SCCs of asynchronous systems. Because of its advantages in many applications, we employ saturation on two previously proposed approaches: the Xie-Beerel algorithm and transitive closure. First, saturation speeds up state-space exploration when computing each SCC in the Xie-Beerel algorithm. Then, our main contribution is a novel algorithm to compute the transitive closure using saturation. Experimental results indicate that our improved algorithms achieve a clear speedup over previous algorithms in some cases. With the help of the new transitive closure computation algorithm, up to 10(exp 150) SCCs can be explored within a few seconds.

Zhao, Yang↗

Implementing Connected Component Labeling as a User Defined Operator for SciDB

We have implemented a flexible User Defined Operator (UDO) for labeling connected components of a binary mask expressed as an array in SciDB, a parallel distributed database management system based on the array data model. This UDO is able to process very large multidimensional arrays by exploiting SciDB's memory management mechanism that efficiently manipulates arrays whose memory requirements far exceed available physical memory. The UDO takes as primary inputs a binary mask array and a binary stencil array that specifies the connectivity of a given cell to its neighbors. The UDO returns an array of the same shape as the input mask array with each foreground cell containing the label of the component it belongs to. By default, dimensions are treated as non-periodic, but the UDO also accepts optional input parameters to specify periodicity in any of the array dimensions. The UDO requires four stages to completely label connected components. In the first stage, labels are computed for each subarray or chunk of the mask array in parallel across SciDB instances using the weighted quick union (WQU) with half-path compression algorithm. In the second stage, labels around chunk boundaries from the first stage are stored in a temporary SciDB array that is then replicated across all SciDB instances. Equivalences are resolved by again applying the WQU algorithm to these boundary labels. In the third stage, relabeling is done for each chunk using the resolved equivalences. In the fourth stage, the resolved labels, which so far are "flattened" coordinates of the original binary mask array, are renamed with sequential integers for legibility. The UDO is demonstrated on a 3-D mask of O(1011) elements, with O(108) foreground cells and O(106) connected components. The operator completes in 19 minutes using 84 SciDB instances.

UDO↗

Parallel algorithms for geometric connected component labeling on a hypercube multiprocessor

Different algorithms for the geometric connected component labeling (GCCL) problem are defined each of which involves d stages of message passing, for a d-dimensional hypercube. The major idea is that in each stage a hypercube multiprocessor increases its knowledge of domain. The algorithms under consideration include the QUAD algorithm for small number of processors and the Overlap Quad algorithm for large number of processors, subject to the locality of the connected sets. These algorithms differ in their run time, memory requirements, and message complexity. They were implemented on an Intel iPSC2/D4/MX hypercube.

Belkhale, K. P.↗

The Livingstone Model of a Main Propulsion System

Livingstone is a discrete, propositional logic-based inference engine that has been used for diagnosis of physical systems. We present a component-based model of a Main Propulsion System (MPS) and say how it is used with Livingstone (L2) in order to implement a diagnostic system for integrated vehicle health management (IVHM) for the Propulsion IVHM Technology Experiment (PITEX). We start by discussing the process of conceptualizing such a model. We describe graphical tools that facilitated the generation of the model. The model is composed of components (which map onto physical components), connections between components and constraints. A component is specified by variables, with a set of discrete, qualitative values for each variable in its local nominal and failure modes. For each mode, the model specifies the component's behavior and transitions. We describe the MPS components' nominal and fault modes and associated Livingstone variables and data structures. Given this model, and observed external commands and observations from the system, Livingstone tracks the state of the MPS over discrete time-steps by choosing trajectories that are consistent with observations. We briefly discuss how the compiled model fits into the overall PITEX architecture. Finally we summarize our modeling experience, discuss advantages and disadvantages of our approach, and suggest enhancements to the modeling process.

Bajwa, Anupa↗

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↗

Systems Modeling to Implement Integrated System Health Management Capability

ISHM capability includes: detection of anomalies, diagnosis of causes of anomalies, prediction of future anomalies, and user interfaces that enable integrated awareness (past, present, and future) by users. This is achieved by focused management of data, information and knowledge (DIaK) that will likely be distributed across networks. Management of DIaK implies storage, sharing (timely availability), maintaining, evolving, and processing. Processing of DIaK encapsulates strategies, methodologies, algorithms, etc. focused on achieving high ISHM Functional Capability Level (FCL). High FCL means a high degree of success in detecting anomalies, diagnosing causes, predicting future anomalies, and enabling health integrated awareness by the user. A model that enables ISHM capability, and hence, DIaK management, is denominated the ISHM Model of the System (IMS). We describe aspects of the IMS that focus on processing of DIaK. Strategies, methodologies, and algorithms require proper context. We describe an approach to define and use contexts, implementation in an object-oriented software environment (G2), and validation using actual test data from a methane thruster test program at NASA SSC. Context is linked to existence of relationships among elements of a system. For example, the context to use a strategy to detect leak is to identify closed subsystems (e.g. bounded by closed valves and by tanks) that include pressure sensors, and check if the pressure is changing. We call these subsystems Pressurizable Subsystems. If pressure changes are detected, then all members of the closed subsystem become suspect of leakage. In this case, the context is defined by identifying a subsystem that is suitable for applying a strategy. Contexts are defined in many ways. Often, a context is defined by relationships of function (e.g. liquid flow, maintaining pressure, etc.), form (e.g. part of the same component, connected to other components, etc.), or space (e.g. physically close, touching the same common element, etc.). The context might be defined dynamically (if conditions for the context appear and disappear dynamically) or statically. Although this approach is akin to case-based reasoning, we are implementing it using a software environment that embodies tools to define and manage relationships (of any nature) among objects in a very intuitive manner. Context for higher level inferences (that use detected anomalies or events), primarily for diagnosis and prognosis, are related to causal relationships. This is useful to develop root-cause analysis trees showing an event linked to its possible causes and effects. The innovation pertaining to RCA trees encompasses use of previously defined subsystems as well as individual elements in the tree. This approach allows more powerful implementations of RCA capability in object-oriented environments. For example, if a pressurizable subsystem is leaking, its root-cause representation within an RCA tree will show that the cause is that all elements of that subsystem are suspect of leak. Such a tree would apply to all instances of leak-events detected and all elements in all pressurizable subsystems in the system. Example subsystems in our environment to build IMS include: Pressurizable Subsystem, Fluid-Fill Subsystem, Flow-Thru-Valve Subsystem, and Fluid Supply Subsystem. The software environment for IMS is designed to potentially allow definition of any relationship suitable to create a context to achieve ISHM capability.

Figueroa, Jorge F.↗

Digital simulation of the serpentuator using MARSYAS

Serpentuator is a serpentine teleoperator device for intravehicular and extravehicular activities in space. The serpentuator is simulated using simulation software system MARSYAS and using the Component-Connection Simulation model and the Direct Simulation model. A comparison of the results for the two cases shows that under identical conditions, simulation execution time in the Component-Connection model case is reduced by a factor of the order of 100. A visual display of the serpentuator positions is obtained using the AMTRAN system on the Datacraft DC 6024 computer.

Singh, S., P.↗

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↗

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]↗

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↗

Dynamics of Rotating Multi-component Turbomachinery Systems

The ultimate objective of turbomachinery vibration analysis is to predict both the overall, as well as component dynamic response. To accomplish this objective requires complete engine structural models, including multistages of bladed disk assemblies, flexible rotor shafts and bearings, and engine support structures and casings. In the present approach each component is analyzed as a separate structure and boundary information is exchanged at the inter-component connections. The advantage of this tactic is that even though readily available detailed component models are utilized, accurate and comprehensive system response information may be obtained. Sample problems, which include a fixed base rotating blade and a blade on a flexible rotor, are presented.

Lawrence, Charles↗

Dynamics of rotating multicomponent turbomachinery systems

The ultimate objective of turbomachinery vibration analysis is to predict both the overall, as well as component dynamic response. To accomplish this objective requires complete engine structural models, including multistages of bladed disk assemblies, flexible rotor shafts and bearings, and engine support structures and casings. In the present approach each component is analyzed as a separate structure and boundary information is exchanged at the inter-component connections. The advantage of this tactic is that even though readily available detailed component models are utilized, accurate and comprehensive system response information may be obtained. Sample problems, which include a fixed base rotating blade and a blade on a flexible rotor, are presented.

Lawrence, Charles↗

Low-Friction, Low-Profile, High-Moment Two-Axis Joint

The two-axis joint is a mechanical device that provides two-degrees-of-freedom motion between connected components. A compact, moment-resistant, two-axis joint is used to connect an electromechanical actuator to its driven structural members. Due to the requirements of the overall mechanism, the joint has a low profile to fit within the allowable space, low friction, and high moment-reacting capability. The mechanical arrangement of this joint can withstand high moments when loads are applied. These features allow the joint to be used in tight spaces where a high load capability is required, as well as in applications where penetrating the mounting surface is not an option or where surface mounting is required. The joint consists of one base, one clevis, one cap, two needle bearings, and a circular shim. The base of the joint is the housing (the base and the cap together), and is connected to the grounding structure via fasteners and a bolt pattern. Captive within the housing, between the base and the cap, are the rotating clevis and the needle bearings. The clevis is attached to the mechanical system (linear actuator) via a pin. This pin, and the rotational movement of the clevis with respect to the housing, provides two rotational degrees of freedom. The larger diameter flange of the clevis is sandwiched between a pair of needle bearings, one on each side of the flange. During the assembly of the two-axis joint, the circular shims are used to adjust the amount of preload that is applied to the needle bearings. The above arrangement enables the joint to handle high moments with minimal friction. To achieve the high-moment capability within a low-profile joint, the use of depth of engagement (like that of a conventional rotating shaft) to react moment is replaced with planar engagement parallel to the mounting surface. The needle bearings with the clevis flange provide the surface area to react the clevis loads/moments into the joint housing while providing minimal friction during rotation. The diameter of the flange and the bearings can be increased to react higher loads and still maintain a compact surface mounting capability. This type of joint can be used in a wide variety of mechanisms and mechanical systems. It is especially effective where precise, smooth, continuous motion is required. For example, the joint can be used at the end of a linear actuator that is required to extend and rotate simultaneously. The current design application is for use in a spacecraft docking-system capture mechanism. Other applications might include industrial robotic or assembly line apparatuses, positioning systems, or in the motion-based simulator industry that employs complex, multi-axis manipulators for various types of motions.

Lewis, James L.↗

Detection of Machining Chips by Pressure Reversal

Inaccessible interior spaces inspected acoustically. In acoustic inspection, inlet and outlet ports of component connected to pneumatic hoses of apparatus that rapidly reverses induced pressure differential. If loose particles inside this component, they will generate noise detected by series of contact microphones attached to component. Noise indicates general location of contaminants, and its characteristic helps in identifying particles from their acoustic signatures.

Wyett, L. M.↗