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 289 records · Page 16

A Model-Free No-arbitrage Price Bound for Variance Options

We suggest a numerical approximation for an optimization problem, motivated by its applications in finance to find the model-free no-arbitrage bound of variance options given the marginal distributions of the underlying asset. A first approximation restricts the computation to a bounded domain. Then we propose a gradient projection algorithm together with the finite difference scheme to solve the optimization problem. We prove the general convergence, and derive some convergence rate estimates. Finally, we give some numerical examples to test the efficiency of the algorithm.

97 MATHEMATICS AND COMPUTING↗

Multistart algorithm for identifying all optima of nonconvex stochastic functions

Here, we propose a multistart algorithm to identify all local minima of a constrained, nonconvex stochastic optimization problem. The algorithm uniformly samples points in the domain and then starts a local stochastic optimization run from any point that is the "probabilistically best" point in its neighborhood. Under certain conditions, our algorithm is shown to asymptotically identify all local optima with high probability; this holds even though our algorithm is shown to almost surely start only finitely many local stochastic optimization runs. We demonstrate the performance of an implementation of our algorithm on nonconvex stochastic optimization problems, including identifying optimal variational parameters for the quantum approximate optimization algorithm.

97 MATHEMATICS AND COMPUTING↗

Stable Difference Schemes for the Neutron Transport Equation

The initial boundary value problem for the neutron transport equation is considered. The first and second orders of accuracy difference schemes for the approximate solution of this problem are presented. In applications, the stability estimates for solutions of difference schemes for the approximate solution of the neutron transport equation are obtained. Numerical techniques are developed and algorithms are tested on an example in MATLAB.

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗

First order nonadiabatic coupling matrix elements between excited states: Implementation and application at the TD-DFT and pp-TDA levels

The recently proposed rigorous yet abstract theory of first order nonadiabatic coupling matrix elements (fo-NACME) between electronically excited states [Z. Li and W. Liu, J. Chem. Phys. 141, 014110 (2014)] is specified in detail for two widely used models: The time-dependent density functional theory and the particle-particle Tamm-Dancoff approximation. The actual implementation employs a Lagrangian formalism with atomic-orbital based direct algorithms, which makes the computation of fo-NACME very similar to that of excited-state gradients. Although the methods have great potential in investigating internal conversions and nonadiabatic dynamics between excited states of large molecules, only prototypical systems as a first pilot application are considered here to illustrate some conceptual aspects.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Grover-QAOA for 3-SAT: quadratic speedup, fair-sampling, and parameter clustering

Abstract The SAT problem is a prototypical NP-complete problem of fundamental importance in computational complexity theory with many applications in science and engineering; as such, it has long served as an essential benchmark for classical and quantum algorithms. This study shows numerical evidence for a quadratic speedup of the Grover Quantum Approximate Optimization Algorithm (G-QAOA) over random sampling for finding all solutions to 3-SAT (All-SAT) and Max-SAT problems. G-QAOA is less resource-intensive and more adaptable for these problems than Grover’s algorithm, and it surpasses conventional QAOA in its ability to sample all solutions. We show these benefits by classical simulations of many-round G-QAOA on thousands of random 3-SAT instances. We also observe G-QAOA advantages on the IonQ Aria quantum computer for small instances, finding that current hardware suffices to determine and sample all solutions. Interestingly, a single-angle-pair constraint that uses the same pair of angles at each G-QAOA round greatly reduces the classical computational overhead of optimizing the G-QAOA angles while preserving its quadratic speedup. We also find parameter clustering of the angles. The single-angle-pair protocol and parameter clustering significantly reduce obstacles to classical optimization of the G-QAOA angles.

Zhang, Zewen (ORCID:000000032258613X)↗

An Adaptive Derivative-based Method for Function Approximation

