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 55 records · Page 3
All sourcesNASA NTRSDOE OSTI
DOE OSTI2025

Randomized Adiabatic Quantum Linear Solver Algorithm with Optimal Complexity Scaling and Detailed Running Costs

Solving linear systems of equations is a fundamental problem with a wide variety of applications across many fields of science, and there is increasing effort to develop quantum linear solver algorithms. Subaşı et al. [Phys. Rev. Lett. 122, 060504 (2019)] proposed a randomized algorithm inspired by adiabatic quantum computing, based on a sequence of random Hamiltonian simulation steps, with suboptimal scaling in the condition number 𝜅 of the linear system and the target error 𝜖. Here we go beyond these results in several ways. Firstly, using filtering [Lin and Tong, Quantum 4, 361 (2020)] and Poissonization techniques [Cunningham and Roland, ArXiv:2406.03972 (2024)], the algorithm complexity is improved to the optimal scaling 𝑂⁡(𝜅⁢log (1/𝜖))—an exponential improvement in 𝜖, and a shaving of a log 𝜅 scaling factor in 𝜅. Secondly, the algorithm is further modified to achieve constant factor improvements, which are vital as we progress towards hardware implementations on fault-tolerant devices. We introduce a cheaper randomized walk operator method replacing Hamiltonian simulation—which also removes the need for potentially challenging classical precomputations; randomized routines are sampled over optimized random variables; circuit constructions are improved. We obtain a closed formula rigorously upper bounding the expected number of times one needs to apply a block-encoding of the linear system matrix to output a quantum state encoding the solution to the linear system. The upper bound is 837⁢𝜅 at 𝜖 = 10 −10 for Hermitian matrices.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS2023

Bandelier Ecological Conservation: Mapping Invasive Species Along the Rio Grande Corridor in Bandelier National Monument

The Southwest U.S. has experienced a growth of invasive riparian species, specifically Elaeagnus angustifolia (Russian olive), Tamarix ramosissima (saltcedar), and Ulmus pumila (Siberian elm), which alter local soil chemistry and outcompete native species. Locating these exotic species is critical for ecological conservation; however, field identification can be resource intensive. NASA DEVELOP partnered with the National Park Service (NPS) at Bandelier National Monument (BAND) to assess the feasibility of using Earth observation data to map invasive species along the Rio Grande corridor of the park. The team used Landsat 8 OLI, Sentinel-2 MSI, and ISS DESIS imagery to compute principal components based on spectral bands, vegetation indices, and terrain indices. Using the first five principal components, the team created classification maps using both a k-means classification algorithm and a random forest algorithm to differentiate between native and non-native species. The team derived maps for the three invasive riparian species in the region for the last five years. The team found that invasive species covered 33% of the park's river corridor in 2023, and the invasive species extent has increased by 5.7% from 2019 to 2023. The methods will serve as a guide for aiding historic and present invasive species identification in riparian regions, and the NPS staff at BAND will use the results to inform local mitigation practices and advocate for invasive species removal.

Evan Barrett↗
NASA NTRS1972

Relabeling of finite element meshes using a random process

An algorithm is presented to relabel automatically the nodes of an arbitrary finite-element mesh. The purpose of such relabeling is to reduce the bandwidth of the master stiffness matrix produced by the finite-element method. The algorithm uses a random process for the relabeling. Computing time is reduced substantially, compared to systematic methods.

Roberts, E., Jr.↗
NASA NTRS1967

Study of a global search algorithm for optimal control.

Adaptive random search algorithm utilizing boundary cost-function hypersurfaces measurement to implement Pontryagin maximum principle, discussing hybrid computer use, iterative solution and convergence properties

Brocker, D. H.↗
NASA NTRS1970

Global search algorithm for optimal control

Random-search algorithm employs local and global properties to solve two-point boundary value problem in Pontryagin maximum principle for either fixed or variable end-time problems. Mixed boundary value problem is transformed to an initial value problem. Mapping between initial and terminal values utilizes hybrid computer.

Brocker, D. H.↗
NASA NTRS2012

Recursive Branching Simulated Annealing Algorithm

