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 271 records · Page 15

Quantum Monte Carlo estimation of complex-time correlations for the study of the ground-state dynamic structure function

We present a method based on the path integral Monte Carlo formalism for the calculation of ground-state time correlation functions in quantum systems. The key point of the method is the consideration of time as a complex variable whose phase δ acts as an adjustable parameter. By using high-order approximations for the quantum propagator, it is possible to obtain Monte Carlo data all the way from purely imaginary time to δ values near the limit of real time. As a consequence, it is possible to infer accurately the spectral functions using simple inversion algorithms. We test this approach in the calculation of the dynamic structure function S(q, ω) of two one-dimensional model systems, harmonic and quartic oscillators, for which S(q, ω) can be exactly calculated. We notice a clear improvement in the calculation of the dynamic response with respect to the common approach based on the inverse Laplace transform of the imaginary-time correlation function.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Double sweep preconditioner for optimized Schwarz methods applied to the Helmholtz problem

This paper presents a preconditioner for non-overlapping Schwarz methods applied to the Helmholtz problem. Starting from a simple analytic example, we show how such a preconditioner can be designed by approximating the inverse of the iteration operator for a layered partitioning of the domain. The preconditioner works by propagating information globally by concurrently sweeping in both directions over the subdomains, and can be interpreted as a coarse grid for the domain decomposition method. The resulting algorithm is shown to converge very fast, independently of the number of subdomains and frequency. The preconditioner has the advantage that, like the original Schwarz algorithm, it can be implemented as a matrix-free routine, with no additional preprocessing.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Attosecond Streaking Enables the Measurement of Quantum Phase

Attosecond streaking, as a measurement technique, was originally conceived as a means to characterize attosecond light pulses, which is a good approximation if the relevant transition matrix elements are approximately constant within the bandwidth of the light pulse. Our analysis of attosecond streaking measurements on systems with a complex response to the photoionizing pulse reveals the relation between the momentum-space wave function of the outgoing electron and the result of conventional retrieval algorithms. This finding enables the measurement of the quantum phase associated with bound-continuum transitions.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Quench dynamics in SRF cavities: can we locate the quench origin with 2nd sound?

A newly developed method of locating quenches in SRF cavities by detecting second-sound waves has been gaining popularity in SRF laboratories. The technique is based on measurements of time delays between the quench as determined by the RF system and arrival of the second-sound wave to the multiple detectors placed around the cavity in superfluid helium. Unlike multi-channel temperature mapping, this approach requires only a few sensors and simple readout electronics; it can be used with SRF cavities of almost arbitrary shape. One of its drawbacks is that being an indirect method it requires one to solve an inverse problem to find the location of a quench. We tried to solve this inverse problem by using a parametric forward model. By analyzing the data we found that the approximation where the second-sound emitter is a near-singular source does not describe the physical system well enough. A time-dependent analysis of the quench process can help us to put forward a more adequate model. We present here our current algorithm to solve the inverse problem and discuss the experimental results.

43 PARTICLE ACCELERATORS↗

ADDITIVE SELF-HELICITY AS A KINK MODE THRESHOLD

In this paper, we propose that additive self-helicity, introduced by Longcope and Malanushenko, plays a role in the kink instability for complex equilibria, similar to twist helicity for thin flux tubes. We support this hypothesis by a calculation of additive self-helicity of a twisted flux tube from the simulation of Fan and Gibson. As more twist gets introduced, the additive self-helicity increases, and the kink instability of the tube coincides with the drop of additive self-helicity, after the latter reaches the value of H{sub A} /{phi}{sup 2} {approx} 1.5 (where {phi} is the flux of the tube and H{sub A} is the additive self-helicity). We compare the additive self-helicity to twist for a thin subportion of the tube to illustrate that H{sub A} /{phi}{sup 2} is equal to the twist number, studied by Berger and Field, when the thin flux tube approximation is applicable. We suggest that the quantity H{sub A} /{phi}{sup 2} could be treated as a generalization of a twist number, when the thin flux tube approximation is not applicable. A threshold on a generalized twist number might prove extremely useful studying complex equilibria, just as the twist number itself has proven useful studying idealized thin flux tubes. We explicitly describe a numerical method for calculating additive self-helicity, which includes an algorithm for identifying a domain occupied by a flux bundle and a method of calculating potential magnetic field confined to this domain. We also describe a numerical method to calculate twist of a thin flux tube, using a frame parallelly transported along the axis of the tube.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

