Search NASA⌕ Search

SEARCH · Search NASA

Results for “partitioning algorithms”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 127 records · Page 7
All sourcesNASA NTRSDOE OSTI
NASA NTRS1991

Rectilinear partitioning of irregular data parallel computations

New mapping algorithms for domain oriented data-parallel computations, where the workload is distributed irregularly throughout the domain, but exhibits localized communication patterns are described. Researchers consider the problem of partitioning the domain for parallel processing in such a way that the workload on the most heavily loaded processor is minimized, subject to the constraint that the partition be perfectly rectilinear. Rectilinear partitions are useful on architectures that have a fast local mesh network. Discussed here is an improved algorithm for finding the optimal partitioning in one dimension, new algorithms for partitioning in two dimensions, and optimal partitioning in three dimensions. The application of these algorithms to real problems are discussed.

Nicol, David M.↗
NASA NTRS2003

Applications of Space-Filling-Curves to Cartesian Methods for CFD

The proposed paper presents a variety novel uses of Space-Filling-Curves (SFCs) for Cartesian mesh methods in 0. While these techniques will be demonstrated using non-body-fitted Cartesian meshes, most are applicable on general body-fitted meshes -both structured and unstructured. We demonstrate the use of single O(N log N) SFC-based reordering to produce single-pass (O(N)) algorithms for mesh partitioning, multigrid coarsening, and inter-mesh interpolation. The intermesh interpolation operator has many practical applications including warm starts on modified geometry, or as an inter-grid transfer operator on remeshed regions in moving-body simulations. Exploiting the compact construction of these operators, we further show that these algorithms are highly amenable to parallelization. Examples using the SFC-based mesh partitioner show nearly linear speedup to 512 CPUs even when using multigrid as a smoother. Partition statistics are presented showing that the SFC partitions are, on-average, within 10% of ideal even with only around 50,000 cells in each subdomain. The inter-mesh interpolation operator also has linear asymptotic complexity and can be used to map a solution with N unknowns to another mesh with M unknowns with O(max(M,N)) operations. This capability is demonstrated both on moving-body simulations and in mapping solutions to perturbed meshes for finite-difference-based gradient design methods.

Aftosmis, Michael J.↗
NASA NTRS2003

Applications of Space-Filling-Curves to Cartesian Methods for CFD

This paper presents a variety of novel uses of space-filling-curves (SFCs) for Cartesian mesh methods in CFD. While these techniques will be demonstrated using non-body-fitted Cartesian meshes, many are applicable on general body-fitted meshes-both structured and unstructured. We demonstrate the use of single theta(N log N) SFC-based reordering to produce single-pass (theta(N)) algorithms for mesh partitioning, multigrid coarsening, and inter-mesh interpolation. The intermesh interpolation operator has many practical applications including warm starts on modified geometry, or as an inter-grid transfer operator on remeshed regions in moving-body simulations Exploiting the compact construction of these operators, we further show that these algorithms are highly amenable to parallelization. Examples using the SFC-based mesh partitioner show nearly linear speedup to 640 CPUs even when using multigrid as a smoother. Partition statistics are presented showing that the SFC partitions are, on-average, within 15% of ideal even with only around 50,000 cells in each sub-domain. The inter-mesh interpolation operator also has linear asymptotic complexity and can be used to map a solution with N unknowns to another mesh with M unknowns with theta(M + N) operations. This capability is demonstrated both on moving-body simulations and in mapping solutions to perturbed meshes for control surface deflection or finite-difference-based gradient design methods.

Aftosmis, M. J.↗
NASA NTRS1991

Fast, efficient lossless data compression

This paper presents lossless data compression and decompression algorithms which can be easily implemented in software. The algorithms can be partitioned into their fundamental parts which can be implemented at various stages within a data acquisition system. This allows for efficient integration of these functions into systems at the stage where they are most applicable. The algorithms were coded in Forth to run on a Silicon Composers Single Board Computer (SBC) using the Harris RTX2000 Forth processor. The algorithms require very few system resources and operate very fast. The performance of the algorithms with the RTX enables real time data compression and decompression to be implemented for a wide range of applications.

