Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “randomized sketching”

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.

13 records
All sourcesNASA NTRSDOE OSTI
DOE OSTI2025

A randomized sketching trust-region secant method for low-memory dynamic optimization

The numerical solution of dynamic optimization problems is often limited by the memory required to store the state trajectory, which is used to evaluate the objective function and its derivatives. Recently, [R. Muthukumar et al., SIAM Journal on Optimization 31(2), pp. 1242–1275 (2021)] introduced a trust-region method for dynamic optimization that employs randomized sketching to compress the state trajectory, resulting in inexact derivative computations. By adaptively learning the sketch rank, the trust-region algorithm achieves rigorous convergence guarantees. Here, we extend this approach to use secant Hessian approximations. Due to the randomness introduced by the sketch, the traditional secant update formulae can produce poor Hessian approximations. In particular, the difference of two gradients, computed from two different sketches, may be inconsistent. To overcome this, we employ a sketched approximation of the Hessian application, in lieu of computing the gradient difference. We numerically demonstrate the improved stability of this approach on an example from PDE-constrained optimization.

dynamic optimization↗
DOE OSTI2025

Surrogate-Based Autotuning for Randomized Sketching Algorithms in Regression Problems

Algorithms from Randomized Numerical Linear Algebra (RandNLA) are known to be effective in handling high-dimensional computational problems, providing high-quality empirical performance as well as strong probabilistic guarantees. However, their practical application is complicated by the fact that the user needs to set various algorithm-specific tuning parameters which are different from those used in traditional NLA. This paper demonstrates how a surrogate-based autotuning approach can be used to address fundamental problems of parameter selection in RandNLA algorithms. In particular, we provide a detailed investigation of surrogate-based autotuning for sketch-and-precondition (SAP)-based randomized least squares methods, which have been one of the great success stories in modern RandNLA. Empirical results show that our surrogate-based autotuning approach can achieve near-optimal performance with much less tuning cost than a random search (up to about 7.6x fewer trials of different parameter configurations). Moreover, while our experiments focus on least squares, our results demonstrate a general-purpose autotuning pipeline applicable to any kind of RandNLA algorithm.

Cho, Younghyun↗
DOE OSTI2024

Get Non-Real: Randomized Sketching for High-Dimensional Non-Real Valued Data (Final Report)

In our final report for DE-C0022186, we describe the work we did on this grant towards the goals we proposed. Our first goal was characterizing fundamental limits for sketching of discrete high-dimensional matrices with low-dimensional structures. Our second main goal was designing algorithms for data reconstruction from sketches. We focus on approaches that are either specifically designed for non-real-valued data (binary, finite field) or that will translate more readily to that setting.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

Randomized Algorithms for Linear Solvers

Recently, randomized algorithms in numerical linear algebra, specifically those centered around random sketching, have gained traction in primarily theoretical research due to their potential to significantly reduce problem dimensionality at the cost of an O(1) multiplicative distortion factor. It has been assumed that this sketching can be done efficiently, but thorough investigation into how precisely to do it has been neglected. Moreover, the theory-based community has argued for sketching’s ability to reduce computational cost via complexity analysis, but has not researched how it affects the stability of the algorithms. At Sandia, efficient linear solvers that scale well on modern HPC architectures while maintaining stability are imperative for practical applications. In this LDRD, we developed a random sketching strategy that is substantially faster than existing ones, and demonstrate its superior performance in practice on a NVIDIA H100 GPU. Moreover, we show how this can be used to significantly outperform existing linear least squares solvers while improving the solver’s stability as well. Additionally, we demonstrate how this sketching strategy can be used to make a fast, stable QR factorization that can subsequently be used in s-step and block Krylov solvers. Finally, we incorporate a sketching-based block orthogonalization scheme into s-step GMRES, which is stable and faster than existing approaches on the Perlmutter supercomputer.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2026

Memory-efficient nonsmooth dynamic optimization using adaptive randomized compression

Dynamic optimization problems arise in many applications including flow control, full waveform inversion, and medical imaging. These problems are plagued by significant computational challenges. One such challenge — and the focus of this work — is the memory limitation induced by the size of the underlying dynamical system. In particular, the entire dynamic trajectory is required for derivative computation and therefore must be stored or recomputed using, e.g., checkpointing. Although recent work demonstrated the use of adaptive randomized sketching to overcome the memory challenge, that work only applies to smooth unconstrained problems, prohibiting its use for nonsmooth regularized and constrained problems. The inclusion of nonsmooth regularizers and constraints is critical as they often arise in an attempt to preserve certain physical properties or to promote sparsity. To solve these problems, we introduce a trust-region algorithm for minimizing the sum of a smooth nonconvex function and a nonsmooth convex function that leverages randomized sketching to compress the dynamical system trajectories and adaptively adjust the sketch rank to satisfy a gradient inexactness condition. We prove convergence of this algorithm and demonstrate that it achieves substantial memory reduction on three discretized PDE-constrained optimization applications.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

