Search NASA⌕ Search

SEARCH · Search NASA

Results for “Parallel 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 1,189 records · Page 66
All sourcesNASA NTRSDOE OSTI
NASA NTRS1994

Accelerated panel methods using the fast multipole method

Panel methods are commonly used in computational fluid dynamics for the solution of potential flow problems. The methods are a numerical technique based on the surface distribution of singularity elements. The solution is the process of finding the strength of the singularity elements distributed over the body's surface. This process involves the solution of the matrix problem Pq = p' for a set of unknowns q. The Fast Multipole Method is used to directly compute q without using matrix solvers. The algorithm works in O(N) time for N points, a great improvement over standard matrix solvers. In panel methods, the surface of a body is divided into a series of quadrilateral panels. The methods involve the computation of the influence of all other panels on each individual panel. The influence is based on the surface distribution, though this can be approximated by the area for distant panels. An alternative approximation, though with arbitrary accuracy, is to develop a multipole expansion about the center of the panel to describe the effect of a given panel on distant points in space. The expansion is based on the moments of the panel, thus allow the use of various surface distributions without changing the basic algorithm, just the computation of the various moments. The expansions are then manipulated in a tree walk to develop Taylor series expansions about a point in space which describe the effect of all distant panels on any point within a volume of convergence. The effect of near panels then needs to be computed directly, but the effect of all distant panels can be computed by simply evaluating the resulting expansion. The Fast Multipole Method has been applied to panel methods for the solution of source and doublet distributions. A major feature of the algorithm is that the algorithm does not change to derive the potential and velocity for sources and doublets. The same expansions can be used for both sources and doublets. Since the velocity is related to the potential, and the doublet potential is related to the z-component of the source velocity, all values can be derived from the same expansion by taking a series of partial derivatives. This requires more expansion terms to be kept since terms are lost in the process of taking partial derivatives. Thus to maintain accuracy for the doublet computation, more terms are required than if just evaluating for sources. The resulting Fast Multipole code should then parallelize better than classical panel methods due to the locality of data dependencies found in the Fast Multipole Method. Theoretically the parallelized code should execute in O(log N) time with O(N) processors, though this is not practical. Ongoing work includes implementing the parallel accelerated panel method, including methods to improve the load balancing of the problem by taking advantage of the known geometry of panels, and to encorporate sensitivity analysis into the algorithm.

Leathrum, James F., Jr.↗
DOE OSTI2024

Plastic Parallel Pathways Platform - 4P Model

Global momentum is building towards a circular economy capable of keeping plastics in use and out of waste streams. Given that 79% of all plastic produced since 1950 has accumulated in landfills or the natural environment,rapid implementation of various end-of-life (EoL) management technologies will be needed to reach this target. However, it can be challenging to develop an effective plastic EoL strategy when the available options - chemical or molecular recycling, energy recovery, upcycling, downcycling, closed-loop (plastic-to-plastic) or open-loop (plastic-to-x) recycling, among others - can generate products ranging from low-grade to virgin-quality plastic and from fuels to value-added chemicals. We present a flexible material flow model capable of analyzing the effects of both plastic-to-plastic and plastic-to-x EoL management strategies on the U.S. PET economy. This Plastic Parallel Pathways Platform (4P) assesses the environmental impacts, costs, and circularity of a PET system in which waste is managed through six potential EoL pathways: landfill, incineration with energy recovery, pyrolysis to fuel oil, upcycling to glass fiber reinforced plastic (GFRP), mechanical recycling to low-grade PET, and chemical recycling (glycolysis) to bottle-grade PET. We compare the pathways across multiple metrics using multi-criteria decision analysis (MCDA) and then use a brute force algorithm to predict an optimal combination of EoL pathways to minimize greenhouse gas (GHG) emissions and costs and maximize circularity. This work highlights the need to implement a diverse portfolio of EoL strategies in parallel to enable a PET economy that meets environmental, economic, and circularity requirements simultaneously.

downcycling↗
DOE OSTI2026

Linear complexity