To alleviate the high computational cost of large-scale multi-physics simulations to study the relationships between the model parameters and the outputs of interest, response surfaces are often used in place of the exact functional relationships. This report explores a method for response surface construction using adaptive sampling guided by derivative information at each selected sample point. This method is especially suitable for applications that can readily provide added information such as gradients and Hessian with respect to the input parameters under study. When higher order terms (third and above) in the Taylor series are negligible, the approximation error for this method can be controlled. We present details of the adaptive algorithm and numerical results on a few test problems.

99 GENERAL AND MISCELLANEOUS↗

Improved local linearization algorithm for solving the quaternion equations

The objective of this paper is to develop a new and more accurate local linearization algorithm for numerically solving sets of linear time-varying differential equations. Of special interest is the application of this algorithm to the quaternion rate equations. The results are compared, both analytically and experimentally, with previous results using local linearization methods. The new algorithm requires approximately one-third more calculations per step than the previously developed local linearization algorithm; however, this disadvantage could be reduced by using parallel implementation. For some cases the new algorithm yields significant improvement in accuracy, even with an enlarged sampling interval. The reverse is true in other cases. The errors depend on the values of angular velocity, angular acceleration, and integration step size. One important result is that for the worst case the new algorithm can guarantee eigenvalues nearer the region of stability than can the previously developed algorithm.

Yen, K.↗

A Monte Carlo algorithm for degenerate plasmas

A procedure for performing Monte Carlo calculations of plasmas with an arbitrary level of degeneracy is outlined. It has possible applications in inertial confinement fusion and astrophysics. Degenerate particles are initialised according to the Fermi–Dirac distribution function, and scattering is via a Pauli blocked binary collision approximation. The algorithm is tested against degenerate electron–ion equilibration, and the degenerate resistivity transport coefficient from unmagnetised first order transport theory. The code is applied to the cold fuel shell and alpha particle equilibration problem of inertial confinement fusion.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

Quantum approximate optimization of the long-range Ising model with a trapped-ion quantum simulator

Quantum computers and simulators may offer significant advantages over their classical counterparts, providing insights into quantum many-body systems and possibly improving performance for solving exponentially hard problems, such as optimization and satisfiability. Here, we report the implementation of a low-depth Quantum Approximate Optimization Algorithm (QAOA) using an analog quantum simulator. We estimate the ground-state energy of the Transverse Field Ising Model with long-range interactions with tunable range, and we optimize the corresponding combinatorial classical problem by sampling the QAOA output with high-fidelity, single-shot, individual qubit measurements. We execute the algorithm with both an exhaustive search and closed-loop optimization of the variational parameters, approximating the ground-state energy with up to 40 trapped-ion qubits. We benchmark the experiment with bootstrapping heuristic methods scaling polynomially with the system size. We observe, in agreement with numerics, that the QAOA performance does not degrade significantly as we scale up the system size and that the runtime is approximately independent from the number of qubits. We finally give a comprehensive analysis of the errors occurring in our system, a crucial step in the path forward toward the application of the QAOA to more general problem instances.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Sparse approximation of fitting surface by elastic net

The goal of this paper is to develop a computational model and corresponding efficient algorithm for obtaining a sparse representation of the fitting surface to the given scattered data. The basic idea of the model is to utilize the principal shift invariant space and the balanced l{sub 1},l{sub 2} norm minimization (named elastic net). The elastic net can be solved efficiently by an adapted split Bregman iteration algorithm. Numerical experiments indicate that by choosing appropriate regularization parameters, the model can efficiently provide an acceptable compromise between the minimization of the data mismatch term and the sparsity of the solution.

97 MATHEMATICS AND COMPUTING↗

A study of differentiation errors in large-eddy simulations based on the EDQNM theory

