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 73 records · Page 4
All sourcesNASA NTRSDOE OSTI
DOE OSTI2020

Permutation matrix representation quantum Monte Carlo

We present a quantum Monte Carlo algorithm for the simulation of general quantum and classical many-body models within a single unifying framework. The algorithm builds on a power series expansion of the quantum partition function in its off-diagonal terms and is both parameter-free and Trotter error-free. In our approach, the quantum dimension consists of products of elements of a permutation group. As such, it allows for the study of a very wide variety of models on an equal footing. To demonstrate the utility of our technique, we use it to clarify the emergence of the sign problem in the simulations of non-stoquastic physical models. We showcase the flexibility of our algorithm and the advantages it offers over existing state-of-the-art by simulating transverse- field Ising model Hamiltonians and comparing the performance of our technique against that of the stochastic series expansion algorithm. Furthermore, we also study a transverse-field Ising model augmented with randomly chosen two-body transverse-field interactions.

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗
DOE OSTI2020

First-principles calculation of the configurational energy density of states for a solid-state ion conductor with a variant of the Wang and Landau algorithm

In this work, a variant of the Wang and Landau algorithm for calculation of the configurational energy density of states is proposed. The algorithm was developed for the purpose of using first-principles simulations, such as density functional theory, to calculate the partition function of disordered sublattices in crystal materials. The expensive calculations of first-principles methods make a parallel algorithm necessary for a practical computation of the configurational energy density of states within a supercell approximation of a solid-state material. The algorithm developed in this work is tested with the two-dimensional (2d) Ising model to bench mark the algorithm and to help provide insight for implementation to a materials science application. Tests with the 2d Ising model revealed that the algorithm has good performance compared to the original Wang and Landau algorithm and the 1/$\textit{t}$ algorithm, in particular the short iteration performance. Further, a proof of convergence is presented within an adiabatic assumption, and the analysis is able to correctly predict the time dependence of the modification factor to the density of states. The algorithm was then applied to the lithium and lanthanum sublattice of the solid-state lithium ion conductor Li 0.5 La 0.5 TiO 3 . This was done to help understand the disordered nature of the lithium and lanthanum. The results find, overall, that the algorithm performs very well for the 2d Ising model and that the results for Li 0.5 La 0.5 TiO 3 are consistent with experiment while providing additional insight into the lithium and lanthanum ordering in the material. The primary result is that the lithium and lanthanum become more mixed between layers along the c axis for increasing temperature. In part, the simulation of the disordered Li 0.5 La 0.5 TiO 3 system serves as a benchmark for what size systems are currently and in the near future practical to calculate with density functional theory methods.

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗
DOE OSTI2025

Partitioned Quantum Subspace Expansion

We present an iterative generalisation of the quantum subspace expansion algorithm used with a Krylov basis. The iterative construction connects a sequence of subspaces via their lowest energy states. Diagonalising a Hamiltonian in a given Krylov subspace requires the same quantum resources in both the single step and sequential cases. We propose a variance-based criterion for determining a good iterative sequence and provide numerical evidence that these good sequences display improved numerical stability over a single step in the presence of finite sampling noise. Implementing the generalisation requires additional classical processing with a polynomial overhead in the subspace dimension. By exchanging quantum circuit depth for additional measurements the quantum subspace expansion algorithm appears to be an approach suited to near term or early error-corrected quantum hardware. Our work suggests that the numerical instability limiting the accuracy of this approach can be substantially alleviated in a parameter-free way.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Understanding nanoscale structural distortions in Pb(Zr 0.2 Ti 0.8 )O 3 by utilizing X-ray nanodiffraction and clustering algorithm analysis

Hard X-ray nanodiffraction provides a unique nondestructive technique to quantify local strain and structural inhomogeneities at nanometer length scales. However, sample mosaicity and phase separation can result in a complex diffraction pattern that can make it challenging to quantify nanoscale structural distortions. In this work, a k-means clustering algorithm was utilized to identify local maxima of intensity by partitioning diffraction data in a three-dimensional feature space of detector coordinates and intensity. This technique has been applied to X-ray nanodiffraction measurements of a patterned ferroelectric PbZr 0.2 Ti 0.8 O 3 sample. The analysis reveals the presence of two phases in the sample with different lattice parameters. A highly heterogeneous distribution of lattice parameters with a variation of 0.02 Å was also observed within one ferroelectric domain. This approach provides a nanoscale survey of subtle structural distortions as well as phase separation in ferroelectric domains in a patterned sample.

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗
DOE OSTI2026

