Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “graph decomposition”

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 55 records · Page 3

Coding gains and error rates from the Big Viterbi Decoder

A prototype hardware Big Viterbi Decoder (BVD) was completed for an experiment with the Galileo Spacecraft. Searches for new convolutional codes, studies of Viterbi decoder hardware designs and architectures, mathematical formulations, and decompositions of the deBruijn graph into identical and hierarchical subgraphs, and very large scale integration (VLSI) chip design are just a few examples of tasks completed for this project. The BVD bit error rates (BER), measured from hardware and software simulations, are plotted as a function of bit signal to noise ratio E sub b/N sub 0 on the additive white Gaussian noise channel. Using the constraint length 15, rate 1/4, experimental convolutional code for the Galileo mission, the BVD gains 1.5 dB over the NASA standard (7,1/2) Maximum Likelihood Convolution Decoder (MCD) at a BER of 0.005. At this BER, the same gain results when the (255,233) NASA standard Reed-Solomon decoder is used, which yields a word error rate of 2.1 x 10(exp -8) and a BER of 1.4 x 10(exp -9). The (15, 1/6) code to be used by the Cometary Rendezvous Asteroid Flyby (CRAF)/Cassini Missions yields 1.7 dB of coding gain. These gains are measured with respect to symbols input to the BVD and increase with decreasing BER. Also, 8-bit input symbol quantization makes the BVD resistant to demodulated signal-level variations which may cause higher bandwidth than the NASA (7,1/2) code, these gains are offset by about 0.1 dB of expected additional receiver losses. Coding gains of several decibels are possible by compressing all spacecraft data.

Onyszchuk, I. M.↗

Replace Human Intelligence with Fast and Smart Geometric Reasoning and Graph Neural Network to Accelerate Next Gen ModSim Workflows

We present an agent-guided approach to CAD geometry decomposition that automates hex/hybrid meshing with graph neural networks (GNNs) to accelerate next-generation ModSim workflows. Our end-to-end pipeline (i) reduces 3D boundary-representation (B-Rep) models to a 2D chordal axis skeleton (CAT) and then to a 1D bipartite graph of surface and curve nodes, (ii) assigns per node labels as Cubit® WebCut actions, (iii) trains a multi-action GNN under supervised learning, and (iv) predicts five surface-node and three curve-node actions on out-of-distribution test geometries. Each graph node carries geometric, topological, and meshing attributes drawn from the B-Rep “skin” and CAT “skeleton,” with two-way mappings across 3D↔2D↔1D representations to maintain traceability back to 3D CAD. The supervised learning model exhibits stable convergence of the binary cross-entropy loss and achieves 98.7% accuracy on unseen lattice models. To operationalize decision-making, we rank predicted commands by geometric significance and prototyped the agent-guided workflow through the Cubit® Meshing PowerTool GUI. As a stretch goal, we explore reinforcement learning (RL) to reduce or remove label requirements and to learn policies for action sequences that maximize total reward (e.g., size of hex-meshable regions and resulting hex mesh quality). When all-hex meshing is not feasible, the agent assists in producing hybrid meshes—prioritizing hex in critical regions and transitioning to tetrahedral elements (tets) elsewhere—maintaining fidelity while ensuring robustness. The overarching objective is to replace manual, heuristics-based decomposition with data-driven, reproducible automation, cutting meshing turnaround time by orders of magnitude. We anticipate direct impact on simulation workflows through intelligent, scalable decomposition of complex CAD models into hex-meshable subdomains.

97 MATHEMATICS AND COMPUTING↗

Graph-based modeling and simulation of complex systems

We present graph-based modeling abstractions to represent cyber-physical dependencies arising in complex systems. Specifically, we propose an algebraic graph abstraction to capture physical connectivity in complex optimization models and a computing graph abstraction to capture communication connectivity in computing architectures. The proposed abstractions are scalable and are used as the backbone of a Julia-based software package that we call Plasmo.j1. Here, we show how the algebraic graph abstraction facilitates the implementation, analysis, and decomposition of optimization problems and we show how the computing graph abstraction facilitates the implementation of optimization and control algorithms and their simulation in virtual environments that involve distributed, centralized, and hierarchical computing architectures.

