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.

SourceResearch connectionFrom yearThrough year

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 757 records · Page 42

All sources NASA NTRS DOE OSTI

DOE OSTI2025

Parallel sorting algorithm classification: is manual instrumentation necessary?

Understanding parallel algorithms is crucial for accelerating scientific simulations on complex, distributed memory, high-performance computers. Modern algorithm classification approaches learn semantics directly from source code to differentiate between algorithms, however, accessing source code is not always possible. We can learn about parallel algorithms from observing their performance, as programs running the same algorithms and using the same hardware should exhibit similar performance characteristics. We present an approach to learn algorithm classes from parallel performance data directly in order to classify algorithms without access to the source code. We extend previous work to enable classifying parallel sorting algorithms using automatic instrumentation instead of requiring manual region annotations in the source code. In this work, we design and demonstrate a study for classification of parallel sorting algorithms using parallel performance data collected from automatic instrumentation, and evaluate the performance of our new methodology on classification. We leverage Caliper to collect the performance data, Thicket for our exploratory data analysis (EDA), and PyTorch and Scikit-learn to evaluate the effectiveness of random forests, support vector machines (SVMs), decision trees, neural networks, and logistic regressions on parallel performance data. Additionally, we study noise in parallel performance data, whether the removal of noise and pre-processing of the data is necessary to accurately classify parallel sorting algorithms, and determine the effectiveness of features created from performance data. In conclusion, we demonstrate classification accuracy for these five different models of up to 97.7% across four different parallel algorithm classes.

Algorithm Classification↗

DOE OSTI2023

A Randomization-Based, Zero-Trust Cyberattack Detection Method for Hierarchical Systems

This paper demonstrates a novel randomization-based approach for verifying power system control signals with application to detecting cyberattacks. We consider fully connected hierarchical systems containing multiple local agents and a global "trust" agent. The global agent uses a time-varying randomized assignment scheme to identify corrupt network links based on principles of zero trust and majority rule. To evaluate the performance of this detection approach, we implement our algorithm in MATLAB and run it against nearly 43 million unique attack scenarios spanning a range of system sizes. For each scenario, the algorithm determines whether the identified corruptions satisfy a set of validity constraints reflecting network topology and uses that result to say whether the recovered state value for one or more local agents is malicious. We compare the algorithm's determination to the true state of the system to assess performance and find that classification accuracy converges to 100% as system size increases, suggesting that the validity constraints become more difficult to satisfy for larger systems. We further explore the scenarios that evade detection to understand practical implications for employing this detection approach.

cybersecurity↗

DOE OSTI2025

Quantum algorithm to simulate Lindblad master equations

We present a quantum algorithm for simulating a family of Markovian master equations that can be realized through a probabilistic application of unitary channels and state preparation. Our approach employs a second-order product formula for the Lindblad master equation, achieved by decomposing the dynamics into dissipative and Hamiltonian components and replacing the dissipative segments with randomly compiled, easily implementable elements. The sampling approach eliminates the need for ancillary qubits to simulate the dissipation process and reduces the gate complexity in terms of the number of jump operators. We provide a rigorous performance analysis of the algorithm. We also extend the algorithm to time-dependent Lindblad equations, generalize the family of Markovian master equations it can be applied to, and explore applications beyond the Markovian noise model. A new error bound, in terms of the diamond norm, for second-order product formulas for time-dependent Liouvillians is provided that might be of independent interest. Published by the American Physical Society 2025

Borras, Evan (ORCID:000900017709037X)↗

DOE OSTI2021

Analysis of the ratio of ℓ 1 and ℓ 2 norms in compressed sensing

We study the ratio of ℓ 1 and ℓ 2 norms ( ℓ 1 / ℓ 2 ) as a sparsity-promoting objective in compressed sensing. We first propose a novel criterion that guarantees that an s-sparse signal is the local minimizer of the ℓ 1 / ℓ 2 objective; our criterion is interpretable and useful in practice. We also give the first uniform recovery condition using a geometric characterization of the null space of the measurement matrix, and show that this condition is satisfied for a class of random matrices. We also present analysis on the robustness of the procedure when noise pollutes data. Numerical experiments are provided that compare ℓ 1 / ℓ 2 with some other popular non-convex methods in compressed sensing. Finally, we propose a novel initialization approach to accelerate the numerical optimization procedure. We call this initialization approach support selection, and we demonstrate that it empirically improves the performance of existing ℓ 1 / ℓ 2 algorithms.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2022

An adaptive stochastic sequential quadratic programming with differentiable exact augmented lagrangians

