Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “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.

At least 19 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

Dynamical Sketching for Enhanced Communication Efficiency in Federated Learning

Federated learning (FL) has revolutionized distributed machine learning by enabling collaborative model training without sharing local data. However, communication efficiency and privacy guarantees remain significant challenges. This paper introduces a dynamic sketching mechanism in FL, optimizing the trade-off between communication efficiency and model accuracy. By dynamically selecting the sketch matrix size, our approach adapts to the evolving characteristics of the data and the model, ensuring optimal performance across diverse scenarios. We leverage Bayesian optimization to systematically tune the sketch parameters, achieving an effective balance between resource efficiency and model performance. Experimental results on the MNIST dataset using a convolutional neural network (CNN) architecture validate the proposed method's efficiency and scalability. Our dynamic sketching approach significantly outperforms fixed-size sketching techniques, achieving higher compression ratios (up to 62x) and providing better privacy guarantees while maintaining high model accuracy. These findings highlight the robustness and versatility of our approach and make it a valuable solution for privacy-preserving, communication-efficient federated learning.

Afrose, Sharmin [ORNL]↗
DOE OSTI2022

Dynamic mode decomposition with core sketch

With the increase in collected data volumes, either from experimental measurements or high fidelity simulations, there is an ever-growing need to develop computationally efficient tools to process, analyze, and interpret these datasets. Modal analysis techniques have gained great interest due to their ability to identify patterns in the data and extract valuable information about the system being considered. Dynamic mode decomposition (DMD) relies on elements of the Koopman approximation theory to compute a set of modes, each associated with a fixed oscillation frequency and a decay/growth rate. Extracting these details from large datasets can be computationally expensive due to the need to implement singular value decomposition of the input data matrix. Sketching algorithms have become popular in numerical linear algebra where statistical theoretic approaches are utilized to reduce the cost of major operations. A sketch of a matrix is another matrix, which is significantly smaller, but still sufficiently approximates the original system. We put forth an efficient DMD framework, SketchyDMD, based on a core sketching algorithm that captures information about the range and corange (their mutual relationship) of input data. The proposed sketching-based framework can accelerate various portions of the DMD routines, compared to classical methods that operate directly on the raw input data. We conduct numerical experiments using the spherical shallow water equations as a prototypical model in the context of geophysical flows. In conclusion, we show that the proposed SketchyDMD is superior to existing randomized DMD methods that are based on capturing only the range of the input data.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2020

An investigation of Newton-Sketch and subsampled Newton methods

Sketching, a dimensionality reduction technique, has received much attention in the statistics community. In this paper, we study sketching in the context of Newton's method for solving finite-sum optimization problems in which the number of variables and data points are both large. In this work, we study two forms of sketching that perform dimensionality reduction in data space: Hessian subsampling and randomized Hadamard transformations. Each has its own advantages, and their relative tradeoffs have not been investigated in the optimization literature. Additionally, our study focuses on practical versions of the two methods in which the resulting linear systems of equations are solved approximately, at every iteration, using an iterative solver. The advantages of using the conjugate gradient method vs. a stochastic gradient iteration are revealed through a set of numerical experiments, and a complexity analysis of the Hessian subsampling method is presented.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Randomized Sketching Algorithms for Low-Memory Dynamic Optimization

This paper develops a novel limited-memory method to solve dynamic optimization problems. The memory requirements for such problems often present a major obstacle, particularly for problems with PDE constraints such as optimal flow control, full waveform inversion, and optical tomography. In these problems, PDE constraints uniquely determine the state of a physical system for a given control; the goal is to find the value of the control that minimizes an objective. While the control is often low dimensional, the state is typically more expensive to store. This paper suggests using randomized matrix approximation to compress the state as it is generated and shows how to use the compressed state to reliably solve the original dynamic optimization problem. Concretely, the compressed state is used to compute approximate gradients and to apply the Hessian to vectors. The approximation error in these quantities is controlled by the target rank of the sketch. This approximate first- and second-order information can readily be used in any optimization algorithm. As an example, we develop a sketched trust-region method that adaptively chooses the target rank using a posteriori error information and provably converges to a stationary point of the original problem. Numerical experiments with the sketched trust-region method show promising performance on challenging problems such as the optimal control of an advection-reaction-diffusion equation and the optimal control of fluid flow past a cylinder.