We present factorization and solution phases for a new linear complexity direct solver designed for concurrent batch operations on fine-grained parallel architectures, for matrices amenable to hierarchical representation. We focus on the strong-admissibility-based $\mathscr{H}^{2}$ format, where strong recursive skeletonization factorization compresses remote interactions. We build upon previous implementations of $\mathscr{H}^{2}$ matrix construction for efficient factorization and solution algorithm design, which are illustrated graphically in stepwise detail. The algorithms are ‘blackbox’ in the sense that the only inputs are the matrix and right-hand side, without analytical or geometrical information about the origin of the system. We demonstrate linear complexity scaling in both time and memory on four representative families of dense matrices up to one million in size. Parallel scaling up to 16 threads is enabled by a multi-level matrix graph coloring and avoidance of dynamic memory allocations thanks to prefix-sum memory management. An experimental backward error analysis is included. We break down the timings of different phases, identify phases that are memory-bandwidth limited, and discuss alternatives for phases that may be sensitive to the trend to employ lower precisions for performance.

Boukaram, Wajih↗
DOE OSTI2025

Fragme∩t: An Open‐Source Framework for Multiscale Quantum Chemistry Based on Fragmentation

Fragment-based quantum chemistry offers a means to circumvent the nonlinear computational scaling of conventional electronic structure calculations, by partitioning a large calculation into smaller subsystems then considering the many-body interactions between them. Variants of this approach have been used to parameterize classical force fields and machine learning potentials, applications that benefit from interoperability between quantum chemistry codes. However, there is a dearth of software that provides interoperability yet is purpose-built to handle the combinatorial complexity of fragment-based calculations. To fill this void we introduce “Fragme∩t”, an open-source software application that provides a tool for community validation of fragment-based methods, a platform for developing new approximations, and a framework for analyzing many-body interactions. Fragme∩t includes algorithms for automatic fragment generation and structure modification, and for distance- and energy-based screening of the requisite subsystems. Checkpointing, database management, and parallelization are handled internally and results are archived in a portable database. Interfaces to various quantum chemistry engines are easy to write and exist already for Q-Chem, PySCF, xTB, Orca, CP2K, MRCC, Psi4, NWChem, GAMESS, and MOPAC. Applications reported here demonstrate parallel efficiencies around 96% on more than 1000 processors but also showcase that the code can handle large-scale protein fragmentation using only workstation hardware, all with a codebase that is designed to be usable by non-experts. Fragme∩t conforms to modern software engineering best practices and is built upon well established technologies including Python, SQLite, and Ray. The source code is available under the Apache 2.0 license.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
NASA NTRS1975

Operation of the Institute for Computer Applications in Science and Engineering

The ICASE research program is described in detail; it consists of four major categories: (1) efficient use of vector and parallel computers, with particular emphasis on the CDC STAR-100; (2) numerical analysis, with particular emphasis on the development and analysis of basic numerical algorithms; (3) analysis and planning of large-scale software systems; and (4) computational research in engineering and the natural sciences, with particular emphasis on fluid dynamics. The work in each of these areas is described in detail; other activities are discussed, a prognosis of future activities are included.

Source record↗
NASA NTRS1978

Feasibility of a special-purpose computer to solve the Navier-Stokes equations

Orders-of-magnitude improvements in computer performance can be realized with a parallel array of thousands of fast microprocessors. In this architecture, wiring congestion is minimized by limiting processor communication to nearest neighbors. When certain standard algorithms are applied to a viscous flow problem and existing LSI technology is used, performance estimates of this conceptual design show a dramatic decrease in computational time when compared to the CDC 7600.

Gritton, E. C.↗
NASA NTRS1985

A Uniform Subdivision Method for Triangular Bezier Patches

A subdivision method for Bezier triangles is presented that parallels the development of Lane-Riesenfeld for Bezier Curves. The method is developed from the mathematical description of the patch, and the resulting algorithm does not require evaluation of the blending functions. This method subdivides the triangle uniformly so that the lengths of the sides of the subtriangles are uniformly reduced. This method is a member of the class of methods first presented by Goldman, which contain subdivision methods that arise from degenerate subdivision of Bezier tetrahedra. It is shown that a certain method is a natural extension of the Lane-Riesenfeld results for Bezier curves.

Joy, K. I.↗
NASA NTRS2012

Airborne Precision Spacing for Dependent Parallel Operations Interface Study