On low-rank updates to the singular value and Tucker decompositions

The singular value decomposition is widely used in signal processing and data mining. Since the data often arrives in a stream, the problem of updating matrix decompositions under low-rank modification has been widely studied. Brand developed a technique in 2006 that has many advantages. However, the technique does not directly approximate the updated matrix, but rather its previous low-rank approximation added to the new update, which needs justification. Further, the technique is still too slow for large information processing problems. We show that the technique minimizes the change in error per update, so if the error is small initially it remains small. We show that an updating algorithm for large sparse matrices should be sub-linear in the matrix dimension in order to be practical for large problems, and demonstrate a simple modification to the original technique that meets the requirements.

99 GENERAL AND MISCELLANEOUS↗

Back-and-forth approximation as a simple neutron transport model - 14607

The back-and-forth approximation is a very simple neutron transport model that helps get a number of exact solutions which qualitatively describe the actual characteristics of planar, cylindrical and spherical systems with fissile material. The model allows its absolutely accurate implementation in Monte Carlo codes and can be used to test the algorithms which do not treat geometry or interaction data. (author)

42 ENGINEERING↗

Ultra-Scale Computing for Emergency Evacuation

Emergency evacuations are carried out in anticipation of a disaster such as hurricane landfall or flooding, and in response to a disaster that strikes without a warning. Existing emergency evacuation modeling and simulation tools are primarily designed for evacuation planning and are of limited value in operational support for real time evacuation management. In order to align with desktop computing, these models reduce the data and computational complexities through simple approximations and representations of real network conditions and traffic behaviors, which rarely represent real-world scenarios. With the emergence of high resolution physiographic, demographic, and socioeconomic data and supercomputing platforms, it is possible to develop micro-simulation based emergency evacuation models that can foster development of novel algorithms for human behavior and traffic assignments, and can simulate evacuation of millions of people over a large geographic area. However, such advances in evacuation modeling and simulations demand computational capacity beyond the desktop scales and can be supported by high performance computing platforms. This paper explores the motivation and feasibility of ultra-scale computing for increasing the speed of high resolution emergency evacuation simulations.

99 GENERAL AND MISCELLANEOUS↗

A New Hybrid Quantum-Classical Algorithm for Solving the Unit Commitment Problem

Solving problems related to planning and operations of large-scale power systems is challenging on classical computers due to their inherent nature as mixed-integer and nonlinear problems. Quantum computing provides new avenues to approach these problems. We develop a hybrid quantum-classical algorithm for the Unit Commitment (UC) problem in power systems which aims at minimizing the total cost while optimally allocating generating units to meet the hourly demand of the power loads. The hybrid algorithm combines a variational quantum algorithm (VQA) with a classical Benders-type heuristic. The resulting algorithm computes approximate solutions to UC in three stages: i) a collection of UC vectors capable meeting the power demand with lowest possible operating costs is generated based on VQA; ii) a classical sequential least squares programming (SLSQP) routine is leveraged to find the optimal power level corresponding to a predetermined number of candidate vectors; iii) in the last stage, the approximate solution of UC along with generating units power level combination is given. To demonstrate the effectiveness of the presented method, three different systems with 3 generating units, 10 generating units, and 26 generating units were tested for different time periods. In addition, convergence of the hybrid quantum-classical algorithm for select time periods is proven out on IonQ's Forte system.

Aboumrad, Willie [IonQ, Inc]↗

PADÉ APPROXIMANTS FOR THE EQUATION OF STATE FOR RELATIVISTIC HYDRODYNAMICS BY KINETIC THEORY