97 MATHEMATICS AND COMPUTING↗
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]↗
NASA NTRS1989

From primal sketches to the recovery of intensity and reflectance representations

A local change in intensity (edge) is a characteristic that is preserved when an image is filtered through a bandpass filter. Primal sketch representations of images, using the bandpass-filtered data, have become a common process since Marr proposed his model for early human vision. Here, researchers move beyond the primal sketch extraction to the recovery of intensity and reflectance representations using only the bandpass-filtered data. Assessing the response of an ideal step edge to the Laplacian of Gaussian (NAb/A squared G) filter, they found that the resulting filtered data preserves the original change of intensity that created the edge in addition to the edge location. Using the filtered data, they can construct the primal sketches and recover the original (relative) intensity levels between the boundaries. It was found that the result of filtering an ideal step edge with the Intensity-Dependent Spatial Summation (IDS) filter preserves the actual intensity on both sides of the edge, in addition to the edge location. The IDS filter also preserves the reflectance ratio at the edge location. Therefore, one can recover the intensity levels between the edge boundaries as well as the (relative) reflectance representation. The recovery of the reflectance representation is of special interest as it erases shadowing degradations and other dependencies on temporal illumination. This method offers a new approach to low-level vision processing as well as to high data-compression coding. High compression can be gained by transmitting only the information associated with the edge location (edge primitives) that is necessary for the recovery

Alter-Gartenberg, Rachel↗
NASA NTRS2000

User's Guide for SKETCH

A user's guide for the computer program SKETCH is presented on this disk. SKETCH solves a popular problem in computer graphics-the removal of hidden lines from images of solid objects. Examples and illustrations are included in the guide. Also included is the SKETCH program, so a user can incorporate the information into a particular software system.

Hedgley, David R., Jr.↗
NASA NTRS2020

Sketch-to-Solution: A Case Study in RCS Aerodynamic Interaction

Thanks to recent advances in the fields of anisotropic grid adaptation, error estimation, and geometry modeling, a sketch-to-solution work flow is now possible for viscous computational fluid dynamic (CFD) simulations. With this workflow, a CFD application engineer provides geometry, boundary conditions, and flow parameters; and the sketch-to-solution process yields a CFD simulation through automatic, error-based, grid adaptation. To explore the benefits of this nascent capability, a conventional manual grid generation work flow is compared to this new automatic grid generation work flow for a given engineering question: What are the aerodynamic interactions caused by the reaction control system (RCS) on an entry vehicle? This case study indicates that while the automatic grid generation sketch-to- solution process is not yet mature, it is preferred over a manual grid generation work flow because it greatly reduces manual labor, eliminates many opportunities for human error, and provides grid sensitivity information.

Bill Kleb↗
NASA NTRS1982

User's guide for SKETCH

A user's guide for the computer program SKETCH is presented. The removal of hidden lines from images of solid objects is a problem in computer graphics which is solved by SKETCH.

Hedgley, D. R., Jr.↗
DOE OSTI2024

Patch2Self2: Self-supervised Denoising on Coresets via Matrix Sketching