97 MATHEMATICS AND COMPUTING↗

Incremental k-core decomposition: Algorithms and evaluation

A k-core of a graph is a maximal connected subgraph in which every vertex is connected to at least k vertices in the subgraph. k-core decomposition is often used in large-scale network analysis, such as community detection, protein function prediction, visualization, and solving NP-hard problems on real networks efficiently, like maximal clique finding. In many real-world applications, networks change over time. As a result, it is essential to develop efficient incremental algorithms for dynamic graph data. In this paper, we propose a suite of incremental k-core decomposition algorithms for dynamic graph data. These algorithms locate a small subgraph that is guaranteed to contain the list of vertices whose maximum k-core values have changed and efficiently process this subgraph to update the k-core decomposition. We present incremental algorithms for both insertion and deletion operations, and propose auxiliary vertex state maintenance techniques that can further accelerate these operations. Our results show a significant reduction in runtime compared to non-incremental alternatives. We illustrate the efficiency of our algorithms on different types of real and synthetic graphs, at varying scales. Furthermore, for a graph of 16 million vertices, we observe relative throughputs reaching a million times, relative to the non-incremental algorithms.

97 MATHEMATICS AND COMPUTING↗

Decomposition Algorithm for Global Reachability Analysis on a Time-Varying Graph with an Application to Planetary Exploration

Hot air (Montgolfiere) balloons represent a promising vehicle system for possible future exploration of planets and moons with thick atmospheres such as Venus and Titan. To go to a desired location, this vehicle can primarily use the horizontal wind that varies with altitude, with a small help of its own actuation. A main challenge is how to plan such trajectory in a highly nonlinear and time-varying wind field. This paper poses this trajectory planning as a graph search on the space-time grid and addresses its computational aspects. When capturing various time scales involved in the wind field over the duration of long exploration mission, the size of the graph becomes excessively large. We show that the adjacency matrix of the graph is block-triangular, and by exploiting this structure, we decompose the large planning problem into several smaller subproblems, whose memory requirement stays almost constant as the problem size grows. The approach is demonstrated on a global reachability analysis of a possible Titan mission scenario.

Dijkstra's algorithm↗

A Block-Based Triangle Counting Algorithm on Heterogeneous Environments

Triangle counting is a fundamental building block in graph algorithms. In this article, we propose a block-based triangle counting algorithm to reduce data movement during both sequential and parallel execution. Our block-based formulation makes the algorithm naturally suitable for heterogeneous architectures. The problem of partitioning the adjacency matrix of a graph is well-studied. Our task decomposition goes one step further: it partitions the set of triangles in the graph. By streaming these small tasks to compute resources, we can solve problems that do not fit on a device. We demonstrate the effectiveness of our approach by providing an implementation on a compute node with multiple sockets, cores and GPUs. The current state-of-the-art in triangle enumeration processes the Friendster graph in 2.1 seconds, not including data copy time between CPU and GPU. Using that metric, our approach is 20 percent faster. When copy times are included, our algorithm takes 3.2 seconds. This is 5.6 times faster than the fastest published CPU-only time.

97 MATHEMATICS AND COMPUTING↗

A Block-Based Triangle Counting Algorithm on Heterogeneous Environments

Triangle counting is a fundamental building block in graph algorithms. In this paper, we propose a block-based triangle counting algorithm to reduce data movement during both sequential and parallel execution. Our block-based formulation makes the algorithm naturally suitable for heterogeneous architectures. The problem of partitioning the adjacency matrix of a graph is well-studied. Our task decomposition goes one step further: it partitions the set of triangles in the graph. By streaming these small tasks to compute resources, we can solve problems that do not fit on a device. We demonstrate the effectiveness of our approach by providing an implementation on a compute node with multiple sockets, cores and GPUs. The current state-of-the-art in triangle enumeration processes the Friendster graph in 2.1 seconds, not including data copy time between CPU and GPU. Using that metric, our approach is 20 percent faster. When copy times are included, our algorithm takes 3.2 seconds. This is 5.6 times faster than the fastest published CPU-only time.