This paper describes a usability study of proposed cockpit interfaces to support Airborne Precision Spacing (APS) operations for aircraft performing dependent parallel approaches (DPA). NASA has proposed an airborne system called Pair Dependent Speed (PDS) which uses their Airborne Spacing for Terminal Arrival Routes (ASTAR) algorithm to manage spacing intervals. Interface elements were designed to facilitate the input of APS-DPA spacing parameters to ASTAR, and to convey PDS system information to the crew deemed necessary and/or helpful to conduct the operation, including: target speed, guidance mode, target aircraft depiction, and spacing trend indication. In the study, subject pilots observed recorded simulations using the proposed interface elements in which the ownship managed assigned spacing intervals from two other arriving aircraft. Simulations were recorded using the Aircraft Simulation for Traffic Operations Research (ASTOR) platform, a medium-fidelity simulator based on a modern Boeing commercial glass cockpit. Various combinations of the interface elements were presented to subject pilots, and feedback was collected via structured questionnaires. The results of subject pilot evaluations show that the proposed design elements were acceptable, and that preferable combinations exist within this set of elements. The results also point to potential improvements to be considered for implementation in future experiments.

Volk, Paul M.↗
NASA NTRS1991

A contention-based bus-control scheme for multiprocessor systems

The authors study contention-based bus-control schemes for scheduling processors in using a bit-parallel shared bus. The protocol is designed under the requirements that each processor exhibit a random access behavior, that there be no centralized bus control in the system, and that access be granted in real time. The proposed scheme is based on splitting algorithms used in conventional contention-resolution schemes, and utilizes two-state information obtained from collision detection. Two versions of the bus-control scheme are studied. The static one resolves contentions of N requesting processors in an average of O(logW/2N) iterations, where W is the number of bits in the bit-parallel bus. An adaptive version resolves contentions in an average time that is independent of N.

Juang, Jie-Yong↗
DOE OSTI2026

Parallel-in-Time Solution of Allen-Cahn Equations by Integrating Operator Learning into the Parareal Method

While recent advances in deep learning have shown promising efficiency gains in solving time-dependent partial differential equations (PDEs), matching the accuracy of conventional numerical solvers still remains a challenge. One strategy to improve the accuracy of deep learning-based solutions for time-dependent PDEs is to use the learned model as the coarse propagator in the Parareal method and a traditional numerical method as the fine solver. However, successful integration of deep learning into the Parareal method requires consistency between the coarse and fine solvers, particularly for PDEs exhibiting rapid changes such as sharp transitions. Here, to ensure this consistency, we propose using convolutional neural networks (CNNs) to learn the fully discrete time-stepping operator defined by the same numerical scheme employed as the fine solver. We demonstrate the effectiveness of the proposed method in solving the classical and mass-conservative Allen–Cahn (AC) equations. Through iterative updates in the Parareal algorithm, our approach achieves a significant computational speedup compared to traditional fine solvers while converging to high-accuracy solutions. Our results highlight that the proposed hybrid Parareal algorithm effectively accelerates simulations, particularly when implemented on multiple GPUs, and converges to the desired accuracy in only a few iterations. Another advantage of our method is that the CNN model is trained on trajectory-based data generated from random initial conditions, such that the trained model can be used to solve the AC equations with various initial conditions without retraining. This work demonstrates the potential of integrating neural network methods into parallel-in-time frameworks for efficient and accurate simulations of time-dependent PDEs.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS2006

LDCM Grid Prototype (LGP)

The LGP successfully demonstrated that grid technology could be used to create a collaboration among research scientists, their science development machines, and distributed data to create a science production system in a nationally distributed environment. Grid technology provides a low cost and effective method of enabling production of science products by the science community. To demonstrate this, the LGP partnered with NASA GSFC scientists and used their existing science algorithms to generate virtual Landsat-like data products using distributed data resources. LGP created 48 output composite scenes with 4 input scenes each for a total of 192 scienes processed in parallel. The demonstration took 12 hours, which beat the requirement by almost 50 percent, well within the LDCM requirement to process 250 scenes per day. The LGP project also showed the successful use of workflow tools to automate the processing. Investing in this technology has led to funding for a ROSES ACCESS proposal. The proposal intends to enable an expert science user to produce products from a number of similar distributed instrument data sets using the Land Cover Change Community-based Processing and Analysis System (LC-ComPS) Toolbox. The LC-ComPS Toolbox is a collection of science algorithms that enable the generation of data with ground resolution on the order of Landsat-class instruments.

Weinstein, Beth↗
DOE OSTI2025

