Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “randomized 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 289 records · Page 16

FuseIM: Fusing Probabilistic Traversals for Influence Maximization on Exascale Systems

Probabilistic breadth-first traversals (BPTs) are used in many network science and graph machine learning applications. In this paper, we are motivated by the application of BPTs in stochastic diffusion-based graph problems such as influence maximization. These applications heavily rely on BPTs to implement a Monte-Carlo sampling step for their approximations. Given the large sampling complexity, stochasticity of the diffusion process, and the inherent irregularity in real-world graph topologies, efficiently parallelizing these BPTs remains significantly challenging. In this paper, we present a new algorithm to fuse massive number of concurrently executing BPTs with random starts on the input graph. Our algorithm is designed to fuse BPTs by combining separate traversals into a unified frontier on distributed multi-GPU systems. To show the general applicability of the fused BPT technique, we have incorporated it into two state-of-the-art influence maximization parallel implementations (gIM and Ripples). Our experiments on up to 4K nodes of the OLCF Frontier supercomputer (32,768 GPUs and 196K CPU cores) show strong scaling behavior, and that fused BPTs can improve the performance of these implementations up to 34x (for gIM) and ~360x (for Ripples).

Neff, Reece W.↗

Estimating Compressional Velocity and Bulk Density Logs in Marine Gas Hydrates Using Machine Learning

Compressional velocity (Vp) and bulk density (ρb) logs are essential for characterizing gas hydrates and near-seafloor sediments; however, it is sometimes difficult to acquire these logs due to poor borehole conditions, safety concerns, or cost-related issues. We present a machine learning approach to predict either compressional Vp or ρb logs with high accuracy and low error in near-seafloor sediments within water-saturated intervals, in intervals where hydrate fills fractures, and intervals where hydrate occupies the primary pore space. We use scientific-quality logging-while-drilling well logs, gamma ray, ρb, Vp, and resistivity to train the machine learning model to predict Vp or ρb logs. Of the six machine learning algorithms tested (multilinear regression, polynomial regression, polynomial regression with ridge regularization, K nearest neighbors, random forest, and multilayer perceptron), we find that the random forest and K nearest neighbors algorithms are best suited to predicting Vp and ρb logs based on coefficients of determination (R2) greater than 70% and mean absolute percentage errors less than 4%. Given the high accuracy and low error results for Vp and ρb prediction in both hydrate and water-saturated sediments, we argue that our model can be applied in most LWD wells to predict Vp or ρb logs in near-seafloor siliciclastic sediments on continental slopes irrespective of the presence or absence of gas hydrate.

Naim, Fawz↗

Grover-QAOA for 3-SAT: quadratic speedup, fair-sampling, and parameter clustering

Abstract The SAT problem is a prototypical NP-complete problem of fundamental importance in computational complexity theory with many applications in science and engineering; as such, it has long served as an essential benchmark for classical and quantum algorithms. This study shows numerical evidence for a quadratic speedup of the Grover Quantum Approximate Optimization Algorithm (G-QAOA) over random sampling for finding all solutions to 3-SAT (All-SAT) and Max-SAT problems. G-QAOA is less resource-intensive and more adaptable for these problems than Grover’s algorithm, and it surpasses conventional QAOA in its ability to sample all solutions. We show these benefits by classical simulations of many-round G-QAOA on thousands of random 3-SAT instances. We also observe G-QAOA advantages on the IonQ Aria quantum computer for small instances, finding that current hardware suffices to determine and sample all solutions. Interestingly, a single-angle-pair constraint that uses the same pair of angles at each G-QAOA round greatly reduces the classical computational overhead of optimizing the G-QAOA angles while preserving its quadratic speedup. We also find parameter clustering of the angles. The single-angle-pair protocol and parameter clustering significantly reduce obstacles to classical optimization of the G-QAOA angles.

Zhang, Zewen (ORCID:000000032258613X)↗

Differentiation and classification of bacterial endotoxins based on surface enhanced Raman scattering and advanced machine learning

