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 775 records · Page 43

A Matrix Computation View of the FastMap and RobustMap Dimension Reduction Algorithms

Given a set of pairwise object distances and a dimension $k$, FastMap and RobustMap algorithms compute a set of $k$-dimensional coordinates for the objects. These metric space embedding methods implicitly assume a higher-dimensional coordinate representation and are a sequence of translations and orthogonal projections based on a sequence of object pair selections (called pivot pairs). We develop a matrix computation viewpoint of these algorithms that operates on the coordinate representation explicitly using Householder reflections. The resulting Coordinate Mapping Algorithm (CMA) is a fast approximate alternative to truncated principal component analysis (PCA) and it brings the FastMap and RobustMap algorithms into the mainstream of numerical computation where standard BLAS building blocks are used. Motivated by the geometric nature of the embedding methods, we further show that truncated PCA can be computed with CMA by specific pivot pair selections. Describing FastMap, RobustMap, and PCA as CMA computations with different pivot pair choices unifies the methods along a pivot pair selection spectrum. We also sketch connections to the semi-discrete decomposition and the QLP decomposition.

99 GENERAL AND MISCELLANEOUS↗

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

Method for calculating multiphoton above-threshold processes in atoms: Two-photon above-threshold ionization

The two-photon above-threshold ionization of atoms is calculated using numerical algorithms of the Pade approximation in the model-potential method with the Coulomb asymptotics. The total and differential cross sections of the above-threshold ionization of helium and alkali metal atoms by elliptically polarized radiation are presented. The dependence of the angular distribution of photoelectrons on the sign of the ellipticity of radiation (the elliptic dichroism phenomenon) is analyzed in the above-threshold frequency range.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

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↗

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↗

Learning algorithms for stack filter classifiers

Stack Filters define a large class of increasing filter that is used widely in image and signal processing. The motivations for using an increasing filter instead of an unconstrained filter have been described as: (1) fast and efficient implementation, (2) the relationship to mathematical morphology and (3) more precise estimation with finite sample data. This last motivation is related to methods developed in machine learning and the relationship was explored in an earlier paper. In this paper we investigate this relationship by applying Stack Filters directly to classification problems. This provides a new perspective on how monotonicity constraints can help control estimation and approximation errors, and also suggests several new learning algorithms for Boolean function classifiers when they are applied to real-valued inputs.

97 MATHEMATICS AND COMPUTING↗

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↗

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↗

DCA++: A software framework to solve correlated electron problems with modern quantum cluster methods

We present the first open release of the DCA++ project, a high-performance research software framework to solve quantum many-body problems with cutting edge quantum cluster algorithms. DCA++ implements the dynamical cluster approximation (DCA) and its DCA extension with a continuous self-energy. The algorithms capture nonlocal correlations in strongly correlated electron systems, thereby giving insight into high-$T_c$ superconductivity. The code’s scalability allows efficient usage of systems at all scales, from workstations to leadership computers. With regard to the increasing heterogeneity of modern computing machines, DCA++ provides portable performance on conventional and emerging new architectures, such as hybrid CPU–GPU, sustaining multiple petaflops on ORNL’s Titan and CSCS’ Piz Daint supercomputers. Moreover, we show how sustainable and scalable development of the code base has been achieved by adopting standard techniques of the software industry. These include employing a distributed version control system, applying test-driven development and following continuous integration.

97 MATHEMATICS AND COMPUTING↗

Coupling compositional liquid gas Darcy and free gas flows at porous and free-flow domains interface

This paper proposes an efficient splitting algorithm to solve coupled liquid gas Darcy and free gas flows at the interface between a porous medium and a free-flow domain. This model is compared to the reduced model introduced in [6] using a 1D approximation of the gas free flow. For that purpose, the gas molar fraction diffusive flux at the interface in the free-flow domain is approximated by a two point flux approximation based on a low-frequency diagonal approximation of a Steklov–Poincaré type operator. The splitting algorithm and the reduced model are applied in particular to the modelling of the mass exchanges at the interface between the storage and the ventilation galleries in radioactive waste deposits.