In this study, we consider solving nonlinear optimization problems with a stochastic objective and deterministic equality constraints. We assume for the objective that its evaluation, gradient, and Hessian are inaccessible, while one can compute their stochastic estimates by, for example, subsampling. We propose a stochastic algorithm based on sequential quadratic programming (SQP) that uses a differentiable exact augmented Lagrangian as the merit function. To motivate our algorithm design, we first revisit and simplify an old SQP method Lucidi developed for solving deterministic problems, which serves as the skeleton of our stochastic algorithm. Based on the simplified deterministic algorithm, we then propose a non-adaptive SQP for dealing with stochastic objective, where the gradient and Hessian are replaced by stochastic estimates but the stepsizes are deterministic and prespecified. Finally, we incorporate a recent stochastic line search procedure Paquette and Scheinberg into the non-adaptive stochastic SQP to adaptively select the random stepsizes, which leads to an adaptive stochastic SQP. The global "almost sure" convergence for both non-adaptive and adaptive SQP methods is established. Numerical experiments on nonlinear problems in CUTEst test set demonstrate the superiority of the adaptive algorithm.

97 MATHEMATICS AND COMPUTING↗

NASA NTRS2021

Lila: Optimal Dispatching in Probabilistic Temporal Networks using Monte Carlo Tree Search

Executing a Probabilistic Simple Temporal Network (PSTN) amounts at scheduling, i.e. \textit{dispatch}, a set of events under time uncertainty. This constitutes a NP-hard online optimization problem. The right execution time must be dynamically assigned to each event of the PSTN such that the temporal constraints are met, whereas activity durations are progressively observed as the execution unfolds. We propose a dispatching algorithm based on Monte Carlo Tree Search, called Lila, with the following characteristics: (i) it is an anytime algorithm, both offline and online, proven asymptotically optimal; (ii) it returns the current probability of success, either before or at any moment during operations; (iii) it handles any possible continuous or discrete, even non-parametric, probability distributions, as well as inter-dependencies between random variables, exogenous and endogenous uncertainty; and (iv) can be easily extended to handle probabilistic external events, PSTNs with resources, PSTNs with cutoff times and precondition chains, etc. Lila is universal in the sense that it can handle any dispatching protocol, simply by specifying it to the algorithm. It has the unlimited flexibility offered by the simulation paradigm, whilst it asymptotically converges to optimal decisions and/or robustness approximations.

Chien, Steve A.↗

DOE OSTI2021

An Observationally Trained Markov Model for MJO Propagation

A Markovian stochastic model is developed for studying the propagation of the Madden-Julian Oscillation (MJO). This model represents the daily changes in real time multivariate MJO (RMM) indices as random functions of their current state and background conditions. The probability distribution function of the RMM changes is obtained using a machine learning algorithm trained to maximize MJO forecast skills using observed daily indices of RMM and different modes of variability. Skillful forecasts are obtained for lead times between 8 and 27 days. Large ensemble simulations by the stochastic model show that with monsoonal changes in the background state, MJO propagation across the Maritime Continent (MC) is most likely to be disrupted in boreal spring and summer when MJO events propagate from favorable conditions over the Indian Ocean to unfavorable ones over the MC, and predictability is higher during spring and summer when MJO activity is away from the MC region.

54 ENVIRONMENTAL SCIENCES↗

DOE OSTI2026

Testing Classical Properties from Quantum Data

Many properties of Boolean functions can be tested far more efficiently than the function itself can be learned. However, this dramatic advantage often disappears when testers are limited to random samples of ƒ instead of adaptively chosen queries to f. In this work we investigate the quantum version of this restriction: quantum algorithms that test properties of a Boolean function f solely from copies of either the function state |ƒ⟩ ∝ ∑ x |x, ƒ(x)⟩ or the phase state |(-1) ƒ ⟩ ∝ ∑ x (-1) ƒ(x) |x⟩. For monotonicity, symmetry, and triangle-freeness, we show passive quantum testers are unboundedly or super-polynomially better than their classical passive testing counterparts. They are competitive with classic query -based testers in each case. Our new testers use techniques beyond quantum Fourier sampling, and it turns out this is necessary: we show a certain class of bent functions can be tested from 𝒪(1) function states but has a sample complexity lower bound of 2 Ω(n) for any tester relying exclusively on Fourier and classical samples. Our passive quantum testers are competitive with classical query -based testers, but this isn't universal: we exhibit a testing problem that can be solved from 𝒪(1) classical queries but requires Ω(2 n/2 ) function state copies. The Forrelation problem provides a separation of the same magnitude in the opposite direction, so we conclude that quantum data and classical queries are "maximally incomparable" resources for testing. We also begin the study of lower bounds for testing from quantum data. For quantum monotonicity testing, we prove that the ensembles of [Goldreich et al., 2000; Black, 2024], which give exponential lower bounds for classical sample-based testing, do not yield any nontrivial lower bounds for testing from quantum data. New insights specific to quantum data will be required for proving copy complexity lower bounds for testing in this model.

