Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “algorithmic”

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 379 records · Page 21
All sourcesNASA NTRSDOE OSTI
DOE OSTI2021

Explicit structure-preserving geometric particle-in-cell algorithm in curvilinear orthogonal coordinate systems and its applications to whole-device 6D kinetic simulations of tokamak physics

Explicit structure-preserving geometric particle-in-cell (PIC) algorithm in curvilinear orthogonal coordinate systems is developed. The work reported represents a further development of the structure-preserving geometric PIC algorithm achieving the goal of practical applications in magnetic fusion research. The algorithm is constructed by discretizing the field theory for the system of charged particles and electromagnetic field using Whitney forms, discrete exterior calculus, and explicit non-canonical symplectic integration. In addition to the truncated infinitely dimensional symplectic structure, the algorithm preserves exactly many important physical symmetries and conservation laws, such as local energy conservation, gauge symmetry and the corresponding local charge conservation. As a result, the algorithm possesses the long-term accuracy and fidelity required for first-principles-based simulations of the multiscale tokamak physics. The algorithm has been implemented in the SymPIC code, which is designed for high-efficiency massively-parallel PIC simulations in modern clusters. The code has been applied to carry out whole-device 6D kinetic simulation studies of tokamak physics. A self-consistent kinetic steady state for fusion plasma in the tokamak geometry is numerically found with a predominately diagonal and anisotropic pressure tensor. The state also admits a steady-state sub-sonic ion flow in the range of 10 km s -1 , agreeing with experimental observations and analytical calculations Kinetic ballooning instability in the self-consistent kinetic steady state is simulated. It is shown that high-n ballooning modes have larger growth rates than low-n global modes, and in the nonlinear phase the modes saturate approximately in 5 ion transit times at the 2% level by the E × B flow generated by the instability. These results are consistent with early and recent electromagnetic gyrokinetic simulations.

43 PARTICLE ACCELERATORS↗
DOE OSTI2018

A case study evaluating the portability of an executable computable phenotype algorithm across multiple institutions and electronic health record environments