Randomized Algorithms for Symmetric Nonnegative Matrix Factorization

Symmetric Nonnegative Matrix Factorization (SymNMF) is a technique in data analysis and machine learning that approximates a matrix with a product of a nonnegative, low-rank matrix and it transpose. To design faster and more scalable algorithms for SymNMF we develop two randomized algorithms for its computation. The first method uses randomized matrix sketching to compute an initial low-rank approximation to the input matrix and proceeds to uses this as a low-rank input to rapidly compute a SymNMF. The second methods uses randomized leverage score sampling to approximately solve constrained least squares problems. Many successful methods for SymNMF rely on (approximately) solving sequences of constrained least squares problems. Here, we prove theoretically that leverage score sampling can approximately solve constrained least squares problems to e-accuracy. Finally we demonstrate both methods work in practice by applying them to graph clustering tasks on large real world data sets. These experiments show that our methods approximately maintain solution quality and achieve significant speed ups for both large dense and large sparse problems.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2026

Augmenting subspace optimization methods with linear bandits

In this work, we consider the framework of methods for unconstrained minimization that are, in each iteration, restricted to a model that is only a valid approximation to the objective function on some affine subspace containing an incumbent point. These methods are of practical interest in computational settings where derivative information is either expensive or impossible to obtain. Recent attention has been paid in the literature to employing randomized matrix sketching for generating the affine subspaces within this framework. We consider a relatively straightforward, deterministic augmentation of such a generic subspace optimization method. In particular, we consider a sequential optimization framework where actions consist of one-dimensional linear subspaces and rewards consist of (approximations to) the magnitudes of directional derivatives computed in the direction of the action subspace. Reward maximization in this context is consistent with maximizing lower bounds on descent guaranteed by first-order Taylor models. This sequential optimization problem can be analysed through the lens of dynamic regret. We modify an existing linear upper confidence bound (UCB) bandit method and prove sublinear dynamic regret in the subspace optimization setting. We demonstrate the efficacy of employing this linear UCB method in a setting where forward-mode algorithmic differentiation can provide directional derivatives in arbitrary directions and in a derivative-free setting. For the derivative-free setting, we propose SS-POUNDers, an extension of the derivative-free optimization method POUNDers that employs the linear UCB mechanism to identify promising subspaces. Our numerical experiments suggest a preference, in either computational setting, for employing a linear UCB mechanism within a subspace optimization method.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1967

Concepts for a theoretical and experimental study of lifting rotor random loads and vibrations, Phase 1

A number of lifting rotor conditions with random inputs are discussed. The present state of random process theory, applicable to lifting rotor problems is sketched. Possible theories of random blade flapping and random blade flap-bending are outlined and their limitations discussed. A plan for preliminary experiments to study random flapping motions of a see-saw rotor is developed.

Hohenemser, K. H.↗
NASA NTRSDate not supplied

Planning Bias: Planning as a Source of Sampling Bias

Many data-driven planning methods are trained on data generated by planners. It is well known that many statistical learning methods are sensitive to sampling bias, and yet there has been little or no attention to planning as a sampling method and its role in introducing sampling bias into planner-generated training data. Recently, it has been demonstrated that A**,* in the presence of problems with variable heuristic error, prefers some solutions over other equally cost-optimal solutions. But, as we discuss in this paper, mitigation may not be as simple as resolving arbitrary tie-breaking by sampling from ties uniformly at random. In this paper, we formalize an intuition of planning bias. We focus on problems which output a single solution. Diverse planning only complicates the problem by generalizing it to bias in the set of sets; we show how it is subject to bias in the single solution. We make some useful observations about deterministic algorithms in contrast to non-deterministic algorithms. We explain how information entropy may be a good way to measure planning bias, and discuss some issues in evaluating practical approaches to measurement. We address the intuition that uniform random tiebreaking should mitigate bias; and sketch a novel approach to constructing an appropriate random distribution for duplicate detection during forward search for unbiased A*. Finally, we suggest directions for future work.

Planning Scheduling Algorithms↗
DOE OSTI2025

Randomized Algorithms for Low-Rank Matrix and Tensor Decompositions

This paper surveys randomized algorithms in numerical linear algebra for low-rank decompositions of matrices and tensors. The survey begins with a review of classical matrix algorithms that can be accelerated by randomized dimensionality reduction, such as the singular value decomposition (SVD) or interpolative (ID) and CUR decompositions. Recent advances in randomized dimensionality reduction are discussed, including new methods of fast matrix sketching and sampling techniques, which are incorporated into classical matrix algorithms for fast low-rank matrix approximations. The extension of randomized matrix algorithms to tensors is then explored for several low-rank tensor decompositions in the CP and Tucker formats, including the higher-order SVD, ID, and CUR decomposition.

