Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “approximation algorithm”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

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

At least 433 records · Page 24
All sourcesNASA NTRSDOE OSTI
NASA NTRS2012

Terra MODIS Band 27 Electronic Crosstalk Effect and Its Removal

The MODerate-resolution Imaging Spectroradiometer (MODIS) is one of the primary instruments in the NASA Earth Observing System (EOS). The first MODIS instrument was launched in December, 1999 on-board the Terra spacecraft. MODIS has 36 bands, covering a wavelength range from 0.4 micron to 14.4 micron. MODIS band 27 (6.72 micron) is a water vapor band, which is designed to be insensitive to Earth surface features. In recent Earth View (EV) images of Terra band 27, surface feature contamination is clearly seen and striping has become very pronounced. In this paper, it is shown that band 27 is impacted by electronic crosstalk from bands 28-30. An algorithm using a linear approximation is developed to correct the crosstalk effect. The crosstalk coefficients are derived from Terra MODIS lunar observations. They show that the crosstalk is strongly detector dependent and the crosstalk pattern has changed dramatically since launch. The crosstalk contributions are positive to the instrument response of band 27 early in the mission but became negative and much larger in magnitude at later stages of the mission for most detectors of the band. The algorithm is applied to both Black Body (BB) calibration and MODIS L1B products. With the crosstalk effect removed, the calibration coefficients of Terra MODIS band 27 derived from the BB show that the detector differences become smaller. With the algorithm applied to MODIS L1B products, the Earth surface features are significantly removed and the striping is substantially reduced in the images of the band. The approach developed in this report for removal of the electronic crosstalk effect can be applied to other MODIS bands if similar crosstalk behaviors occur.

Sun, Junqiang↗
DOE OSTI2024

Provable bounds for noise-free expectation values computed from noisy samples

Quantum computing has emerged as a powerful computational paradigm capable of solving problems beyond the reach of classical computers. However, today’s quantum computers are noisy, posing challenges to obtaining accurate results. Here, we explore the impact of noise on quantum computing, focusing on the challenges in sampling bit strings from noisy quantum computers and the implications for optimization and machine learning. We formally quantify the sampling overhead to extract good samples from noisy quantum computers and relate it to the layer fidelity, a metric to determine the performance of noisy quantum processors. Further, we show how this allows us to use the conditional value at risk of noisy samples to determine provable bounds on noise-free expectation values. We discuss how to leverage these bounds for different algorithms and demonstrate our findings through experiments on real quantum computers involving up to 127 qubits. The results show strong alignment with theoretical predictions.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

Fast truncated SVD of sparse and dense matrices on graphics processors

We investigate the solution of low-rank matrix approximation problems using the truncated singular value decomposition (SVD). For this purpose, we develop and optimize graphics processing unit (GPU) implementations for the randomized SVD and a blocked variant of the Lanczos approach. Our work takes advantage of the fact that the two methods are composed of very similar linear algebra building blocks, which can be assembled using numerical kernels from existing high-performance linear algebra libraries. Furthermore, the experiments with several sparse matrices arising in representative real-world applications and synthetic dense test matrices reveal a performance advantage of the block Lanczos algorithm when targeting the same approximation accuracy.

Computer Science↗
NASA NTRS2005

TRMM Re-Entry Planning: Attitude Determination and Control During Thruster Modes

The Tropical Rainfall Measuring Mission (TRMM) spacecraft has been undergoing design for a controlled re-entry to Earth. During simulation of the re-entry plan, there was evidence of errors in the attitude determination algorithms during thruster modes. These errors affected the bum efficiency, and thus planning, during re-entry. During thruster modes, the spacecraft attitude is controlled off of integrated Gyro Error Angles that were designed to closely follow the nominal spacecraft pointing frame (Tip Frame). These angles, however, were not exactly mapped to the Tip Frame from the Body Frame. Additionally, in the initial formulation of the thruster mode attitude determination algorithms, several assumptions and approximations were made to conserve processor speed. These errors became noticeable and significant when simulating bums of much longer duration (-10 times) than had been produced in flight. A solution is proposed that uses attitude determination information from a propagated extended Kalman filter that already exists in the TRMM thruster modes. This attitude information is then used to rotate the Gyro Error Angles into the Tip Frame. An error analysis is presented that compares the two formulations. The new algorithm is tested using the TRMM High-Fidelity Simulator and verified with the TRMM Software Testing and Training Facility. Simulation results for both configurations are also presented.

DeWeese, Keith↗
DOE OSTI2022

Novel Solver Algorithms for Nearly Singular Linear Systems Arising in Combustion Modelling