Bacterial endotoxin, a major component of the Gram-negative bacterial outer membrane leaflet, is a lipopolysaccharide shed from bacteria during their growth and infection and can be utilized as a biomarker for bacterial detection. Here, the surface enhanced Raman scattering (SERS) spectra of eleven bacterial endotoxins with an average detection amount of 8.75 pg per measurement have been obtained based on silver nanorod array substrates, and the characteristic SERS peaks have been identified. With appropriate spectral pre-processing procedures, different classical machine learning algorithms, including support vector machine, k-nearest neighbor, random forest, etc., and a modified deep learning algorithm, RamanNet, have been applied to differentiate and classify these endotoxins. It has been found that most conventional machine learning algorithms can attain a differentiation accuracy of >99%, while RamanNet can achieve 100% accuracy. Such an approach has the potential for precise classification of endotoxins and could be used for rapid medical diagnoses and therapeutic decisions for pathogenic infections.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Evaluation of Algorithms for a Miles-in-Trail Decision Support Tool

Four machine learning algorithms were prototyped and evaluated for use in a proposed decision support tool that would assist air traffic managers as they set Miles-in-Trail restrictions. The tool would display probabilities that each possible Miles-in-Trail value should be used in a given situation. The algorithms were evaluated with an expected Miles-in-Trail cost that assumes traffic managers set restrictions based on the tool-suggested probabilities. Basic Support Vector Machine, random forest, and decision tree algorithms were evaluated, as was a softmax regression algorithm that was modified to explicitly reduce the expected Miles-in-Trail cost. The algorithms were evaluated with data from the summer of 2011 for air traffic flows bound to the Newark Liberty International Airport (EWR) over the ARD, PENNS, and SHAFF fixes. The algorithms were provided with 18 input features that describe the weather at EWR, the runway configuration at EWR, the scheduled traffic demand at EWR and the fixes, and other traffic management initiatives in place at EWR. Features describing other traffic management initiatives at EWR and the weather at EWR achieved relatively high information gain scores, indicating that they are the most useful for estimating Miles-in-Trail. In spite of a high variance or over-fitting problem, the decision tree algorithm achieved the lowest expected Miles-in-Trail costs when the algorithms were evaluated using 10-fold cross validation with the summer 2011 data for these air traffic flows.

Bloem, Michael↗

Numerical solution of the problem of flame propagation by the use of the random element method

A numerical, grid-free algorithm is presented for one-dimensional reaction-diffusion model of laminar flame propagation in premixed gases. It is based on the random element method we developed for the analysis of diffusional processes. The effect of combustion is taken into account by applying the principle of fractional steps to separate the process of diffusion, modeled by the random walk of computational elements, from the exothermic effects of chemical reaction, monitoring their strength. The validity of the algorithm is demonstrated by application to flame propagation problems for which exact solutions exist. The flame speed evaluated by its use oscillates around the exact value at a relatively small amplitude, while the temperature and species concentration profiles are self-correcting in their convergence to the exact solution. A satisfactory resolution is obtained by the use of quite a small number of computational elements which automatically adjust their distribution of fit sharp gradients.

Ghoniem, A. F.↗

Self‐Potential Tomography Preconditioned by Particle Swarm Optimization—Application to Monitoring Hyporheic Exchange in a Bedrock River

Abstract A self‐potential (SP) data‐inversion algorithm was developed and tested on an analytical model of electrical‐potential profile data attributed to single and multiple polarized electrical sources. The developed algorithm was then validated by an application to SP‐monitoring field data measured on the floodplain of East Fork Poplar Creek, Oak Ridge, Tennessee, to image electrical sources in areas conducive to preferential flow into the flood plain from the bedrock‐lined riverbed. The algorithm combined stochastic source‐localization by particle‐swarm‐optimization (PSO) of electrical sources characterized by simplified geometries with source tomography by regularized weighted least‐squares minimization of a quadratic objective function. Prior information was incorporated by preconditioning the tomography algorithm by PSO results. Variable percentages of random noise were added to analytical‐model data to evaluate the algorithm performance. Results indicated that true parameters of single‐source models were inverted and approximated with small residual error, whereas inversion of analytical‐model data representing multiple electrical sources accurately approximated the locations of the sources but miscalculated some parameters because of the non‐uniqueness of the inverse‐model solution. Source tomography applied to analytical model data during testing produced a spatially continuous parameter field that identified the locations of point‐scale synthetic dipole sources of electrical current flow with varying degrees of accuracy depending on the prior information incorporated into the tomography. When applied to SP‐monitoring field data, the algorithm imaged electrical sources within a known fault that intersects the bedrock riverbed and flood plain of East Fork Poplar Creek and depicted dynamic electrical conditions attributed to hyporheic exchange.

