Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “partitioned algorithm”

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 163 records · Page 9
All sourcesNASA NTRSDOE OSTI
NASA NTRS1990

Optimal parallel solution of sparse triangular systems

A method for the parallel solution of triangular sets of equations is described that is appropriate when there are many right-handed sides. By preprocessing, the method can reduce the number of parallel steps required to solve Lx = b compared to parallel forward or backsolve. Applications are to iterative solvers with triangular preconditioners, to structural analysis, or to power systems applications, where there may be many right-handed sides (not all available a priori). The inverse of L is represented as a product of sparse triangular factors. The problem is to find a factored representation of this inverse of L with the smallest number of factors (or partitions), subject to the requirement that no new nonzero elements be created in the formation of these inverse factors. A method from an earlier reference is shown to solve this problem. This method is improved upon by constructing a permutation of the rows and columns of L that preserves triangularity and allow for the best possible such partition. A number of practical examples and algorithmic details are presented. The parallelism attainable is illustrated by means of elimination trees and clique trees.

Alvarado, Fernando L.↗
NASA NTRS1996

Spray Combustion Modeling with VOF and Finite-Rate Chemistry

A spray atomization and combustion model is developed based on the volume-of-fluid (VOF) transport equation with finite-rate chemistry model. The gas-liquid interface mass, momentum and energy conservation laws are modeled by continuum surface force mechanisms. A new solution method is developed such that the present VOF model can be applied for all-speed range flows. The objectives of the present study are: (1) to develop and verify the fractional volume-of-fluid (VOF) cell partitioning approach into a predictor-corrector algorithm to deal with multiphase (gas-liquid) free surface flow problems; (2) to implement the developed unified algorithm in a general purpose computational fluid dynamics (CFD) code, Finite Difference Navier-Stokes (FDNS), with droplet dynamics and finite-rate chemistry models; and (3) to demonstrate the effectiveness of the present approach by simulating benchmark problems of jet breakup/spray atomization and combustion. Modeling multiphase fluid flows poses a significant challenge because a required boundary must be applied to a transient, irregular surface that is discontinuous, and the flow regimes considered can range from incompressible to highspeed compressible flows. The flow-process modeling is further complicated by surface tension, interfacial heat and mass transfer, spray formation and turbulence, and their interactions. The major contribution of the present method is to combine the novel feature of the Volume of Fluid (VOF) method and the Eulerian/Lagrangian method into a unified algorithm for efficient noniterative, time-accurate calculations of multiphase free surface flows valid at all speeds. The proposed method reformulated the VOF equation to strongly couple two distinct phases (liquid and gas), and tracks droplets on a Lagrangian frame when spray model is required, using a unified predictor-corrector technique to account for the non-linear linkages through the convective contributions of VOF. The discontinuities within the sharp interface will be modeled as a volume force to avoid stiffness. Formations of droplets, tracking of droplet dynamics and modeling of the droplet breakup/evaporation, are handled through the same unified predictor-corrector procedure. Thus the new algorithm is non-iterative and is flexible for general geometries with arbitrarily complex topology in free surfaces. The FDNS finite-difference Navier-Stokes code is employed as the baseline of the current development. Benchmark test cases of shear coaxial LOX/H2 liquid jet with atomization/combustion and impinging jet test cases are investigated in the present work. Preliminary data comparisons show good qualitative agreement between data and the present analysis. It is indicative from these results that the present method has great potential to become a general engineering design analysis and diagnostics tool for problems involving spray combustion.

Chen, Yen-Sen↗
NASA NTRS1995

Numerical modeling of spray combustion with an advanced VOF method

This paper summarizes the technical development and validation of a multiphase computational fluid dynamics (CFD) numerical method using the volume-of-fluid (VOF) model and a Lagrangian tracking model which can be employed to analyze general multiphase flow problems with free surface mechanism. The gas-liquid interface mass, momentum and energy conservation relationships are modeled by continuum surface mechanisms. A new solution method is developed such that the present VOF model can be applied for all-speed flow regimes. The objectives of the present study are to develop and verify the fractional volume-of-fluid cell partitioning approach into a predictor-corrector algorithm and to demonstrate the effectiveness of the present approach by simulating benchmark problems including laminar impinging jets, shear coaxial jet atomization and shear coaxial spray combustion flows.