Ross, Douglas↗
DOE OSTI2025

Overset-Grid Method with Smooth Orbital Partitioning for Molecular Scattering Calculations

To solve molecular photoionization and electron scattering problems, we use an overset-grid representation of electronic continuum functions, which has an extended central spherical grid that overlaps small spherical grids (subgrids) centered on each atom of a polyatomic molecule. Here, in this work, we present an improved algorithm that smoothly partitions the total wave function between the central grid and the atomic subgrids. The smooth partitioning allows one to use approximately one-fourth the number of partial waves on the central grid compared to our previous implementation with switching functions. The resulting numerical method for treating electron scattering and photoionization of polyatomic molecules combines the accuracy and flexibility of pure numerical grid representations with the rapid convergence of hybrid combinations of atom-centered basis-set expansions and grid methods. The overset-grid representation is implemented using the complex Kohn variational principle for scattering and photoionization amplitudes. The faster convergence with respect to the number of central grid partial waves is demonstrated and accuracy is verified by comparisons with the previous implementation and with far more computationally demanding single-center numerical expansions in electron-molecule scattering and photoionization calculations on the neon dimer (Ne 2 ) system, carbon tetrafluoride (CF 4 ) molecule, and the pyridine (C 5 H 5 N) molecule in the static-exchange approximation.

Molecules↗
DOE OSTI2017

Computation of disordered system from the first principles of classical mechanics and ℕℙ hard problem

We study the classical 1D Heisenberg spin glasses in the framework of nearest-neighboring model. Based on the Hamilton equations we obtained the system of recurrence equations which allows to perform node-by-node calculations of a spin-chain. It is shown that calculations from the first principles of classical mechanics lead to ℕℙ hard problem, that however in the limit of the statistical equilibrium can be calculated by ℙ algorithm. For the partition function of the ensemble a new representation is offered in the form of one-dimensional integral of spin-chains’ energy distribution.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2024

Quantum Tensor-Product Decomposition from Choi-State Tomography

The Schmidt decomposition is the go-to tool for measuring bipartite entanglement of pure quantum states. Similarly, it is possible to study the entangling features of a quantum operation using its operator-Schmidt or tensor-product decomposition. While quantum technological implementations of the former are thoroughly studied, entangling properties on the operator level are harder to extract in the quantum computational framework because of the exponential nature of sample complexity. Here, we present an algorithm for unbalanced partitions into a small subsystem and a large one (the environment) to compute the tensor-product decomposition of a unitary the effect of which on the small subsystem is captured in classical memory, while the effect on the environment is accessible as a quantum resource. This quantum algorithm may be used to make predictions about operator nonlocality and effective open quantum dynamics on a subsystem, as well as for finding low-rank approximations and low-depth compilations of quantum circuit unitaries. We demonstrate the method and its applications on a time-evolution unitary of an isotropic Heisenberg model in two dimensions. Published by the American Physical Society 2024

Mansuroglu, Refik (ORCID:000000017352513X)↗
NASA NTRS1987

A dual-processor multi-frequency implementation of the FINDS algorithm

This report presents a parallel processing implementation of the FINDS (Fault Inferring Nonlinear Detection System) algorithm on a dual processor configured target flight computer. First, a filter initialization scheme is presented which allows the no-fail filter (NFF) states to be initialized using the first iteration of the flight data. A modified failure isolation strategy, compatible with the new failure detection strategy reported earlier, is discussed and the performance of the new FDI algorithm is analyzed using flight recorded data from the NASA ATOPS B-737 aircraft in a Microwave Landing System (MLS) environment. The results show that low level MLS, IMU, and IAS sensor failures are detected and isolated instantaneously, while accelerometer and rate gyro failures continue to take comparatively longer to detect and isolate. The parallel implementation is accomplished by partitioning the FINDS algorithm into two parts: one based on the translational dynamics and the other based on the rotational kinematics. Finally, a multi-rate implementation of the algorithm is presented yielding significantly low execution times with acceptable estimation and FDI performance.

