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 109 records · Page 6
All sourcesNASA NTRSDOE OSTI
NASA NTRS1975

Hybrid computer methods for direct functional optimization

Control and trajectory optimization involves the minimization of a performance index (PI) of integral form where some optimal control law exists in a dynamic system. In this paper, a hybrid minicomputer with an adaptive random-search algorithm implements an iterative search for the optimal control. The search assumes that some initial control is randomly perturbed and a fast analog computer generates respective PI from the analog response of the dynamic system. An improved PI informs the digital computer to utilize the perturbed control as a basis for the next iteration; otherwise a new perturbation replaces the old perturbation in the next iteration. The search terminates when no further improvements occur.

Andrews, M.↗
DOE OSTI2021

iRF v2.0

A predictive, stable, and interpretable machine learning tool: the iterative random forest algorithm (iRF). iRF discovers high-order interactions among variables with the same order of computational cost as random forests (RF). We have demonstrated the utility of iRF in several applications in the biological and environmental sciences. It is a general purpose machine learning framework for building "explainable" predictive engines.

Brown, JamesB.↗
DOE OSTI2021

Leveraging Randomized Compiling for the QITE Algorithm

The success of the current generation of Noisy Intermediate-Scale Quantum (NISQ) hardware shows that quantum hardware may be able to tackle complex problems even without error correction. One outstanding issue is that of coherent errors arising from the increased complexity of these devices. These errors can accumulate through a circuit, making their impact on algorithms hard to predict and mitigate. Iterative algorithms like Quantum Imaginary Time Evolution are susceptible to these errors. This article presents the combination of both noise tailoring using Randomized Compiling and error mitigation with a purification. We also show that Cycle Benchmarking gives an estimate of the reliability of the purification. We apply this method to the Quantum Imaginary Time Evolution of a Transverse Field Ising Model and report an energy estimation and a ground state infidelity both below 1\%. Our methodology is general and can be used for other algorithms and platforms. We show how combining noise tailoring and error mitigation will push forward the performance of NISQ devices.

Ville, Jean-Loup↗
DOE OSTI2021

An extended numerical manifold method for unsaturated soil-water interaction analysis at micro-scale

To investigate unsaturated soil-water interaction at micro-scale, this work extends the numerical manifold method (NMM) by incorporating a soil-water coupling model considering specific capillary water distribution and capillary force calculation. The soil skeleton is constructed by a soil skeleton generation algorithm with random polygons. To more realistically capture the interaction between soil grains and capillary water, a capillary mechanics-based geometric algorithm is proposed to iteratively calculate the capillary water distribution. The capillary forces corresponding to the capillary water distribution are calculated based on the Young-Laplace equation. The proposed capillary water solving framework is first verified by reproducing the soil-water characteristic curve and the capillary water distribution of an ideal contact-disk model against analytical solutions. To further validate the ability of the capillary water solving framework to predict hydraulic behavior of the real soil, a laboratory test on the Toyoura sand is reproduced numerically. Then an ideal direct shear test is performed to further validate the two-way soil-water coupling procedure, in which a comparison between the numerical and analytical results regarding the shear strength and matric suction is presented. Finally, microscopic hydraulic and compression tests are conducted on two soil specimens with the same porosity and mean grain diameter but different uniformity coefficients. The results elucidate that the extended method is a potential tool to explore unsaturated soil behaviors at micro-scale.

58 GEOSCIENCES↗
DOE OSTI2021

Alert Classification for the ALeRCE Broker System: The Light Curve Classifier