54 ENVIRONMENTAL SCIENCES↗

Quantum annealing-assisted lattice optimization

High Entropy Alloys (HEAs) have drawn great interest due to their exceptional properties compared to conventional materials. The configuration of HEA system is considered a key to their superior properties, but exhausting all possible configurations of atom coordinates and species to find the ground energy state is extremely challenging. In this work, we proposed a quantum annealing-assisted lattice optimization (QALO) algorithm, which is an active learning framework that integrates the Field-aware Factorization Machine (FFM) as the surrogate model for lattice energy prediction, Quantum Annealing (QA) as an optimizer and Machine Learning Potential (MLP) for ground truth energy calculation. By applying our algorithm to the NbMoTaW alloy, we reproduced the Nb depletion and W enrichment observed in bulk HEA. We found our optimized HEAs to have superior mechanical properties compared to the randomly generated alloy configurations. Our algorithm highlights the potential of quantum computing in materials design and discovery, laying a foundation for further exploring and optimizing structure-property relationships.

36 MATERIALS SCIENCE↗

Traffic Prediction for Uncommunicative Aircraft in Terminal Airspace: Development Framework and Performance Evaluations

This paper presents an air traffic prediction algorithm that takes observations of an aircraft and classifies aircraft type, estimates the aircraft's intent to and method of joining an airport traffic pattern, and predicts the aircaft's future trajectory. To develop algorithms that enable autonomous aircraft to safely insert into un-towered traffic patterns, several challenges need to be addressed. These challenges range from traffic detection to sensor fusion to own-ship trajectory replanning. Critical to a trajectory replanning algorithm is information regarding the future behavior of all traffic aircraft in the operational environment. The presented traffic prediction algorithm generates this information using regular measurements of traffic aircraft position and velocity to classify the aircraft by speed-class, estimate how the aircraft will approach the runway, and construct a predicted trajectory to the runway including future positions and velocities at specific times. The predictions of the presented algorithm are the necessary inputs for any downstream traffic pattern sequencing and own-ship trajectory planning routines. The presented algorithm is benchmarked using approximately 300 randomized traffic trajectories, spanning four vehicle weight classes and eight traffic entry types. While the algorithm can process multiple traffic vehicles in the terminal area, there is no prediction of traffic-on-traffic interaction. Each traffic vehicle is processed separately.

John D McMinn↗

Systems aspects of COBE science data compression

A general approach to compression of diverse data from large scientific projects has been developed and this paper addresses the appropriate system and scientific constraints together with the algorithm development and test strategy. This framework has been implemented for the COsmic Background Explorer spacecraft (COBE) by retrofitting the existing VAS-based data management system with high-performance compression software permitting random access to the data. Algorithms which incorporate scientific knowledge and consume relatively few system resources are preferred over ad hoc methods. COBE exceeded its planned storage by a large and growing factor and the retrieval of data significantly affects the processing, delaying the availability of data for scientific usage and software test. Embedded compression software is planned to make the project tractable by reducing the data storage volume to an acceptable level during normal processing.

Freedman, I.↗

Data processing/display design for the space shuttle/spacelab Electromagnetic Environment Experiment (EEE)

Methods for data analysis, data compression including universal coding, storage and retrieval on random access storage devices, and display were developed and implemented on the GSFC Interdata computer. The original 64 bit per frequency band representation was reduced to 10 bits through source coding/universal coding, a compression ratio of 6.4, prior to storage. Rapid encoding/decoding was achieved by the algorithms used so that rapid random access is retained.

Davisson, L. D.↗

Efficient Subset Simulation using Hamiltonian Neural Network enhanced Markov Chain Monte Carlo Methods