Parallel derivative-free optimization for simulation-based design of behind-the-meter energy systems

In this work, the integrated design and dispatch of behind-the-meter or distributed resources (e.g. stationary battery storage and solar PV generation) is considered. A simulation-based framework is employed, generating high-fidelity results with closed-loop predictive control at a fine resolution, at the expense of high computational cost (several minutes to a few hours per design point). To address this challenge, parallel derivative-free design methods are considered. Four methods are compared, including state-of-the-art surrogate-based methods (Radial-Basis Functions and Gaussian processes) and sampling strategies, an evolutionary-based method, and a simple sequential grid refinement method. As a case study, two types of design problem with increasing complexity are considered, namely, the design of behind-the-meter resources (three design variables) and the inclusion of grid capacity (four design variables). The second yields a constrained design problem for which violations can only be determined after solving the computationally expensive simulation. For the three-dimensional case, all methods present a good performance, achieving a solution within 1% of the optimum after the first iteration, with the sequential grid refinement exhibiting the fastest convergence and achieving the best final objective value. This indicates that the parallel evaluation of multiple sampling points may be more important than the choice of method for small decision spaces. For the four-dimensional constrained case, the Genetic Algorithm presents the best tradeoff between performance and computational effort, while the rough objective function terrain generated by constraint violation penalties reduces the performance of surrogate-based methods. Contour plots with flat regions indicate flexibility in the optimal design and highlight the importance of characterizing the solution space.

24 POWER TRANSMISSION AND DISTRIBUTION↗
NASA NTRS1987

Performance limitations in parallel processor simulations

A jet-engine model is partitioned and simulated on a parallel processor system consisting of five 8086/8087 floating-point computers. The simulation uses Heun's integration method. A near-optimal parallel simulation (in the sense of minimum execution time) achieves speedup of only 2.13 and efficiency of 42.6 percent, in effect wasting 57.4 percent of the available processing power. A detailed analysis identifies and graphically demonstrates why the system fails to achieve ideal performance (viz., speedup of 5 and efficiency of 100 percent). Inherent characteristics of the problem equations and solution algorithm account for the loss of nearly half of the available processing power. Overheads associated with interprocessor communication and processor synchronization account for only a small fraction of the lost processing power. The effects of these and other factors which limit parallel processor performance are illustrated through real-time timing-analyzer tracers describing the run/idle status of the parallel processors during the simulation.

O'Grady, E. Pearse↗
NASA NTRS2000

Airbreathing Propulsion System Analysis Using Multithreaded Parallel Processing

In this paper, parallel processing is used to analyze the mixing, and combustion behavior of hypersonic flow. Preliminary work for a sonic transverse hydrogen jet injected from a slot into a Mach 4 airstream in a two-dimensional duct combustor has been completed [Moon and Chung, 1996]. Our aim is to extend this work to three-dimensional domain using multithreaded domain decomposition parallel processing based on the flowfield-dependent variation theory. Numerical simulations of chemically reacting flows are difficult because of the strong interactions between the turbulent hydrodynamic and chemical processes. The algorithm must provide an accurate representation of the flowfield, since unphysical flowfield calculations will lead to the faulty loss or creation of species mass fraction, or even premature ignition, which in turn alters the flowfield information. Another difficulty arises from the disparity in time scales between the flowfield and chemical reactions, which may require the use of finite rate chemistry. The situations are more complex when there is a disparity in length scales involved in turbulence. In order to cope with these complicated physical phenomena, it is our plan to utilize the flowfield-dependent variation theory mentioned above, facilitated by large eddy simulation. Undoubtedly, the proposed computation requires the most sophisticated computational strategies. The multithreaded domain decomposition parallel processing will be necessary in order to reduce both computational time and storage. Without special treatments involved in computer engineering, our attempt to analyze the airbreathing combustion appears to be difficult, if not impossible.

Schunk, Richard Gregory↗
NASA NTRS1994

Parallel implicit unstructured grid Euler solvers