This paper is concerned with the investigation of numerical errors in large-eddy simulations by means of two-point turbulence modeling. Based on the eddy-damped quasi-normal Markovian (EDQNM) theory, a stochastic model is developed in order to predict the time evolution of the kinetic energy spectrum obtained by a large-eddy simulation (LES), including the effects of the numerics. Using this framework, the influence of the accuracy of the approximate space differencing schemes on LES quality is studied, for decaying homogeneous isotropic incompressible turbulence, with Reynolds numbers Re{sub {lambda}} based on the transverse Taylor scale equal to 780, 2500 and 8000. The results show that the discretization of the filtered Navier-Stokes equations leads to differentiation and aliasing errors. Error spectra are also presented, and indicate that the numerical errors are mainly originating from the approximate differentiation. In addition, increasing the order of accuracy of the differencing schemes or using algorithms optimized in the Fourier space is found to widen the range of well-resolved scales. Unfortunately, for all the schemes, the smaller scales with wavenumbers close to the grid cut-off wavenumber, are badly calculated and generate differentiation errors over the whole energy spectrum. The eventual use of explicit filtering to remove spurious motions with short wavelength is finally shown to significantly improve LES accuracy.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Coulomb correlation effects in LaFeAsO: An LDA + DMFT(QMC) study

Effects of Coulomb correlation on the LaFeAsO electronic structure are investigated by the LDA + DMFT(QMC) method (combination of the local density approximation with the dynamic mean-field theory; impurity solver is a quantum Monte Carlo algorithm). The calculation results show that LaFeAsO is in the regime of intermediate correlation strength with a significant part of the spectral density moved from the Fermi energy to the Hubbard bands and far from the edge of the metal-insulator transition. Correlations affect iron d-orbitals differently. The t{sub 2g} states (xz, yz and x{sup 2} - y{sup 2} orbitals) have a higher energy due to crystal field splitting and are nearly half-filled. Their spectral functions have a pseudogap with the Fermi level position on the higher subband slope. The lower energy e{sub g} set (xy and 3z{sup 2} - r{sup 2} orbitals) have occupancies significantly larger than 1/2 with typically metallic spectral functions.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Stochastic approximation methods-Powerful tools for simulation and optimization: A survey of some recent work on multi-agent systems and cyber-physical systems

Stochastic approximation methods have found extensive and diversified applications. Recent emergence of networked systems and cyber-physical systems has generated renewed interest in advancing stochastic approximation into a general framework to support algorithm development for information processing and decisions in such systems. This paper presents a survey on some recent developments in stochastic approximation methods and their applications. Using connected vehicles in platoon formation and coordination as a platform, we highlight some traditional and new methodologies of stochastic approximation algorithms and explain how they can be used to capture essential features in networked systems. Distinct features of networked systems with randomly switching topologies, dynamically evolving parameters, and unknown delays are presented, and control strategies are provided.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

A continuation multilevel Monte Carlo algorithm

Here, we propose a novel Continuation Multi Level Monte Carlo (CMLMC) algorithm for weak approximation of stochastic models. The CMLMC algorithm solves the given approximation problem for a sequence of decreasing tolerances, ending when the required error tolerance is satisfied. CMLMC assumes discretization hierarchies that are defined a priori for each level and are geometrically refined across levels. Moreover, the actual choice of computational work across levels is based on parametric models for the average cost per sample and the corresponding variance and weak error. These parameters are calibrated using Bayesian estimation, taking particular notice of the deepest levels of the discretization hierarchy, where only few realizations are available to produce the estimates. The resulting CMLMC estimator exhibits a non-trivial splitting between bias and statistical contributions. We also show the asymptotic normality of the statistical error in the MLMC estimator and justify in this way our error estimate that allows prescribing both required accuracy and confidence in the final result. Our numerical results substantiate the above results and illustrate the corresponding computational savings in examples that are described in terms of differential equations either driven by random measures or with random coefficients.

97 MATHEMATICS AND COMPUTING↗

Optimal Estimation Framework for Ocean Color Atmospheric Correction and Pixel-level Uncertainty Quantification