Godiwala, Pankaj M.↗
DOE OSTI2018

Detecting Anomalies from End-to-End Internet Performance Measurements (PingER) Using Cluster Based Local Outlier Factor

PingER (Ping End-to-End Reporting) is a worldwide end-to-end Internet performance measurement framework. It was developed by the SLAC National Accelerator Laboratory, Stanford, USA and running from the last 20 years. It has more than 700 monitoring agents and remote sites which monitor the performance of Internet links around 170 countries of the world. At present, the size of the compressed PingER data set is about 60 GB comprising of 100,000 flat files. The data is publicly available for valuable Internet performance analyses. However, the data sets suffer from missing values and anomalies due to congestion, bottleneck links, queuing overflow, network software misconfiguration, hardware failure, cable cuts, and social upheavals. Therefore, the objective of this paper is to detect such performance drops or spikes labeled as anomalies or outliers for the PingER data set. In the proposed approach, the raw text files of the data set are transformed into a PingER dimensional model. The missing values are imputed using the k-NN algorithm. The data is partitioned into similar instances using the k-means clustering algorithm. Afterward, clustering is integrated with the Local Outlier Factor (LOF) using the Cluster Based Local Outlier Factor (CBLOF) algorithm to detect the anomalies or outliers from the PingER data. Lastly, anomalies are further analyzed to identify the time frame and location of the hosts generating the major percentage of the anomalies in the PingER data set ranging from 1998 to 2016.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

A Higher Order, Stable Partitioned Scheme for Fluid-Structure Interaction Problems

Although still a very active area of research with many open questions, there exist highly-accurate and efficient algorithms for numerically estimating solutions to the equations of fluid motion. Similarly, great strides have been made in numerically modeling the motion of solids. However, there exist many practical applications where one must solve both fluid and structure in tandem. There is a gap in the literature for high order unconditionally stable partitioned algorithms for problems of this type. We investigate a new partitioned scheme which shows promise in filling this gap. We use a finite-element-based model with an added mass approach on problems coupling the Euler beam equation with the incompressible Navier-Stokes equations.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Accelerated impurity solver for DMFT and its diagrammatic extensions

Here, we present ComCTQMC, a GPU accelerated quantum impurity solver. It uses the continuous-time quantum Monte Carlo (CTQMC) algorithm wherein the partition function is expanded in terms of the hybridisation function (CT-HYB). ComCTQMC supports both partition and worm-space measurements, and it uses improved estimators and the reduced density matrix to improve observable measurements whenever possible. ComCTQMC efficiently measures all one and two-particle Green's functions, all static observables which commute with the local Hamiltonian, and the occupation of each impurity orbital. ComCTQMC can solve complex-valued impurities with crystal fields that are hybridized to both fermionic and bosonic baths. Most importantly, ComCTQMC utilizes graphical processing units (GPUs), if available, to dramatically accelerate the CTQMC algorithm when the Hilbert space is sufficiently large. We demonstrate acceleration by a factor of over 600 (100) in a simulation of δ-Pu at 600 K with (without) crystal fields. In easier problems, the GPU offers less impressive acceleration or even decelerates the CTQMC. Here we describe the theory, algorithms, and structure used by ComCTQMC in order to achieve this set of features and level of acceleration.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2017

A physics-motivated Centroidal Voronoi Particle domain decomposition method

In this paper, we propose a novel domain decomposition method for large-scale simulations in continuum mechanics by merging the concepts of Centroidal Voronoi Tessellation (CVT) and Voronoi Particle dynamics (VP). The CVT is introduced to achieve a high-level compactness of the partitioning subdomains by the Lloyd algorithm which monotonically decreases the CVT energy. The number of computational elements between neighboring partitioning subdomains, which scales the communication effort for parallel simulations, is optimized implicitly as the generated partitioning subdomains are convex and simply connected with small aspect-ratios. Moreover, Voronoi Particle dynamics employing physical analogy with a tailored equation of state is developed, which relaxes the particle system towards the target partition with good load balance. Since the equilibrium is computed by an iterative approach, the partitioning subdomains exhibit locality and the incremental property. Numerical experiments reveal that the proposed Centroidal Voronoi Particle (CVP) based algorithm produces high-quality partitioning with high efficiency, independently of computational-element types. Thus it can be used for a wide range of applications in computational science and engineering.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2019

