Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “randomized 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 811 records · Page 45
All sourcesNASA NTRSDOE OSTI
DOE OSTI2018

Teaching Game Theory to Kids and Limits of Prediction

I have once been asked to read a lecture to a group of 6th graders on Game Theory. After agreeing to it, I realized that explaining the game theory basics to 6th graders my be difficult, given that terms such as Nash equilibrium, minimax, maximin, optimization may not resonate in a 6th grade classroom. Instead I've introduced game theory using the rock-paper-scissors (RPS) game. Turns out kids are excellent gametheoreticians. In RPS, they understood both the benefits of randomizing their own strategy and of predicting their opponent's moves. They offered a number of heuristics both for the prediction and opening move. These heuristics included optimizing against past opponent moves, such as not playing rock if the opponent just played scissors, and playing a specific opening hand, such as "paper". Visualizing the effects of such strategic choices on-the-fly would be interesting and educational. This brief essay attempts demonstrating and visualizing the value of a few different strategic options in RPS. Specifically, we would like to illustrate the following: 1) what is the value of being unpredictable?; and 2) what is the value of being able to predict your opponent? In regard to prediction of human players, the question 2) has been reflected in Jon McLoone's entry in Wolfram Blog from January 20, 2014[1]. McLoone created a predictive algorithm for playing against human opponents, that learns to beat human opponents reliably after approximately 30 - 40 games. I use McLoone's implementation to represent a predictive and random strategies. The rest of this documents 1) investigates performance of this predictive strategy against a random strategy (which is optimal in RPS) and in 2) attempts to turn this predictive power against the predictive strategy by allowing the opponent the full knowledge of the predictor's strategy (but not the choices made using the strategy). This exposes a weakness in predictions made without taking risks into account by illustrating that predictive strategy may make the predictor predictable as well.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2012

HIGH-CONTRAST IMAGING VIA MODAL CONVERGENCE OF DEFORMABLE MIRROR

For extremely high contrast imaging, such as direct observation of faint stellar companions, an adaptive optics system is required to produce low-halo and low-speckle regions in the focal plane. A method for deformable mirror control is proposed to achieve this goal. The method relies on a modal convergence of the deformable mirror driven by a focal-plane metric. The modal sets are derived from the Walsh functions. The Walsh-function modes serve two purposes: the expansion of the actuator displacements and the expansion of the phase functions. Taking advantage of the unique properties of the modal functions, a universal control algorithm is devised for the realization of high-contrast focal planes with and without the help of conventional coronagraphy. Numerical modeling is conducted to simulate complete imaging systems under various scenarios. It is shown that the proposed method reliably produces high-contrast focal planes using either a segmented or a membrane mirror. In the presence of random aberration the method is shown to be able to maintain high-contrast focal planes. Requiring neither retrieval of electric fields nor detailed knowledge of the deformable mirrors, this technique may allow high-contrast imaging in real time.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2021

Removal of spurious data in Bragg coherent diffraction imaging: an algorithm for automated data preprocessing