Diffusion MRI (dMRI) non-invasively maps brain white matter yet necessitates denoising due to low signal-to-noise ratios. Patch2Self (P2S) employing self-supervised techniques and regression on a Casorati matrix effectively denoises dMRI images and has become the new de-facto standard in this field. P2S however is resource intensive both in terms of running time and memory usage as it uses all voxels (n) from all-but-one held-in volumes (d-1) to learn a linear mapping Phi : \mathbb R ^ n x(d-1) \mapsto \mathbb R ^ n for denoising the held-out volume. The increasing size and dimensionality of higher resolution dMRI acquisitions can make P2S infeasible for large-scale analyses. This work exploits the redundancy imposed by P2S to alleviate its performance issues and inspect regions that influence the noise disproportionately. Specifically this study makes a three-fold contribution: (1) We present Patch2Self2 (P2S2) a method that uses matrix sketching to perform self-supervised denoising. By solving a sub-problem on a smaller sub-space so called coreset we show how P2S2 can yield a significant speedup in training time while using less memory. (2) We present a theoretical analysis of P2S2 focusing on determining the optimal sketch size through rank estimation a key step in achieving a balance between denoising accuracy and computational efficiency. (3) We show how the so-called statistical leverage scores can be used to interpret the denoising of dMRI data a process that was traditionally treated as a black-box. Experimental results on both simulated and real data affirm that P2S2 maintains denoising quality while significantly enhancing speed and memory efficiency achieved by training on a reduced data subset.

Fadnavis, Shreyas↗
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 OSTI2023

An inexact semismooth Newton method with application to adaptive randomized sketching for dynamic optimization

In many applications, one can only access the inexact gradients and inexact hessian times vector products. Thus it is essential to consider algorithms that can handle such inexact quantities with a guaranteed convergence to solution. An inexact adaptive and provably convergent semismooth Newton method is considered to solve constrained optimization problems. In particular, dynamic optimization problems, which are known to be highly expensive, are the focus. A memory efficient semismooth Newton algorithm is introduced for these problems. The source of efficiency and inexactness is the randomized matrix sketching. Further, applications to optimization problems constrained by partial differential equations are also considered.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

Large Scale Tensor Factorization via Parallel Sketches

Tensor factorization methods have recently gained increased popularity. A key feature that renders tensors attractive is the ability to directly model multi-relational data. In this work, we propose ParaSketch, a parallel tensor factorization algorithm that enables massive parallelism, to deal with large tensors. The idea is to compress the large tensor into multiple small tensors, decompose each small tensor in parallel, and combine the results to reconstruct the desired latent factors. Prior art in this direction entails potentially very high complexity in the (Gaussian) compression and final combining stages. Adopting sketching matrices for compression, the proposed method enjoys a dramatic reduction in compression complexity, and features a much lighter combining step. Moreover, theoretical analysis shows that the compressed tensors inherit latent identifiability under mild conditions, hence establishing correctness of the overall approach. Numerical experiments corroborate the theory and demonstrate the effectiveness of the proposed algorithm.

block term decomposition↗
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 OSTI2021

Sketching Algorithms in Distributed Systems

In this position paper, we discuss exciting recent advancements in sketching algorithms applied to distributed systems. That is, we look at randomized algorithms that simultaneously reduce the data dimensionality, offer potential privacy benefits, while maintaining verifiably high levels of algorithm accuracy and performance in multi-node computational setups. We look at next steps and discuss the applicability to real systems.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1972

Geologic sketch map of the candidate Proclus Apollo landing site, part K

An Apollo 15 panoramic camera frame was used as a base for a geologic sketch map of an area near Proclus Crater. The map was prepared to investigate the usefulness of the panoramic camera photography in large-scale geologic mapping and to assess the geologic value of the area as a potential Apollo landing site. The photographs, taken under high solar illumination, resulted in good definition of albedo features, and stereoscopic viewing provided extreme clarity of topographic relief with terrain units easily delineated. The geological characteristics of the area as evidenced by the high-resolution photographs is discussed. It is concluded that the panoramic camera photographs reveal a wealth of detail and are eminently suited for geologic mapping purposes. In addition, the Proclus area, as a potential landing site, offers relatively rough plains terrain.

Lucchitta, B. K.↗