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 595 records · Page 33

Optimizing wind farm siting to reduce power system impacts of wind variability

We introduce and solve two variants of a biobjective optimization model to reduce the negative impact of wind variability on the power system by strategically locating wind farms. The first model variant considers average changes in wind power over time; the second captures extreme fluctuations in wind power. A complementary set of wind sites is selected with the aim of minimizing both residual demand and the variability in residual demand. Because exact optimization is computationally intensive, we develop two heuristics—forward and backward greedy algorithms—to find approximate solutions. The results are compared with the exact optimization results for a well-selected subset of the data as well as to the results from selecting sites based on average wind alone. The two models are solved using demand data and potential wind sites for the Southwest Power Pool. Though both objectives can be improved by adding more sites, for a fixed number of sites, minimizing residual demand and variability in residual demand are competing objectives. Here, we find an approximate efficient frontier to compare trade-offs between the two objectives. We also vary the parameter in the heuristic that controls how the two objectives are prioritized. For the case study, the backward greedy algorithm is more effective at reducing the wind power variability than the forward greedy algorithm. Furthermore, using the backward algorithm for the full dataset is more effective than solving the exact optimization on a subset of the data when the results are evaluated using the full dataset.

17 WIND ENERGY↗

Quantum Local Search with the Quantum Alternating Operator Ansatz

We present a new hybrid, local search algorithm for quantum approximate optimization of constrained combinatorial optimization problems. We focus on the Maximum Independent Set problem and demonstrate the ability of quantum local search to solve large problem instances on quantum devices with few qubits. This hybrid algorithm iteratively finds independent sets over carefully constructed neighborhoods and combines these solutions to obtain a global solution. We study the performance of this algorithm on 3-regular, Community, and Erdős-Rényi graphs with up to 100 nodes.

Tomesh, Teague↗

Sparsity of the electron repulsion integral tensor using different localized virtual orbital representations in local second-order Møller–Plesset theory

Utilizing localized orbitals, local correlation theory can reduce the unphysically high system-size scaling of post-Hartree–Fock (post-HF) methods to linear scaling in insulating molecules. The sparsity of the four-index electron repulsion integral (ERI) tensor is central to achieving this reduction. For second-order Møller–Plesset theory (MP2), one of the simplest post-HF methods, only the (ia|jb) ERIs are needed, coupling occupied orbitals i, j and virtuals a, b. In this paper, we compare the numerical sparsity (called the “ragged list”) and two other approaches revealing the low-rank sparsity of the ERI. The ragged list requires only one set of (localized) virtual orbitals, and we find that the orthogonal valence virtual-hard virtual set of virtuals originally proposed by Subotnik et al. gives the sparsest ERI tensor. To further compress the ERI tensor, the pair natural orbital (PNO) type representation uses different sets of virtual orbitals for different occupied orbital pairs, while the occupied-specific virtual (OSV) approach uses different virtuals for each occupied orbital. Here, our results indicate that while the low-rank PNO representation achieves significant rank reduction, it also requires more memory than the ragged list. The OSV approach requires similar memory to that of the ragged list, but it involves greater algorithmic complexity. An approximation (called the “fixed sparsity pattern”) for solving the local MP2 equations using the numerically sparse ERI tensor is proposed and tested to be sufficiently accurate and to have highly controllable error. A low-scaling local MP2 algorithm based on the ragged list and the fixed sparsity pattern is therefore promising.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Compressible Flow Toolbox

The Compressible Flow Toolbox is primarily a MATLAB-language implementation of a set of algorithms that solve approximately 280 linear and nonlinear classical equations for compressible flow. The toolbox is useful for analysis of one-dimensional steady flow with either constant entropy, friction, heat transfer, or Mach number greater than 1. The toolbox also contains algorithms for comparing and validating the equation-solving algorithms against solutions previously published in open literature. The classical equations solved by the Compressible Flow Toolbox are as follows: The isentropic-flow equations, The Fanno flow equations (pertaining to flow of an ideal gas in a pipe with friction), The Rayleigh flow equations (pertaining to frictionless flow of an ideal gas, with heat transfer, in a pipe of constant cross section), The normal-shock equations, The oblique-shock equations, and The expansion equations.