Bragg coherent diffraction imaging (BCDI) provides a powerful tool for obtaining high-resolution structural information from nanocrystalline materials. Here a BCDI sample consisting of a large number of randomly oriented nanoscale crystals is considered. Ideally, only one crystal is oriented to produce a Bragg peak on the detector. However, diffraction from other crystals often produces additional signals on the detector. Before the measured diffraction patterns can be processed into structural images, scientists routinely need to manually identify and remove the `alien' intensities from sources other than the intended crystal. With the development of modern high-coherence storage rings, such as the upgraded Advanced Photon Source (APS), the already slow process of manual preprocessing will be untenable for the large volumes of data that will be produced. An automated method of identifying and deleting alien intensities is proposed. This method exploits the fact that BCDI of a perfect crystal produces diffraction data with inversion symmetry around the Bragg peak. This approach uses the machine learning clustering method DBSCAN to distinguish between diffraction from multiple sources, and then calculates cluster size and inversion symmetry to assess whether clusters of intensity belong to desired data or alien signals. This approach can dramatically reduce the amount of time spent manually processing data, allowing BCDI data processing capabilities to keep pace with the technological advances of fourth-generation synchrotron light sources.

36 MATERIALS SCIENCE↗
DOE OSTI2023

Computing rank‐revealing factorizations of matrices stored out‐of‐core

This paper describes efficient algorithms for computing rank-revealing factorizations of matrices that are too large to fit in main memory (RAM), and must instead be stored on slow external memory devices such as disks (out-of-core or out-of-memory). Traditional algorithms for computing rank-revealing factorizations (such as the column pivoted QR factorization and the singular value decomposition) are very communication intensive as they require many vector-vector and matrix-vector operations, which become prohibitively expensive when data is not in RAM. Randomization allows to reformulate new methods so that large contiguous blocks of the matrix are processed in bulk. The paper describes two distinct methods. The first is a blocked version of column pivoted Householder QR, organized as a “left-looking” method to minimize the number of the expensive write operations. The second method results employs a UTV factorization. It is organized as an algorithm-by-blocks to overlap computations and I/O operations. As it incorporates power iterations, it is much better at revealing the numerical rank. Numerical experiments on several computers demonstrate that the new algorithms are almost as fast when processing data stored on slow memory devices as traditional algorithms are for data stored in RAM.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Austenitic parent grain reconstruction in martensitic steel using deep learning

In this work we develop a deep convolutional architecture to estimate the prior austenite structure from observed martensite electron backscatter diffraction micrographs. A novel data augmentation strategy randomizes the global reference coordinate system which makes it possible to train our model from only four micrographs. The model is much faster than algorithmic approaches and generalizes well when applied to micrographs of a different material. Empirical evidence suggests the efficacy of the model depends on the scale of the microstructure and receptive field of the vision model. Furthermore, this work demonstrates that modern computer vision approaches are well suited for capturing complex spatial-orientation patterns present in orientation imaging micrographs.

36 MATERIALS SCIENCE↗
DOE OSTI2017

Phase Imaging: A Compressive Sensing Approach

Since Wolfgang Pauli posed the question in 1933, whether the probability densities |Ψ(r)|² (real-space image) and |Ψ(q)|² (reciprocal space image) uniquely determine the wave function Ψ(r) [1], the so called Pauli Problem sparked numerous methods in all fields of microscopy [2, 3]. Reconstructing the complete wave function Ψ(r) = a(r)e-iφ(r) with the amplitude a(r) and the phase φ(r) from the recorded intensity enables the possibility to directly study the electric and magnetic properties of the sample through the phase. In transmission electron microscopy (TEM), electron holography is by far the most established method for phase reconstruction [4]. Requiring a high stability of the microscope, next to the installation of a biprism in the TEM, holography cannot be applied to any microscope straightforwardly. Recently, a phase retrieval approach was proposed using conventional TEM electron diffractive imaging (EDI). Using the SAD aperture as reciprocal-space constraint, a localized sample structure can be reconstructed from its diffraction pattern and a real-space image using the hybrid input-output algorithm [5]. We present an alternative approach using compressive phase-retrieval [6]. Our approach does not require a real-space image. Instead, random complimentary pairs of checkerboard masks are cut into a 200 nm Pt foil covering a conventional TEM aperture (cf. Figure 1). Used as SAD aperture, subsequently diffraction patterns are recorded from the same sample area. Hereby every mask blocks different parts of gold particles on a carbon support (cf. Figure 2). The compressive sensing problem has the following formulation. First, we note that the complex-valued reciprocal-space wave-function is the Fourier transform of the (also complex-valued) real-space wave-function, Ψ(q) = F[Ψ(r)], and subsequently the diffraction pattern image is given by |Ψ(q)|2 = |F[Ψ(r)]|2. We want to find Ψ(r) given a few differently coded diffraction pattern measurements yn = |F[HnΨ(r)]|2, where the matrices Hn encode the mask structure of the aperture. This is a nonlinear inverse problem, but has been shown to be solvable even in the underdetermined case [6]. Since each diffraction pattern yn contains diffraction information from selected regions of the same sample, the differences in each pattern contain local phase information, which can be combined to form a full estimate of the real-space wave-function[7]. References: [1] W. Pauli in “Die allgemeinen Prinzipien der Wellenmechanik“, ed. H Geiger and W Scheel, (Julius Springer, Berlin). [2] A. Tonomura, Rev. Mod. Phys. 59 (1987), p. 639. [3] J. Miao et al, Nature 400 (1999), p. 342. [4] H. Lichte et al, Annu. Rev. Mater. Res. 37 (2007), p. 539. [5] J. Yamasaki et al, Appl. Phys. Lett. 101 (2012), 234105. [6] P Schniter and S Rangan. Signal Proc., IEEE Trans. on. 64(4), (2015), pp. 1043. [7] Supported by the Chemical Imaging, Signature Discovery, and Analytics in Motion initiatives at PNNL. PNNL is operated by Battelle Memorial Inst. for the US DOE; contract DE-AC05-76RL01830.

Schneider, Sebastian↗
DOE OSTI2015

2D Surface Structures in Small Zeolite MFI Crystals

Utilization of new hierarchical zeolites comprised of small crystallites (<50 nm) provides enhanced processing rates in separation and catalytic applications. Yet, molecular permeation through surface pores in small zeolite crystals has been shown to control the overall rate, resulting in apparent site-to-site intracrystalline kinetics that vary by as much as three orders of magnitude. Here, the external surface of small zeolite MFI crystals was characterized by combining experimental kinetics and molecular simulation to evaluate the hypothesis of a two-dimensional distribution of surface pores that are either open or closed (i.e., fraction, popen). The movement of benzene through the MFI lattice and surface was evaluated with a discrete space kinetic Monte Carlo algorithm with varying particle sizes (1.0 nm ≤ R ≤ 640 nm) and fraction of surface pore openings (10 –4 < p open < 10 0 ). Introduction of randomly distributed surface pore blockages was shown to increase the molecular path length for adsorbates exiting the particle while maintaining a constant apparent activation energy, consistent with additional molecular motion near the internal surface. Comparison of the dimensionless surface barrier (λ = τ Surface /τ Bulk ) obtained by simulation to experimental measurements (zero length chromatography) for silicalite-1 particles (62 nm to 3 μm, 50–110 °C) reveals that the vast majority (>99.9%) of surface pores must be blocked (p open < 10 –3 ) to justify the observed surface permeation rate of hydrocarbon adsorbates.

36 MATERIALS SCIENCE↗
DOE OSTI2020

Machine Learning for Searching the Dark Energy Survey for Trans-Neptunian Objects

In this paper we investigate how implementing machine learning could improve the efficiency of the search for Trans-Neptunian Objects (TNOs) within Dark Energy Survey (DES) data when used alongside orbit fitting. The discovery of multiple TNOs that appear to show a similarity in their orbital parameters has led to the suggestion that one or more undetected planets, an as yet undiscovered “Planet 9”, may be present in the outer solar system. DES is well placed to detect such a planet and has already been used to discover many other TNOs. Here, we perform tests on eight different supervised machine learning algorithms, using a data set consisting of simulated TNOs buried within real DES noise data. We found that the best performing classifier was the Random Forest which, when optimized, performed well at detecting the rare objects. We achieve an area under the receiver operating characteristic (ROC) curve, (AUC) = 0.996 ± 0.001. After optimizing the decision threshold of the Random Forest, we achieve a recall of 0.96 while maintaining a precision of 0.80. Finally, by using the optimized classifier to pre-select objects, we are able to run the orbit-fitting stage of our detection pipeline five times faster.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗
DOE OSTI2024

Newton-Raphson AC Power Flow Convergence Based on Deep Learning Initialization and Homotopy Continuation

Power flow forms the basis of many power system studies. With the increased penetration of renewable energy, grid planners tend to perform multiple power flow simulations under various operating conditions and not just selected snapshots at peak or light load conditions. Getting a converged AC power flow (ACPF) case remains a significant challenge for grid planners especially in large power grid networks. This paper proposes a two-stage approach to improve Newton-Raphson ACPF convergence and was applied to a 6102 bus Electric Reliability Council of Texas (ERCOT) system. The first stage utilizes a deep learning-based initializer with data re-training. Here a deep neural network (DNN) initializer is developed to provide better initial voltage magnitude and angle guesses to aid in power flow convergence. This is because Newton-Raphson ACPF is quite sensitive to the initial conditions and bad initialization could lead to divergence. The DNN initializer includes a data re-training framework that improves the initializer's performance when faced with limited training data. The DNN initializer successfully solved 3,285 cases out of 3,899 non-converging dispatch and performed better than random forest and DC power flow initialization methods. ACPF cases not solved in this first stage are then passed through a hot-starting algorithm based on homotopy continuation with switched shunt control. The hot-starting algorithm successfully converged 416 cases out of the remaining 614 non-converging ACPF dispatch. In conclusion, the combined two-stage approach achieved a 94.9% success rate, by converging a total of 3,701 cases out of the initial 3,899 unsolved cases.

Deep learning↗
DOE OSTI2023

Efficient QAOA Optimization using Directed Restarts and Graph Lookup

Variational Quantum Algorithms (VQA) aim to enhance the capabilities of Noisy Intermediate-Scale Quantum (NISQ) devices. These algorithms utilize parameterized circuits and classical optimizers to iteratively execute circuits with varying parameters. However, VQA faces computational overheads due to repeated iterations and random restarts. Prior work suggests using basic sub-graphs to transfer parameters for the input graph, reducing optimizer overheads but limiting applicability to structured regular graphs. In real-world applications, random irregular graphs are common, and existing methods are not scalable or practical for such graphs. This paper presents a framework that aims to improve random irregular graphs in VQA. The framework uses graph similarity and important features like total edge counts, average edge counts, and variance. It follows an iterative process to choose basis sub-graphs from a small database and adjust parameters accordingly. Classical optimizers then utilize these parameters to determine when to restart and perform gradient descent. This approach increases the chances of reaching global maximum points.

Wang, Meng↗
DOE OSTI2024

Autonomous Emergency Landing for Fixed-Wing Aircraft with Energy-Constrained Closed-Loop Prediction

Here this paper presents a new approach for autonomous motion planning for aircraft suffering from a loss-of-thrust emergency. Specifically, we show how modifications to the Closed-Loop Rapidly exploring Random Trees (CL-RRT) framework combined with controlled energy dissipation can enable rapid and effective kinodynamic motion planning. This CL-RRT Glide algorithm uses closed-loop prediction not only for node connections but also to estimate the remaining energy and prune infeasible paths. This greatly speeds up the search process, which is essential for emergency situations. In addition, we improve the ability of the gliding aircraft to reach a goal position and energy state. We do so by creating a Dissipative Total Energy Control Scheme (TECS). Dissipative TECS enables the glider to lose excess altitude in order to reach a desired energy level. Simulation results illustrate how the proposed methods enable faster motion planning. We also integrate the system into a small unmanned aerial vehicle system and experimentally demonstrate autonomous glide planning and execution during a motor-failure event. This type of algorithm can primarily benefit unmanned aircraft but can also serve to assist pilots in stressful emergency situations.

42 ENGINEERING↗
DOE OSTI2018

Efficient Stochastic Inversion Using Adjoint Models and Kernel-PCA

Performing stochastic inversion on a computationally expensive forward simulation model with a high-dimensional uncertain parameter space (e.g. a spatial random field) is computationally prohibitive even with gradient information provided. Moreover, the ‘nonlinear’ mapping from parameters to observables generally gives rise to non-Gaussian posteriors even with Gaussian priors, thus hampering the use of efficient inversion algorithms designed for models with Gaussian assumptions. In this work, we propose a novel Bayesian stochastic inversion methodology, characterized by a tight coupling between a gradient-based Langevin Markov Chain Monte Carlo (LMCMC) method and a kernel principal component analysis (KPCA). This approach addresses the ‘curse-of-dimensionality’ via KPCA to identify a low-dimensional feature space within the high-dimensional and nonlinearly correlated spatial random field. Moreover, non-Gaussian full posterior probability distribution functions are estimated via an efficient LMCMC method on both the projected low-dimensional feature space and the recovered high-dimensional parameter space. We demonstrate this computational framework by integrating and adapting recent developments such as data-driven statistics-on-manifolds constructions and reduction-through-projection techniques to solve inverse problems in linear elasticity.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2015

An adaptive filtered back-projection for photoacoustic image reconstruction

Purpose: The purpose of this study is to develop an improved filtered-back-projection (FBP) algorithm for photoacoustic tomography (PAT), which allows image reconstruction with higher quality compared to images reconstructed through traditional algorithms. Methods: A rigorous expression of a weighting function has been derived directly from a photoacoustic wave equation and used as a ramp filter in Fourier domain. The authors’ new algorithm utilizes this weighting function to precisely calculate each photoacoustic signal’s contribution and then reconstructs the image based on the retarded potential generated from the photoacoustic sources. In addition, an adaptive criterion has been derived for selecting the cutoff frequency of a low pass filter. Two computational phantoms were created to test the algorithm. The first phantom contained five spheres with each sphere having different absorbances. The phantom was used to test the capability for correctly representing both the geometry and the relative absorbed energy in a planar measurement system. The authors also used another phantom containing absorbers of different sizes with overlapping geometry to evaluate the performance of the new method for complicated geometry. In addition, random noise background was added to the simulated data, which were obtained by using an arc-shaped array of 50 evenly distributed transducers that spanned 160° over a circle with a radius of 65 mm. A normalized factor between the neighbored transducers was applied for correcting measurement signals in PAT simulations. The authors assumed that the scanned object was mounted on a holder that rotated over the full 360° and the scans were set to a sampling rate of 20.48 MHz. Results: The authors have obtained reconstructed images of the computerized phantoms by utilizing the new FBP algorithm. From the reconstructed image of the first phantom, one can see that this new approach allows not only obtaining a sharp image but also showing the correct signal strength of the absorbers. The reconstructed image of the second phantom further demonstrates the capability to form clear images of the spheres with sharp borders in the overlapping geometry. The smallest sphere is clearly visible and distinguishable, even though it is surrounded by two big spheres. In addition, image reconstructions were conducted with randomized noise added to the observed signals to mimic realistic experimental conditions. Conclusions: The authors have developed a new FBP algorithm that is capable for reconstructing high quality images with correct relative intensities and sharp borders for PAT. The results demonstrate that the weighting function serves as a precise ramp filter for processing the observed signals in the Fourier domain. In addition, this algorithm allows an adaptive determination of the cutoff frequency for the applied low pass filter.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗
DOE OSTI2023

A Consistent Representation of Cloud Overlap and Cloud Subgrid Vertical Heterogeneity

Many global climate models underestimate the cloud cover and overestimate the cloud albedo, especially for low-level clouds. We determine how a correct representation of the vertical structure of clouds can fix part of this bias. We use the 1D McICA framework and focus on low-level clouds. Using Large Eddy Simulations results as reference, we propose a method based on exponential-random overlap that represents the cloud overlap between layers and the subgrid cloud properties over several vertical scales, with a single value of the overlap parameter. Starting from a coarse vertical grid, representative of atmospheric models, this algorithm is used to generate the vertical profile of the cloud fraction with a finer vertical resolution, or to generate it on the coarse grid but with subgrid heterogeneity and cloud overlap that ensures a correct cloud cover. Doing so we find decorrelation lengths are dependent on the vertical resolution, except if the vertical subgrid heterogeneity and interlayer overlap are taken into account coherently. We confirm that the frequently used maximum-random overlap leads to a significant error by underestimating the low-level cloud cover with a relative error of about 50%, that can lead to an error of SW cloud albedo as big as 70%. Not taking into account the subgrid vertical heterogeneity of clouds can cause a relative error of 20% in brightness, assuming the cloud cover is correct.

54 ENVIRONMENTAL SCIENCES↗
DOE OSTI2017

Validating precision estimates in horizontal wind measurements from a Doppler lidar

Results from a recent field campaign are used to assess the accuracy of wind speed and direction precision estimates produced by a Doppler lidar wind retrieval algorithm. The algorithm, which is based on the traditional velocity-azimuth-display (VAD) technique, estimates the wind speed and direction measurement precision using standard error propagation techniques, assuming the input data (i.e., radial velocities) to be contaminated by random, zero-mean, errors. For this study, the lidar was configured to execute an 8-beam plan-position-indicator (PPI) scan once every 12 min during the 6-week deployment period. Several wind retrieval trials were conducted using different schemes for estimating the precision in the radial velocity measurements. Here, the resulting wind speed and direction precision estimates were compared to differences in wind speed and direction between the VAD algorithm and sonic anemometer measurements taken on a nearby 300 m tower.

17 WIND ENERGY↗
DOE OSTI2022

Quantum computational phase transition in combinatorial problems

Quantum Approximate Optimization algorithm (QAOA) aims to search for approximate solutions to discrete optimization problems with near-term quantum computers. As there are no algorithmic guarantee possible for QAOA to outperform classical computers, without a proof that bounded-error quantum polynomial time (BQP) ≠ nondeterministic polynomial time (NP), it is necessary to investigate the empirical advantages of QAOA. We identify a computational phase transition of QAOA when solving hard problems such as SAT—random instances are most difficult to train at a critical problem density. We connect the transition to the controllability and the complexity of QAOA circuits. Moreover, we find that the critical problem density in general deviates from the SAT-UNSAT phase transition, where the hardest instances for classical algorithms lies. Then, we show that the high problem density region, which limits QAOA’s performance in hard optimization problems (reachability deficits), is actually a good place to utilize QAOA: its approximation ratio has a much slower decay with the problem density, compared to classical approximate algorithms. Indeed, it is exactly in this region that quantum advantages of QAOA over classical approximate algorithms can be identified.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2026

Hamiltonian simulation in Zeno subspaces

Here, we investigate the quantum Zeno effect as a framework for designing and analyzing quantum algorithms for Hamiltonian simulation. We show that frequent projective measurements of an ancilla qubit register can be used to simulate quantum dynamics on a target qubit register with a circuit complexity similar to randomized approaches. The classical sampling overhead in the latter approaches is traded for ancilla qubit overhead in Zeno-based approaches. A second-order Zeno sequence is developed to improve scaling and implementations through unitary kicks are discussed. We derive rigorous error bounds that allow for identifying the associated circuit complexities for the first- and second-order Zeno sequences. We show that the circuits over the combined register can be identified as a subroutine commonly used in post-Trotter Hamiltonian simulation methods. We build on this observation to reveal connections between different Hamiltonian simulation algorithms.

Hamiltonian simulation↗
DOE OSTI2013

ON THE ESTIMATION OF RANDOM UNCERTAINTIES OF STAR FORMATION HISTORIES

The standard technique for measurement of random uncertainties of star formation histories (SFHs) is the bootstrap Monte Carlo, in which the color-magnitude diagram (CMD) is repeatedly resampled. The variation in SFHs measured from the resampled CMDs is assumed to represent the random uncertainty in the SFH measured from the original data. However, this technique systematically and significantly underestimates the uncertainties for times in which the measured star formation rate is low or zero, leading to overly (and incorrectly) high confidence in that measurement. This study proposes an alternative technique, the Markov Chain Monte Carlo (MCMC), which samples the probability distribution of the parameters used in the original solution to directly estimate confidence intervals. While the most commonly used MCMC algorithms are incapable of adequately sampling a probability distribution that can involve thousands of highly correlated dimensions, the Hybrid Monte Carlo algorithm is shown to be extremely effective and efficient for this particular task. Several implementation details, such as the handling of implicit priors created by parameterization of the SFH, are discussed in detail.

79 ASTRONOMY AND ASTROPHYSICS↗