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 559 records · Page 31

Two-Dimensional Inlet Simulation Using a Diagonal Implicit Algorithm

A modification of an implicit approximate-factorization finite-difference algorithm applied to the two-dimensional Euler and Navier-Stokes equations in general curvilinear coordinates is presented for supersonic freestream flow about and through inlets. The modification transforms the coupled system of equations Into an uncoupled diagonal form which requires less computation work. For steady-state applications the resulting diagonal algorithm retains the stability and accuracy characteristics of the original algorithm. Solutions are given for inviscid and laminar flow about a two-dimensional wedge inlet configuration. Comparisons are made between computed results and exact theory.

Chaussee, D.S.↗

Convergence of the SMI and the diagonally loaded SMI algorithms with weak interference

Approximations for the power levels at the output of an adaptive array that uses the diagonally loaded sample-matrix inversion (SMI) algorithm are derived. Diagonal loading is a technique where the diagonal of the covariance matrix is augmented with a positive or negative constant prior to inversion. This paper examines how the signal-to-interference-plus-noise ratio (SINR) and signal-to-interference ratio (SIR) at the array output vary with the number of samples taken when the input signals are CW. It is shown that positive loading produces more rapid convergence with a reduction in output SIR. Negative loading provides an improved SIR level, but positive loading produces more rapid convergence. Negative loading provides an improved SIR level, but the output power levels are erratic and slow to converge. Simulation results which verify the theoretical procedure are given.

Ganz, Matthew W.↗

Communication-Efficient Property Preservation in Tracer Transport

Atmospheric tracer transport is a computationally demanding component of the atmospheric dynamical core of weather and climate simulations. Simulations typically have tens to hundreds of tracers. A tracer field is needed to preserve several properties, including mass, shape, and tracer consistency. To improve computational efficiency, it is common to apply different spatial and temporal discretizations to the tracer transport equations than to the dynamical equations. Using different discretizations increases the difficulty of preserving properties. This paper provides a unified framework to analyze the property preservation problem and classes of algorithms to solve it. We observe the primary problem and a safety problem; describe three classes of algorithms to solve these; introduce new algorithms in two of these classes; make connections among the algorithms; analyze each algorithm in terms of correctness, bound on its solution magnitude, and its communication efficiency; and study numerical results. A new algorithm, QLT, has the smallest communication volume, and in an important case it redistributes mass approximately locally. These algorithms are only very loosely coupled to the underlying discretizations of the dynamical and tracer transport equations and thus are broadly and efficiently applicable. In addition, they may be applied to remap problems in applications other than tracer transport.

97 MATHEMATICS AND COMPUTING↗

A stochastic biomass blending problem in decentralized supply chains

Blending biomass materials of different physical or chemical properties provides an opportunity to adjust the quality of the feedstock to meet the specifications of the conversion platform. We propose a model which identifies the right mix of biomass to optimize the performance of the thermochemical conversion process at the mini-mum cost. This is a chance-constraint programming (CCP) model which takes into account the stochastic nature of biomass quality. The proposed CCP model ensures that process requirements, which are impacted by physical and chemical properties of biomass, are met most of the time. We consider two problem settings, a centralized and a decentralized supply chain. We propose a mixed-integer linear program to model the blending problem in the centralized setting and a bilevel program to model the blending problem in the decentralized setting. We use the sample average approximation method to approximate the chance constraints, and propose solution algorithms to solve this approximation. We develop a case study for South Carolina using data provided by the Billion Ton Study. Based on our results, the blends identified consist mainly of pine and softwood residues. The blends identified and the suppliers selected by both models are different. The cost of the centralized supply chain is 2%–6% lower. The implications of these results are twofold. First, these results could lead to improved collaborations in the supply chain. Second, these results provide an estimate of the approximation error from assuming centralized decision making in the supply chain.

09 BIOMASS FUELS↗

Algorithm for Compressing Time-Series Data