Abstract Electronic health record (EHR) algorithms for defining patient cohorts are commonly shared as free-text descriptions that require human intervention both to interpret and implement. We developed the Phenotype Execution and Modeling Architecture (PhEMA, http://projectphema.org) to author and execute standardized computable phenotype algorithms. With PhEMA, we converted an algorithm for benign prostatic hyperplasia, developed for the electronic Medical Records and Genomics network (eMERGE), into a standards-based computable format. Eight sites (7 within eMERGE) received the computable algorithm, and 6 successfully executed it against local data warehouses and/or i2b2 instances. Blinded random chart review of cases selected by the computable algorithm shows PPV ≥90%, and 3 out of 5 sites had >90% overlap of selected cases when comparing the computable algorithm to their original eMERGE implementation. This case study demonstrates potential use of PhEMA computable representations to automate phenotyping across different EHR systems, but also highlights some ongoing challenges.

Pacheco, Jennifer A.↗
DOE OSTI2019

Quantum algorithm for simulating the wave equation

We present a quantum algorithm for simulating the wave equation under Dirichlet and Neumann boundary conditions. The algorithm uses Hamiltonian simulation and quantum linear system algorithms as subroutines. It relies on factorizations of discretized Laplacian operators to allow for polynomially improved scaling in truncation errors and improved scaling for state preparation relative to general purpose quantum algorithms for solving linear differential equations. Relative to classical algorithms for simulating the D-dimensional wave equation, our quantum algorithm achieves exponential space savings and achieves a speedup which is polynomial for fixed D and exponential in D. Furthermore, we also consider using Hamiltonian simulation for Klein-Gordon equations and Maxwell's equations.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2019

Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing

We present two quantum algorithms based on evolution randomization, a simple variant of adiabatic quantum computing, to prepare a quantum state |x⟩ that is proportional to the solution of the system of linear equations $A\overrightarrow{x} = \overrightarrow{b}$. The time complexities of our algorithms are O(κ 2 log(κ)/ε) and O(κ log(κ)/ε), where κ is the condition number of A and ε is the precision. Both algorithms are constructed using families of Hamiltonians that are linear combinations of products of A, the projector onto the initial state |b⟩, and single-qubit Pauli operators. The algorithms are conceptually simple and easy to implement. They are not obtained from equivalences between the gate model and adiabatic quantum computing. They do not use phase estimation or variable-time amplitude amplification, and do not require large ancillary systems. We discuss a gate-based implementation via Hamiltonian simulation and prove that our second algorithm is almost optimal in terms of κ. Like previous methods, our techniques yield an exponential quantum speed-up under some assumptions. Our results emphasize the role of Hamiltonian-based models of quantum computing for the discovery of important algorithms.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

Generalized Cycle Benchmarking Algorithm for Characterizing Midcircuit Measurements

Midcircuit measurements (MCMs) are crucial ingredients in the development of fault-tolerant quantum computation. While there have been rapid experimental progresses in realizing MCMs, a systematic method for characterizing noisy MCMs is still under exploration. In this work, we develop a cycle benchmarking (CB)-type algorithm to characterize noisy MCMs. The key idea is to use a joint Fourier transform on the classical and quantum registers and then estimate parameters in the Fourier space, analogous to Pauli fidelities used in CB-type algorithms for characterizing the Pauli-noise channel of Clifford gates. Furthermore, we develop a theory of the noise learnability of MCMs, which determines what information can be learned about the noise model (in the presence of state preparation and terminating measurement noise) and what cannot, which shows that all learnable information can be learned using our algorithm. As an application, we show how to use the learned information to test the independence between measurement noise and state-preparation noise in an MCM. Finally, we conduct numerical simulations to illustrate the practical applicability of the algorithm. Similar to other CB-type algorithms, we expect the algorithm to provide a useful toolkit that is of experimental interest. Published by the American Physical Society 2025

Zhang, Zhihan (ORCID:0009000862907691)↗
DOE OSTI2021

GPU-accelerated multitiered iterative phasing algorithm for fluctuation X-ray scattering

The multitiered iterative phasing (MTIP) algorithm is used to determine the biological structures of macromolecules from fluctuation scattering data. It is an iterative algorithm that reconstructs the electron density of the sample by matching the computed fluctuation X-ray scattering data to the external observations, and by simultaneously enforcing constraints in real and Fourier space. This paper presents the first ever MTIP algorithm acceleration efforts on contemporary graphics processing units (GPUs). The Compute Unified Device Architecture (CUDA) programming model is used to accelerate the MTIP algorithm on NVIDIA GPUs. The computational performance of the CUDA-based MTIP algorithm implementation outperforms the CPU-based version by an order of magnitude. Furthermore, the Heterogeneous-Compute Interface for Portability (HIP) runtime APIs are used to demonstrate portability by accelerating the MTIP algorithm across NVIDIA and AMD GPUs.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

Validation of Microgrid Algorithms using At-Scale Simulation and Emulation Real-Time (ASSERT) Framework

This paper presents a novel framework for validating microgrid algorithms using a At-Scale Simulation and Emulation Real-Time (ASSERT) setup. The proposed universal microgrid validation framework was developed at Advanced Research on Integrated Energy Systems (ARIES) platform at National Renewable Energy Laboratory in Golden, Colorado, USA. As the number of intercommunicating devices grow in power systems, along with more integration of inverter-based resources, developing and validating microgrid operation and control algorithms is becoming complex and time-consuming task. The ASSERT framework is designed to provide a comprehensive, accurate, and efficient solution for validating microgrid algorithms. It combines at-scale simulations and real-time emulation to create a virtual environment that closely mimics the behavior of a physical microgrids which are characteristic of future smart distribution systems, such as: (1) increasing variability in the physical size of new energy technologies; (2) requiring control large numbers of interconnected devices, and (3) integrating diverse technologies that have not previously worked together. The paper describes the technical details of the ASSERT framework, its validation process, and its benefits over traditional validation methods. The framework's ability to validate the performance of various algorithms is demonstrated through a case study, which shows that it can effectively identify the weaknesses of an algorithm and optimize its performance. Overall, the ASSERT framework is a promising tool that can significantly enhance the development and validation of microgrid algorithms, leading to more reliable and efficient microgrid operation.

at-scale↗
DOE OSTI2021

Scaling Out a Combinatorial Algorithm for Discovering Carcinogenic Gene Combinations to Thousands of GPUs

Cancer is a leading cause of death in the US, second only to heart disease. It is primarily a result of a combination of an estimated two-nine genetic mutations (multi-hit combinations). Although a body of research has identified hundreds of cancer-causing genetic mutations, we don’t know the specific combination of mutations responsible for specific instances of cancer for most cancer types. An approximate algorithm for solving the weighted set cover problem was previously adapted to identify combinations of genes with mutations that may be responsible for individual instances of cancer. However, the algorithm’s computational requirement scales exponentially with the number of genes, making it impractical for identifying more than three-hit combinations, even after the algorithm was parallelized and scaled up to a V100 GPU. Since most cancers have been estimated to require more than three hits, we scaled out the algorithm to identify combinations of four or more hits using 1000 nodes (6000 V100 GPUs with ≈48×106 processing cores) on the Summit supercomputer at Oak Ridge National Laboratory. Efficiently scaling out the algorithm required a series of algorithmic innovations and optimizations for balancing an exponentially divergent workload across processors and for minimizing memory latency and inter-node communication. We achieved an average strong scaling efficiency of 90.14% (80.96%–97.96% for 200 to 1000 nodes), compared to a 100 node run, with 84.18% scaling efficiency for 1000 nodes. With experimental validation, the multi-hit combinations identified here could provide further insight into the etiology of different cancer subtypes and provide a rational basis for targeted combination therapy.

Dash, Sajal↗
DOE OSTI2019

Parallel-in-Time Simulation Algorithm for Power Electronics: MMC-HVdc System

The complexity in simulating power electronics like modular multilevel converters (MMCs) requires simulation algorithms to speed-up the process. Existing simulation algorithms exploit spatial parallelism to speed-up simulation. With rise in complexity of power electronics and presence of increased number of states within them, there are limits in the speed-up using spatial parallelism. In this paper, a temporal parallelism algorithm based on parallel-in-time methods is developed for simulation of power-electronics-systems. The temporal parallelism algorithm is based on computation of power-electronics-states on coarse and fine time-steps using different models. The models of power-electronics-systems used in coarse and fine time-steps are average-value and detailed models, respectively. The updates to states on coarse time-step are computed serially and are used to initialize the states on fine time-step. The updates on fine time-step are computed in parallel. A translation method is proposed in this paper to update the states on fine time-step from the simulations in the coarse time-step, and vice-versa. The proposed algorithm is applied to simulate MMCs and is validated with respect to a detailed reference MMC model. The proposed algorithm recorded a speed-up of up to 3.47× with 5 cores.

42 ENGINEERING↗
DOE OSTI2019

A Synchronization-Avoiding Distance-1 Grundy Coloring Algorithm for Power-Law Graphs

In this paper, we propose a distributed, unordered, label-correcting distance-1 Grundy (vertex) coloring algorithm, namely, Distributed Control (DC) coloring algorithm. Our algorithm eliminates the need for vertex-centric barriers and global synchronization for color refinement, relying only on atomic operations and local termination detection to update vertex color. DC proceeds optimistically, correcting the colors asynchronously as the algorithm progresses and depends on local ordering of tasks to minimize the execution of sub-optimal work. We implement our DC coloring algorithm and the well-known Jones-Plassmann algorithm and compare their performance with 4 different types of standard RMAT graphs and real-world graphs. We show that the elimination of waiting time of global and vertex-centric barriers and investing this time for local ordering leads to improved scaling for graphs with prominent power-law characteristics and densely interconnected local subgraphs.

Firoz, Jesun S.↗
DOE OSTI2015

Impacts of Time Delays on Distributed Algorithms for Economic Dispatch

Economic dispatch problem (EDP) is an important problem in power systems. It can be formulated as an optimization problem with the objective to minimize the total generation cost subject to the power balance constraint and generator capacity limits. Recently, several consensus-based algorithms have been proposed to solve EDP in a distributed manner. However, impacts of communication time delays on these distributed algorithms are not fully understood, especially for the case where the communication network is directed, i.e., the information exchange is unidirectional. This paper investigates communication time delay effects on a distributed algorithm for directed communication networks. The algorithm has been tested by applying time delays to different types of information exchange. Several case studies are carried out to evaluate the effectiveness and performance of the algorithm in the presence of time delays in communication networks. It is found that time delay effects have negative effects on the convergence rate, and can even result in an incorrect converge value or fail the algorithm to converge.

Yang, Tao↗
DOE OSTI2023

Fast Tuning-Free Distributed Algorithm for Solving the Network-Constrained Economic Dispatch

With the increasing penetration of distributed energy resources (DERs) and their participation in the electricity market, it becomes more desirable to apply distributed algorithms for resource allocation in order to address the resulting computational and communicational challenges. Most of the existing distributed algorithms for solving the network-constrained economic dispatch (NCED) problem require the tuning of certain auxiliary parameters. As a result, the robustness of these algorithms against the varieties in DERs is greatly undermined. In this paper, a new distributed algorithm, optimality condition consensus (OCC), is proposed to solve the NCED problem by using distributed power flow (DPF) and ratio consensus as fundamental tools. It inherits the advantages of existing distributed algorithms for the NCED problem but removes the need for parameter tuning to improve performance in practice. In conclusion, the effectiveness of the proposed distributed algorithm in terms of efficiency, scalability, and robustness is demonstrated through detailed case studies.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2020

An Algebraic Sparsified Nested Dissection Algorithm Using Low-Rank Approximations

Here, we propose a new algorithm for the fast solution of large, sparse, symmetric positive-definite linear systems, spaND (sparsified Nested Dissection). It is based on nested dissection, sparsification, and low-rank compression. After eliminating all interiors at a given level of the elimination tree, the algorithm sparsifies all separators corresponding to the interiors. This operation reduces the size of the separators by eliminating some degrees of freedom but without introducing any fill-in. This is done at the expense of a small and controllable approximation error. The result is an approximate factorization that can be used as an efficient preconditioner. We then perform several numerical experiments to evaluate this algorithm. We demonstrate that a version using orthogonal factorization and block-diagonal scaling takes fewer CG iterations to converge than previous similar algorithms on various kinds of problems. Furthermore, this algorithm is provably guaranteed to never break down and the matrix stays symmetric positive-definite throughout the process. We evaluate the algorithm on some large problems show it exhibits near-linear scaling. The factorization time is roughly $\mathcal{O}$(N), and the number of iterations grows slowly with N.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2018

The Pandora multi-algorithm approach to automated pattern recognition of cosmic-ray muon and neutrino events in the MicroBooNE detector

The development and operation of Liquid-Argon Time-Projection Chambers for neutrino physics has created a need for new approaches to pattern recognition in order to fully exploit the imaging capabilities offered by this technology. Whereas the human brain can excel at identifying features in the recorded events, it is a significant challenge to develop an automated, algorithmic solution. The Pandora Software Development Kit provides functionality to aid the design and implementation of pattern-recognition algorithms. It promotes the use of a multi-algorithm approach to pattern recognition, in which individual algorithms each address a specific task in a particular topology. Many tens of algorithms then carefully build up a picture of the event and, together, provide a robust automated pattern-recognition solution. This paper describes details of the chain of over one hundred Pandora algorithms and tools used to reconstruct cosmic-ray muon and neutrino events in the MicroBooNE detector. Metrics that assess the current pattern-recognition performance are presented for simulated MicroBooNE events, using a selection of final-state event topologies.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
DOE OSTI2020

A supernodal all-pairs shortest path algorithm

We show how to exploit graph sparsity in the Floyd-Warshall algorithm for the all-pairs shortest path (Apsp) problem. Floyd-Warshall is an attractive choice for Apsp on high-performing systems due to its structural similarity to solving dense linear systems and matrix multiplication. However, if sparsity of the input graph is not properly exploited, Floyd-Warshall will perform unnecessary asymptotic work and thus may not be a suitable choice for many input graphs. To overcome this limitation, the key idea in our approach is to use the known algebraic relationship between Floyd-Warshall and Gaussian elimination, and import several algorithmic techniques from sparse Cholesky factorization, namely, fill-in reducing ordering, symbolic analysis, supernodal traversal, and elimination tree parallelism. When combined, these techniques reduce computation, improve locality and enhance parallelism. We implement these ideas in an efficient shared memory parallel prototype that is orders of magnitude faster than an efficient multi-threaded baseline Floyd-Warshall that does not exploit sparsity. Our experiments suggest that the Floyd-Warshall algorithm can compete with Dijkstra's algorithm (the algorithmic core of Johnson's algorithm) for several classes sparse graphs.