Melcher, Kevin J.↗

Extending the eigCG algorithm to non-symmetric linear systems with multiple right-hand sides

For Hermitian positive definite linear systems and eigenvalue problems, the eigCG algorithm is a memory efficient algorithm that solves the linear system and simultaneously computes some of its eigenvalues. The algorithm is based on the Conjugate-Gradient (CG) algorithm, however, it uses only a window of the vectors generated by the CG algorithm to compute approximate eigenvalues. The number and accuracy of the eigenvectors can be increased by solving more right-hand sides. For Hermitian systems with multiple right-hand sides, the computed eigenvectors can be used to speed up the solution of subsequent systems. The algorithm was tested on Lattice QCD problems by solving the normal equations and was shown to give large speed up factors and to remove the critical slowing down as we approach light quark masses. Here, an extension to the non-symmetric case based on the two-sided Lanczos algorithm is given. The new algorithm is tested on Lattice QCD problems and is shown to give promising results. We also study the removal of the critical slowing down and compare results with those of the eigCG algorithm. We also discuss the case when the system is gamma5-Hermitian.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Configuring Airspace Sectors with Approximate Dynamic Programming

In response to changing traffic and staffing conditions, supervisors dynamically configure airspace sectors by assigning them to control positions. A finite horizon airspace sector configuration problem models this supervisor decision. The problem is to select an airspace configuration at each time step while considering a workload cost, a reconfiguration cost, and a constraint on the number of control positions at each time step. Three algorithms for this problem are proposed and evaluated: a myopic heuristic, an exact dynamic programming algorithm, and a rollouts approximate dynamic programming algorithm. On problem instances from current operations with only dozens of possible configurations, an exact dynamic programming solution gives the optimal cost value. The rollouts algorithm achieves costs within 2% of optimal for these instances, on average. For larger problem instances that are representative of future operations and have thousands of possible configurations, excessive computation time prohibits the use of exact dynamic programming. On such problem instances, the rollouts algorithm reduces the cost achieved by the heuristic by more than 15% on average with an acceptable computation time.

Bloem, Michael↗

Exact Reconstruction From Uniformly Attenuated Helical Cone-Beam Projections in SPECT

In recent years the development of cone-beam reconstruction algorithms has been an active research area in x-ray computed tomography (CT), and significant progress has been made in the advancement of algorithms. Theoretically exact and computationally efficient analytical algorithms can be found in the literature. However, in single photon emission computed tomography (SPECT), published cone-beam reconstruction algorithms are either approximate or involve iterative methods. The SPECT reconstruction problem is more complicated due to degradations in the imaging detection process, one of which is the effect of attenuation of gamma ray photons. Attenuation should be compensated for to obtain quantitative results. In this paper, an analytical reconstruction algorithm for uniformly attenuated cone-beam projection data is presented for SPECT imaging. The algorithm adopts the DBH method, a procedure consisting of differentiation and backprojection followed by a finite inverse cosh-weighted Hilbert transform. The significance of the proposed approach is that a selected region of interest can be reconstructed even with a detector with a reduced field of view. The algorithm is designed for a general trajectory. However, to validate the algorithm, a numerical study was performed using a helical trajectory. The implementation is efficient and the simulation result is promising.

62 RADIOLOGY AND NUCLEAR MEDICINE↗

Improving underwater localization accuracy with machine learning

Machine learning classification and regression algorithms were applied to calibrate the localization errors of a time-difference-of-arrival (TDOA)-based acoustic sensor array used for tracking salmon passage through a hydroelectric dam on the Snake River, Washington, USA. The locations of stationary and mobile acoustic tags were first tracked using the approximate maximum likelihood algorithm. Next, ensembles of classification trees successfully identified and filtered data points with large localization errors. This prefiltering step allowed the creation of a machine-learned regression model function, which decreased the median distance error by 50% for the stationary tracks and by 34% for the mobile tracks. It also extended the previous range of sub-meter localization accuracy from 100 m to 250 m horizontal distance from the dam face (the receivers). Median distance errors in the depth direction were especially decreased, falling from 0.49 m to 0.04 m in the stationary tracks and from 0.38 m to 0.07 m in the mobile tracks. These methods would have application to the calibration of error in any TDOA-based sensor network with a steady environment and array configuration.