A two-point Padé approximant (TPPA) algorithm is developed for the equation of state (EOS) for relativistic hydrodynamic systems, which are described by the classical Maxwell–Boltzmann statistics and the semiclassical Fermi–Dirac statistics with complete degeneracy. The underlying rational function is determined by the ratios of the macroscopic state variables with various orders of accuracy taken at the extreme relativistic limits. The nonunique TPPAs are validated by Taub's inequality for the consistency of the kinetic theory and the special theory of relativity. The proposed TPPA is utilized in deriving the EOS of the dilute gas and in calculating the specific heat capacity, the adiabatic index function, and the isentropic sound speed of the ideal gas. Some general guidelines are provided for the application of an arbitrary accuracy requirement. The superiority of the proposed TPPA is manifested in manipulating the constituent polynomials of the approximants, which avoids the arithmetic complexity of struggling with the modified Bessel functions and the hyperbolic trigonometric functions arising from the relativistic kinetic theory.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Expectation propagation for nonlinear inverse problems – with an application to electrical impedance tomography

In this paper, we study a fast approximate inference method based on expectation propagation for exploring the posterior probability distribution arising from the Bayesian formulation of nonlinear inverse problems. It is capable of efficiently delivering reliable estimates of the posterior mean and covariance, thereby providing an inverse solution together with quantified uncertainties. Some theoretical properties of the iterative algorithm are discussed, and the efficient implementation for an important class of problems of projection type is described. The method is illustrated with one typical nonlinear inverse problem, electrical impedance tomography with complete electrode model, under sparsity constraints. Numerical results for real experimental data are presented, and compared with that by Markov chain Monte Carlo. The results indicate that the method is accurate and computationally very efficient.

97 MATHEMATICS AND COMPUTING↗

Electron transfer dynamics: Zusman equation versus exact theory

The Zusman equation has been widely used to study the effect of solvent dynamics on electron transfer reactions. However, application of this equation is limited by the classical treatment of the nuclear degrees of freedom. In this paper, we revisit the Zusman equation in the framework of the exact hierarchical equations of motion formalism, and show that a high temperature approximation of the hierarchical theory is equivalent to the Zusman equation in describing electron transfer dynamics. Thus the exact hierarchical formalism naturally extends the Zusman equation to include quantum nuclear dynamics at low temperatures. This new finding has also inspired us to rescale the original hierarchical equations and incorporate a filtering algorithm to efficiently propagate the hierarchical equations. Numerical exact results are also presented for the electron transfer reaction dynamics and rate constant calculations.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

A mixed quantum-classical Liouville study of the population dynamics in a model photo-induced condensed phase electron transfer reaction

We apply two approximate solutions of the quantum-classical Liouville equation (QCLE) in the mapping representation to the simulation of the laser-induced response of a quantum subsystem coupled to a classical environment. These solutions, known as the Poisson Bracket Mapping Equation (PBME) and the Forward-Backward (FB) trajectory solutions, involve simple algorithms in which the dynamics of both the quantum and classical degrees of freedom are described in terms of continuous variables, as opposed to standard surface-hopping solutions in which the classical degrees of freedom hop between potential energy surfaces dictated by the discrete adiabatic state of the quantum subsystem. The validity of these QCLE-based solutions is tested on a non-trivial electron transfer model involving more than two quantum states, a time-dependent Hamiltonian, strong subsystem-bath coupling, and an initial energy shift between the donor and acceptor states that depends on the strength of the subsystem-bath coupling. In particular, we calculate the time-dependent population of the photoexcited donor state in response to an ultrafast, on-resonance pump pulse in a three-state model of an electron transfer complex that is coupled asymmetrically to a bath of harmonic oscillators through the optically dark acceptor state. Within this approach, the three-state electron transfer complex is treated quantum mechanically, while the bath oscillators are treated classically. When compared to the more accurate QCLE-based surface-hopping solution and to the numerically exact quantum results, we find that the PBME solution is not capable of qualitatively capturing the population dynamics, whereas the FB solution is. However, when the subsystem-bath coupling is decreased (which also decreases the initial energy shift between the donor and acceptor states) or the initial shift is removed altogether, both the PBME and FB results agree better with the QCLE-based surface-hopping results. These findings highlight the challenges posed by various conditions such as a time-dependent external field, the strength of the subsystem-bath coupling, and the degree of asymmetry on the accuracy of the PBME and FB algorithms.

74 ATOMIC AND MOLECULAR PHYSICS↗

A Preconditioned Low-Rank Projection Method with a Rank-Reduction Scheme for Stochastic Partial Differential Equations