Sao, Piyush↗
DOE OSTI2021

PAGANI: a parallel adaptive GPU algorithm for numerical integration

We present a new adaptive parallel algorithm for the challenging problem of multi-dimensional numerical integration on massively parallel architectures. Adaptive algorithms have demonstrated the best performance, but efficient many-core utilization is difficult to achieve because the adaptive work-load can vary greatly across the integration space and is impossible to predict a priori. Existing parallel algorithms utilize sequential computations on independent processors, which results in bottlenecks due to the need for data redistribution and processor synchronization. Our algorithm employs a high-throughput approach in which all existing sub-regions are processed and sub-divided in parallel. Repeated sub-region classification and filtering improves upon a brute-force approach and allows the algorithm to make efficient use of computation and memory resources. A CUDA implementation shows orders of magnitude speedup over the fastest open-source CPU method and extends the achievable accuracy for difficult integrands. Our algorithm typically outperforms other existing deterministic parallel methods.

Sakiotis, Ioannis↗
DOE OSTI2018

Cylindricity Error Evaluation Based on an Improved Harmony Search Algorithm

The cylindricity error is one of the basic form errors in mechanical parts, which greatly influences the assembly accuracy and service life of relevant parts. For the minimum zone method (MZM) in international standards, there is no specific formula to calculate the cylindricity error. Therefore, the evaluation methods of the cylindricity error under the MZM have been widely concerned by international scholars. To improve the evaluation accuracy and accelerate the iteration speed of the cylindricity, an improved harmony search (IHS) algorithm is proposed and applied to compute the cylindricity. On the basis of the standard harmony search algorithm, the logistic chaotic initialization is introduced into the generation of initial solution to improve the quality of solutions. During the iterative process, the global and local search capabilities are balanced by adopting the par and b w operators adaptively. After each iteration, the Cauchy mutation strategy is adopted to the best solution to further improve the calculation precision of the IHS algorithm. Finally, four test functions and three groups of cylindricity error examples were applied to validity verification of the IHS algorithm, the simulation test results show that the IHS algorithm has advantages of the computing accuracy and iteration speed compared with other traditional algorithms, and it is very effective for the application in the evaluation of the cylindricity error.

Yang, Yang↗
DOE OSTI2025

Pulse: An Outlier Sensitive Downsampling Algorithm For Timeseries Data

Pulse is a downsampling algorithm for timeseries data. Frequently datasets become so large that visualization tools and web browsers cannot effectively render graphics due to memory constraints. Downsampling algorithms are commonly applied to minimize the quantity of data required to visualize important features or trends in the data, but some datasets are composed by distinct enough features and trends that most existing downsampling algorithms fail to preserve them. Pule was developed to downsample timeseries data for galvanostatic stack test data at the Idaho National Laboratory. These datasets were composed by approximately 4 million records, most of them being extremely uniform. However, during relatively brief time periods when the stack test changes state, for example when the test article is powered on, or a load is added, the data produce sparse asymptotes. No existing downsampling algorithm was capable of preserving the sparse asymptotes in electrolysis stack test data. Instead, we develop a downsampling algorithm that preserves important outliers in data, and otherwise aggressively downsamples uniform data. The algorithm has applications in other domains like seismology, in the measurement of earthquakes, or astronomy, in the measurement of quasars or transit photometry.

Woodruff, Nathan [Idaho National Laboratory (INL),↗