An algorithm based on Chebyshev polynomials effects lossy compression of time-series data or other one-dimensional data streams (e.g., spectral data) that are arranged in blocks for sequential transmission. The algorithm was developed for use in transmitting data from spacecraft scientific instruments to Earth stations. In spite of its lossy nature, the algorithm preserves the information needed for scientific analysis. The algorithm is computationally simple, yet compresses data streams by factors much greater than two. The algorithm is not restricted to spacecraft or scientific uses: it is applicable to time-series data in general. The algorithm can also be applied to general multidimensional data that have been converted to time-series data, a typical example being image data acquired by raster scanning. However, unlike most prior image-data-compression algorithms, this algorithm neither depends on nor exploits the two-dimensional spatial correlations that are generally present in images. In order to understand the essence of this compression algorithm, it is necessary to understand that the net effect of this algorithm and the associated decompression algorithm is to approximate the original stream of data as a sequence of finite series of Chebyshev polynomials. For the purpose of this algorithm, a block of data or interval of time for which a Chebyshev polynomial series is fitted to the original data is denoted a fitting interval. Chebyshev approximation has two properties that make it particularly effective for compressing serial data streams with minimal loss of scientific information: The errors associated with a Chebyshev approximation are nearly uniformly distributed over the fitting interval (this is known in the art as the "equal error property"); and the maximum deviations of the fitted Chebyshev polynomial from the original data have the smallest possible values (this is known in the art as the "min-max property").

Hawkins, S. Edward, III↗

Asymptotic-preserving dynamical low-rank method for the stiff nonlinear Boltzmann equation

In kinetic theory, numerically solving the full Boltzmann equation is extremely expensive. This is because the Boltzmann collision operator involves a high-dimensional, nonlinear integral that must be evaluated at each spatial grid point and every time step. The challenge becomes even more pronounced in the fluid (strong collisionality) regime, where the collision operator exhibits strong stiffness, causing explicit time integrators to impose severe stability restrictions. In this paper, we propose addressing this problem through a dynamical low-rank (DLR) approximation. The resulting algorithm requires evaluating the Boltzmann collision operator only r 2 times, where r, the rank of the approximation, is much smaller than the number of spatial grid points. We propose a novel DLR integrator, called the XL integrator, which reduces the number of steps compared to the available alternatives (such as the projector splitting or basis update & Galerkin (BUG) integrator). For a class of problems including the Boltzmann collision operator which enjoys a separation property between physical and velocity space, we further propose a specialized version of the XL integrator, called the sXL integrator. This version requires solving only one differential equation to update the low-rank factors. Furthermore, the proposed low-rank schemes are asymptotic-preserving, meaning they can capture the asymptotic fluid limit in the case of strong collisionality. Our numerical experiments demonstrate the efficiency and accuracy of the proposed methods across a wide range of regimes, from non-stiff (kinetic) to stiff (fluid).

97 MATHEMATICS AND COMPUTING↗

SU-F-BRF-09: A Non-Rigid Point Matching Method for Accurate Bladder Dose Summation in Cervical Cancer HDR Brachytherapy