97 MATHEMATICS AND COMPUTING↗

PURE: Scalable Phase Unwrapping with Spatial Redundant Arcs

Phase unwrapping is a key problem in many coherent imaging systems, such as syntheticapertureradar(SAR)interferometry. Ageneralformulationforredundant integration of finite differences for phase unwrapping (Costantini et al., 2010) was shown to produce a more reliable solution by exploiting redundant differential estimates. However, this technique requires a commercial linear programming solver for large-scale problems. For a linear cost function, we propose a method based on Dual Decomposition that breaks the given problem defined over a nonplanar graph into tractable sub-problems over planar subgraphs. We also propose a decomposition technique that exploits the underlying graph structure for solving thesub-problemsefficientlyandguaranteesasymptoticconvergencetotheglobally optimal solution. The experimental results demonstrate that the proposed approach is comparable to the existing state-of-the-art methods in terms of the estimate with a better runtime and memory footprint.

Lanka, Ravi↗

Cluster self-organization of intermetallic systems: Quasi-spherical nanocluster precursors with internal Friauf polyhedra (A-172) and icosahedra (B-137) in the Li{sub 19}Na{sub 8}Ba{sub 15} (hP842) crystal structure

A combinatorial and topological analysis of Li{sub 19}Na{sub 8}Ba{sub 15} (hP842, a = 20 A, c = 93 A, V = 33552 A{sup 3}, P3-bar) has been performed using computer methods (the TOPOS program package). Two types of crystal-forming quasi-spherical nanoclusters about 20 A in diameter with internal Friauf polyhedra (A-172) and icosahedra (B-137) have been established by the complete decomposition of the 3D factor graph of the structure into cluster substructures. Each type of nanoclusters forms close-packed 2D layers 3{sup 6}, which alternate along the c axis. The B-137 and A-172 nanoclusters are composed of three layers and have shell compositions (1 + 12 + 32 + 92) and (1 + 16 + 59 + 103) with local symmetries 3 and 3-bar, respectively; they were revealed for the first time in crystal structures as cluster precursors. The icosahedral B-137 nanocluster contains a 104-atom quasicrystal approximant (Samson cluster).

77 NANOSCIENCE AND NANOTECHNOLOGY↗

Decomposition Algorithms for Solving NP-hard Problems on a Quantum Annealer

NP-hard problems such as the maximum clique or minimum vertex cover problems, two of Karp’s 21 NP-hard problems, have several applications in computational chemistry, biochemistry and computer network security. Adiabatic quantum annealers can search for the optimum value of such NP-hard optimization problems, given the problem can be embedded on their hardware. However, this is often not possible due to certain limitations of the hardware connectivity structure of the annealer. This paper studies a general framework for a decomposition algorithm for NP-hard graph problems aiming to identify an optimal set of vertices. Our generic algorithm allows us to recursively divide an instance until the generated subproblems can be embedded on the quantum annealer hardware and subsequently solved. Furthermore, the framework is applied to the maximum clique and minimum vertex cover problems, and we propose several pruning and reduction techniques to speed up the recursive decomposition. The performance of both algorithms is assessed in a detailed simulation study.

97 MATHEMATICS AND COMPUTING↗

Optimized Lie–Trotter–Suzuki decompositions for two and three non-commuting terms

Lie–Trotter–Suzuki decompositions are an efficient way to approximate operator exponentials exp ( t H ) when H is a sum of n (non-commuting) terms which, individually, can be exponentiated easily. They are employed in time-evolution algorithms for tensor network states, digital quantum simulation protocols, path integral methods like quantum Monte Carlo, and splitting methods for symplectic integrators in classical Hamiltonian systems. Here, we provide optimized decompositions up to order t 6 . The leading error term is expanded in nested commutators (Hall bases) and we minimize the 1-norm of the coefficients. For n = 2 terms, several of the optima we find are close to those in McLachlan (1995). Generally, our results substantially improve over unoptimized decompositions by Forest, Ruth, Yoshida, and Suzuki. We explain why these decompositions are sufficient to efficiently simulate any one- or two-dimensional lattice model with finite-range interactions. This follows by solving a partitioning problem for the interaction graph.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Closing the Loop between In Situ Stress Complexity and EGS Fracture Complexity