Direct Numerical Simulations of realistic combustion devices are extremely challenging due to the wide separation of scales in the simulation, for example an internal combustion (IC) engine chamber, and the flame thickness of a high-pressure flame. The PeleLMeX solver uses adaptive mesh refinement (AMR) to evolve multi-species reacting flows in the low Mach number limit at the Exascale and relies on an embedded boundary (EB) approach to represent complex geometries. In that framework, the EB geometries often give rise to very small cut-cells along the boundary, which translate into extreme ill-conditioning of the pressure-projection, with eigenvalues that span 15-16 orders of magnitude. In this talk, we focus on the case of a typical IC piston bowl geometry for which we present on a novel approach towards solving these nearly singular linear systems with ILU-based, C-AMG smoothers on massively parallel architectures. In particular, we use scaling and equilibration algorithms to handle the non-normality of the upper triangular factors. This enables us to approximate the highly sequential triangular solve algorithm, embedded in the AMG smoothing-solve phase, with Jacobi iterations. This approximation can be written as a convergent Neumann series whose terms are composed of highly parallel sparse matrix vector multiplications. The result is an algorithm that substantially decreases setup and solve time, compared to state-of-the-art, for these challenging linear systems.

combustion modelling↗
NASA NTRS2010

Navier-Stokes Dynamics by a Discrete Boltzmann Model

This work investigates the possibility of particle-based algorithms for the Navier-Stokes equations and higher order continuum approximations of the Boltzmann equation; such algorithms would generalize the well-known Pullin scheme for the Euler equations. One such method is proposed in the context of a discrete velocity model of the Boltzmann equation. Preliminary results on shock structure are consistent with the expectation that the shock should be much broader than the near discontinuity predicted by the Pullin scheme, yet narrower than the prediction of the Boltzmann equation. We discuss the extension of this essentially deterministic method to a stochastic particle method that, like DSMC, samples the distribution function rather than resolving it completely.

Rubinstein, Robet↗
NASA NTRS1991

An Object-oriented Query Processor that Produces Monotonically Improving Approximate Answers

The paper describes an object-oriented query processor that makes approximate answers available if there is not enough time to produce an exact answer or if part of the database is unavailable. The accuracy of the approximate result produces improves monotonically with the amount of data retrieved to produce the result. The query processing algorithm is based on an approximate relational data model and works within a standard relational algebra framework. The query processor maintains an object-oriented view on an underlying level and can be implemented on a relational database system with little change to the relational architecture. We show how a monotone query processing strategy can be implemented, making effective use of semantic information presented by the object-oriented view.

Vrbsky, S. V.↗
NASA NTRS2003

Genetic Algorithm Tuned Fuzzy Logic for Gliding Return Trajectories

The problem of designing and flying a trajectory for successful recovery of a reusable launch vehicle is tackled using fuzzy logic control with genetic algorithm optimization. The plant is approximated by a simplified three degree of freedom non-linear model. A baseline trajectory design and guidance algorithm consisting of several Mamdani type fuzzy controllers is tuned using a simple genetic algorithm. Preliminary results show that the performance of the overall system is shown to improve with genetic algorithm tuning.

Burchett, Bradley T.↗
DOE OSTI2023

Piecewise linear approximation with minimum number of linear segments and minimum error: A fast approach to tighten and warm start the hierarchical mixed integer formulation

In several areas of economics and engineering, it is often necessary to fit discrete data points or approximate nonlinear functions with continuous functions. Piecewise linear (PWL) functions are a convenient way to achieve this. PWL functions can be modeled in mathematical problems using only linear and integer variables. Moreover, there is a computational benefit in using PWL functions that have the least possible number of segments. This work proposes a novel hierarchical mixed integer linear programming (MILP) formulation that identifies a continuous PWL approximation with minimum number of linear segments for a given target maximum error. The proposed MILP formulation also identifies the solution with the least maximum error among the solutions with minimum number of segments. Then, this work proposes a fast iterative algorithm that identifies non necessarily continuous PWL approximations by solving O(S log N) linear programming (LP) problems, where N is the number of data points and S is the minimum number of segments in the non necessarily continuous case. This work demonstrates that tight bounds for the MILP problem can be derived from these approximations. Next, a fast algorithm is introduced to transform a non necessarily continuous PWL approximation into a continuous one. Finally, the tight bounds and the continuous PWL approximations are used to tighten and warm start the MILP problem. The tightened formulation is shown in experimental results to be more efficient, especially for large data sets, with a solution time that is up to two orders of magnitude less than the existing literature.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

High-precision quantum algorithms for partial differential equations