Pearce, Katherine J. [The University of Texas at A↗
DOE OSTI2026

Two-Level Sketching Alternating Anderson Acceleration for Complex Physics Applications

We present a novel two-level sketching extension of the Alternating Anderson–Picard (AAP) method for accelerating fixed-point iterations in challenging single- and multiphysics simulations governed by discretized PDEs. Our approach combines a static, physics-based projection that reduces the least-squares (LS) problem to the most informative field (e.g., via Schur-complement insight) with a dynamic, algebraic sketching stage driven by a backward stability analysis under Lipschitz continuity. We introduce inexpensive estimators for stability thresholds and cache-aware randomized selection strategies to balance computational cost against memory access overhead. The resulting algorithm solves reduced LS systems in place, minimizes memory footprints, and seamlessly alternates between low-cost Picard updates and Anderson mixing. Implemented in Julia, our two-level sketching AAP achieves up to 50% time-to-solution reductions compared to standard Anderson acceleration—without degrading convergence rates—on benchmark problems including Stokes, 𝑝-Laplacian, bidomain, and Navier–Stokes formulations at varying problem sizes. These results demonstrate the method’s robustness, scalability, and potential for integration into high-performance scientific computing frameworks. Our implementation is available open source in the AAP.jl library.

Barnafi, Nicolas [University of Chile, Santiago]↗
DOE OSTI2025

Randomized Preconditioned Solvers for Strong Constraint 4D-Var Data Assimilation

The Strong Constraint 4D Variational (SC-4DVAR) data assimilation method is widely used in climate and weather applications. SC-4DVAR involves solving a minimization problem to compute the maximum a posteriori estimate, which we tackle using the Gauss-Newton method. The computation of the descent direction is expensive since it involves the solution of a large-scale and potentially ill-conditioned linear system, solved using the preconditioned conjugate gradient (PCG) method. Here, to address this cost, we efficiently construct scalable preconditioners using three different randomization techniques, which all rely on a certain low-rank structure involving the Gauss-Newton Hessian. The proposed techniques come with theoretical guarantees on the condition number, and at the same time, are amenable to parallelization. We also develop an adaptive approach to estimate the sketch size and choose between the reuse or recomputation of the preconditioner. We demonstrate the performance and effectiveness of our methodology on two representative model problems—the Burgers and barotropic vorticity equation—showing a drastic reduction in both the number of PCG iterations and the number of Gauss-Newton Hessian products after including the preconditioner construction cost.

Gauss-Newton↗
NASA NTRS2007

Potential of VIIRS Time Series Data for Aiding the USDA Forest Service Early Warning System for Forest Health Threats: A Gypsy Moth Defoliation Case Study

This report details one of three experiments performed during FY 2007 for the NASA RPC (Rapid Prototyping Capability) at Stennis Space Center. This RPC experiment assesses the potential of VIIRS (Visible/Infrared Imager/Radiometer Suite) and MODIS (Moderate Resolution Imaging Spectroradiometer) data for detecting and monitoring forest defoliation from the non-native Eurasian gypsy moth (Lymantria dispar). The intent of the RPC experiment was to assess the degree to which VIIRS data can provide forest disturbance monitoring information as an input to a forest threat EWS (Early Warning System) as compared to the level of information that can be obtained from MODIS data. The USDA Forest Service (USFS) plans to use MODIS products for generating broad-scaled, regional monitoring products as input to an EWS for forest health threat assessment. NASA SSC is helping the USFS to evaluate and integrate currently available satellite remote sensing technologies and data products for the EWS, including the use of MODIS products for regional monitoring of forest disturbance. Gypsy moth defoliation of the mid-Appalachian highland region was selected as a case study. Gypsy moth is one of eight major forest insect threats listed in the Healthy Forest Restoration Act (HFRA) of 2003; the gypsy moth threatens eastern U.S. hardwood forests, which are also a concern highlighted in the HFRA of 2003. This region was selected for the project because extensive gypsy moth defoliation occurred there over multiple years during the MODIS operational period. This RPC experiment is relevant to several nationally important mapping applications, including agricultural efficiency, coastal management, ecological forecasting, disaster management, and carbon management. In this experiment, MODIS data and VIIRS data simulated from MODIS were assessed for their ability to contribute broad, regional geospatial information on gypsy moth defoliation. Landsat and ASTER (Advanced Spaceborne Thermal Emission and Reflection Radiometer) data were used to assess the quality of gypsy moth defoliation mapping products derived from MODIS data and from simulated VIIRS data. The project focused on use of data from MODIS Terra as opposed to MODIS Aqua mainly because only MODIS Terra data was collected during 2000 and 2001-years with comparatively high amounts of gypsy moth defoliation within the study area. The project assessed the quality of VIIRS data simulation products. Hyperion data was employed to assess the quality of MODIS-based VIIRS simulation datasets using image correlation analysis techniques. The ART (Application Research Toolbox) software was used for data simulation. Correlation analysis between MODIS-simulated VIIRS data and Hyperion-simulated VIIRS data for red, NIR (near-infrared), and NDVI (Normalized Difference Vegetation Index) image data products collectively indicate that useful, effective VIIRS simulations can be produced using Hyperion and MODIS data sources. The r(exp 2) for red, NIR, and NDVI products were 0.56, 0.63, and 0.62, respectively, indicating a moderately high correlation between the 2 data sources. Temporal decorrelation from different data acquisition times and image misregistration may have lowered correlation results. The RPC experiment also generated MODIS-based time series data products using the TSPT (Time Series Product Tool) software. Time series of simulated VIIRS NDVI products were produced at approximately 400-meter resolution GSD (Ground Sampling Distance) at nadir for comparison to MODIS NDVI products at either 250- or 500-meter GSD. The project also computed MODIS (MOD02) NDMI (Normalized Difference Moisture Index) products at 500-meter GSD for comparison to NDVI-based products. For each year during 2000-2006, MODIS and VIIRS (simulated from MOD02) time series were computed during the peak gypsy moth defoliation time frame in the study area (approximately June 10 through July 27). Gypsy moth defoliation mapping products from simated VIIRS and MOD02 time series were produced using multiple methods, including image classification and change detection via image differencing. The latter enabled an automated defoliation detection product computed using percent change in maximum NDVI for a peak defoliation period during 2001 compared to maximum NDVI across the entire 2000-2006 time frame. Final gypsy moth defoliation mapping products were assessed for accuracy using randomly sampled locations found on available geospatial reference data (Landsat and ASTER data in conjunction with defoliation map data from the USFS). Extensive gypsy moth defoliation patches were evident on screen displays of multitemporal color composites derived from MODIS data and from simulated VIIRS vegetation index data. Such defoliation was particularly evident for 2001, although widespread denuded forests were also seen for 2000 and 2003. These visualizations were validated using aforementioned reference data. Defoliation patches were visible on displays of MODIS-based NDVI and NDMI data. The viewing of apparent defoliation patches on all of these products necessitated adoption of a specialized temporal data processing method (e.g., maximum NDVI during the peak defoliation time frame). The frequency of cloud cover necessitated this approach. Multitemporal simulated VIIRS and MODIS Terra data both produced effective general classifications of defoliated forest versus other land cover. For 2001, the MOD02-simulated VIIRS 400-meter NDVI classification produced a similar yet slightly lower overall accuracy (87.28 percent with 0.72 Kappa) than the MOD02 250-meter NDVI classification (88.44 percent with 0.75 Kappa). The MOD13 250-meter NDVI classification had a lower overall accuracy (79.13 percent) and a much lower Kappa (0.46). The report discusses accuracy assessment results in much more detail, comparing overall classification and individual class accuracy statistics for simulated VIIRS 400-meter NDVI, MOD02 250-meter NDVI, MOD02-500 meter NDVI, MOD13 250-meter NDVI, and MOD02 500-meter NDMI classifications. Automated defoliation detection products from simulated VIIRS and MOD02 data for 2001 also yielded similar, relatively high overall classification accuracy (85.55 percent for the VIIRS 400-meter NDVI versus 87.28 percent for the MOD02 250-meter NDVI). In contrast, the USFS aerial sketch map of gypsy moth defoliation showed a lower overall classification accuracy at 73.64 percent. The overall classification Kappa values were also similar for the VIIRS (approximately 0.67 Kappa) versus the MOD02 (approximately 0.72 Kappa) automated defoliation detection product, which were much higher than the values exhibited by the USFS sketch map product (overall Kappa of approximately 0.47). The report provides additional details on the accuracy of automated gypsy moth defoliation detection products compared with USFS sketch maps. The results suggest that VIIRS data can be effectively simulated from MODIS data and that VIIRS data will produce gypsy moth defoliation mapping products that are similar to MODIS-based products. The results of the RPC experiment indicate that VIIRS and MODIS data products have good potential for integration into the forest threat EWS. The accuracy assessment was performed only for 2001 because of time constraints and a relative scarcity of cloud-free Landsat and ASTER data for the peak defoliation period of the other years in the 2000-2006 time series. Additional work should be performed to assess the accuracy of gypsy moth defoliation detection products for additional years.The study area (mid-Appalachian highlands) and application (gypsy moth forest defoliation) are not necessarily representative of all forested regions and of all forest threat disturbance agents. Additional work should be performed on other inland and coastal regions as well as for other major forest threats.

Spruce, Joseph P.↗