Ocean color remote sensing requires compensation for atmospheric scattering and absorption (aerosol, Rayleigh, and trace gases), referred to as atmospheric correction (AC). AC allows inference of parameters such as spectrally resolved remote sensing reflectance ( R rs )(λ) ; sr 1 ) at the ocean surface from the top-of-atmosphere reflectance. Often, the uncertainty of this process is not fully explored. Bayesian inference techniques provide a simultaneous AC and uncertainty assessment via a full posterior distribution of the relevant variables, given the prior distribution of those variables and the radiative transfer (RT) likelihood function. Given uncertainties in the algorithm inputs, the Bayesian framework enables better constraints on the AC process by using the complete spectral information compared to traditional approaches that use only a subset of bands for AC. This paper investigates a Bayesian inference research method (Optimal Estimation, OE) for ocean color AC by simultaneously retrieving atmospheric and ocean properties using all visible and near-infrared spectral bands. The OE algorithm analytically approximates the posterior distribution of parameters based on normality assumptions and provides a potentially viable operational algorithm with a reduced computational expense. We developed a Neural Network (NN) RT forward model look-up-table-based emulator to increase algorithm efficiency further and thus speed up the likelihood computations. We then applied the OE algorithm to synthetic data and observations from the MODerate resolution Imaging Spectroradiometer (MODIS) on NASA’s Aqua spacecraft. We compared the R rs )(λ) retrieval and its uncertainty estimates from the OE method with in-situ validation data from the SeaWiFS Bio-optical Archive and Storage System (SeaBASS) and Aerosol Robotic Network Ocean Color (AERONET-OC) datasets. The OE algorithm improved R rs )(λ) estimates relative to the NASA standard operational algorithm by improving all statistical metrics at 443, 555, and 667 nm. Unphysical negative R rs )(λ) , which often appear in complex water conditions, was reduced by a factor of 3. The OE-derived pixel-level R rs )(λ) uncertainty estimates were also assessed relative to in-situ data and were shown to have skill.

Atmospheric correction↗

Quantum Complexity of the Kronecker Coefficients

Whether or not the Kronecker coefficients of the symmetric group count some set of combinatorial objects is a longstanding open question. In this work we show that a given Kronecker coefficient is proportional to the rank of a projector that can be measured efficiently using a quantum computer. In other words a Kronecker coefficient counts the dimension of the vector space spanned by the accepting witnesses of a QMA verifier, where QMA is the quantum analogue of NP . This implies that approximating the Kronecker coefficients to within a given relative error is not harder than a certain natural class of problems that captures the complexity of estimating thermal properties of quantum many-body systems. A second consequence is that deciding positivity of Kronecker coefficients is contained in QMA , complementing a recent NP -hardness result of Ikenmeyer, Mulmuley, and Walter. We obtain similar results for the related problem of approximating row sums of the character table of the symmetric group. Finally, we discuss an efficient quantum algorithm that approximates normalized Kronecker coefficients to inverse-polynomial additive error. Published by the American Physical Society 2024

Physics↗

Optimization Algorithms as Quantum Performance Benchmarks

Combinatorial optimization is anticipated to be one of the primary use cases for quantum computation in the coming years. The Quantum Approximate Optimization Algorithm (QAOA) and Quantum Annealing (QA) have the potential to demonstrate significant run-time performance benefits over current state-of-the-art solutions. Using existing methods for characterizing classical optimization algorithms, we analyze solution quality obtained by solving Max-Cut problems using a quantum annealing device and gate-model quantum simulators and devices. This is used to guide the development of an advanced benchmarking framework for quantum computers designed to evaluate the trade-off between run-time execution performance and the solution quality for iterative hybrid quantum-classical applications. The framework generates performance profiles through effective visualizations that show performance progression as a function of time for various problem sizes and illustrates algorithm limitations uncovered by the benchmarking approach. The framework is an enhancement to the existing open-source QED-C Application-Oriented Benchmark suite and can connect to the open-source analysis libraries. The suite can be executed on various quantum simulators and quantum hardware systems.

benchmarking↗