This innovation is a variation of a simulated-annealing optimization algorithm that uses a recursive-branching structure to parallelize the search of a parameter space for the globally optimal solution to an objective. The algorithm has been demonstrated to be more effective at searching a parameter space than traditional simulated-annealing methods for a particular problem of interest, and it can readily be applied to a wide variety of optimization problems, including those with a parameter space having both discrete-value parameters (combinatorial) and continuous-variable parameters. It can take the place of a conventional simulated- annealing, Monte-Carlo, or random- walk algorithm. In a conventional simulated-annealing (SA) algorithm, a starting configuration is randomly selected within the parameter space. The algorithm randomly selects another configuration from the parameter space and evaluates the objective function for that configuration. If the objective function value is better than the previous value, the new configuration is adopted as the new point of interest in the parameter space. If the objective function value is worse than the previous value, the new configuration may be adopted, with a probability determined by a temperature parameter, used in analogy to annealing in metals. As the optimization continues, the region of the parameter space from which new configurations can be selected shrinks, and in conjunction with lowering the annealing temperature (and thus lowering the probability for adopting configurations in parameter space with worse objective functions), the algorithm can converge on the globally optimal configuration. The Recursive Branching Simulated Annealing (RBSA) algorithm shares some features with the SA algorithm, notably including the basic principles that a starting configuration is randomly selected from within the parameter space, the algorithm tests other configurations with the goal of finding the globally optimal solution, and the region from which new configurations can be selected shrinks as the search continues. The key difference between these algorithms is that in the SA algorithm, a single path, or trajectory, is taken in parameter space, from the starting point to the globally optimal solution, while in the RBSA algorithm, many trajectories are taken; by exploring multiple regions of the parameter space simultaneously, the algorithm has been shown to converge on the globally optimal solution about an order of magnitude faster than when using conventional algorithms. Novel features of the RBSA algorithm include: 1. More efficient searching of the parameter space due to the branching structure, in which multiple random configurations are generated and multiple promising regions of the parameter space are explored; 2. The implementation of a trust region for each parameter in the parameter space, which provides a natural way of enforcing upper- and lower-bound constraints on the parameters; and 3. The optional use of a constrained gradient- search optimization, performed on the continuous variables around each branch s configuration in parameter space to improve search efficiency by allowing for fast fine-tuning of the continuous variables within the trust region at that configuration point.

Bolcar, Matthew↗
NASA NTRS1975

Simulation of multicorrelated random processes using the FFT algorithm

A technique for the digital simulation of multicorrelated Gaussian random processes is described. This technique is based upon generating discrete frequency functions which correspond to the Fourier transform of the desired random processes, and then using the fast Fourier transform (FFT) algorithm to obtain the actual random processes. The main advantage of this method of simulation over other methods is computation time; it appears to be more than an order of magnitude faster than present methods of simulation. One of the main uses of multicorrelated simulated random processes is in solving nonlinear random vibration problems by numerical integration of the governing differential equations. The response of a nonlinear string to a distributed noise input is presented as an example.

Wittig, L. E.↗
NASA NTRS1994

System Design under Uncertainty: Evolutionary Optimization of the Gravity Probe-B Spacecraft

This paper discusses the application of evolutionary random-search algorithms (Simulated Annealing and Genetic Algorithms) to the problem of spacecraft design under performance uncertainty. Traditionally, spacecraft performance uncertainty has been measured by reliability. Published algorithms for reliability optimization are seldom used in practice because they oversimplify reality. The algorithm developed here uses random-search optimization to allow us to model the problem more realistically. Monte Carlo simulations are used to evaluate the objective function for each trial design solution. These methods have been applied to the Gravity Probe-B (GP-B) spacecraft being developed at Stanford University for launch in 1999, Results of the algorithm developed here for GP-13 are shown, and their implications for design optimization by evolutionary algorithms are discussed.

Pullen, Samuel P.↗
NASA NTRS2010

Exhaustive Versus Randomized Searchers for Nonlinear Optimization in 21st Century Computing: Solar Application

