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 415 records · Page 23
All sourcesNASA NTRSDOE OSTI
DOE OSTI2022

Krylov subspace recycling for evolving structures

Krylov subspace recycling is a powerful tool when solving a long series of large, sparse linear systems that change only slowly over time. In PDE constrained shape optimization, these series appear naturally, as typically hundreds or thousands of optimization steps are needed with only small changes in the geometry. In this setting, however, applying Krylov subspace recycling can be a difficult task. As the geometry evolves, in general, so does the finite element mesh defined on or representing this geometry, including the numbers of nodes and elements and element connectivity. This is especially the case if re-meshing techniques are used. As a result, the number of algebraic degrees of freedom in the system changes, and in general the linear system matrices resulting from the finite element discretization change size from one optimization step to the next. Changes in the mesh connectivity also lead to structural changes in the matrices. In the case of re-meshing, even if the geometry changes only a little, the corresponding mesh might differ substantially from the previous one. Obviously, this prevents any straightforward mapping of the approximate invariant subspace of the linear system matrix (the focus of recycling in this work) from one optimization step to the next; similar problems arise for other selected subspaces. In this paper, we present an algorithm to map an approximate invariant subspace of the linear system matrix for the previous optimization step to an approximate invariant subspace of the linear system matrix for the current optimization step, for general meshes. This is achieved by exploiting the map from coefficient vectors to finite element functions on the mesh, combined with interpolation or approximation of functions on the finite element mesh. We demonstrate the effectiveness of our approach numerically with several proof of concept studies for a specific meshing technique.

42 ENGINEERING↗
NASA NTRS1973

Algorithms for changing the step size

Approximately ten different ways for changing the step size used by multistep methods are enumerated, and their good and bad features are compared. More efficient algorithms are given for the difference formulations of a frequently used halving and doubling process, and a cure for the instability inherent in this halving process is proposed.

Krogh, F. T.↗
DOE OSTI2024

nuclear-score-maximization v1.0

This software library presents efficient and multithreaded implementations of matrix low rank approximation via column selection in C++17 code. The algorithms are described in Fornace, Mark, and Michael Lindsey. "Column and row subset selection using nuclear scores: algorithms and theory for Nystro m approximation, CUR decomposition, and graph Laplacian reduction." arXiv preprint arXiv:2407.01698 (2024). The presented methods are by-and-large ver novel, have provable approximation guarantees, multiple use-cases, and exhibit higher quality approximations on a variety of studied examples.

Fornace, Mark↗
NASA NTRS1986

Sensitivity analysis and approximation methods for general eigenvalue problems

Optimization of dynamic systems involving complex non-hermitian matrices is often computationally expensive. Major contributors to the computational expense are the sensitivity analysis and reanalysis of a modified design. The present work seeks to alleviate this computational burden by identifying efficient sensitivity analysis and approximate reanalysis methods. For the algebraic eigenvalue problem involving non-hermitian matrices, algorithms for sensitivity analysis and approximate reanalysis are classified, compared and evaluated for efficiency and accuracy. Proper eigenvector normalization is discussed. An improved method for calculating derivatives of eigenvectors is proposed based on a more rational normalization condition and taking advantage of matrix sparsity. Important numerical aspects of this method are also discussed. To alleviate the problem of reanalysis, various approximation methods for eigenvalues are proposed and evaluated. Linear and quadratic approximations are based directly on the Taylor series. Several approximation methods are developed based on the generalized Rayleigh quotient for the eigenvalue problem. Approximation methods based on trace theorem give high accuracy without needing any derivatives. Operation counts for the computation of the approximations are given. General recommendations are made for the selection of appropriate approximation technique as a function of the matrix size, number of design variables, number of eigenvalues of interest and the number of design points at which approximation is sought.

Murthy, D. V.↗
DOE OSTI2024

Statistical mechanical model for crack growth

Analytic relations that describe crack growth are vital for modeling experiments and building a theoretical understanding of fracture. Upon constructing an idealized model system for the crack and applying the principles of statistical thermodynamics, it is possible to formulate the rate of thermally activated crack growth as a function of load, but the result is analytically intractable. In this report an asymptotically correct theory is used to obtain analytic approximations of the crack growth rate from the fundamental theoretical formulation. These crack growth rate relations are compared to those that exist in the literature and are validated with respect to Monte Carlo calculations and experiments. The success of this approach is encouraging for future modeling endeavors that might consider more complicated fracture mechanisms, such as inhomogeneity or a reactive environment.

36 MATERIALS SCIENCE↗
DOE OSTI2024

Rapidly convergent quantum Monte Carlo using a Chebyshev projector