Chen, Yen-Sen↗
NASA NTRS1994

Atomization simulations using an Eulerian-VOF-Lagrangian method

This paper summarizes the technical development and validation of a multiphase computational fluid dynamics (CFD) numerical method using the volume-of-fluid (VOF) model and a Lagrangian tracking model which can be employed to analyze general multiphase flow problems with free surface mechanism. The gas-liquid interface mass, momentum and energy conservations are modeled by continuum surface mechanisms. A new solution method is developed such that the present VOF model can be applied for all-speed flow regimes. The objectives of the present study are to develop and verify the fractional volume-of-fluid cell partitioning approach into a predictor-corrector algorithm and to demonstrate the effectiveness of the present innovative approach by simulating benchmark problems including the coaxial jet atomization.

Chen, Yen-Sen↗
NASA NTRS1988

A multistage linear array assignment problem

The implementation of certain algorithms on parallel processing computing architectures can involve partitioning contiguous elements into a fixed number of groups, each of which is to be handled by a single processor. It is desired to find an assignment of elements to processors that minimizes the sum of the maximum workloads experienced at each stage. This problem can be viewed as a multi-objective network optimization problem. Polynomially-bounded algorithms are developed for the case of two stages, whereas the associated decision problem (for an arbitrary number of stages) is shown to be NP-complete. Heuristic procedures are therefore proposed and analyzed for the general problem. Computational experience with one of the exact problems, incorporating certain pruning rules, is presented with one of the exact problems. Empirical results also demonstrate that one of the heuristic procedures is especially effective in practice.

Nicol, David M.↗
DOE OSTI2024

Picasso: Memory-Efficient Graph Coloring Using Palettes With Applications in Quantum Computing

A coloring of a graph is an assignment of colors to vertices such that no two neighboring vertices have the same color. The need for memory-efficient coloring algorithms is motivated by their application in computing clique partitions of graphs arising in quantum computations where the objective is to map a large set of Pauli strings into a compact set of unitaries. We present Picasso, a randomized memory-efficient iterative parallel graph coloring algorithm with theoretical sublinear space guarantees under practical assumptions. The parameters of our algorithm provide a trade-off between coloring quality and resource consumption. To assist the user, we also propose a machine learning model to predict the coloring algorithm’s parameters considering these trade-offs. We provide a sequential and a parallel implementation of the proposed algorithm. We perform an experimental evaluation on a 64-core AMD CPU equipped with 512 GB of memory and an Nvidia A100 GPU with 40GB of memory. For a small dataset where existing coloring algorithms can be executed within the 512 GB memory budget, we show up to 68× memory savings. On massive datasets we demonstrate that GPU-accelerated Picasso can process inputs with 49.5× more Pauli strings (vertex set in our graph) and 2,478× more edges than state-of-the-art parallel approaches.

artificial intelligence, quantum computing↗
NASA NTRS1994

Detecting bimodality in astronomical datasets

We discuss statistical techniques for detecting and quantifying bimodality in astronomical datasets. We concentrate on the KMM algorithm, which estimates the statistical significance of bimodality in such datasets and objectively partitions data into subpopulations. By simulating bimodal distributions with a range of properties we investigate the sensitivity of KMM to datasets with varying characteristics. Our results facilitate the planning of optimal observing strategies for systems where bimodality is suspected. Mixture-modeling algorithms similar to the KMM algorithm have been used in previous studies to partition the stellar population of the Milky Way into subsystems. We illustrate the broad applicability of KMM by analyzing published data on globular cluster metallicity distributions, velocity distributions of galaxies in clusters, and burst durations of gamma-ray sources. FORTRAN code for the KMM algorithm and directions for its use are available from the authors upon request.

Ashman, Keith A.↗
DOE OSTI2023

Tools for analysis of optimization models

The software is code for analyzing, debugging, and solving optimization models. The code implements several algorithms and provides convenient APIs to apply these algorithms to optimization models. The algorithms are primarily based on graph theory. They compute well-known partitions of graphs, and use these partitions to provide the user information about their optimization model, including diagnosing certain types of structural modeling errors. Some algorithms may be used as a subroutine to solve an optimization problem, and may call an optimization solver to facilitate this. Well-known linear algebra routines are called to provide further diagnostics. The software contains no data and no models other than toy models used for testing.