Boolean Functions↗

NASA NTRS1972

Comparison of genetic algorithms with conjugate gradient methods

Genetic algorithms for mathematical function optimization are modeled on search strategies employed in natural adaptation. Comparisons of genetic algorithms with conjugate gradient methods, which were made on an IBM 1800 digital computer, show that genetic algorithms display superior performance over gradient methods for functions which are poorly behaved mathematically, for multimodal functions, and for functions obscured by additive random noise. Genetic methods offer performance comparable to gradient methods for many of the standard functions.

Bosworth, J. L.↗

NASA NTRS1978

A study of digital holographic filters generation. Phase 2: Digital data communication system, volume 1

An empirical study of the performance of the Viterbi decoders in bursty channels was carried out and an improved algebraic decoder for nonsystematic codes was developed. The hybrid algorithm was simulated for the (2,1), k = 7 code on a computer using 20 channels having various error statistics, ranging from pure random error to pure bursty channels. The hybrid system outperformed both the algebraic and the Viterbi decoders in every case, except the 1% random error channel where the Viterbi decoder had one bit less decoding error.

Ingels, F. M.↗

NASA NTRS1987

Turbulence control on airborne laser platform

An avctive flow control device to generate large-scale, periodic structures in a turbulent shear flow is developed. Together with adaptive optics, the device may be used on airborne laser platforms to reduce or eliminate optical distortion caused by the turbulence in the aircraft's boundary layer. A flat plate towed in a water channel is used as a test bed. A cyclic jet issuing from a spanwise slot is used to collect the turbulent boundary layer for a finite time during its 'on' period. When the jet is turned 'off', all of the turbulent fluid is released instantaneously in one large eddy that convects downstream. Flow visualization and hot-film probe measurements are used together with pattern recognition algorithms to demonstrate the viability of the flow control method. The instantaneous velocity signal is used to compute important statistical quantities of the random velocity field, such as the mean, the root-mean-square, the spectral distribution, and the probability density function. When optimized for a given boundary layer, the cyclic jet produces periodic structures that are qualitatively similar to the random, naturally occurring ones. These structures seem to trigger the onset of bursting events near the wall. Thus, the present device generates periodic structures in both the outer and inner regions of a turbulent boundary layer.

Gad-El-hak, Mohamed↗

NASA NTRS1991

Estimation of optical flow in airborne electro-optical sensors by stochastic approximation

The essence of motion or range estimation by passive electrooptical means is the ability to determine the correspondence of picture elements in pairs of image frames and to estimate their coordinates and their disparity (relative shifts) in the image plane of an electrooptical imaging sensor. The disparity can be in successive frames due to self-motion or in simultaneous frames of a stereo pair. A key issue is to provide these estimates on-line. This paper describes the theoretical background of such an interframe shift estimator. It is based on a stochastic gradient algorithm, specifically implementing a form of stochastic approximation, which can achieve rapid convergence of the shift estimate. Analytical and numerical simulation examples for random texture and isolated features validate the feasibility and the effectiveness of the estimator.

Merhav, S. J.↗

NASA NTRS1994

Aerosol Abundances and Optical Characteristics in the Pacific Basin Free Troposphere