The multireference coupled-cluster Monte Carlo (MR-CCMC) algorithm is a determinant-based quantum Monte Carlo (QMC) algorithm that is conceptually similar to Full Configuration Interaction QMC (FCIQMC). It has been shown to offer a balanced treatment of both static and dynamic correlation while retaining polynomial scaling, although application to large systems with significant strong correlation remained impractical. In this paper, we document recent algorithmic advances that enable rapid convergence and a more black-box approach to the multireference problem. These include a logarithmically scaling metric-tree-based excitation acceptance algorithm to search for determinants connected to the reference space at the desired excitation level and a symmetry-screening procedure for the reference space. We show that, for moderately sized reference spaces, the new search algorithm brings about an approximately 8-fold acceleration of one MR-CCMC iteration, while the symmetry screening procedure reduces the number of active reference space determinants with essentially no loss of accuracy. We also introduce a stochastic implementation of an approximate wall projector, which is the infinite imaginary time limit of the exponential projector, using a truncated expansion of the wall function in Chebyshev polynomials. Notably, this wall-Chebyshev projector can be used to accelerate any projector-based QMC algorithm. We show that it requires significantly fewer applications of the Hamiltonian to achieve the same statistical convergence. We benchmark these acceleration methods on the beryllium and carbon dimers, using initiator FCIQMC and MR-CCMC with basis sets up to cc-pVQZ quality.

Zhao, Zijun↗
NASA NTRS2016

The Sensitivity of SeaWiFS Ocean Color Retrievals to Aerosol Amount and Type

As atmospheric reflectance dominates top-of-the-atmosphere radiance over ocean, atmospheric correction is a critical component of ocean color retrievals. This paper explores the operational Sea-viewing Wide Field-of-View Sensor (SeaWiFS) algorithm atmospheric correction with approximately 13 000 coincident surface-based aerosol measurements. Aerosol optical depth at 440 nm (AOD(sub 440)) is overestimated for AOD below approximately 0.1-0.15 and is increasingly underestimated at higher AOD; also, single-scattering albedo (SSA) appears overestimated when the actual value less than approximately 0.96.AOD(sub 440) and its spectral slope tend to be overestimated preferentially for coarse-mode particles. Sensitivity analysis shows that changes in these factors lead to systematic differences in derived ocean water-leaving reflectance (Rrs) at 440 nm. The standard SeaWiFS algorithm compensates for AOD anomalies in the presence of nonabsorbing, medium-size-dominated aerosols. However, at low AOD and with absorbing aerosols, in situ observations and previous case studies demonstrate that retrieved Rrs is sensitive to spectral AOD and possibly also SSA anomalies. Stratifying the dataset by aerosol-type proxies shows the dependence of the AOD anomaly and resulting Rrs patterns on aerosol type, though the correlation with the SSA anomaly is too subtle to be quantified with these data. Retrieved chlorophyll-a concentrations (Chl) are affected in a complex way by Rrs differences, and these effects occur preferentially at high and low Chl values. Absorbing aerosol effects are likely to be most important over biologically productive waters near coasts and along major aerosol transport pathways. These results suggest that future ocean color spacecraft missions aiming to cover the range of naturally occurring and anthropogenic aerosols, especially at wavelengths shorter than 440 nm, will require better aerosol amount and type constraints.

single scattering albedo↗
DOE OSTI2021

Distributed and communication-efficient solutions to linear equations with special sparse structure

In this paper we report two distributed and communication-efficient algorithms based on the multi-agent system are proposed to solve a system of linear equations with the Laplacian sparse system matrix. One algorithm is based on the gradient descent method in optimization. In this algorithm, the agents only share partial information instead of all of their collective state vectors to save significant communication. The other algorithm is obtained by approximating Newton’s method for a faster convergence rate. Although it requires twice as much communication as the first one, it is still communication-efficient given the low dimension of the information shared among agents. The convergence at a linear rate is proved for both algorithms, and a comprehensive comparison of their convergence rate, communication burden, and computation costs is also performed. The proposed algorithms can be applied to various systems to solve those problems that can be modeled as a system of linear equations with a Laplacian sparse system matrix. Simulation results with the electric power system illustrate their effectiveness.

42 ENGINEERING↗
NASA NTRS1980

Dual methods and approximation concepts in structural synthesis

Approximation concepts and dual method algorithms are combined to create a method for minimum weight design of structural systems. Approximation concepts convert the basic mathematical programming statement of the structural synthesis problem into a sequence of explicit primal problems of separable form. These problems are solved by constructing explicit dual functions, which are maximized subject to nonnegativity constraints on the dual variables. It is shown that the joining together of approximation concepts and dual methods can be viewed as a generalized optimality criteria approach. The dual method is successfully extended to deal with pure discrete and mixed continuous-discrete design variable problems. The power of the method presented is illustrated with numerical results for example problems, including a metallic swept wing and a thin delta wing with fiber composite skins.

Fleury, C.↗
NASA NTRS1987

Vectorizable implicit algorithms for the flux-difference split, three-dimensional Navier-Stokes equations