Purpose: To propose and validate a deformable point matching scheme for surface deformation to facilitate accurate bladder dose summation for fractionated HDR cervical cancer treatment. Method: A deformable point matching scheme based on the thin plate spline robust point matching (TPSRPM) algorithm is proposed for bladder surface registration. The surface of bladders segmented from fractional CT images is extracted and discretized with triangular surface mesh. Deformation between the two bladder surfaces are obtained by matching the two meshes' vertices via the TPS-RPM algorithm, and the deformation vector fields (DVFs) characteristic of this deformation is estimated by B-spline approximation. Numerically, the algorithm is quantitatively compared with the Demons algorithm using five clinical cervical cancer cases by several metrics: vertex-to-vertex distance (VVD), Hausdorff distance (HD), percent error (PE), and conformity index (CI). Experimentally, the algorithm is validated on a balloon phantom with 12 surface fiducial markers. The balloon is inflated with different amount of water, and the displacement of fiducial markers is benchmarked as ground truth to study TPS-RPM calculated DVFs' accuracy. Results: In numerical evaluation, the mean VVD is 3.7(±2.0) mm after Demons, and 1.3(±0.9) mm after TPS-RPM. The mean HD is 14.4 mm after Demons, and 5.3mm after TPS-RPM. The mean PE is 101.7% after Demons and decreases to 18.7% after TPS-RPM. The mean CI is 0.63 after Demons, and increases to 0.90 after TPS-RPM. In the phantom study, the mean Euclidean distance of the fiducials is 7.4±3.0mm and 4.2±1.8mm after Demons and TPS-RPM, respectively. Conclusions: The bladder wall deformation is more accurate using the feature-based TPS-RPM algorithm than the intensity-based Demons algorithm, indicating that TPS-RPM has the potential for accurate bladder dose deformation and dose summation for multi-fractional cervical HDR brachytherapy. This work is supported in part by the National Natural ScienceFoundation of China (no 30970866 and no 81301940)

60 APPLIED LIFE SCIENCES↗

Approximating the Generalized Voronoi Diagram of Closely Spaced Objects

We present an algorithm to compute an approximation of the generalized Voronoi diagram (GVD) on arbitrary collections of 2D or 3D geometric objects. In particular, we focus on datasets with closely spaced objects; GVD approximation is expensive and sometimes intractable on these datasets using previous algorithms. With our approach, the GVD can be computed using commodity hardware even on datasets with many, extremely tightly packed objects. Our approach is to subdivide the space with an octree that is represented with an adjacency structure. We then use a novel adaptive distance transform to compute the distance function on octree vertices. The computed distance field is sampled more densely in areas of close object spacing, enabling robust and parallelizable GVD surface generation. We demonstrate our method on a variety of data and show example applications of the GVD in 2D and 3D.

97 MATHEMATICS AND COMPUTING↗

An approximate Riemann solver for real gas parabolized Navier-Stokes equations

Under specific assumptions, parabolized Navier-Stokes equations are a suitable mean to study channel flows. A special case is that of high pressure flow of real gases in cooling channels where large crosswise gradients of thermophysical properties occur. To solve the parabolized Navier-Stokes equations by a space marching approach, the hyperbolicity of the system of governing equations is obtained, even for very low Mach number flow, by recasting equations such that the streamwise pressure gradient is considered as a source term. For this system of equations an approximate Roe's Riemann solver is developed as the core of a Godunov type finite volume algorithm. The properties of the approximated Riemann solver, which is a modification of Roe's Riemann solver for the parabolized Navier-Stokes equations, are presented and discussed with emphasis given to its original features introduced to handle fluids governed by a generic real gas EoS. Sample solutions are obtained for low Mach number high compressible flows of transcritical methane, heated in straight long channels, to prove the solver ability to describe flows dominated by complex thermodynamic phenomena.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Nonlinear Estimation of Discrete-Time Signals Under Random Observation Delay

This paper presents an approximation to the nonlinear least-squares estimation problem of discrete-time stochastic signals using nonlinear observations with additive white noise which can be randomly delayed by one sampling time. The observation delay is modelled by a sequence of independent Bernoulli random variables whose values, zero or one, indicate that the real observation arrives on time or it is delayed and, hence, the available measurement to estimate the signal is not up-to-date. Assuming that the state-space model generating the signal is unknown and only the covariance functions of the processes involved in the observation equation are ready for use, a filtering algorithm based on linear approximations of the real observations is proposed.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

On substructuring algorithms and solution techniques for the numerical approximation of partial differential equations