We present a simple multi-dimensional exhaustive search method to obtain, in a reasonable time, the optimal solution of a nonlinear programming problem. It is more relevant in the present day non-mainframe computing scenario where an estimated 95% computing resources remains unutilized and computing speed touches petaflops. While the processor speed is doubling every 18 months, the band width is doubling every 12 months, and the hard disk space is doubling every 9 months. A randomized search algorithm or, equivalently, an evolutionary search method is often used instead of an exhaustive search algorithm. The reason is that a randomized approach is usually polynomial-time, i.e., fast while an exhaustive search method is exponential-time i.e., slow. We discuss the increasing importance of exhaustive search in optimization with the steady increase of computing power for solving many real-world problems of reasonable size. We also discuss the computational error and complexity of the search algorithm focusing on the fact that no measuring device can usually measure a quantity with an accuracy greater than 0.005%. We stress the fact that the quality of solution of the exhaustive search - a deterministic method - is better than that of randomized search. In 21 st century computing environment, exhaustive search cannot be left aside as an untouchable and it is not always exponential. We also describe a possible application of these algorithms in improving the efficiency of solar cells - a real hot topic - in the current energy crisis. These algorithms could be excellent tools in the hands of experimentalists and could save not only large amount of time needed for experiments but also could validate the theory against experimental results fast.

Sen, Syamal K.↗
DOE OSTI2025

Selection of high-redshift Lyman-Break Galaxies from broadband and wide photometric surveys

In this paper, we investigate the possibility of selecting high-redshift Lyman-Break Galaxies (LBG) using current and future broadband wide photometric surveys, such as the Ultraviolet Near Infrared Optical Northern Survey (UNIONS) or the Vera C. Rubin Legacy Survey of Space and Time (LSST), using a Random Forest algorithm. This work is conducted in the context of future large-scale structure spectroscopic surveys like DESI-II, the next phase of the Dark Energy Spectroscopic Instrument (DESI), which will start around 2029.We use deep imaging data from the Hyper Suprime Camera (HSC) and the Canada-France-Hawaii Telescope Large Area U-band Deep Survey (CLAUDS) on the COSMOS and XMM-LSS fields. To predict the selection performance of LBGs with image quality similar to UNIONS, we degrade the u,g,r,i and z bands to UNIONS depth.The Random Forest algorithm is trained with the u,g,r,i and z bands to classify LBGs in the 2.5 < z < 3.5 range.We find that fixing a target density budget of 1,100 deg$^{-2}$, the Random Forest approach gives a density of z > 2 targets of 873 deg$^{-2}$, and a density of 493 deg$^{-2}$ of confirmed LBGs after spectroscopic confirmation with DESI. This UNIONS-like selection was tested in a dedicated spectroscopic observation campaign of 1,000 targets with DESI on the COSMOS field, providing a safe spectroscopic sample with a mean redshift of 3. This sample is used to derive forecasts for DESI-II, assuming a sky coverage of 5,000 deg$^{2}$. We predict uncertainties on Alcock-Paczynski parameters α$_{⊥}$ and α$_{∥}$ to be 0.7% and 1% for 2.6 < z < 3.2, resulting in a potential 2% measurement of the dark energy fraction at high redshift. Additionally, we estimate the uncertainty in local non-Gaussianity and predict σ$_{fNL}$ ≈ 7, which would be comparable to the current best precision achieved by Planck. The latter forecast suggests that achieving the precision required to place stringent constraints on inflationary models (σ$_{fNL}$ ≈ 1) using spectroscopic galaxy surveys necessitates the development of a next-generation (Stage V) spectroscopic survey.

79 ASTRONOMY AND ASTROPHYSICS↗
DOE OSTI2025

Selection of high-redshift Lyman-Break Galaxies from broadband and wide photometric surveys

Here, in this paper, we investigate the possibility of selecting high-redshift Lyman-Break Galaxies (LBG) using current and future broadband wide photometric surveys, such as the Ultraviolet Near Infrared Optical Northern Survey (UNIONS) or the Vera C. Rubin Legacy Survey of Space and Time (LSST), using a Random Forest algorithm. This work is conducted in the context of future large-scale structure spectroscopic surveys like DESI-II, the next phase of the Dark Energy Spectroscopic Instrument (DESI), which will start around 2029. We use deep imaging data from the Hyper Suprime Camera (HSC) and the Canada-France-Hawaii Telescope Large Area U-band Deep Survey (CLAUDS) on the COSMOS and XMM-LSS fields. To predict the selection performance of LBGs with image quality similar to UNIONS, we degrade the u,g,r,i and z bands to UNIONS depth. The Random Forest algorithm is trained with the u,g,r,i and z bands to classify LBGs in the 2.5 < z < 3.5 range. We find that fixing a target density budget of 1,100 deg -2 , the Random Forest approach gives a density of z > 2 targets of 873 deg -2 , and a density of 493 deg -2 of confirmed LBGs after spectroscopic confirmation with DESI. This UNIONS-like selection was tested in a dedicated spectroscopic observation campaign of 1,000 targets with DESI on the COSMOS field, providing a safe spectroscopic sample with a mean redshift of 3. This sample is used to derive forecasts for DESI-II, assuming a sky coverage of 5,000 deg 2 . We predict uncertainties on Alcock-Paczynski parameters α ⊥ and α ∥ to be 0.7% and 1% for 2.6 < z < 3.2, resulting in a potential 2% measurement of the dark energy fraction at high redshift. Additionally, we estimate the uncertainty in local non-Gaussianity and predict σ fNL ≈ 7, which would be comparable to the current best precision achieved by Planck. The latter forecast suggests that achieving the precision required to place stringent constraints on inflationary models (σ fNL ≈ 1) using spectroscopic galaxy surveys necessitates the development of a next-generation (Stage V) spectroscopic survey.