12 MANAGEMENT OF RADIOACTIVE AND NON-RADIOACTIVE W↗

Collaborative Project: Building improved optimized parameter estimation algorithms to improve methane and nitrogen fluxes in a climate model

Soils in natural and managed ecosystems and wetlands are well known sources of methane, nitrous oxides, and reactive nitrogen gases, but the magnitudes of gas flux to the atmosphere are still poorly constrained. Thus, the reasons for the large increases in atmospheric concentrations of methane and nitrous oxide since the preindustrial time period are not well understood. The low atmospheric concentrations of methane and nitrous oxide, despite being more potent greenhouse gases than carbon dioxide, complicate empirical studies to provide explanations. In addition to climate concerns, the emissions of reactive nitrogen gases from soils are important to the changing nitrogen balance in the earth system, subject to human management, and may change substantially in the future. Thus improved modeling of the emission fluxes of these species from the land surface is important. Currently, there are emission modules for methane and some nitrogen species in the Community Earth System Model’s Community Land Model (CLM-ME/N); however, there are large uncertainties and problems in the simulations, resulting in coarse estimates. In this proposal, we seek to improve these emission modules by combining state-of-the-art process modules for emissions, available data, and new optimization methods. In earth science problems, we often have substantial data and knowledge of processes in disparate systems, and thus we need to combine data and a general process level understanding into a model for projections of future climate that are as accurate as possible. The best methodologies for optimization of parameters in earth system models are still being developed. In this proposal we will develop and apply surrogate algorithms that a) were especially developed for computationally expensive simulations like CLM-ME/N models; b) were (in the earlier surrogate optimization Stochastic RBF) demonstrated to perform very well on computationally expensive complex partial differential equations in earth science with limited numbers of simulations; and, c) will be (as part of the proposed research) significantly improved both by adding asynchronous parallelism, early truncation of unsuccessful simulations, and the improvement of both serial and parallel performance by the use of derivative and sensitivity information from global and local surrogate approximations S(x) . The algorithm development and testing will be focused on the CLM-ME/N model application, but the methods are general and are expected to also perform well on optimization for parameter estimation of other climate models and other classes of continuous multimodal optimization problems arising from complex simulation models. In addition, this proposal will compile available datasets of emissions of methane, nitrous oxides and reactive nitrogen species and develop protocols for site level comparisons with the CLM-ME/N. Once the model parameters are optimized against site level data, the model will be simulated at the global level and compared to atmospheric concentration measurements for the current climate, and future emissions will be estimated using climate change as simulated by the CESM. This proposal combines experts in earth system modeling, optimization, computer science, and process level understanding of soil gas emissions in an interdisciplinary team in order to improve the modeling of methane and nitrogen gas emissions. This proposal thus meets the requirements of the SciDAC RFP, by integrating state-of-the-art computer science and earth system to build an improved earth system model.

54 ENVIRONMENTAL SCIENCES↗

Quantum-assisted quantum compiling

Compiling quantum algorithms for near-term quantum computers (accounting for connectivity and native gate alphabets) is a major challenge that has received significant attention both by industry and academia. Avoiding the exponential overhead of classical simulation of quantum dynamics will allow compilation of larger algorithms, and a strategy for this is to evaluate an algorithm's cost on a quantum computer. To this end, we propose a variational hybrid quantum-classical algorithm called quantum-assisted quantum compiling (QAQC). In QAQC, we use the overlap between a target unitary U and a trainable unitary V as the cost function to be evaluated on the quantum computer. More precisely, to ensure that QAQC scales well with problem size, our cost involves not only the global overlap T r ( V † U ) but also the local overlaps with respect to individual qubits. We introduce novel short-depth quantum circuits to quantify the terms in our cost function, and we prove that our cost cannot be efficiently approximated with a classical algorithm under reasonable complexity assumptions. We present both gradient-free and gradient-based approaches to minimizing this cost. As a demonstration of QAQC, we compile various one-qubit gates on IBM's and Rigetti's quantum computers into their respective native gate alphabets. Furthermore, we successfully simulate QAQC up to a problem size of 9 qubits, and these simulations highlight both the scalability of our cost function as well as the noise resilience of QAQC. Future applications of QAQC include algorithm depth compression, black-box compiling, noise mitigation, and benchmarking.

