Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “approximation algorithms”

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 757 records · Page 42

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.↗

Approximate solutions of acoustic 3D integral equation and their application to seismic modeling and full-waveform inversion

Over the recent decades, a number of fast approximate solutions of Lippmann–Schwinger equation, which are more accurate than classic Born and Rytov approximations, were proposed in the field of electromagnetic modeling. Those developments could be naturally extended to acoustic and elastic fields; however, until recently, they were almost unknown in seismology. This paper presents several solutions of this kind applied to acoustic modeling for both lossy and lossless media. We evaluated the numerical merits of those methods and provide an estimation of their numerical complexity. In our numerical realization we use the matrix-free implementation of the corresponding integral operator. We study the accuracy of those approximate solutions and demonstrate, that the quasi-analytical approximation is more accurate, than the Born approximation. Further, we apply the quasi-analytical approximation to the solution of the inverse problem. It is demonstrated that, this approach improves the estimation of the data gradient, comparing to the Born approximation. The developed inversion algorithm is based on the conjugate-gradient type optimization. Numerical model study demonstrates that the quasi-analytical solution significantly reduces computation time of the seismic full-waveform inversion. We also show how the quasi-analytical approximation can be extended to the case of elastic wavefield.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

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↗

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↗

Matrix interdiction problem

In the matrix interdiction problem, a real-valued matrix and an integer k is given. The objective is to remove k columns such that the sum over all rows of the maximum entry in each row is minimized. This combinatorial problem is closely related to bipartite network interdiction problem which can be applied to prioritize the border checkpoints in order to minimize the probability that an adversary can successfully cross the border. After introducing the matrix interdiction problem, we will prove the problem is NP-hard, and even NP-hard to approximate with an additive n{gamma} factor for a fixed constant {gamma}. We also present an algorithm for this problem that achieves a factor of (n-k) mUltiplicative approximation ratio.

45 MILITARY TECHNOLOGY, WEAPONRY, AND NATIONAL DEF↗

Effect of Diffusion Length in Modeling of Equiaxed Dendritic Solidification under Buoyancy Flow in a Configuration of Hebditch–Hunt Experiment

Modeling of equiaxed solidification is vital for understanding the solidification process of metallic alloys. In this work, an extended literature review is given for the models currently used for equiaxed solidification simulations. Based on this analysis, we present a three-phase multiscale equiaxed solidification model in which some approximations regarding solute transport at microscopic scale are put together in a new way and incorporated into macroscopic transport equations. For the latter, a term relating to the momentum exchange between the two phases is revised, and a modification for the grain packing algorithm is proposed. A modernized model for equiaxed dendrite growth is tested using a case of solidification of Sn-5 wt pct Pb alloy in a parallelepiped cavity that mimics the Hebditch–Hunt experiment. The results obtained using two approaches to calculate diffusion length are presented and compared both with each other and with numerical results from elsewhere. It is demonstrated that diffusion length has a crucial effect on the final segregation pattern.

36 MATERIALS SCIENCE↗

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↗

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↗

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.↗

Unifying parameter estimation and the Deutsch-Jozsa algorithm for continuous variables

We reveal a close relationship between quantum metrology and the Deutsch-Jozsa algorithm on continuous-variable quantum systems. We develop a general procedure, characterized by two parameters, that unifies parameter estimation and the Deutsch-Jozsa algorithm. Depending on which parameter we keep constant, the procedure implements either the parameter-estimation protocol or the Deutsch-Jozsa algorithm. The parameter-estimation part of the procedure attains the Heisenberg limit and is therefore optimal. Due to the use of approximate normalizable continuous-variable eigenstates, the Deutsch-Jozsa algorithm is probabilistic. The procedure estimates a value of an unknown parameter and solves the Deutsch-Jozsa problem without the use of any entanglement.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Inner Approximation of Minkowski Sums: A Union-Based Approach and Applications to Aggregated Energy Resources: Preprint

This paper develops and compares algorithms to compute the inner approximation of Minkowski sum of convex polytopes. We consider flexibility from distributed re- sources, such as solar photovoltaic (PV) inverters, demand side resources, etc. A polytopic representation of a single inverter's feasible operating region is proposed first. The aggregate flexibility can be computed using the Minkowski sum. Homothet and Zonotope-based approaches have been explored in literature. We show that as heterogeneity increases, such approaches lead to conservative estimates. Hence, we show how to exploit union-based Minkowski sum computation through successive homothetic decomposition of polytopes. While the union-based approach can lead to dimensionality issues, we show how to limit the complexity by predefining a candidate set. Efficiency, accuracy and trade-offs have been analyzed. Numerical examples have been presented to illustrate the effectiveness of the proposed algorithm.

14 SOLAR ENERGY↗

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.↗

Gradient algorithm applied to laboratory quantum control

The exploration of a quantum control landscape, which is the physical observable as a function of the control variables, is fundamental for understanding the ability to perform observable optimization in the laboratory. For high control variable dimensions, trajectory-based methods provide a means for performing such systematic explorations by exploiting the measured gradient of the observable with respect to the control variables. This paper presents a practical, robust, easily implemented statistical method for obtaining the gradient on a general quantum control landscape in the presence of noise. In order to demonstrate the method's utility, the experimentally measured gradient is utilized as input in steepest-ascent trajectories on the landscapes of three model quantum control problems: spectrally filtered and integrated second harmonic generation as well as excitation of atomic rubidium. The gradient algorithm achieves efficiency gains of up to approximately three times that of the standard genetic algorithm and, as such, is a promising tool for meeting quantum control optimization goals as well as landscape analyses. The landscape trajectories directed by the gradient should aid in the continued investigation and understanding of controlled quantum phenomena.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

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.↗

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↗

Learning planar ising models

Inference and learning of graphical models are both well-studied problems in statistics and machine learning that have found many applications in science and engineering. However, exact inference is intractable in general graphical models, which suggests the problem of seeking the best approximation to a collection of random variables within some tractable family of graphical models. In this paper, we focus our attention on the class of planar Ising models, for which inference is tractable using techniques of statistical physics [Kac and Ward; Kasteleyn]. Based on these techniques and recent methods for planarity testing and planar embedding [Chrobak and Payne], we propose a simple greedy algorithm for learning the best planar Ising model to approximate an arbitrary collection of binary random variables (possibly from sample data). Given the set of all pairwise correlations among variables, we select a planar graph and optimal planar Ising model defined on this graph to best approximate that set of correlations. We present the results of numerical experiments evaluating the performance of our algorithm.

36 MATERIALS SCIENCE↗

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.↗

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.↗