cosmological parameters from LSS↗
DOE OSTI2024

Machine learning approaches for influenza A virus risk assessment identifies predictive correlates using ferret model in vivo data

In vivo assessments of influenza A virus (IAV) pathogenicity and transmissibility in ferrets represent a crucial component of many pandemic risk assessment rubrics, but few systematic efforts to identify which data from in vivo experimentation are most useful for predicting pathogenesis and transmission outcomes have been conducted. To this aim, we aggregated viral and molecular data from 125 contemporary IAV (H1, H2, H3, H5, H7, and H9 subtypes) evaluated in ferrets under a consistent protocol. Three overarching predictive classification outcomes (lethality, morbidity, transmissibility) were constructed using machine learning (ML) techniques, employing datasets emphasizing virological and clinical parameters from inoculated ferrets, limited to viral sequence-based information, or combining both data types. Among 11 different ML algorithms tested and assessed, gradient boosting machines and random forest algorithms yielded the highest performance, with models for lethality and transmission consistently better performing than models predicting morbidity. Comparisons of feature selection among models was performed, and highest performing models were validated with results from external risk assessment studies. Our findings show that ML algorithms can be used to summarize complex in vivo experimental work into succinct summaries that inform and enhance risk assessment criteria for pandemic preparedness that take in vivo data into account.

59 BASIC BIOLOGICAL SCIENCES↗
NASA NTRS2017

Computationally Efficient Motion Planning Algorithms for Agile Autonomous Vehicles in Cluttered Environments

Fast, real-time motion planning of an agile, autonomous vehicle in a cluttered environment, with many geometrically-fixed obstacles, is a very complex problem, especially because of the vehicle dynamics constraints and resource constrained computational capabilities onboard the vehicle. In this paper, we present computationally-efficient versions of our novel motion planning algorithm called the Spherical Expansion and Sequential Convex Programming (SE–SCP) algorithm. The SE–SCP algorithm first uses a spherical-expansion-based randomized sampling algorithm to explore the workspace. Oncea path is found from the start position to the goal position, the algorithm computes a locally optimal trajectory, within its homotopy class for a desired cost function, by solving a sequence of convex optimization problems. Thus, the SE–SCP algorithm is anytime locally optimal and the trajectory is globally optimal if the number of samples tends to infinity. In this paper, we further enhance the computational efficiency of the SE–SCP algorithm using uni-directional and bi-directional rewiring techniques. We also present a detailed proof of the local optimality characteristics of the new SE–SCP algorithms for aspecial case of vehicle dynamics. Simulation examples involving quadrotor and spacecraft help demonstrate the effectiveness of our new algorithms.

Bandyopadhyay, Saptarshi↗
DOE OSTI2024

Real-time capable modeling of ICRF heating on NSTX and WEST via machine learning approaches

Abstract A real-time capable core Ion Cyclotron Range of Frequencies (ICRF) heating model on NSTX and WEST is developed. The model is based on two nonlinear regression algorithms, the random forest ensemble of decision trees and the multilayer perceptron neural network. The algorithms are trained on TORIC ICRF spectrum solver simulations of the expected flat-top operation scenarios in NSTX and WEST assuming Maxwellian plasmas. The surrogate models are shown to successfully capture the multi-species core ICRF power absorption predicted by the original model for the high harmonic fast wave and the ion cyclotron minority heating schemes while reducing the computational time by six orders of magnitude. Although these models can be expanded, the achieved regression scoring, computational efficiency and increased model robustness suggest these strategies can be implemented into integrated modeling frameworks for real-time control applications.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