Substructuring methods are in common use in mechanics problems where typically the associated linear systems of algebraic equations are positive definite. Here these methods are extended to problems which lead to nonpositive definite, nonsymmetric matrices. The extension is based on an algorithm which carries out the block Gauss elimination procedure without the need for interchanges even when a pivot matrix is singular. Examples are provided wherein the method is used in connection with finite element solutions of the stationary Stokes equations and the Helmholtz equation, and dual methods for second-order elliptic equations.

Gunzburger, M. D.↗

A Taylor weak-statement algorithm for hyperbolic conservation laws

Finite element analysis, applied to computational fluid dynamics (CFD) problem classes, presents a formal procedure for establishing the ingredients of a discrete approximation numerical solution algorithm. A classical Galerkin weak-statement formulation, formed on a Taylor series extension of the conservation law system, is developed herein that embeds a set of parameters eligible for constraint according to specification of suitable norms. The derived family of Taylor weak statements is shown to contain, as special cases, over one dozen independently derived CFD algorithms published over the past several decades for the high speed flow problem class. A theoretical analysis is completed that facilitates direct qualitative comparisons. Numerical results for definitive linear and nonlinear test problems permit direct quantitative performance comparisons.

Baker, A. J.↗

Risk-based Multiobjective Optimization Model for Bridge Maintenance Planning

Determining the optimal maintenance plan is essential for successful bridge management. The optimization objectives are defined in the forms of minimizing life-cycle cost and maximizing performance indicators. Previous bridge maintenance models assumed the process of bridge deterioration and the estimate of maintenance cost are deterministic, i.e., known with certainty. This assumption, however, is invalid especially with estimates over a long time horizon of bridge life. In this study, we consider the risks associated with bridge deterioration and maintenance cost in determining the optimal maintenance plan. The decisions variables include the strategic choice of essential maintenance (such as silane treatment and cathodic protection), and the intervals between periodic maintenance. A epsilon-constrained Particle Swarm Optimization algorithm is used to approximate the tradeoff between life-cycle cost and performance indicators. During stochastic search for optimal solutions, Monte-Carlo simulation is used to evaluate the impact of risks on the objective values, at an acceptance level of reliability. The proposed model can facilitate decision makers to select the compromised maintenance plan with a group of alternative choices, each of which leads to a different level of performance and life-cycle cost. A numerical example is used to illustrate the proposed model.

97 MATHEMATICS AND COMPUTING↗

Adaptive DFT-based Interferometer Fringe Tracking

An automatic interferometer fringe tracking system has been developed, implemented, and tested at the Infrared Optical Telescope Array (IOTA) observatory at Mt. Hopkins, Arizona. The system can minimize the optical path differences (OPDs) for all three baselines of the Michelson stellar interferometer at IOTA. Based on sliding window discrete Fourier transform (DFT) calculations that were optimized for computational efficiency and robustness to atmospheric disturbances, the algorithm has also been tested extensively on off-line data. Implemented in ANSI C on the 266 MHz PowerPC processor running the VxWorks real-time operating system, the algorithm runs in approximately 2.0 milliseconds per scan (including all three interferograms), using the science camera and piezo scanners to measure and correct the OPDs. The adaptive DFT-based tracking algorithm should be applicable to other systems where there is a need to detect or track a signal with an approximately constant-frequency carrier pulse.

Wilson, Edward↗

Differential visualisation of a spectrally selective structure of strongly scattering objects

We describe a modification of the algorithm for the fast approximate solution of the diffuse optical tomography inverse problem. In this modification the amount of a priori (auxiliary) information necessary for the visualisation of the internal structure of the object is reduced by using a differential measurement scheme. The experiment is performed at two different wavelengths, and some a priori information, necessary to reconstruct only the spectrally selective component of the internal structure (the difference structure of the spatial distributions of the extinction coefficient at the wavelength employed), is replaced by the data of one of these measurements. (laser biophotonics)

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗

Sythesis of MCMC and Belief Propagation