Herein, we consider the numerical solution of large systems of linear equations obtained from the stochastic Galerkin formulation of stochastic partial differential equations. We propose an iterative algorithm that exploits the Kronecker product structure of the linear systems. The proposed algorithm efficiently approximates the solutions in low-rank tensor format. Using standard Krylov subspace methods for the data in tensor format is computationally prohibitive due to the rapid growth of tensor ranks during the iterations. To keep tensor ranks low over the entire iteration process, we devise a rank-reduction scheme that can be combined with the iterative algorithm. The proposed rank-reduction scheme identifies an important subspace in the stochastic domain and compresses tensors of high rank on-the-fly during the iterations. The proposed reduction scheme is a coarse-grid method in that the important subspace can be identified inexpensively in a coarse spatial grid setting. The efficiency of the present method is displayed by numerical experiments on benchmark problems.

97 MATHEMATICS AND COMPUTING↗

A Note on Euler Approximations for Stochastic Differential Equations with Delay

An existence and uniqueness theorem for a class of stochastic delay differential equations is presented, and the convergence of Euler approximations for these equations is proved under general conditions. Moreover, the rate of almost sure convergence is obtained under local Lipschitz and also under monotonicity conditions.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Laser-plasma interactions with a Fourier-Bessel particle-in-cell method

A new spectral particle-in-cell (PIC) method for plasma modeling is presented and discussed. In the proposed scheme, the Fourier-Bessel transform is used to translate the Maxwell equations to the quasi-cylindrical spectral domain. In this domain, the equations are solved analytically in time, and the spatial derivatives are approximated with high accuracy. In contrast to the finite-difference time domain (FDTD) methods, that are used commonly in PIC, the developed method does not produce numerical dispersion and does not involve grid staggering for the electric and magnetic fields. These features are especially valuable in modeling the wakefield acceleration of particles in plasmas. The proposed algorithm is implemented in the code PLARES-PIC, and the test simulations of laser plasma interactions are compared to the ones done with the quasi-cylindrical FDTD PIC code CALDER-CIRC.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

Multi-qubit entanglement and algorithms on a neutral-atom quantum computer

Gate model quantum computers promise to solve currently intractable computational problems if they can be operated at scale with long coherence times and high fidelity logic. Neutral atom hyperfine qubits provide inherent scalability due to their identical characteristics, long coherence times, and ability to be trapped in dense multi-dimensional arrays. Combined with the strong entangling interactions provided by Rydberg states, all the necessary characteristics for quantum computation are available. Here we demonstrate several quantum algorithms on a programmable gate model neutral atom quantum computer in an architecture based on individual addressing of single atoms with tightly focused optical beams scanned across a two-dimensional array of qubits. Preparation of entangled Greenberger-Horne-Zeilinger (GHZ) states with up to 6 qubits, quantum phase estimation for a chemistry problem, and the Quantum Approximate Optimization Algorithm (QAOA) for the MaxCut graph problem are demonstrated. These results highlight the emergent capability of neutral atom qubit arrays for universal, programmable quantum computation, as well as preparation of non-classical states of use for quantum enhanced sensing.

97 MATHEMATICS AND COMPUTING↗

Distributed approximate minimal Steiner trees with millions of seed vertices on billion-edge graphs

In this report, we present a parallel 2-approximation Steiner minimal tree algorithm and its MPI-based distributed implementation. In place of expensive distance computations between all pairs of seed vertices, the solution we employ exploits a cheaper Voronoi cell computation. Our design leverages asynchronous processing and message prioritization to accelerate convergence of distance computations, and harnesses vertex and edge centric processing to offer fast time-to-solution. We demonstrate scalability and performance using real-world graphs with up to 128 billion edges and 512 compute nodes, and show the ability to find Steiner trees with up to one million seed vertices. Using 12 data instances, we present comparison with the state-of-the-art exact solver, SCIP-Jack, and two sequential 2-approximate algorithms. We empirically show that, on average, the total distance of the Steiner tree identified by our solution is 1.1290 times greater than the Steiner minimal tree – well within the theoretical approximation bound of 2.

97 MATHEMATICS AND COMPUTING↗