A mesh-vertex finite volume scheme for solving the Euler equations on triangular unstructured meshes is implemented on an MIMD (multiple instruction/multiple data stream) parallel computer. An explicit four-stage Runge-Kutta scheme is used to solve two-dimensional flow problems. A family of implicit schemes is also developed to solve these problems, where the linear system that arises at each time step is solved by a preconditioned GMRES algorithm. Two partitioning strategies are employed, one that partitions triangles and the other that partitions vertices. The choice of the preconditioner in a distributed memory setting is discussed. All the methods are compared both in terms of elapsed times and convergence rates. It is shown that the implicit schemes offer adequate parallelism at the expense of minimal sequential overhead. The use of a global coarse grid to further minimize this overhead is also investigated. The schemes are implemented on a distributed memory parallel computer, the iPSC/860.

Venkatakrishnan, V.↗
NASA NTRS2000

General Purpose Fortran Program for Discrete-Ordinate-Method Radiative Transfer in Scattering and Emitting Layered Media: An Update of DISORT

This update reports a state-of-the-art discrete ordinate algorithm for monochromatic unpolarized radiative transfer in non-isothermal, vertically inhomogeneous, but horizontally homogeneous media. The physical processes included are Planckian thermal emission, scattering with arbitrary phase function, absorption, and surface bidirectional reflection. The system may be driven by parallel or isotropic diffuse radiation incident at the top boundary, as well as by internal thermal sources and thermal emission from the boundaries. Radiances, fluxes, and mean intensities are returned at user-specified angles and levels. DISORT has enjoyed considerable popularity in the atmospheric science and other communities since its introduction in 1988. Several new DISORT features are described in this update: intensity correction algorithms designed to compensate for the 8-M forward-peak scaling and obtain accurate intensities even in low orders of approximation; a more general surface bidirectional reflection option; and an exponential-linear approximation of the Planck function allowing more accurate solutions in the presence of large temperature gradients. DISORT has been designed to be an exemplar of good scientific software as well as a program of intrinsic utility. An extraordinary effort has been made to make it numerically well-conditioned, error-resistant, and user-friendly, and to take advantage of robust existing software tools. A thorough test suite is provided to verify the program both against published results, and for consistency where there are no published results. This careful attention to software design has been just as important in DISORT's popularity as its powerful algorithmic content.

Tsay, Si-Chee↗
NASA NTRSDate not supplied

Hybrid-Electric Aero-Propulsion Controls Testbed Results with Energy Storage

Electrified aircraft propulsion (EAP) research is a priority of the National Aeronautics and Space Administration (NASA) for its potential to increase propulsion system efficiency, performance, and operability at the subsystem and vehicle levels while decreasing emissions. These EAP systems demand more advanced control algorithms due to increased complexity. NASA has developed a reconfigurable, hardware-in-the-loop rig to verify control algorithm performance using a sub-scale electro-mechanical system. A novel capability of this rig is the ability to test full scale EAP control algorithms on a sub-scale representation of the electro-mechanical system without turbomachinery/rotors. A novel feature is the use of a physical energy storage device within the electro-mechanical system. A dual spool, parallel hybrid-electric turbofan architecture and energy management control system is tested with the goal of verifying the ability to obtain turbomachinery model operability benefits while controlling sub-scale electro-mechanical hardware. Pre-test predictions of the turbofan model, control, and rig performance were obtained through simulation using a software model of the rig. Theoretical results showing the true performance of the turbofan model were obtained through a software simulation using full-scale mechanical shaft models. The paper compares theoretical, predicted, and actual test results from the turbofan model, energy management control and rig perspectives. The results show that the presence of sub-scale electro-mechanical hardware did not inhibit the energy management algorithm from achieving turbomachinery operability benefits.

hybrid↗
NASA NTRS1994

Parallel implicit unstructured grid Euler solvers

A mesh-vertex finite volume scheme for solving the Euler equations on triangular unstructured meshes is implemented on a multiple-instruction/multiple-data stream parallel computer. An explicit four-stage Runge-Kutta scheme is used to solve two-dimensional flow problems. A family of implicit schemes is also developed to solve these problems, where the linear system that arises at each time step is solved by a preconditioned GMRES algorithm. Two partitioning strategies are employed: one that partitions triangles and the other that partitions vertices. The choice of the preconditioner in a distributed memory setting is discussed. All of the methods are compared both in terms of elapsed times and convergence rates. It is shown that the implicit schemes offer adequate parallelism at the expense of minimal sequential overhead. The use of a global coarse grid to further minimize this overhead is also investigated. The schemes are implemented on a distributed memory parallel computer, the Intel iPSC/860.

TRT-THEORETICAL↗