Markov Chain Monte Carlo (MCMC) and Belief Propagation (BP) are the most popular algorithms for computational inference in Graphical Models (GM). In principle, MCMC is an exact probabilistic method which, however, often suffers from exponentially slow mixing. In contrast, BP is a deterministic method, which is typically fast, empirically very successful, however in general lacking control of accuracy over loopy graphs. In this paper, we introduce MCMC algorithms correcting the approximation error of BP, i.e., we provide a way to compensate for BP errors via a consecutive BP-aware MCMC. Our framework is based on the Loop Calculus (LC) approach which allows to express the BP error as a sum of weighted generalized loops. Although the full series is computationally intractable, it is known that a truncated series, summing up all 2-regular loops, is computable in polynomial-time for planar pair-wise binary GMs and it also provides a highly accurate approximation empirically. Motivated by this, we first propose a polynomial-time approximation MCMC scheme for the truncated series of general (non-planar) pair-wise binary models. Our main idea here is to use the Worm algorithm, known to provide fast mixing in other (related) problems, and then design an appropriate rejection scheme to sample 2-regular loops. Furthermore, we also design an efficient rejection-free MCMC scheme for approximating the full series. The main novelty underlying our design is in utilizing the concept of cycle basis, which provides an efficient decomposition of the generalized loops. In essence, the proposed MCMC schemes run on transformed GM built upon the non-trivial BP solution, and our experiments show that this synthesis of BP and MCMC outperforms both direct MCMC and bare BP schemes.

97 MATHEMATICS AND COMPUTING↗

Ru L[subscript 2,3] XANES theoretical simulation with DFT: A test of the core-hole treatment

Density functional theory (DFT)-based relativistic calculations were performed to model the Ru L-edge X-ray absorption near edge structure (XANES) spectra of the hexaammineruthenium complex [Ru(NH{sub 3}){sub 6}]{sup 3+} and 'blue dimer' water oxidation catalyst, cis,cis- [(bpy){sub 2}(H{sub 2}O)Ru{sup III}ORu{sup III}(OH{sub 2})(bpy){sub 2}]{sup 4+} (bpy is 2,2-bipyridine). Two computational approaches were compared: simulations without the core-hole and by modeling of the core-hole within the Z+1 approximation. Good agreement between calculated and experimental XANES spectra is achieved without including the core-hole. Simulations with algorithms beyond the Z+1 approximation were only possible in a framework of the scalar relativistic treatment. Time-dependent DFT (TD-DFT) was used to compute the Ru L-edge spectrum for [Ru(NH{sub 3}){sub 6}]{sup 3+} model compound. Three different core-hole treatments were compared in a real-space full multiple scattering XANES modeling within the Green function formalism (implemented in the FEFF9.5 package) for the [Ru(Mebimpy)(bpm)(H{sub 2}O)]{sup 2+} complex. The latter approaches worked well in cases where spin-orbit treatment of relativistic effects is not required.

99 GENERAL AND MISCELLANEOUS↗

Synthesis of single-qutrit circuits from Clifford+𝑅 gates

Here, we present two deterministic compilation algorithms for single-qutrit unitaries with O ( log 1 / ɛ ) gate depth. Each algorithm selects a nearby approximation to the target unitary and then exactly synthesizes the approximation over the Clifford + R basis. The first algorithm exhaustively searches over the group; while the second algorithm searches only for Householder reflections. The exhaustive search algorithm yields an average R count of 2.193 ( 11 ) + 8.621 ( 7 ) log 10 ( 1 / ɛ ) , albeit with a time complexity of O ( ɛ − 4.4 ) . The Householder search algorithm results in a larger average R count of 3.20 ( 13 ) + 10.77 ( 3 ) log 10 ( 1 / ɛ ) at a reduced time complexity of O ( ɛ − 0.42 ) , greatly extending the reach in ɛ . These costs correspond asymptotically to 35% and 69% more non-Clifford gates compared with synthesizing the same unitary with two qubits. Such initial results are encouraging for using the R gate as the nontransversal gate for qutrit-based computation.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