Chemical Recommender System: Replacement Suggestions for Small Molecules

The Chemical Recommender System (CRS) is an open-source, high-performance toolkit that enables real-time similarity searches across the complete PubChem database (over 50 million molecules) using commodity hardware. The CRS addresses critical limitations in existing chemical informatics platforms through a novel vector database infrastructure, extensible model integration capabilities, and complete algorithmic transparency. The system implements a vector database deployment with partitioned indexing that achieves a ~60x speedup over traditional approaches. A containerized model integration framework allows researchers to seamlessly incorporate custom predictive models into the full-scale search and scoring pipeline, while complete configurability of search parameters, filtering logic, and scoring functions provides capabilities not available in existing black-box solutions. Beyond structural similarity, the CRS integrates OPERA QSAR models for thermophysical and toxicity predictions, RDKit synthetic accessibility scoring, and user-defined models to compute weighted final replacement scores. The complete system is accessible through an interactive web application supporting real-time progress monitoring, post-processing score re-weighting, automated PDF reporting, and batch processing capabilities.

Nair, Parthiv Anand [Sandia National Laboratories ↗
DOE OSTI2022

Metropolis-style random sampling of quantum gates for the estimation of low-energy observables

In this work, we propose a quantum algorithm to compute low-energy expectation values of a quantum Hamiltonian by sampling a partition function associated with the average energy of that Hamiltonian. For any given quantum circuit-Hamiltonian pair, there is an associated average energy. The sampling is done through an accept/reject Metropolis-style algorithm on the quantum gates of the circuit itself. Observables calculated under the canonical ensemble from these samples of circuits are extrapolated from higher energies to the ground state.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
DOE OSTI2020

A Clustering-based biased Monte Carlo Approach to Protein Titration Curve Prediction

We develop and implement a novel approach to computing the ensemble averages in systems characterized by pair-wise interactions between the entities. Methods involving full enumeration of the configuration space result in exponential complexity. Sampling methods such as Markov Chain Monte Carlo (MCMC) algorithms have been proposed to tackle the exponential complexity of these problems. In certain scenarios where significant energetic coupling exists between the entities, the accuracy of the such algorithms can be diminished. We propose a strategy to improve the accuracy of the MCMC runs by taking advantage of the cluster structure in the interaction energy matrix. We propose two different schemes for performing the biased MCMC runs on the partitioned systems and show that they are valid MCMC schemes. We then apply these algorithms to the problem of computing the protonation fractions and hence the titration curves of titratable protein residues that constitute a given protein. We leverage both synthesized and real-world systems and show the improved performance of our biased MCMC methods when compared to the regular MCMC method.

Visweswara Sathanur, Arun↗
DOE OSTI2023

Framework for Extensible, Asynchronous Task Scheduling (FEATS) in Fortran

Most parallel scientific programs contain compiler directives (pragmas) such as those from OpenMP, explicit calls to runtime library procedures such as those implementing the Message Passing Interface (MPI), or compiler-specific language extensions such as those provided by CUDA. By contrast, the recent Fortran standards empower developers to express parallel algorithms without directly referencing lower-level parallel programming models. Fortran’s parallel features place the language within the Partitioned Global Address Space (PGAS) class of programming models. When writing programs that exploit data-parallelism, application developers often find it straightforward to develop custom parallel algorithms. Problems involving complex, heterogeneous, staged calculations, however, pose much greater challenges. Such applications require careful coordination of tasks in a manner that respects dependencies prescribed by a directed acyclic graph. When rolling one’s own solution proves difficult, extending a customizable framework becomes attractive. The paper presents the design, implementation, and use of the Framework for Extensible Asynchronous Task Scheduling (FEATS), which we believe to be the first task-scheduling tool written in modern Fortran. We describe the benefits and compromises associated with choosing Fortran as the implementation language, and we propose ways in which future Fortran standards can best support the use case in this paper.

Richardson, Brad↗
DOE OSTI2022

Intelligent System Partitioning for Agent-Based Security Constrained Optimal Power Flow

This project developed scalable, computationally efficient algorithms to solve realistic large-scale power system optimization problems as part of a larger series of competitions run by ARPA-E. These problems are important because the secure and reliable operation of the power grid, especially under increased uncertainty and variability, is growing increasingly challenging. The economic feasibility of the proposed methods developed by our team is quite low, considering it’s a purely software-based solution to operate power grids more efficiently. The technical effectiveness, as evidenced by our performance in the competition, balances heuristics and approximations to provide a tradeoff between speed and accuracy.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2022

Randomized Cholesky Preconditioning for Graph Partitioning Applications

A graph is a mathematical representation of a network; we say it consists of a set of vertices, which are connected by edges. Graphs have numerous applications in various fields, as they can model all sorts of connections, processes, or relations. For example, graphs can model intricate transit systems or the human nervous system. However, graphs that are large or complicated become difficult to analyze. This is why there is an increased interest in the area of graph partitioning, reducing the size of the graph into multiple partitions. For example, partitions of a graph representing a social network might help identify clusters of friends or colleagues. Graph partitioning is also a widely used approach to load balancing in parallel computing. The partitioning of a graph is extremely useful to decompose the graph into smaller parts and allow for easier analysis. There are different ways to solve graph partitioning problems. For this work, we focus on a spectral partitioning method which forms a partition based upon the eigenvectors of the graph Laplacian (details presented in Acer, et. al.). This method uses the LOBPCG algorithm to compute these eigenvectors. LOBPCG can be accelerated by an operator called a preconditioner. For this internship, we evaluate a randomized Cholesky (rchol) preconditioner for its effectiveness on graph partitioning problems with LOBPCG. We compare it with two standard preconditioners: Jacobi and Incomplete Cholesky (ichol). This research was conducted from August to December 2021 in conjunction with Sandia National Laboratories.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Quantum Simulation of the First-Quantized Pauli-Fierz Hamiltonian

We provide an explicit recursive divide-and-conquer approach for simulating quantum dynamics and derive a discrete first-quantized nonrelativistic QED Hamiltonian based on the many-particle Pauli-Fierz Hamiltonian. We apply this recursive divide-and-conquer algorithm to this Hamiltonian and compare it to a concrete simulation algorithm that uses qubitization. Our divide-and-conquer algorithm, using lowest-order Trotterization, scales for fixed grid spacing as O ~ ( Λ N 2 η 2 t 2 / ϵ ) for grid size N , η particles, simulation time t , field cutoff Λ , and error ϵ . Our qubitization algorithm scales as O ~ ( N ( η + N ) ( η + Λ 2 ) t log ( 1 / ϵ ) ) . This shows that even a naive partitioning and low-order splitting formula can yield, through our divide-and-conquer formalism, superior scaling to qubitization for large Λ . We compare the relative costs of these two algorithms on systems that are relevant for applications such as the spontaneous emission of photons and the photoionization of electrons. We observe that for different parameter regimes, one method can be favored over the other. Finally, we give new algorithmic and circuit-level techniques for gate optimization, including a new way of implementing a group of multicontrolled- X gates that can be used for better analysis of circuit cost. Published by the American Physical Society 2024

Mukhopadhyay, Priyanka (ORCID:0000000164639100)↗
DOE OSTI2022

Profile Images and Annotations for Vehicle Re-identification Algorithms (PRIMAVERA)

This dataset contains 636,246 profile images of vehicles representing 13,963 unique vehicles. The data was collected by a set of roadside sensors over the course of three years. Each time a vehicle passed by one of the sensors, a series of images was collected. The images were processed to detect and localize each vehicle, and a license plate reader collocated with the sensor was used to provide a unique ID for the vehicle. Actual license plate numbers have been obfuscated by replacing with an arbitrary numerical ID for each vehicle. After localizing the vehicle in each image, the original RGB image was rotated, scaled, and shifted to produce a new RGB image of size 234x234 pixels such that the outermost two wheels are located at predetermined pixel locations in the image. In this way, all vehicle images are aligned to one another. This registration process occasionally results in a portion of certain vehicles being cutoff at the edges of the image. The dataset has been partitioned into two sets called training and validation. The two partitions no common vehicles, i.e., a vehicle present in one partition is guaranteed not to be present in the other. In this way, an algorithm can be validated against a set of new vehicles that were not seen during the training process. The training set contains 543,926 images from 64,440 vehicle passes representing 11,918 unique vehicles, while the validation set contains 92,320 images from 10,991 vehicle passes representing 2,045 unique vehicles. Vehicle images are organized by directories corresponding to unique vehicles. The file naming scheme is as follows: veh_{vehID}_tr_{passID}_{frameID}_{elevation}_{timeofday}.jpg where {vehID} is the vehicle ID (unique across the entire dataset), {passID} is an identifier for each tracked vehicle pass (unique across the entire dataset), {frameID} is the index of the frame within the given vehicle pass starting at 0, {elevation} is a two-letter string indicating whether the sensor was elevated (el) or at ground-level (gl), and {timeofday} is a two-letter string indicating whether the image was captured during daytime (dt) or nighttime (nt).

image↗
DOE OSTI2023

A Fast and Scalable Genetic Algorithm-Based Approach for Planning of Microgrids in Distribution Networks

As a result of climate change, extreme weather events are occurring more frequently and with increasing impact. This trend poses a significant challenge for distribution utilities and system operators to ensure that there is uninterrupted power supply to critical loads in their networks; thus, the level of proactive preparation of the distribution system to be able to handle severe impacts of extreme weather events represents the system's resilience. One method that distribution system planners can use to prepare for future extreme events is to plan multiple microgrids which can use local generation as much as possible to supply critical loads. But partitioning an existing distribution system such that multiple feasible islands are planned and which are capable of supporting critical loads is still challenging for distribution systems - first, because of the size of the network graph partitioning problem and, second, because of the difficulty in properly formulating the desired attributes of such islands or microgrids. Therefore, this paper presents a genetic algorithm based approach that facilitates incorporating multiple objectives for grid partitioning by formulating two types of problems - node allocation and edge elimination - and it considers multiple topological and resilience-enhancing objectives. The performance of the proposed genetic algorithm-based approach is numerically evaluated on multiple test systems as well as on a real distribution feeder in Colorado, United States.

genetic algorithm↗
DOE OSTI2024

PANDORA: A Parallel Dendrogram Construction Algorithm for Single Linkage Clustering on GPU

This paper introduces Pandora, a parallel algorithm for computing dendrograms, the hierarchical cluster trees for single linkage clustering (SLC). Current parallel approaches construct dendrograms by partitioning a minimum spanning tree and removing edges. However, they struggle with skewed, hard-to-parallelize real-world dendrograms. Consequently, computing dendrograms is the sequential bottleneck in HDBSCAN*[21], a popular SLC variant. Pandora uses recursive tree contraction to address this limitation. Pandora contracts nodes to construct progressively smaller trees. It computes the smallest contracted dendrogram and expands it by inserting contracted edges. This recursive strategy is highly parallel, skew-independent, work-optimal, and well-suited for GPUs and multicores. We develop a performance portable implementation of Pandora in Kokkos[31] and evaluate its performance on multicore CPUs and multi-vendor GPUs (e.g., Nvidia, AMD) for dendrogram construction in HDBSCAN*. Multithreaded Pandora is 2.2x faster than the current best-multithreaded implementation. Our GPU version achieves 6-20x speedup on AMD GPUs and 10-37x on NVIDIA GPUs over multithreaded Pandora. Pandora removes HDBSCAN*’s sequential bottleneck, greatly boosting efficiency, particularly with GPUs.

Sao, Piyush↗
DOE OSTI2024

Distributed Multi-GPU Community Detection on Exascale Computing Platforms

Community detection is a fundamental operation in graph mining, and by uncovering hidden structures and patterns within complex systems it helps solve fundamental problems pertaining to social networks, such as information diffusion, epidemics, and recommender systems. Scaling graph algorithms for massive networks becomes challenging on modern distributed-memory multi-GPU (Graphics Processing Unit) systems due to limitations such as irregular memory access patterns, load imbalances, higher communication-computation ratios, and cross-platform support. We present a novel algorithm HiPDPL-GPU (distributed parallel Louvain) to address these challenges. We conduct experiments involving different partitioning techniques to achieve optimized performance of HiPDPL-GPU on the two largest supercomputers: Frontier and Summit. Remarkably, HiPDPL-GPU processes a graph with 4.2 billion edges in less than 3 minutes using 1024 GPUs. Qualitatively performance of HiPDPL-GPU is similar or better compared to other state-of-the-art CPU- and GPU-based implementations. While prior GPU implementations have predominantly employed CUDA, our first-of-its-kind implementation for community detection is cross-platform, accommodating both AMD and NVIDIA GPUs.

graph algorithms, high performance comptuing↗
DOE OSTI2024

Distributed Multi-GPU Community Detection on Exascale Computing Platforms

Community detection is a fundamental operation in graph mining, and by uncovering hidden structures and patterns within complex systems it helps solve fundamental problems pertaining to social networks, such as information diffusion, epidemics, and recommender systems. Scaling graph algorithms for massive networks becomes challenging on modern distributed-memory multi-GPU (Graphics Processing Unit) systems due to limitations such as irregular memory access patterns, load imbalances, higher communication-computation ratios, and cross-platform support. We present a novel algorithm HiPDPL-GPU (Distributed Parallel Louvain) to address these challenges. We conduct experiments involving different partitioning techniques to achieve an optimized performance of HiPDPL-GPU on the two largest supercomputers: Frontier and Summit. Remarkably, HiPDPL-GPU processes a graph with 4.2 billion edges in less than 3 minutes using 1024 GPUs. Qualitatively, the performance of HiPDPL-GPU is similar or better compared to other state-of-the-art CPU- and GPU-based implementations. While prior GPU implementations have predominantly employed CUDA, our first-of-its-kind implementation for community detection is cross-platform, accommodating both AMD and NVIDIA GPUs.

Sattar, Naw Safrin↗
DOE OSTI2024

Scheduling and Performance of Asynchronous Tasks in Fortran 2018 with FEATS

Most parallel scientific programs contain compiler directives (pragmas) such as those from OpenMP (Hermanns in Parallel programming in Fortran 95 using openMP, 2002. School of Aeronautical Engineering, Universidad Politécnica de Madrid, España, 2011), explicit calls to runtime library procedures such as those implementing the Message Passing Interface (MPI) (in A message-passing interface standard version 4.0, 2021. https://www.mpi-forum.org/docs/mpi-4.0/mpi40-report.pdf), or compiler-specific language extensions such as those provided by CUDA (Ruetsch and Fatica in CUDA Fortran for scientists and engineers: best practices for efficient CUDA Fortran programming, Elsevier, 2013). By contrast, the recent Fortran standards empower developers to express parallel algorithms without directly referencing lower-level parallel programming models (Numrich in Parallel programming with co-arrays, CRC Press, 2018, and Curcic in Modern Fortran: building efficient parallel applications, Manning Publications, 2020). Fortran’s parallel features place the language within the Partitioned Global Address Space (PGAS) class of programming models. When writing programs that exploit data parallelism, application developers often find it straightforward to develop custom parallel algorithms. Problems involving complex, heterogeneous, staged calculations, however, pose much greater challenges. Such applications require careful coordination of tasks in a manner that respects dependencies prescribed by a directed acyclic graph. When rolling one’s own solution proves difficult, extending a customizable framework becomes attractive. Further, the paper presents the design, implementation, and use of the Framework for Extensible Asynchronous Task Scheduling (FEATS), which we believe to be the first task scheduling tool written in modern Fortran. We describe the benefits and compromises associated with choosing Fortran as the implementation language, and we propose ways in which future Fortran standards can best support the use case in this paper.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

The unitary dependence theory for characterizing quantum circuits and states

Abstract Most existing quantum algorithms are discovered accidentally or adapted from classical algorithms, and there is the need for a systematic theory to understand and design quantum circuits. Here we develop a unitary dependence theory to characterize the behaviors of quantum circuits and states in terms of how quantum gates manipulate qubits and determine their measurement probabilities. Compared to the conventional entanglement description of quantum circuits and states, the unitary dependence picture offers more practical information on the measurement and manipulation of qubits, easier generalization to many-qubit systems, and better robustness upon partitioning of the system. The unitary dependence theory can be applied to systematically understand existing quantum circuits and design new quantum algorithms.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