97 MATHEMATICS AND COMPUTING↗

Monte Carlo evaluation of the convolution/superposition algorithm of Hi-Art tomotherapy in heterogeneous phantoms and clinical cases

The reliability of the convolution/superposition (C/S) algorithm of the Hi-Art tomotherapy system is evaluated by using the Monte Carlo model TomoPen, which has been already validated for homogeneous phantoms. The study was performed in three stages. First, measurements with EBT Gafchromic film for a 1.25x2.5 cm{sup 2} field in a heterogeneous phantom consisting of two slabs of polystyrene separated with Styrofoam were compared to simulation results from TomoPen. The excellent agreement found in this comparison justifies the use of TomoPen as the reference for the remaining parts of this work. Second, to allow analysis and interpretation of the results in clinical cases, dose distributions calculated with TomoPen and C/S were compared for a similar phantom geometry, with multiple slabs of various densities. Even in conditions of lack of lateral electronic equilibrium, overall good agreement was obtained between C/S and TomoPen results, with deviations within 3%/2 mm, showing that the C/S algorithm accounts for modifications in secondary electron transport due to the presence of a low density medium. Finally, calculations were performed with TomoPen and C/S of dose distributions in various clinical cases, from large bilateral head and neck tumors to small lung tumors with diameter of <3 cm. To ensure a ''fair'' comparison, identical dose calculation grid and dose-volume histogram calculator were used. Very good agreement was obtained for most of the cases, with no significant differences between the DVHs obtained from both calculations. However, deviations of up to 4% for the dose received by 95% of the target volume were found for the small lung tumors. Therefore, the approximations in the C/S algorithm slightly influence the accuracy in small lung tumors even though the C/S algorithm of the tomotherapy system shows very good overall behavior.

61 RADIATION PROTECTION AND DOSIMETRY↗

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↗

Phase space barriers and dividing surfaces in the absence of critical points of the potential energy: Application to roaming in ozone

We examine the phase space structures that govern reaction dynamics in the absence of critical points on the potential energy surface. We show that in the vicinity of hyperbolic invariant tori, it is possible to define phase space dividing surfaces that are analogous to the dividing surfaces governing transition from reactants to products near a critical point of the potential energy surface. We investigate the problem of capture of an atom by a diatomic molecule and show that a normally hyperbolic invariant manifold exists at large atom-diatom distances, away from any critical points on the potential. This normally hyperbolic invariant manifold is the anchor for the construction of a dividing surface in phase space, which defines the outer or loose transition state governing capture dynamics. We present an algorithm for sampling an approximate capture dividing surface, and apply our methods to the recombination of the ozone molecule. We treat both 2 and 3 degrees of freedom models with zero total angular momentum. We have located the normally hyperbolic invariant manifold from which the orbiting (outer) transition state is constructed. This forms the basis for our analysis of trajectories for ozone in general, but with particular emphasis on the roaming trajectories.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

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↗

A line search algorithm for wind field adjustment with incomplete data and RBF approximation

The problem of concern in this work is the construction of free divergence fields given scattered horizontal components. As customary, the problem is formulated as a PDE constrained least squares problem. The novelty of our approach is to construct the so-called adjusted field, as the unique solution along an appropriately chosen descent direction. The latter is obtained by the adjoint equation technique. It is shown that the classical adjusted field of Sasaki’s is a particular case. On choosing descent directions, the underlying mass consistent model leads to the solution of an elliptic problem which is solved by means of a radial basis functions method. Finally, some numerical results for wind field adjustment are presented.

97 MATHEMATICS AND COMPUTING↗