Parker, Robert↗
DOE OSTI2020

The Case for Strong Scaling in Deep Learning: Training Large 3D CNNs with Hybrid Parallelism

Here, we present scalable hybrid-parallel algorithms for training large-scale 3D convolutional neural networks. Deep learning-based emerging scientific workflows often require model training with large, high-dimensional samples, which can make training much more costly and even infeasible due to excessive memory usage. We solve these challenges by extensively applying hybrid parallelism throughout the end-to-end training pipeline, including both computations and I/O. Our hybrid-parallel algorithm extends the standard data parallelism with spatial parallelism, which partitions a single sample in the spatial domain, realizing strong scaling beyond the mini-batch dimension with a larger aggregated memory capacity. We evaluate our proposed training algorithms with two challenging 3D CNNs, CosmoFlow and 3D U-Net. Our comprehensive performance studies show that good weak and strong scaling can be achieved for both networks using up to 2K GPUs. More importantly, we enable training of CosmoFlow with much larger samples than previously possible, realizing an order-of-magnitude improvement in prediction accuracy.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Race conditions and data partitioning: risks posed by common errors to reproducible parallel simulations

When parallel algorithms for simulation were introduced in the 1970s, their development and use interested only experts in parallel computation. This circumstance changed as multi-core processors became commonplace, putting a parallel computer into the hands of every modeler. A natural outcome is growing interest in parallel simulation among persons not intimately familiar with parallel computing. At the same time, parallel simulation tools continue to be developed with the implicit assumption that the modeler is knowledgeable about parallel programming. The unintended consequence is a rapidly growing number of users of parallel simulation tools that are unlikely to recognize when the interaction of race conditions, partitioning strategies, and simultaneous action in their simulation models make results non-reproducible, thereby calling into question the validity of conclusions drawn from the simulation data. Here, we illustrate the potential dangers of exposing parallel algorithms to users who are not experts in parallel computation with example models constructed using existing parallel simulation tools. By doing so, we hope to refocus tool developers on usability, even if this new focus incurs loss of some performance.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS2015

Hybrid Glacier Inventory, Gravimetry and Altimetry (HIGA) Mass Balance Product for Greenland and the Canadian Arctic

We present a novel inversion algorithm that generates a mass balance field that is simultaneously consistent with independent observations of glacier inventory derived from optical imagery, cryosphere-attributed mass trends derived from satellite gravimetry, and ice surface elevation trends derived from airborne and satellite altimetry. We use this algorithm to assess mass balance across Greenland and the Canadian Arctic over the Sep-2003 to Oct- 2009 period at 26 kilometers resolution. We evaluate local algorithm-inferred mass balance against forty in situ point observations. This evaluation yields a root mean squared error (RMSE) of 0.15 mWE/a ( 0.15 meters (water equivalent) per annum), and highlights a paucity of in situ observations from regions of high dynamic mass loss and peripheral glaciers. We assess mass losses of 212 plus or minus 67 Gigatons per annum to the Greenland ice sheet proper, 38 Gigatons per annum to peripheral glaciers in Greenland, and 42 Gigatons per annum to glaciers in the Canadian Arctic. These magnitudes of mass loss are dependent on the gravimetry-derived spherical harmonic mass trend we invert. We spatially partition the transient glacier continuity equation by differencing algorithm inferred mass balance from modeled surface mass balance, in order to solve the horizontal divergence of ice flux as a residual. This residual ice dynamic field infers flux divergence (or submergent flow) in the ice sheet accumulation area and at tidewater margins, and flux convergence (or emergent flow) in land-terminating ablation areas, which is consistent with continuum mechanics theory.

Altimetry↗
NASA NTRS1993

(abstract) 3D Electromagnetic Plasma Particle Simulations