47 OTHER INSTRUMENTATION↗

Programmatic Advantages of Linear Equivalent Seismic Models

Underground explosions nonlinearly deform the surrounding earth material and can interact with the free surface to produce spall. However, at typical seismological observation distances the seismic wavefield can be accurately modeled using linear approximations. Although nonlinear algorithms can accurately simulate very near field ground motions, they are computationally expensive and potentially unnecessary for far field wave simulations. Conversely, linearized seismic wave propagation codes are orders of magnitude faster computationally and can accurately simulate the wavefield out to typical observational distances. Thus, devising a means of approximating a nonlinear source in terms of a linear equivalent source would be advantageous both for scenario modeling and for interpretation of seismic source models that are based on linear, far-field approximations. This allows fast linear seismic modeling that still incorporates many features of the nonlinear source mechanics built into the simulation results so that one can have many of the advantages of both types of simulations without the computational cost of the nonlinear computation. In this report we first show the computational advantage of using linear equivalent models, and then discuss how the near-source (within the nonlinear wavefield regime) environment affects linear source equivalents and how well we can fit seismic wavefields derived from nonlinear sources.

58 GEOSCIENCES↗

Simultaneous Mass Determination for Gravitationally Coupled Asteroids

The conventional least-squares asteroid mass determination algorithm allows us to solve for the mass of a large subject asteroid that is perturbing the trajectory of a smaller test asteroid. However, this algorithm is necessarily a first approximation, ignoring the possibility that the subject asteroid may itself be perturbed by the test asteroid, or that the encounter’s precise geometry may be entangled with encounters involving other asteroids. After reviewing the conventional algorithm, we use it to calculate the masses of 30 main-belt asteroids. Compared to our previous results, we find new mass estimates for eight asteroids (11 Parthenope, 27 Euterpe, 51 Neimausa, 76 Freia, 121 Hermione, 324 Bamberga, 476 Hedwig, and 532 Herculina) and significantly more precise estimates for six others (2 Pallas, 3 Juno, 4 Vesta, 9 Metis, 16 Psyche, and 88 Thisbe). However, we also find that the conventional algorithm yields questionable results in several gravitationally coupled cases. To address such cases, we describe a new algorithm that allows the epoch state vectors of the subject asteroids to be included as solve-for parameters, allowing for the simultaneous solution of the masses and epoch state vectors of multiple subject and test asteroids. We then apply this algorithm to the same 30 main-belt asteroids and conclude that mass determinations resulting from current and future high-precision astrometric sources (such as Gaia ) should conduct a thorough search for possible gravitational couplings and account for their effects.

79 ASTRONOMY AND ASTROPHYSICS↗

Classical Simulation of Boson Sampling Based on Graph Structure

Boson sampling is a fundamentally and practically important task that can be used to demonstrate quantum supremacy using noisy intermediate-scale quantum devices. In this Letter, we present classical sampling algorithms for single-photon and Gaussian input states that take advantage of a graph structure of a linear-optical circuit. The algorithms’ complexity grows as so-called treewidth, which is closely related to the connectivity of a given linear-optical circuit. Using the algorithms, we study approximated simulations for local Haar-random linear-optical circuits. For equally spaced initial sources, we show that, when the circuit depth is less than the quadratic in the lattice spacing, the efficient simulation is possible with an exponentially small error. Notably, right after this depth, photons start to interfere each other and the algorithms’ complexity becomes subexponential in the number of sources, implying that there is a sharp transition of its complexity. Finally, when a circuit is sufficiently deep enough for photons to typically propagate to all modes, the complexity becomes exponential as generic sampling algorithms. We numerically implement a likelihood test with a recent Gaussian boson sampling experiment and show that the treewidth-based algorithm with a limited treewidth renders a larger likelihood than the experimental data.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗

EMGeo 3.0

EMGeo 3.0 an algorithm that improves both the computational capabilities of joint 3D electromagnetic, EM and magnetotelluric and acoustic seismic wavefield simulation and inverse modeling. This seismic wavefield module requires that data be transformed first to the Laplace-Fourier Domain before processing. The inverse modeling is based upon non-liner conjugated gradients and 3D finite differences approximations of the seismic, EM and MT wavefields. Improved modeling efficiencies are obtain by separating the modeling grid from the simulation grid. This grid separation method allows for treatment of very large data sets and imaging volumes. Further computational efficiency is obtained by combining different levels of parallezation using the Message Passing Interface (MPI). Bound constraints are employed in the imaging process to insure stability. Additional acceleration of the inverse modeling is achieved by preconditioning the conjugate gradient optimizer using an approximate Hessian. The algorithm includes improved capabilities to accurately treat models that exhibit transverse anisotropy in the electrical conductivity. However, the seismic acoustic velocity is assumed to be isotropic. Models exhibiting topography and bathymetry can be treated. The software also includes a set of pre and post processing tools for designing input model meshes and data plotting.

Gregory Newman, Michael Commer↗

Universal construction of controlled-unitary gates using dynamical decoupling and the quantum Zeno effect

We present two new algorithms that universally construct a quantum circuit approximating a controlled-U(t) up to a global phase factor of U(t), denoted by Λ{sub θ}U(t), where U(t) = e{sup −iHt} is the unitary evolution operator of an unknown Hamiltonian H of the system, and is given as a black box with tunable parameter t. We show that it is possible to approximately construct Λ{sub θ}U(t) with arbitrarily high accuracy. This algorithm is based on the dynamical decoupling effect [1]. If another black box consisting of a time-inverted version of U(t), namely U(−t), is also available we can implement Λ{sub θ}U(t) exactly with arbitrarily high success probability. This algorithm is based on the quantum Zeno effect.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Stochastic Simplex Approximate Gradient for Robust Life-cycle Production Optimization: Applied to Brugge Field

In oil and gas production industry, production optimization is a viable technique to maximize the oil/gas production or net present value (NPV). Robust optimization is one type of production optimization techniques where the geological uncertainty of reservoir is considered. When well operating conditions, e.g., well flow rates and bottom-hole pressures, are the optimization variables, ensemble-based optimization (EnOpt) is the most popular ensemble-based algorithm for robust life-cycle production optimization. Recently, however, a superior algorithm, stochastic simplex approximate gradient (StoSAG), was proposed. Finally, the purpose of this study is to provide a theoretical discussion on why StoSAG is generally superior to EnOpt and provide reasonable example (Brugge field) where StoSAG generates estimates of optimal well controls that give a life-cycle net present value (NPV) significantly higher than the NPV obtained from EnOpt.

02 PETROLEUM↗

CO 2 water-alternating-gas injection for enhanced oil recovery: Optimal well controls and half-cycle lengths

We report that CO 2 water-alternating-gas (WAG) injection is an enhanced oil recovery method designed to improve sweep efficiency during CO 2 injection with the injected water to control the mobility of CO 2 and to stabilize the gas front. Optimization of CO 2 -WAG injection is widely regarded as a viable technique for controlling the CO 2 and oil miscible process. Poor recovery from CO 2 -WAG injection can be caused by inappropriately designed WAG parameters. In previous study (Chen and Reynolds, 2016), we proposed an algorithm to optimize the well controls which maximize the life-cycle net-present-value (NPV). However, the effect of injection half-cycle lengths for each injector on oil recovery or NPV has not been well investigated. In this paper, an optimization framework based on augmented Lagrangian method and the newly developed stochastic-simplex-approximate-gradient (StoSAG) algorithm is proposed to explore the possibility of simultaneous optimization of the WAG half-cycle lengths together with the well controls. Finally, the proposed framework is demonstrated with three reservoir examples.

42 ENGINEERING↗