We present an agent-guided approach to CAD geometry decomposition that automates hex/hybrid meshing with graph neural networks (GNNs) to accelerate next-generation ModSim workflows. Our end-to-end pipeline (i) reduces 3D boundary-representation (B-Rep) models to a 2D chordal axis skeleton (CAT) and then to a 1D bipartite graph of surface and curve nodes, (ii) assigns per node labels as Cubit® WebCut actions, (iii) trains a multi-action GNN under supervised learning, and (iv) predicts five surface-node and three curve-node actions on out-of-distribution test geometries. Each graph node carries geometric, topological, and meshing attributes drawn from the B-Rep “skin” and CAT “skeleton,” with two-way mappings across 3D↔2D↔1D representations to maintain traceability back to 3D CAD. The supervised learning model exhibits stable convergence of the binary cross-entropy loss and achieves 98.7% accuracy on unseen lattice models. To operationalize decision-making, we rank predicted commands by geometric significance and prototyped the agent-guided workflow through the Cubit® Meshing PowerTool GUI. As a stretch goal, we explore reinforcement learning (RL) to reduce or remove label requirements and to learn policies for action sequences that maximize total reward (e.g., size of hex-meshable regions and resulting hex mesh quality). When all-hex meshing is not feasible, the agent assists in producing hybrid meshes—prioritizing hex in critical regions and transitioning to tetrahedral elements (tets) elsewhere—maintaining fidelity while ensuring robustness. The overarching objective is to replace manual, heuristics-based decomposition with data-driven, reproducible automation, cutting meshing turnaround time by orders of magnitude. We anticipate direct impact on simulation workflows through intelligent, scalable decomposition of complex CAD models into hex-meshable subdomains.

42 ENGINEERING↗

The geometry of the light-cone cell decomposition of moduli space

The moduli space of Riemann surfaces with at least two punctures can be decomposed into a cell complex by using a particular family of ribbon graphs called Nakamura graphs. We distinguish the moduli space with all punctures labelled from that with a single labelled puncture. In both cases, we describe a cell decomposition where the cells are parametrised by graphs or equivalence classes of finite sequences (tuples) of permutations. Each cell is a convex polytope defined by a system of linear equations and inequalities relating light-cone string parameters, quotiented by the automorphism group of the graph. We give explicit examples of the cell decomposition at low genus with few punctures.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Benchmarking treewidth as a practical component of tensor network simulations

Tensor networks are powerful factorization techniques which reduce resource requirements for numerically simulating principal quantum many-body systems and algorithms. The computational complexity of a tensor network simulation depends on the tensor ranks and the order in which they are contracted. Unfortunately, computing optimal contraction sequences (orderings) in general is known to be a computationally difficult (NP-complete) task. In 2005, Markov and Shi showed that optimal contraction sequences correspond to optimal (minimum width) tree decompositions of a tensor network’s line graph, relating the contraction sequence problem to a rich literature in structural graph theory. While treewidth-based methods have largely been ignored in favor of dataset-specific algorithms in the prior tensor networks literature, we demonstrate their practical relevance for problems arising from two distinct methods used in quantum simulation: multi-scale entanglement renormalization ansatz (MERA) datasets and quantum circuits generated by the quantum approximate optimization algorithm (QAOA). We exhibit multiple regimes where treewidth-based algorithms outperform domain-specific algorithms, while demonstrating that the optimal choice of algorithm has a complex dependence on the network density, expected contraction complexity, and user run time requirements. We further provide an open source software framework designed with an emphasis on accessibility and extendability, enabling replicable experimental evaluations and future exploration of competing methods by practitioners.