The Monte Carlo method delivers an unbiased estimate of the probability of failure. However, the variance of the estimate depends on the number of evaluated samples. This number must be very large for estimations of a low probability of failure. If the evaluation of each sample is computationally expensive, the crude Monte Carlo simulation strategy is impracticable. Therefore, subset simulations are used to reduce the required number of evaluations. Subset simulations require a Markov Chain Monte Carlo sampler, such as the random walk Metropolis-Hastings algorithm. The algorithm, however, struggles with sampling in low-probability regions, especially if they are narrow. As a consequence, advanced Markov Chain Monte Carlo simulations have been developed. In particular, the Hamiltonian Monte Carlo method explores the target distribution rapidly. Driven by the idea of Hamiltonian dynamics, this sampler provides a non-random walk through the target distribution. The incorporation of subset simulation and Hamiltonian Monte Carlo methods has shown promising results for reliability analysis. One downside of the Hamiltonian Monte Carlo method is that gradient evaluations are computationally expensive, especially when dealing with high-dimensional problems and evaluating long trajectories. We show that integrating Hamiltonian neural networks in Hamiltonian Monte Carlo simulations significantly speeds up the sampling task. Furthermore, the enhancement of adaptive trajectory length within the Hamiltonian Monte Carlo results in the efficient proposal of the following states. Based on this recent enhancement, we provide a fast sampling strategy for subset simulations using Hamiltonian neural networks to replace the evaluation of the gradient and significantly speed up the Hamiltonian Monte Carlo simulation.

97 MATHEMATICS AND COMPUTING↗

Application of Monte Carlo techniques to optimization of high-energy beam transport in a stochastic environment

An algorithm employing a modified sequential random perturbation, or creeping random search, was applied to the problem of optimizing the parameters of a high-energy beam transport system. The stochastic solution of the mathematical model for first-order magnetic-field expansion allows the inclusion of state-variable constraints, and the inclusion of parameter constraints allowed by the method of algorithm application eliminates the possibility of infeasible solutions. The mathematical model and the algorithm were programmed for a real-time simulation facility; thus, two important features are provided to the beam designer: (1) a strong degree of man-machine communication (even to the extent of bypassing the algorithm and applying analog-matching techniques), and (2) extensive graphics for displaying information concerning both algorithm operation and transport-system behavior. Chromatic aberration was also included in the mathematical model and in the optimization process. Results presented show this method as yielding better solutions (in terms of resolutions) to the particular problem than those of a standard analog program as well as demonstrating flexibility, in terms of elements, constraints, and chromatic aberration, allowed by user interaction with both the algorithm and the stochastic model. Example of slit usage and a limited comparison of predicted results and actual results obtained with a 600 MeV cyclotron are given.

Parrish, R. V.↗

Tensor Decompositions for Count Data that Leverage Stochastic and Deterministic Optimization

There is growing interest to extend low-rank matrix decompositions to multi-way arrays, or tensors. One fundamental low-rank tensor decomposition is the canonical polyadic decomposition (CPD). The challenge of fitting a low-rank, nonnegative CPD model to Poisson-distributed count data is of particular interest. Several popular algorithms use local search methods to approximate the global maximum likelihood estimator from local minima. Simultaneously, a recent trend in theoretical computer science and numerical linear algebra leverages randomization to solve very large, hard problems. The typical approach is to use randomization for a fast approximation and determinism for refinement to yield effective algorithms with theoretical guarantees. Two popular algorithms for Poisson CPD reflect that emergent dichotomy: CP Alternating Poisson Regression is a deterministic algorithm and Generalized Canonical Polyadic decomposition makes use of stochastic algorithms in several variants. This work extends recent work to develop two new methods that leverage randomized and deterministic algorithms for improved accuracy and performance.

97 MATHEMATICS AND COMPUTING↗

Critical points of the random cluster model with Newman–Ziff sampling

Here, we present a method for computing transition points of the random cluster model using a generalization of the Newman–Ziff algorithm, a celebrated technique in numerical percolation, to the random cluster model. The new method is straightforward to implement and works for real cluster weight q > 0. Furthermore, results for an arbitrary number of values of q can be found at once within a single simulation. Because the algorithm used to sweep through bond configurations is identical to that of Newman and Ziff, which was conceived for percolation, the method loses accuracy for large lattices when q > 1. However, by sampling the critical polynomial, accurate estimates of critical points in two dimensions can be found using relatively small lattice sizes, which we demonstrate here by computing critical points for non-integer values of q on the square lattice, to compare with the exact solution, and on the unsolved non-planar square matching lattice. The latter results would be much more difficult to obtain using other techniques.

97 MATHEMATICS AND COMPUTING↗

Applying Simulated Annealing to Problems in Model-Based Diagnosis