Quantum computers can produce a quantum encoding of the solution of a system of differential equations exponentially faster than a classical algorithm can produce an explicit description. However, while high-precision quantum algorithms for linear ordinary differential equations are well established, the best previous quantum algorithms for linear partial differential equations (PDEs) have complexity poly(1/ϵ), where ϵ is the error tolerance. By developing quantum algorithms based on adaptive-order finite difference methods and spectral methods, we improve the complexity of quantum algorithms for linear PDEs to be poly(d,log(1/ϵ)), where d is the spatial dimension. Our algorithms apply high-precision quantum linear system algorithms to systems whose condition numbers and approximation errors we bound. We develop a finite difference algorithm for the Poisson equation and a spectral algorithm for more general second-order elliptic equations.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1995

An approach to the development of numerical algorithms for first order linear hyperbolic systems in multiple space dimensions: The constant coefficient case

Two methods for developing high order single step explicit algorithms on symmetric stencils with data on only one time level are presented. Examples are given for the convection and linearized Euler equations with up to the eighth order accuracy in both space and time in one space dimension, and up to the sixth in two space dimensions. The method of characteristics is generalized to nondiagonalizable hyperbolic systems by using exact local polynominal solutions of the system, and the resulting exact propagator methods automatically incorporate the correct multidimensional wave propagation dynamics. Multivariate Taylor or Cauchy-Kowaleskaya expansions are also used to develop algorithms. Both of these methods can be applied to obtain algorithms of arbitrarily high order for hyperbolic systems in multiple space dimensions. Cross derivatives are included in the local approximations used to develop the algorithms in this paper in order to obtain high order accuracy, and improved isotropy and stability. Efficiency in meeting global error bounds is an important criterion for evaluating algorithms, and the higher order algorithms are shown to be up to several orders of magnitude more efficient even though they are more complex. Stable high order boundary conditions for the linearized Euler equations are developed in one space dimension, and demonstrated in two space dimensions.

Goodrich, John W.↗
NASA NTRS2001

Gamma-Weighted Discrete Ordinate Two-Stream Approximation for Computation of Domain Averaged Solar Irradiance

An algorithm is developed for the gamma-weighted discrete ordinate two-stream approximation that computes profiles of domain-averaged shortwave irradiances for horizontally inhomogeneous cloudy atmospheres. The algorithm assumes that frequency distributions of cloud optical depth at unresolved scales can be represented by a gamma distribution though it neglects net horizontal transport of radiation. This algorithm is an alternative to the one used in earlier studies that adopted the adding method. At present, only overcast cloudy layers are permitted.

Kato, S.↗
DOE OSTI2021

A persistent adjoint method with dynamic time-scaling and an application to mass action kinetics

In this article, we consider an optimization problem where the objective function is evaluated at the fixed-point of a contraction mapping parameterized by a control variable, and optimization takes place over this control variable. Since the derivative of the fixed-point with respect to the parameter can usually not be evaluated exactly, an adjoint dynamical system can be used to estimate gradients. Using this estimation procedure, the optimization algorithm alternates between derivative estimation and an approximate gradient descent step. We analyze a variant of this approach involving dynamic time-scaling, where after each parameter update the adjoint system is iterated until a convergence threshold is passed. Here, we prove that, under certain conditions, the algorithm can find approximate stationary points of the objective function. We demonstrate the approach in the settings of an inverse problem in chemical kinetics, and learning in attractor networks.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Large-scale harmonic balance simulations with Krylov subspace and preconditioner recycling

The multi-harmonic balance method combined with numerical continuation provides an efficient framework to compute a family of time-periodic solutions, or response curves, for large-scale, nonlinear mechanical systems. The predictor and corrector steps repeatedly solve a sequence of linear systems that scale by the model size and number of harmonics in the assumed Fourier series approximation. In this paper, a novel Newton–Krylov iterative method is embedded within the multi-harmonic balance and continuation algorithm to efficiently compute the approximate solutions from the sequence of linear systems that arise during the prediction and correction steps. Further, the method recycles, or reuses, both the preconditioner and the Krylov subspace generated by previous linear systems in the solution sequence. A delayed frequency preconditioner refactorizes the preconditioner only when the performance of the iterative solver deteriorates. The GCRO-DR iterative solver recycles a subset of harmonic Ritz vectors to initialize the solution subspace for the next linear system in the sequence. The performance of the iterative solver is demonstrated on two exemplars with contact-type nonlinearities and benchmarked against a direct solver with traditional Newton–Raphson iterations.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Proof-of-concept of a reinforcement learning framework for wind farm energy capture maximization in time-varying wind