A scalable mixed-integer decomposition approach for optimal power system restoration

The optimal restoration problem lies at the foundation of the evaluation and improvement of resilience in power systems. In this paper we present a scalable decomposition algorithm, based on the integer L-shaped method, for solving this problem for realistic power systems. The algorithm works by partitioning the problem into a master problem and a slave problem. The master problem optimizes over energization sequences of generators, buses and branches, for the entire restoration horizon, while respecting stylized energization requirements. The slave problem verifies that there exist power flow solutions supporting the energization sequences proposed by the master problem, adding cuts to the master if an infeasible sequence is detected. The power flow verification is carried out using a piece-wise linear approximation of the power flow equations, capable of capturing overvoltage situations common in restoration procedures. We develop specialized binary cuts and hybrid Benders-binary cuts for separating infeasible islands, which are stronger than regular no-good cuts, as well as heuristics for obtaining feasible solutions. We present numerical results for the IEEE 39- and 118-bus systems, and for the Chilean 1500-bus grid, where our algorithm finds near-optimal restoration sequences orders of magnitude faster than the state-of-the-art, demonstrating the effectiveness of the proposed approach.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2016

A low-communication, parallel algorithm for solving PDEs based on range decomposition

This work proposes a new, low-communication algorithm for solving PDEs on massively parallel computers. The range decomposition (RD) algorithm exposes coarse-grain parallelism by applying nested iteration and adaptive mesh refinement locally before performing a global communication step. Just a few such steps are observed to be sufficient to obtain accuracy within a small multiple of discretization error. The target applications are petascale and exascale machines, where hierarchical parallelism is required and traditional parallel numerical PDE communication patterns are costly because of message latency. The RD algorithm uses a partition of unity to equally distribute the error, and thus, the work. The computational advantages of this approach are that the decomposed problems can be solved in parallel without any communication until the partitioned solutions are summed. This offers potential advantages in the paradigm of expensive communication but very cheap computation. This paper introduces the method and explains the details of the communication step. Two performance models are developed, showing that the latency cost associated with a traditional parallel implementation of nested iteration is proportional to log(P) 2 , whereas the RD method reduces the communication latency to log(P), while maintaining similar bandwidth costs. Numerical results for two problems, Laplace and advection diffusion, demonstrate the enhanced performance, and a heuristic argument explains why the method converges quickly.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Machine learning-aided inverse design for biogas upgrading through biological CO 2 conversion

The biogas upgrading process through bioconversion of CO 2 to CH 4 by hydrogenotrophic methanogens is an attractive strategy for energy decarbonation. Many studies have optimized operational parameters to improve key performance indicators such as CH 4 % and H 2 utilization efficiency. However, inconsistent laboratory conditions make it challenging to compare results. Existing models for analyzing operating conditions can only assess the impact of individual conditions and lack the ability to simultaneously optimize multiple conditions. To address this, two XGBoost models were built with R 2 of 0.779 and 0.903 with data collected from literatures and were embedded into multi-objective partitive swarm optimization algorithm to optimal operating conditions. Predictions were compared with experimental validations under optimized conditions, revealing an 8.50% and 2.95% relative error in CH 4 % and H 2 conversion rate, respectively. This approach streamlines biogas upgrading processes, offering a data-driven solution to enhance efficiency and consistency in the pursuit of sustainable methane production.

Biogas upgrading↗
DOE OSTI2020

A High-Throughput Solver for Marginalized Graph Kernels on GPU