97 MATHEMATICS AND COMPUTING↗

HyPAM: A hybrid continuum-particle model for incompressible free-surface flows

Three major issues associated with numerical simulations of complex free-surface flows, viz. interface tracking, fragmentation and large physical jumps, are addressed by a new hybrid continuum-particle model (HyPAM). The new model consists of three parts: (1) the Polygonal Area Mapping method [Q. Zhang, P.L.-F. Liu, A new interface tracking method: the polygonal area mapping method, J. Comput. Phys. 227(8) (2008) 4063-4088]; (2) a new algorithm that decomposes the interested (water) phase into a continuum zone, a buffer zone and a particle zone, based on material topology and graph theory; (3) a 'passive-response' assumption, in which the air phase is assumed to respond passively to the continuum part of the water phase. The incompressible inviscid Euler equations and the equations describing the free fall of rigid bodies are used as the governing equations for the continuum-buffer zone and the particle zone, respectively, and separately. A number of examples, including water droplet impact, solitary wave propagation, and dam-break problems, are simulated for the illustration and validation of HyPAM. It is shown that HyPAM is more accurate and versatile than a continuum-based Volume-of-Fluid model. One major contribution of this work is the single-phase decomposition algorithm, useful for many other hybrid formulations. Neglecting surface tension, viscosity and particle interactions, HyPAM is currently limited to mildly-fragmented free-surface flows with high Reynolds and Weber numbers.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Theoretically and practically efficient parallel nucleus decomposition

This paper studies the nucleus decomposition problem, which has been shown to be useful in finding dense substructures in graphs. We present a novel parallel algorithm that is efficient both in theory and in practice. Our algorithm achieves a work complexity matching the best sequential algorithm while also having low depth (parallel running time), which significantly improves upon the only existing parallel nucleus decomposition algorithm (Sariyüce et al. , PVLDB 2018). The key to the theoretical efficiency of our algorithm is a new lemma that bounds the amount of work done when peeling cliques from the graph, combined with the use of a theoretically-efficient parallel algorithms for clique listing and bucketing. We introduce several new practical optimizations, including a new multi-level hash table structure to store information on cliques space-efficiently and a technique for traversing this structure cache-efficiently. On a 30-core machine with two-way hyper-threading on real-world graphs, we achieve up to a 55x speedup over the state-of-the-art parallel nucleus decomposition algorithm by Sariyüce et al. , and up to a 40x self-relative parallel speedup. We are able to efficiently compute larger nucleus decompositions than prior work on several million-scale graphs for the first time.

Computer Science↗

Partitioning of unstructured problems for parallel processing

Many large-scale computational problems are based on unstructured computational domains. Primary examples are unstructured grid calculations based on finite volume methods in computational fluid dynamics, or structural analysis problems based on finite element approximations. The question of how to distribute such unstructured computational domains over a large number of processors in a MIMD machine with distributed memory is addressed. A graph theoretical framework for these problems is established. Based on this framework three decomposition algorithms are introduced. In particular a new decomposition algorithm is discussed, which is based on the computation of an eigenvector of the Laplacian matrix associated with the graph. Numerical comparisons on large-scale two- and three-dimensional problems demonstrate the superiority of the new spectral bisection algorithm.

Simon, H. D.↗

Solving Graph Laplacian Systems Through Recursive Bisections and Two-Grid Preconditioning

We present a parallelizable direct method for computing the solution to graph Laplacian-based linear systems derived from graphs that can be hierarchically bipartitioned with small edge cuts. For a graph of size n with constant-size edge cuts, our method decomposes a graph Laplacian in time O(n log n), and then uses that decomposition to perform a linear solve in time O(n log n). We then use the developed technique to design a preconditioner for graph Laplacians that do not have this property. Finally, we augment this preconditioner with a two-grid method that accounts for much of the preconditioner's weaknesses. We present an analysis of this method, as well as a general theorem for the condition number of a general class of two-grid support graph-based preconditioners. Numerical experiments illustrate the performance of the studied methods.

97 MATHEMATICS AND COMPUTING↗