The computational efficiency of four vectorizable implicit algorithms is assessed when applied to calculate steady-state solutions to the three-dimensional, incompressible Navier-Stokes equations in general coordinates. Two of these algorithms are characterized as hybrid schemes; that is, they combine some approximate factorization in two coordinate directions with relaxation in the remaining spatial direction. The other two algorithms utilize an approximate factorization approach which yields two-factor algorithms for three-dimensional systems. All four algorithms are implemented in identical high-resolution upwind schemes for the flux-difference split Navier-Stokes equations. These highly nonlinear schemes are obtained by extending an implicit Total Variation Diminishing (TVD) scheme recently developed for linear one-dimensional systems of hyperbolic conservation laws to the three-dimensional Navier-Stokes equations. The computation of vortical flow over a sharp-edged, thin delta wing has been chosen as a common numerical test case. The convergence of the algorithms is discussed and the accuracy of the computed flow-field results is assessed. The validity of the present results are demonstrated by a comparison with experimental data.

Hartwich, P. M.↗
NASA NTRS2000

An Adaptive Buddy Check for Observational Quality Control

An adaptive buddy check algorithm is presented that adjusts tolerances for outlier observations based on the variability of surrounding data. The algorithm derives from a statistical hypothesis test combined with maximum-likelihood covariance estimation. Its stability is shown to depend on the initial identification of outliers by a simple background check. The adaptive feature ensures that the final quality control decisions are not very sensitive to prescribed statistics of first-guess and observation errors, nor on other approximations introduced into the algorithm. The implementation of the algorithm in a global atmospheric data assimilation is described. Its performance is contrasted with that of a non-adaptive buddy check, for the surface analysis of an extreme storm that took place in Europe on 27 December 1999. The adaptive algorithm allowed the inclusion of many important observations that differed greatly from the first guess and that would have been excluded on the basis of prescribed statistics. The analysis of the storm development was much improved as a result of these additional observations.

Dee, Dick P.↗
NASA NTRS2012

Application of the Marsupial Paradigm to Tropical Cyclone Formation from Northwestward-Propagating Disturbances

A wave-tracking algorithm is developed for northwestward-propagating waves that, on occasion, play a role in tropical cyclogenesis over the western oceans. To obtain the Lagrangian flow structure, the frame of reference is translated obliquely at the same propagation speed with the precursor disturbance. Trajectory analysis suggests that streamlines in the obliquely translated frame of reference can be used to approximate flow trajectories. The algorithm was applied to Super Typhoon Nakri (2008), Tropical Cyclone Erika (2009), and a few other examples. Diagnoses of meteorological analyses and satellite-derived moisture and precipitation fields show that the marsupial framework for tropical cyclogenesis in tropical easterly waves is relevant also for northwestward-propagating disturbances as are commonly observed in the tropical western Atlantic, the Gulf of Mexico, and the western North Pacific. Finally, it is suggested that analysis of the global model data and satellite observations in the marsupial framework can provide useful guidance on early tropical cyclone advisories.

Wang, Zhuo↗
NASA NTRS1979

An improved analysis/synthesis capability based on dual methods - ACCESS 3

Approximation concepts and dual method algorithms are combined to create a new method for minimum weight design of structural systems. Approximation concepts convert the basic mathematical programming statement of the structural synthesis problem into a sequence of explicit primal problems of separable form. These problems are solved by constructing explicit dual functions, which are maximized subject to nonnegativity constraints. The dual method is successfully extended to deal with pure discrete and mixed continuous-discrete design variable problems. The power of the method presented is illustrated with numerical results for example problems, including a thin delta wing with fiber composite skins.

Schmit, L. A.↗
NASA NTRS1991

Recursive Inversion By Finite-Impulse-Response Filters

Recursive approximation gives least-squares best fit to exact response. Algorithm yields finite-impulse-response approximation of unknown single-input/single-output, causal, time-invariant, linear, real system, response of which is sequence of impulses. Applicable to such system-inversion problems as suppression of echoes and identification of target from its scatter response to incident impulse.

Bach, Ralph E., Jr.↗
NASA NTRS1995

Aerodynamic parameter estimation via Fourier modulating function techniques

Parameter estimation algorithms are developed in the frequency domain for systems modeled by input/output ordinary differential equations. The approach is based on Shinbrot's method of moment functionals utilizing Fourier based modulating functions. Assuming white measurement noises for linear multivariable system models, an adaptive weighted least squares algorithm is developed which approximates a maximum likelihood estimate and cannot be biased by unknown initial or boundary conditions in the data owing to a special property attending Shinbrot-type modulating functions. Application is made to perturbation equation modeling of the longitudinal and lateral dynamics of a high performance aircraft using flight-test data. Comparative studies are included which demonstrate potential advantages of the algorithm relative to some well established techniques for parameter identification. Deterministic least squares extensions of the approach are made to the frequency transfer function identification problem for linear systems and to the parameter identification problem for a class of nonlinear-time-varying differential system models.

Pearson, A. E.↗
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↗