Here, we present the design and optimization of a solver for efficient and high-throughput computation of the marginalized graph kernel on General Purpose GPUs. The graph kernel is computed using the conjugate gradient method to solve a generalized Laplacian of the tensor product between a pair of graphs. To cope with the large gap between the instruction throughput and the memory bandwidth of the GPUs, our solver forms the graph tensor product on-the-fly without storing it in memory. This is achieved by using threads in a warp cooperatively to stream the adjacency and edge label matrices of individual graphs by small square matrix blocks called tiles, which are then staged in registers and the shared memory for later reuse. Warps across a thread block can further share tiles via the shared memory to increase data reuse. We exploit the sparsity of the graphs hierarchically by storing only non-empty tiles using a coordinate format and nonzero elements within each tile using bitmaps. We propose a new partition-based reordering algorithm for aggregating nonzero elements of the graphs into fewer but denser tiles to further exploit sparsity. We carry out extensive theoretical analyses on the graph tensor product primitives for tiles of various density and evaluate their performance on synthetic and real-world datasets. Our solver delivers three to four orders of magnitude speedup over existing CPU-based solvers such as GraKeL and GraphKernels. The capability of the solver enables kernel-based learning tasks at unprecedented scales.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2019

Stochastic Optimization for Grid Resilience. FY18 Final Technical Report

The optimal restoration problem lies at the foundation of the evaluation and improvement of resilience in power systems. In this report we present a scalable decomposition algorithm for solving this problem for realistic power systems. The algorithm has been developed in three major research threads, corresponding to the chapters in the present report. Chapter 1 studies mixed-integer programming (MIP) formulations for the requirement that each electrical island that appears after a recon guration must have at least one energized generator. We provide three alternative MIP formulations for this restriction, show their equivalence, and prove that two of them are stronger in terms of their linear programming relaxation than the formulation most commonly used in the power systems literature. Since the time to solve MIPs can vary signi cantly between equivalent formulations, we also present computational experiments on IEEE test systems for the Intentional Controlled Islanding (ICI) and the Black Start Allocation (BSA) problems. We observe that a polynomially separable, exponential in size, strong formulation yields the best performance for the BSA problem and exhibits a comparable performance to a linear in size, weak formulation for the ICI problem. Chapter 2 presents a methodology to generate mixed-integer linear approximations of the AC power ow equations governing lines, transformers (including tap regulators and phase shifters), shunt and series compensators, and consumption responsive to voltage. Our approximations are capable of capturing limitations for power grids under abnormal or uncommon operating conditions where common assumptions used in power ow relaxations may not hold. Particularly, the approximation captures overvoltages under almost no load, which is a major concern when energizing lines after a blackout. The method constructs piecewise linear approximations of the non-linear power ow equations by minimizing the squared approximation error over a subset of the feasible domain. We test the method using a realistic database for the Chilean system (1548 buses, 1114 lines, 564 transformers). The resulting approximations yield root mean square errors in the order of 0.05pu and are successfully applied to solve a transmission switching instance for the Chilean system. Chapter 3 presents our algorithm for optimal restoration. The algorithm works by partitioning the problem into a master problem and a slave problem. The master problem optimizes over energization sequences of generators, buses and branches, for the entire restoration horizon, while respecting the energization requiments studied in Chapter 1. The slave problem veri es that there exist power ow solutions supporting the energization sequences proposed by the master problem, adding cuts to the master if an infeasible sequence is detected.

24 POWER TRANSMISSION AND DISTRIBUTION↗
NASA NTRS1987

Performance studies of the multigrid algorithms implemented on hypercube multiprocessor systems

In this paper, we analyze and compare the performance on a hypercube multiprocessor of some of the major multigrid techniques used in practice. The model problem considered here is that of solving the 2-D incompressible Navier-Stokes equations representing the flow between two parallel plates. Results obtained by implementing the different multigrid schemes on an iPSC are presented. Effects on the overall performance of various parameters of the algorithms, of the partitioning strategies employed, and of some of the characteristics of the underlying architecture are discussed.

Naik, Vijay K.↗