A 3D electromagnetic plasma particle-in-cell code has been developed using the General Concurrent PIC algorithm. The GCPIC algorithm uses a domain decomposition to divide the computation among the processors. Particles must be exchanged between processors as they move. The efficiencies for 1-, 2-, and 3-dimensional partitions of the three dimensional domain are compared, and the algorithm is found to be very efficient even when a large fraction (e.g., 30%) of the particles must be exchanged at every time step. This PIC code has been used to perform simulations of a variety of space plasma physics problems. Results of three applications will be discussed: 1) plasma disturbances induced by moving conducting bodies in a magnetized plasma; 2) plasma plume interactions; and 3) solar wind termination shock.

electromagnetic plasma particles simulations 3D al↗
NASA NTRS1976

Recursive partitioned inversion of large (1500 x 1500) symmetric matrices

A recursive algorithm was designed to invert large, dense, symmetric, positive definite matrices using small amounts of computer core, i.e., a small fraction of the core needed to store the complete matrix. The described algorithm is a generalized Gaussian elimination technique. Other algorithms are also discussed for the Cholesky decomposition and step inversion techniques. The purpose of the inversion algorithm is to solve large linear systems of normal equations generated by working geodetic problems. The algorithm was incorporated into a computer program called SOLVE. In the past the SOLVE program has been used in obtaining solutions published as the Goddard earth models.

Putney, B. H.↗
DOE OSTI2020

Wave function analysis with a maximum flow algorithm

An efficient algorithm for computing the maximum-flow path in a network is applied to the identification of the dominant configuration state functions (CSFs) in a graphically contracted function (GCF), configuration interaction, wave function. The flow network is a space of spin-adapted CSFs represented by a Shavitt graph, wherein the nodes correspond to orbital occupations and spin quantum numbers. The graph nodes are connected by arcs, and an arc density is defined as sums of the associated squared CSF coefficients. A max-min approach determines an upper bound to the maximum possible incoming flow for each graph node. A backtracking step generates a candidate walk and is followed by a limited search of alternative branching paths for the dominant CSF. The arc density contributions are removed from the graph, and the algorithm is reapplied to the updated graph. This list of generated walks can be partitioned in order to guarantee that the dominant CSFs have been identified. All of the steps in this algorithm are computationally efficient and do not depend on the potentially large dimension of the underlying linear CSF expansion space. An analysis of low-lying valence states of C-2 illustrates the method.

74 ATOMIC AND MOLECULAR PHYSICS↗
DOE OSTI2023

Solving 3d gravity with Virasoro TQFT

We propose a precise reformulation of 3d quantum gravity with negative cosmological constant in terms of a topological quantum field theory based on the quantization of the Teichmüller space of Riemann surfaces that we refer to as “Virasoro TQFT”. This TQFT is similar, but importantly not equivalent, to SL(2, \mathbb{R} ℝ ) Chern-Simons theory. This sharpens the folklore that 3d gravity is related to SL(2, \mathbb{R} ℝ ) Chern-Simons theory into a precise correspondence, and resolves some well-known issues with this lore at the quantum level. Our proposal is computationally very useful and provides a powerful tool for the further study of 3d gravity. In particular, we explain how together with standard TQFT surgery techniques this leads to a fully algorithmic procedure for the computation of the gravity partition function on a fixed topology exactly in the central charge. Mathematically, the relation leads to many nontrivial conjectures for hyperbolic 3-manifolds, Virasoro conformal blocks and crossing kernels.

Collier, Scott↗
NASA NTRS1986

Network design consideration of a satellite-based mobile communications system

Technical considerations for the Mobile Satellite Experiment (MSAT-X), the ground segment testbed for the low-cost spectral efficient satellite-based mobile communications technologies being developed for the 1990's, are discussed. The Network Management Center contains a flexible resource sharing algorithm, the Demand Assigned Multiple Access scheme, which partitions the satellite transponder bandwidth among voice, data, and request channels. Satellite use of multiple UHF beams permits frequency reuse. The backhaul communications and the Telemetry, Tracking and Control traffic are provided through a single full-coverage SHF beam. Mobile Terminals communicate with the satellite using UHF. All communications including SHF-SHF between Base Stations and/or Gateways, are routed through the satellite. Because MSAT-X is an experimental network, higher level network protocols (which are service-specific) will be developed only to test the operation of the lowest three levels, the physical, data link, and network layers.

Yan, T.-Y.↗
DOE OSTI2022

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↗