During NASA's Global Backscatter Experiment (GLOBE) mission flights in November 1989 and May 1990, a DC-8 research aircraft probed the Pacific Basin free troposphere for about 90 flight hours in each month between +72 and -62 degrees latitude, +130 and -120 degrees longitude, and up to 39,000 feet pressure altitudes. Aerosols were sampled continuously in situ by optical particle counters to measure concentration and particle size, and during 48 10-min intervals during each mission by wire impactors for concentration, size, composition, phase and shape analyses. The optical particle counters cover a particle diameter range between 0.3 and 20 microns; wire impactors extend the range down to 0.03 microns. Results of particle number, size, shape, together with the assumption of a refractive index corresponding to (NH4)2SO4 to account for the prevalence of aerosol sulfur, were utilized in a Mie algorithm to calculate aerosol extinction and backscatter for a range of wavelengths (0.385 less than lambda less than 10.64 microns). Computations for 22 randomly selected size distributions yield coefficients of extinction E(0.525) = (2.03 +/- 1.20) x 10(exp -4) km(exp -1) and backscatter beta(0.525) = (6.45 +/- 3.49) x 10(exp -6) km(exp -1) sr(exp -1) in the visible, and E(10.64) = (8.13 +/- 6.47) x 10(exp -6) km(exp -1) and beta(10.64) = (9.98 +/- 10.69) x 10(exp -8) km(exp -1) sr(exp -1) in the infrared, respectively. Large particles (D greater than 0.3 microns) contribute two-thirds to the total extinction in the visible (lambda = 0.525 microns), and almost 100% in the infrared (lambda = 10.64 microns). These results have been used to define an IR optical aerosol climatology of the Pacific Basin free troposphere, from which it follows that the infrared backscatter coefficient at lambda = 9.25 microns wavelength fluctuates between 5.0 x 10(exp -10) and 2.0 x 10(exp -7) km(exp -1) sr(exp -1) with a modal value 2.0 x 10(exp -8) km(exp -1) sr(exp -1).

Pueschel, R. F.↗

NASA NTRS2010

Using MERRA Gridded Innovations for Quantifying Uncertainties in Analysis Fields and Diagnosing Observing System Inhomogeneities

MERRA is a NASA reanalysis for the satellite era using a major new version of the Goddard Earth Observing System Data Assimilation System Version 5 (GEOS-5). The project focuses on historical analyses of the hydrological cycle on a broad range of weather and climate time scales and places the NASA EOS suite of observations in a climate context. The characterization of uncertainty in reanalysis fields is a commonly requested feature by users of such data. While intercomparison with reference data sets is common practice for ascertaining the realism of the datasets, such studies typically are restricted to long term climatological statistics and seldom provide state dependent measures of the uncertainties involved. In principle, variational data assimilation algorithms have the ability of producing error estimates for the analysis variables (typically surface pressure, winds, temperature, moisture and ozone) consistent with the assumed background and observation error statistics. However, these "perceived error estimates" are expensive to obtain and are limited by the somewhat simplistic errors assumed in the algorithm. The observation minus forecast residuals (innovations) by-product of any assimilation system constitutes a powerful tool for estimating the systematic and random errors in the analysis fields. Unfortunately, such data is usually not readily available with reanalysis products, often requiring the tedious decoding of large datasets and not so-user friendly file formats. With MERRA we have introduced a gridded version of the observations/innovations used in the assimilation process, using the same grid and data formats as the regular datasets. Such dataset empowers the user with the ability of conveniently performing observing system related analysis and error estimates. The scope of this dataset will be briefly described. We will present a systematic analysis of MERRA innovation time series for the conventional observing system, including maximum-likelihood estimates of background and observation errors, as well as global bias estimates. Starting with the joint PDF of innovations and analysis increments at observation locations we propose a technique for diagnosing bias among the observing systems, and document how these contextual biases have evolved during the satellite era covered by MERRA.

da Silva, Arlindo↗

NASA NTRS2015

Polarized Bidirectional Reflectance of Optically Thick Sparse Particulate Layers: an Efficient Numerically Exact Radiative-Transfer Solution

We describe a simple yet efficient numerical algorithm for computing polarized bidirectional reflectance of an optically thick (semi-infinite), macroscopically flat layer composed of statistically isotropic and mirror symmetric random particles. The spatial distribution of the particles is assumed to be sparse, random, and statistically uniform. The 44 Stokes reflection matrix is calculated by iterating the Ambartsumian's vector nonlinear integral equation. The result is a numerically exact solution of the vector radiative transfer equation and as such fully satisfies the energy conservation law and the fundamental reciprocity relation. Since this technique bypasses the computation of the internal radiation field, it is very fast and highly accurate. The FORTRAN implementation of the technique is publicly available on the World Wide Web at http://www.giss.nasa.gov/staff/ mmishchenko/brf. It can be combined with several existing computer programs providing the requisite single-scattering properties of spherical or morphologically complex particles and applied to a wide range of optical characterization problems. Benchmark results obtained with this program can be used for testing alternative solvers of the vector radiative transfer equation.

radiative transfer↗

NASA NTRSDate not supplied

Mapping Surface Vapor Pressure Deficits From Geostationary Satellites for Fire Weather Monitoring