Here, we present a proof-of-concept distributed reinforcement learning framework for wind farm energy capture maximization. The algorithm we propose uses Q-Learning in a wake-delayed wind farm environment and considers time-varying, though not yet fully turbulent, wind inflow conditions. These algorithm modifications are used to create the Gradient Approximation with Reinforcement Learning and Incremental Comparison (GARLIC) framework for optimizing wind farm energy capture in time-varying conditions, which is then compared to the FLOw Redirection and Induction in Steady State (FLORIS) static lookup table wind farm controller baseline.

17 WIND ENERGY↗
DOE OSTI2025

Asymptotic errors in adiabatic evolution

The adiabatic theorem in quantum mechanics implies that if a system is in a discrete eigenstate of a Hamiltonian and the Hamiltonian evolves in time arbitrarily slowly, the system will remain in the corresponding eigenstate of the evolved Hamiltonian. Understanding corrections to the adiabatic result that arise when the evolution of the Hamiltonian is slow—but not arbitrarily slow—has become increasingly important, especially since adiabatic evolution has been proposed as a method of state preparation in quantum computing. Here, this paper identifies two regimes, an adiabatic regime in which corrections are generically small and can depend on details of the evolution throughout the path, and a hyperadiabatic regime in which the error is given by a form similar to an asymptotic expansion in the inverse of the evolution time with the coefficients depending principally on the behavior at the endpoints. However, the error in this hyperadiabatic regime is neither given by a true asymptotic series nor solely dependent on the endpoints: the coefficients combine the contributions from both endpoints, with relative phase factors that depend on the average spectral gaps along the trajectory, multiplied by the evolution time. The central result of this paper is to identify a quantity, referred to as the typical error, which is obtained by appropriately averaging the error over evolution times that are small compared to the evolution time itself. This typical error is characterized by an asymptotic series and depends solely on the endpoints of the evolution, remaining independent of the details of the intermediate evolution.

adiabatic approximation↗
DOE OSTI2020

Block Krylov Subspace Methods for Functions of Matrices II: Modified Block FOM

We analyze an expansion of the generalized block Krylov subspace framework of [Electron. Trans. Numer. Anal., 47 (2017), pp. 100--126]. This expansion allows the use of low-rank modifications of the matrix projected onto the block Krylov subspace and contains, as special cases, the block GMRES method and the new block Radau--Arnoldi method. Within this general setting, we present results that extend the interpolation property from the nonblock case to a matrix polynomial interpolation property for the block case, and we relate the eigenvalues of the projected matrix to the latent roots of these matrix polynomials. Some error bounds for these modified block FOM methods for solving linear systems are presented. We then show how cospatial residuals can be preserved in the case of families of shifted linear block systems. This result is used to derive computationally practical restarted algorithms for block Krylov approximations that compute the action of a matrix function on a set of several vectors simultaneously. Finally, we prove some error bounds and present numerical results showing that two modifications of FOM, the block harmonic and the block Radau--Arnoldi methods for matrix functions, can significantly improve the convergence behavior.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Case Study: NREL Campus Chilled Water Storage Potential: Benchmark Datasets Development and Applications, Task 4 - Use Case Demonstration

The Benchmark Datasets Development and Applications project is a three-year collaboration between the National Renewable Energy Laboratory (NREL), Oak Ridge National Laboratory, Pacific Northwest National Laboratory, and Lawrence Berkeley National Laboratory. The project seeks to collect and curate high-resolution, well-calibrated time series of building operational and indoor/outdoor environmental data, which are crucial to understanding and optimizing building energy efficiency performance and demand flexibility capabilities as well as benchmarking energy algorithms. Project outcomes include approximately twelve high-fidelity building datasets, enhanced data representation tools, and four case studies to illustrate example applications. The goal of these case studies is to define and execute analyses that demonstrate how one or more datasets collected through this project can address a data gap or challenge historically faced by building stakeholders. This technical paper summarizes the findings of one of these case studies, in which we studied the operational efficiencies of the central cooling system at NREL. We looked at three years of data from the three chillers in the Field Test Laboratory Building (FTLB), from 2019 to 2021, to compare equipment operation and demand throughout the time period. Our analysis indicates that all three chillers are operating at or below the optimal loading conditions for most of the operation time, and thus there was no efficiency drop due to loading of the chillers at full capacity. Our recommendation is that no chiller capacity increase is needed; instead, the central plant could benefit from adopting advanced control logics for optimal sequencing of chillers during part load operations. Analysis of adding chilled water thermal storage to the central plant indicated 34% savings in demand cost and 24.5% savings in total cost (energy consumption and demand charge cost). The payback period is estimated to be 11-22 years with an assumed TES cost of $\$$100-$200 per ton. This case study shows how a selected dataset is used to solve a practical building problem - learning the operational status of its components, analyzing the effectiveness of a proposed new technique, and aiding decision-making for the building operations and maintenance team.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