We present the first version of the Automatic Learning for the Rapid Classification of Events (ALeRCE) broker light curve classifier. ALeRCE is currently processing the Zwicky Transient Facility (ZTF) alert stream, in preparation for the Vera C. Rubin Observatory. The ALeRCE light curve classifier uses variability features computed from the ZTF alert stream and colors obtained from AllWISE and ZTF photometry. We apply a balanced random forest algorithm with a two-level scheme where the top level classifies each source as periodic, stochastic, or transient, and the bottom level further resolves each of these hierarchical classes among 15 total classes. This classifier corresponds to the first attempt to classify multiple classes of stochastic variables (including core- and host-dominated active galactic nuclei, blazars, young stellar objects, and cataclysmic variables) in addition to different classes of periodic and transient sources, using real data. We created a labeled set using various public catalogs (such as the Catalina Surveys and Gaia DR2 variable stars catalogs, and the Million Quasars catalog), and we classify all objects with ≥6 g-band or ≥6 r-band detections in ZTF (868,371 sources as of 2020 June 9), providing updated classifications for sources with new alerts every day. For the top level we obtain macro-averaged precision and recall scores of 0.96 and 0.99, respectively, and for the bottom level we obtain macro-averaged precision and recall scores of 0.57 and 0.76, respectively. Updated classifications from the light curve classifier can be found at the ALeRCE Explorer website (http://alerce.online).

47 OTHER INSTRUMENTATION↗
DOE OSTI2022

Inexact Newton-CG algorithms with complexity guarantees

Abstract We consider variants of a recently developed Newton-CG algorithm for nonconvex problems (Royer, C. W. & Wright, S. J. (2018) Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization. SIAM J. Optim., 28, 1448–1477) in which inexact estimates of the gradient and the Hessian information are used for various steps. Under certain conditions on the inexactness measures, we derive iteration complexity bounds for achieving $\epsilon $-approximate second-order optimality that match best-known lower bounds. Our inexactness condition on the gradient is adaptive, allowing for crude accuracy in regions with large gradients. We describe two variants of our approach, one in which the step size along the computed search direction is chosen adaptively, and another in which the step size is pre-defined. To obtain second-order optimality, our algorithms will make use of a negative curvature direction on some steps. These directions can be obtained, with high probability, using the randomized Lanczos algorithm. In this sense, all of our results hold with high probability over the run of the algorithm. We evaluate the performance of our proposed algorithms empirically on several machine learning models. Our approach is a first attempt to introduce inexact Hessian and/or gradient information into the Newton-CG algorithm of Royer & Wright (2018, Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization. SIAM J. Optim., 28, 1448–1477).

Mathematics↗
DOE OSTI2024

Gradient Coding With Iterative Block Leverage Score Sampling

Gradient coding is a method for mitigating straggling servers in a centralized computing network that uses erasure-coding techniques to distributively carry out first-order optimization methods. Randomized numerical linear algebra uses randomization to develop improved algorithms for large-scale linear algebra computations. In this study, we propose a method for distributed optimization that combines gradient coding and randomized numerical linear algebra. The proposed method uses a randomized ℓ 2 -subspace embedding and a gradient coding technique to distribute blocks of data to the computational nodes of a centralized network, and at each iteration the central server only requires a small number of computations to obtain the steepest descent update. The novelty of our approach is that the data is replicated according to importance scores, called block leverage scores, in contrast to most gradient coding approaches that uniformly replicate the data blocks. Furthermore, we do not require a decoding step at each iteration, avoiding a bottleneck in previous gradient coding schemes. We show that our approach results in a valid ℓ 2 -subspace embedding, and that our resulting approximation converges to the optimal solution.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS2015

Development of a Climatology of Vertically Complete Wind Profiles from Doppler Radar Wind Profiler Systems

This paper describes in detail the QC and splicing methodology for KSC's 50- and 915-MHz DRWP measurements that generates an extensive archive of vertically complete profiles from 0.20-18.45 km. The concurrent POR from each archive extends from April 2000 to December 2009. MSFC NE applies separate but similar QC processes to each of the 50- and 915-MHz DRWP archives. DRWP literature and data examination provide the basis for developing and applying the automated and manual QC processes on both archives. Depending on the month, the QC'ed 50- and 915-MHz DRWP archives retain 52-65% and 16-30% of the possible data, respectively. The 50- and 915-MHz DRWP QC archives retain 84-91% and 85-95%, respectively, of all the available data provided that data exist in the non- QC'ed archives. Next, MSFC NE applies an algorithm to splice concurrent measurements from both DRWP sources. Last, MSFC NE generates a composite profile from the (up to) five available spliced profiles to effectively characterize boundary layer winds and to utilize all possible 915-MHz DRWP measurements at each timestamp. During a given month, roughly 23,000-32,000 complete profiles exist from 0.25-18.45 km from the composite profiles' archive, and approximately 5,000- 27,000 complete profiles exist from an archive utilizing an individual 915-MHz DRWP. One can extract a variety of profile combinations (pairs, triplets, etc.) from this sample for a given application. The sample of vertically complete DRWP wind measurements not only gives launch vehicle customers greater confidence in loads and trajectory assessments versus using balloon output, but also provides flexibility to simulate different DOL situations across applicable altitudes. In addition to increasing sample size and providing more flexibility for DOL simulations in the vehicle design phase, the spliced DRWP database provides any upcoming launch vehicle program with the capability to utilize DRWP profiles on DOL to compute vehicle steering commands, provided the program applies the procedures that this report describes to new DRWP data on DOL. Decker et al. (2015) details how SLS is proposing to use DRWP data and splicing techniques on DOL. Although automation could enhance the current DOL 50-MHz DRWP QC process and could streamline any future DOL 915-MHz DRWP QC and splicing process, the DOL community would still require manual intervention to ensure that the vehicle only uses valid profiles. If a program desires to use high spatial resolution profiles, then the algorithm could randomly add high-frequency components to the DRWP profiles. The spliced DRWP database provides lots of flexibility in how one performs DOL simulations, and the algorithms that this report provides will assist the aerospace and atmospheric communities that are interested in utilizing the DRWP.

Barbre, Robert E., Jr.↗
NASA NTRS1998

Development of Algorithms and Error Analyses for the Short Baseline Lightning Detection and Ranging System

NASA, at the John F. Kennedy Space Center (KSC), developed and operates a unique high-precision lightning location system to provide lightning-related weather warnings. These warnings are used to stop lightning- sensitive operations such as space vehicle launches and ground operations where equipment and personnel are at risk. The data is provided to the Range Weather Operations (45th Weather Squadron, U.S. Air Force) where it is used with other meteorological data to issue weather advisories and warnings for Cape Canaveral Air Station and KSC operations. This system, called Lightning Detection and Ranging (LDAR), provides users with a graphical display in three dimensions of 66 megahertz radio frequency events generated by lightning processes. The locations of these events provide a sound basis for the prediction of lightning hazards. This document provides the basis for the design approach and data analysis for a system of radio frequency receivers to provide azimuth and elevation data for lightning pulses detected simultaneously by the LDAR system. The intent is for this direction-finding system to correct and augment the data provided by LDAR and, thereby, increase the rate of valid data and to correct or discard any invalid data. This document develops the necessary equations and algorithms, identifies sources of systematic errors and means to correct them, and analyzes the algorithms for random error. This data analysis approach is not found in the existing literature and was developed to facilitate the operation of this Short Baseline LDAR (SBLDAR). These algorithms may also be useful for other direction-finding systems using radio pulses or ultrasonic pulse data.

Starr, Stanley O.↗
NASA NTRS2022

Combining Machine Learning and Numerical Simulation for High-Resolution PM2.5 Concentration Forecast

Forecasting ambient PM2.5 concentrations with spatiotemporal coverage is key to alerting decision-makers of pollution episodes and preventing detrimental public exposure, especially in regions with limited ground air monitoring stations. The existing methods either rely on chemical transport models (CTMs) to forecast spatial distribution of PM2.5 with nontrivial uncertainty or statistical algorithms to forecast PM2.5 concentration time-series at air monitoring locations without continuous spatial coverage. In this study, we developed a PM2.5 forecast framework by combining the robust Random Forest algorithm with a publicly accessible global CTM forecast product – NASA’s Goddard Earth Observing System “Composition Forecasting” (GEOS-CF), providing spatiotemporally continuous PM2.5 concentration forecasts for the next five days at a 1-km spatial resolution. Our forecast experiment was conducted for a region in Central China including the populous and polluted Fenwei Plain. The forecast for the next two days had overall validation R2 of 0.76 and 0.64, respectively; the R2 was around 0.5 for the following three forecast days. Spatial cross-validation showed similar validation metrics. Our forecast model, with validation normalized mean bias close to zero, substantially reduced the large biases in GEOS-CF. The proposed framework requires minimal computational resources compared to running CTMs at urban scales, enabling near-real-time PM2.5 forecast in resource-restricted environments.

PM2.5↗
DOE OSTI2024

Automatic Multiple Experiment Simulation and Fitting (Ames-Fit)

AMES-Fit is a program used to automatically fit the multi-field solid-state NMR spectra of half-integer quadrupolar nuclei. Due to the high dimensional space, gradient algorithms have failed to address the fitting of such data, which is at present done manually. AMES-Fit diverges from these approaches by using an adaptive step size random search algorithm to fit the NMR spectra to consistently find the global best fit parameters.

Perras, Frederic↗
DOE OSTI2024

Stochastic minibatch approach to the ptychographic iterative engine

The ptychographic iterative engine (PIE) is a widely used algorithm that enables phase retrieval at nanometer-scale resolution over a wide range of imaging experiment configurations. By analyzing diffraction intensities from multiple scanning locations where a probing wavefield interacts with a sample, the algorithm solves a difficult optimization problem with constraints derived from the experimental geometry as well as sample properties. The effectiveness at which this optimization problem is solved is highly dependent on the ordering in which we use the measured diffraction intensities in the algorithm, and random ordering is widely used due to the limited ability to escape from stagnation in poor-quality local solutions. In this study, we introduce an extension to the PIE algorithm that uses ideas popularized in recent machine learning training methods, in this case minibatch stochastic gradient descent. Our results demonstrate that these new techniques significantly improve the convergence properties of the PIE numerical optimization problem.

47 OTHER INSTRUMENTATION↗
NASA NTRS2006

Precipitation and Latent Heating Distributions from Satellite Passive Microwave Radiometry. Part II: Evaluation of Estimates Using Independent Data

Rainfall rate estimates from spaceborne microwave radiometers are generally accepted as reliable by a majority of the atmospheric science community. One of the Tropical Rainfall Measuring Mission (TRMM) facility rain-rate algorithms is based upon passive microwave observations from the TRMM Microwave Imager (TMI). In Part I of this series, improvements of the TMI algorithm that are required to introduce latent heating as an additional algorithm product are described. Here, estimates of surface rain rate, convective proportion, and latent heating are evaluated using independent ground-based estimates and satellite products. Instantaneous, 0.5 deg. -resolution estimates of surface rain rate over ocean from the improved TMI algorithm are well correlated with independent radar estimates (r approx. 0.88 over the Tropics), but bias reduction is the most significant improvement over earlier algorithms. The bias reduction is attributed to the greater breadth of cloud-resolving model simulations that support the improved algorithm and the more consistent and specific convective/stratiform rain separation method utilized. The bias of monthly 2.5 -resolution estimates is similarly reduced, with comparable correlations to radar estimates. Although the amount of independent latent heating data is limited, TMI-estimated latent heating profiles compare favorably with instantaneous estimates based upon dual-Doppler radar observations, and time series of surface rain-rate and heating profiles are generally consistent with those derived from rawinsonde analyses. Still, some biases in profile shape are evident, and these may be resolved with (a) additional contextual information brought to the estimation problem and/or (b) physically consistent and representative databases supporting the algorithm. A model of the random error in instantaneous 0.5 deg. -resolution rain-rate estimates appears to be consistent with the levels of error determined from TMI comparisons with collocated radar. Error model modifications for nonraining situations will be required, however. Sampling error represents only a portion of the total error in monthly 2.5 -resolution TMI estimates; the remaining error is attributed to random and systematic algorithm errors arising from the physical inconsistency and/or nonrepresentativeness of cloud-resolving-model-simulated profiles that support the algorithm.

Yang, Song↗
NASA NTRS1992

Laboratory for Engineering Man/Machine Systems (LEMS): System identification, model reduction and deconvolution filtering using Fourier based modulating signals and high order statistics

Several important problems in the fields of signal processing and model identification, such as system structure identification, frequency response determination, high order model reduction, high resolution frequency analysis, deconvolution filtering, and etc. Each of these topics involves a wide range of applications and has received considerable attention. Using the Fourier based sinusoidal modulating signals, it is shown that a discrete autoregressive model can be constructed for the least squares identification of continuous systems. Some identification algorithms are presented for both SISO and MIMO systems frequency response determination using only transient data. Also, several new schemes for model reduction were developed. Based upon the complex sinusoidal modulating signals, a parametric least squares algorithm for high resolution frequency estimation is proposed. Numerical examples show that the proposed algorithm gives better performance than the usual. Also, the problem was studied of deconvolution and parameter identification of a general noncausal nonminimum phase ARMA system driven by non-Gaussian stationary random processes. Algorithms are introduced for inverse cumulant estimation, both in the frequency domain via the FFT algorithms and in the domain via the least squares algorithm.

Pan, Jianqiang↗
DOE OSTI2023

COWALKER:EFFECTIVE TRANSPORT PROPERTIES OF COMPOSITE MATERIALS

SF-23-026 This software computes effective transport properties of composite materials involving fibers and nanoparticles using a random-walk algorithm that efficiently scales to an arbitrary number of processes and cores. Effective transport properties (thermal, electrical) are key to bridge the microstructure of complex materials with its macroscopic behavior. Traditional approaches either use effective medium approximations (closed mathematical expressions that are approximation for certain conditions) or continuum simulation models such as finite element or finite volume, which require the generation of a mesh for each configuration explored. cowalker leverages the equivalence between laplacian or heat equation-based models and random walks to compute the asymptotic transport properties from an ensemble of first sojourn times of a random walker moving through the composite material. This allows us to directly define a composite material as a collection of particles and use algorithms developed for molecular dynamics to quickly compute the intersection of the walker with the different interfaces in the material. cowalker is developed in C++, and it relies on the GNU Scientific Library for random generation. cowalker is currently delivered as source code, so the GSL library is not included in cowalker's distribution. A more userfriendly version, cowalker.jl is currently in development and will be released as part of cowalker.

YANGUAS-GIL, ANGEL↗
NASA NTRS2018

Machine Learning Application to Atmospheric Chemistry Modeling

Atmospheric chemistry is a high-dimensionality, large-data problem and thus may be suited to machine-learning algorithms. We show here the potential of a random forest regression algorithm to replace the gas-phase chemistry solver in the GEOS-Chem chemistry model. In this proof-of-concept study, we used one month of model output to train random forest regression models to predict the concentrations of each long-lived chemical species after integration based upon the physical and chemical conditions before the chemical integration. The choice of prediction type has a strong impact on the skill of the regression model. We find best results from predicting the change in concentration for very long-lived species and the absolute concentration for shorter lived species. The skill of the machine learning algorithm is further improved by using a family approach for NO and NO2 rather than treating them independently.By replacing the numerical integrator with the random forest algorithm and running this model for one month, we find that the model is able to reproduce many of the features of the reference chemistry simulation. Replacing the integration methodology with a machine learning algorithm has the potential to be substantially faster. There are a wide range of applications for such an approach, e.g. to generate boundary conditions, for use in air quality forecasts or chemical data assimilation systems, etc.

Keller, Christoph A.↗
DOE OSTI2023

Developing a SARS-CoV-2 main protease binding prediction random forest model for drug repurposing for COVID-19 treatment

The coronavirus disease 2019 (COVID-19) global pandemic resulted in millions of people becoming infected with the severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2) virus and close to seven million deaths worldwide. It is essential to further explore and design effective COVID-19 treatment drugs that target the main protease of SARS-CoV-2, a major target for COVID-19 drugs. In this study, machine learning was applied for predicting the SARS-CoV-2 main protease binding of Food and Drug Administration (FDA)-approved drugs to assist in the identification of potential repurposing candidates for COVID-19 treatment. Ligands bound to the SARS-CoV-2 main protease in the Protein Data Bank and compounds experimentally tested in SARS-CoV-2 main protease binding assays in the literature were curated. These chemicals were divided into training (516 chemicals) and testing (360 chemicals) data sets. To identify SARS-CoV-2 main protease binders as potential candidates for repurposing to treat COVID-19, 1188 FDA-approved drugs from the Liver Toxicity Knowledge Base were obtained. A random forest algorithm was used for constructing predictive models based on molecular descriptors calculated using Mold2 software. Model performance was evaluated using 100 iterations of fivefold cross-validations which resulted in 78.8% balanced accuracy. The random forest model that was constructed from the whole training dataset was used to predict SARS-CoV-2 main protease binding on the testing set and the FDA-approved drugs. Model applicability domain and prediction confidence on drugs predicted as the main protease binders discovered 10 FDA-approved drugs as potential candidates for repurposing to treat COVID-19. Our results demonstrate that machine learning is an efficient method for drug repurposing and, thus, may accelerate drug development targeting SARS-CoV-2.

Research & Experimental Medicine↗
NASA NTRS2004

Random Matrix Approach to Quantum Adiabatic Evolution Algorithms

We analyze the power of quantum adiabatic evolution algorithms (Q-QA) for solving random NP-hard optimization problems within a theoretical framework based on the random matrix theory (RMT). We present two types of the driven RMT models. In the first model, the driving Hamiltonian is represented by Brownian motion in the matrix space. We use the Brownian motion model to obtain a description of multiple avoided crossing phenomena. We show that the failure mechanism of the QAA is due to the interaction of the ground state with the "cloud" formed by all the excited states, confirming that in the driven RMT models. the Landau-Zener mechanism of dissipation is not important. We show that the QAEA has a finite probability of success in a certain range of parameters. implying the polynomial complexity of the algorithm. The second model corresponds to the standard QAEA with the problem Hamiltonian taken from the Gaussian Unitary RMT ensemble (GUE). We show that the level dynamics in this model can be mapped onto the dynamics in the Brownian motion model. However, the driven RMT model always leads to the exponential complexity of the algorithm due to the presence of the long-range intertemporal correlations of the eigenvalues. Our results indicate that the weakness of effective transitions is the leading effect that can make the Markovian type QAEA successful.

Boulatov, Alexei↗