Generating all diagnoses is computationally intractable. Therefore, many of the state-of-the-art approaches are incomplete. Quantum computers may however offer a solution. The first commercially available quantum computer is being used to minimize polynomials that are difficult for classical simulated annealing but easy for quantum annealing. All problems in Model-based Diagnosis (MBD) can be transformed into a polynomial minimization problem, allowing one to apply a quantum algorithm called quantum annealing to solve MBD problems. To better understand the need for this quantum approach, we designed two simulated annealingdiagnostic algorithms tailored to run on a polynomial representation of MBD. These algorithms differ on their policy for random neighborhood variable selection. In addition, enhanced metrics were devised to provide more diagnostic coverage. Finally, these two simulated annealing algorithms were analyzed and empirically evaluated and compared against state-of-the-art probabilistic methods for MBD such as SAFARI using ISCAS-85.

Simulated annealing↗

Correcting for filter-based aerosol light absorption biases at the Atmospheric Radiation Measurement program's Southern Great Plains site using photoacoustic measurements and machine learning

Abstract. Measurement of light absorption of solar radiation by aerosols is vital for assessing direct aerosol radiative forcing, which affects local and global climate. Low-cost and easy-to-operate filter-based instruments, such as the Particle Soot Absorption Photometer (PSAP), that collect aerosols on a filter and measure light attenuation through the filter are widely used to infer aerosol light absorption. However, filter-based absorption measurements are subject to artifacts that are difficult to quantify. These artifacts are associated with the presence of the filter medium and the complex interactions between the filter fibers and accumulated aerosols. Various correction algorithms have been introduced to correct for the filter-based absorption coefficient measurements toward predicting the particle-phase absorption coefficient (Babs). However, the inability of these algorithms to incorporate into their formulations the complex matrix of influencing parameters such as particle asymmetry parameter, particle size, and particle penetration depth results in prediction of particle-phase absorption coefficients with relatively low accuracy. The analytical forms of corrections also suffer from a lack of universal applicability: different corrections are required for rural and urban sites across the world. In this study, we analyzed and compared 3 months of high-time-resolution ambient aerosol absorption data collected synchronously using a three-wavelength photoacoustic absorption spectrometer (PASS) and PSAP. Both instruments were operated on the same sampling inlet at the Department of Energy's Atmospheric Radiation Measurement program's Southern Great Plains (SGP) user facility in Oklahoma. We implemented the two most commonly used analytical correction algorithms, namely, Virkkula (2010) and the average of Virkkula (2010) and Ogren (2010)–Bond et al. (1999) as well as a random forest regression (RFR) machine learning algorithm to predict Babs values from the PSAP's filter-based measurements. The predicted Babs was compared against the reference Babs measured by the PASS. The RFR algorithm performed the best by yielding the lowest root mean square error of prediction. The algorithm was trained using input datasets from the PSAP (transmission and uncorrected absorption coefficient), a co-located nephelometer (scattering coefficients), and the Aerosol Chemical Speciation Monitor (mass concentration of non-refractory aerosol particles). A revised form of the Virkkula (2010) algorithm suitable for the SGP site has been proposed; however, its performance yields approximately 2-fold errors when compared to the RFR algorithm. To generalize the accuracy and applicability of our proposed RFR algorithm, we trained and tested it on a dataset of laboratory measurements of combustion aerosols. Input variables to the algorithm included the aerosol number size distribution from the Scanning Mobility Particle Sizer, absorption coefficients from the filter-based Tricolor Absorption Photometer, and scattering coefficients from a multiwavelength nephelometer. The RFR algorithm predicted Babs values within 5 % of the reference Babs measured by the multiwavelength PASS during the laboratory experiments. Thus, we show that machine learning approaches offer a promising path to correct for biases in long-term filter-based absorption datasets and accurately quantify their variability and trends needed for robust radiative forcing determination.

54 ENVIRONMENTAL SCIENCES↗

Scattering Models and Basic Experiments in the Microwave Regime

The objectives of research over the next three years are: (1) to develop a randomly rough surface scattering model which is applicable over the entire frequency band; (2) to develop a computer simulation method and algorithm to simulate scattering from known randomly rough surfaces, Z(x,y); (3) to design and perform laboratory experiments to study geometric and physical target parameters of an inhomogeneous layer; (4) to develop scattering models for an inhomogeneous layer which accounts for near field interaction and multiple scattering in both the coherent and the incoherent scattering components; and (5) a comparison between theoretical models and measurements or numerical simulation.

Fung, A. K.↗