The increase in the wildfires were observed globally in accordance with global warming, and to real- time monitoring of wildfire risk in broad scale is demanded for wildfire management to prevent the spread of wildfires. Scientists invented a lot of indices to assess the wildfire risk. Vapor Pressure Deficit (VPD) is one of the most important meteorological components for those indices. Compared to other components of fire weather indices, VPD can change quickly from lower risk to higher risk even in sub-hourly. Therefore, real-time fire risk monitoring requires high-resolution and high- temporal VPD spatial map. Here, we developed VPD estimation method using the GOES Advanced Baseline Imager (ABI) data. Unlike the polar-orbital satellite data, the ABI can observe target region every 10 minutes, so that we can estimate VPD for fire weather in real-time. The method used to estimate VPD is same with the algorithm of NASA Earth Exchange Gridded Daily Meteorology (NEX- GDM), which estimate meteorological variables from ground weather observation and spatial variables based on random forest (RF). We calculated RF importance to select bands of ABI as input of the model. To validate our results, we compared the spatial pattern of our VPD data with the Real- Time Mesoscale Analysis (RTMA) data over the conterminous USA. We sought possibility of applying our method to the region where no real-time high-resolution weather data is available, such as South America. The developed method can produce real-time high-resolution high-frequent VPD data in the continental scale. The derived data from GOES ABI could contribute to improve the fire weather monitoring and lead to prevent wildfires.

Hirofumi Hashimoto↗

DOE OSTI2023

Similarity Downselection: Finding the n Most Dissimilar Molecular Conformers for Reference-Free Metabolomics

Computational methods for creating in silico libraries of molecular descriptors (e.g., collision cross sections) are becoming increasingly prevalent due to the limited number of authentic reference materials available for traditional library building. These so-called “reference-free metabolomics” methods require sampling sets of molecular conformers in order to produce high accuracy property predictions. Due to the computational cost of the subsequent calculations for each conformer, there is a need to sample the most relevant subset and avoid repeating calculations on conformers that are nearly identical. The goal of this study is to introduce a heuristic method of finding the most dissimilar conformers from a larger population in order to help speed up reference-free calculation methods and maintain a high property prediction accuracy. Finding the set of the n items most dissimilar from each other out of a larger population becomes increasingly difficult and computationally expensive as either n or the population size grows large. Because there exists a pairwise relationship between each item and all other items in the population, finding the set of the n most dissimilar items is different than simply sorting an array of numbers. For instance, if you have a set of the most dissimilar n = 4 items, one or more of the items from n = 4 might not be in the set n = 5. An exact solution would have to search all possible combinations of size n in the population exhaustively. We present an open-source software called similarity downselection (SDS), written in Python and freely available on GitHub. SDS implements a heuristic algorithm for quickly finding the approximate set(s) of the n most dissimilar items. We benchmark SDS against a Monte Carlo method, which attempts to find the exact solution through repeated random sampling. We show that for SDS to find the set of n most dissimilar conformers, our method is not only orders of magnitude faster, but it is also more accurate than running Monte Carlo for 1,000,000 iterations, each searching for set sizes n = 3–7 out of a population of 50,000. We also benchmark SDS against the exact solution for example small populations, showing that SDS produces a solution close to the exact solution in these instances. Using theoretical approaches, we also demonstrate the constraints of the greedy algorithm and its efficacy as a ratio to the exact solution.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2026

Data Driven Correlated Noise Simulation for the ICEBERG LArTPC

Accurate electronic-noise simulation is essential for low-energy physics in liquid-argon TPCs. More realistic noise modeling allows us to better tune reconstruction algorithms and more reliably assess and optimize signal-detection thresholds. We present a data-driven noise simulation framework developed for the ICEBERG test stand for DUNE that generates synthetic noise waveforms that reproduce both (i) the measured per-channel magnitude of the Fast Fourier Transform (FFT) and (ii) frequency-dependent channel-to-channel correlations observed in ICEBERG noise data. Using a dedicated noise-only dataset, we build a compact noise model containing per-channel FFT-magnitude targets together with a small set of band-wise cross-wire color matrices. White noise is generated in the frequency domain by drawing circular-symmetric complex Gaussian coefficients with random phases and scaling them to match the measured FFT-magnitude targets, and cross-wire correlations are subsequently imposed using the stored color matrices. The model and algorithm were integrated into the LArSoft + Wire-Cell Toolkit simulation chain and validated by comparing waveform structure, frequency-domain spectra, and band-limited correlation matrices from simulated noise and ICEBERG data. This approach can be extended to other LArTPC operating conditions.

Ghosh, Avik [Iowa State U.]↗