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 523 records · Page 29

Land surface model parameter optimisation using in situ flux data: comparison of gradient-based versus random search algorithms (a case study using ORCHIDEE v1.9.5.2)

Land surface models (LSMs), which form the land component of earth system models, rely on numerous processes for describing carbon, water and energy budgets, often associated with highly uncertain parameters. Data assimilation (DA) is a useful approach for optimising the most critical parameters in order to improve model accuracy and refine future climate predictions. In this study, we compare two different DA methods for optimising the parameters of seven plant functional types (PFTs) of the ORCHIDEE LSM using daily averaged eddy-covariance observations of net ecosystem exchange and latent heat flux at 78 sites across the globe. We perform a technical investigation of two classes of minimisation methods – local gradient-based (the L-BFGS-B algorithm, limited memory Broyden–Fletcher–Goldfarb–Shanno algorithm with bound constraints) and global random search (the genetic algorithm) – by evaluating their relative performance in terms of the model–data fit and the difference in retrieved parameter values. We examine the performance of each method for two cases: when optimising parameters at each site independently (“single-site” approach) and when simultaneously optimising the model at all sites for a given PFT using a common set of parameters (“multi-site” approach). We find that for the single site case the random search algorithm results in lower values of the cost function (i.e. lower model–data root mean square differences) than the gradient-based method; the difference between the two methods is smaller for the multi-site optimisation due to a smoothing of the cost function shape with a greater number of observations. The spread of the cost function, when performing the same tests with 16 random first-guess parameters, is much larger with the gradient-based method, due to the higher likelihood of being trapped in local minima. When using pseudo-observation tests, the genetic algorithm results in a closer approximation of the true posterior parameter value in the L-BFGS-B algorithm. We demonstrate the advantages and challenges of different DA techniques and provide some advice on using it for the LSM parameter optimisation.

58 GEOSCIENCES↗

Approximate solutions of acoustic 3D integral equation and their application to seismic modeling and full-waveform inversion

Over the recent decades, a number of fast approximate solutions of Lippmann–Schwinger equation, which are more accurate than classic Born and Rytov approximations, were proposed in the field of electromagnetic modeling. Those developments could be naturally extended to acoustic and elastic fields; however, until recently, they were almost unknown in seismology. This paper presents several solutions of this kind applied to acoustic modeling for both lossy and lossless media. We evaluated the numerical merits of those methods and provide an estimation of their numerical complexity. In our numerical realization we use the matrix-free implementation of the corresponding integral operator. We study the accuracy of those approximate solutions and demonstrate, that the quasi-analytical approximation is more accurate, than the Born approximation. Further, we apply the quasi-analytical approximation to the solution of the inverse problem. It is demonstrated that, this approach improves the estimation of the data gradient, comparing to the Born approximation. The developed inversion algorithm is based on the conjugate-gradient type optimization. Numerical model study demonstrates that the quasi-analytical solution significantly reduces computation time of the seismic full-waveform inversion. We also show how the quasi-analytical approximation can be extended to the case of elastic wavefield.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Statistical mechanical model for crack growth

Analytic relations that describe crack growth are vital for modeling experiments and building a theoretical understanding of fracture. Upon constructing an idealized model system for the crack and applying the principles of statistical thermodynamics, it is possible to formulate the rate of thermally activated crack growth as a function of load, but the result is analytically intractable. In this report an asymptotically correct theory is used to obtain analytic approximations of the crack growth rate from the fundamental theoretical formulation. These crack growth rate relations are compared to those that exist in the literature and are validated with respect to Monte Carlo calculations and experiments. The success of this approach is encouraging for future modeling endeavors that might consider more complicated fracture mechanisms, such as inhomogeneity or a reactive environment.

36 MATERIALS SCIENCE↗

Rapidly convergent quantum Monte Carlo using a Chebyshev projector

The multireference coupled-cluster Monte Carlo (MR-CCMC) algorithm is a determinant-based quantum Monte Carlo (QMC) algorithm that is conceptually similar to Full Configuration Interaction QMC (FCIQMC). It has been shown to offer a balanced treatment of both static and dynamic correlation while retaining polynomial scaling, although application to large systems with significant strong correlation remained impractical. In this paper, we document recent algorithmic advances that enable rapid convergence and a more black-box approach to the multireference problem. These include a logarithmically scaling metric-tree-based excitation acceptance algorithm to search for determinants connected to the reference space at the desired excitation level and a symmetry-screening procedure for the reference space. We show that, for moderately sized reference spaces, the new search algorithm brings about an approximately 8-fold acceleration of one MR-CCMC iteration, while the symmetry screening procedure reduces the number of active reference space determinants with essentially no loss of accuracy. We also introduce a stochastic implementation of an approximate wall projector, which is the infinite imaginary time limit of the exponential projector, using a truncated expansion of the wall function in Chebyshev polynomials. Notably, this wall-Chebyshev projector can be used to accelerate any projector-based QMC algorithm. We show that it requires significantly fewer applications of the Hamiltonian to achieve the same statistical convergence. We benchmark these acceleration methods on the beryllium and carbon dimers, using initiator FCIQMC and MR-CCMC with basis sets up to cc-pVQZ quality.

Zhao, Zijun↗

Matrix interdiction problem

In the matrix interdiction problem, a real-valued matrix and an integer k is given. The objective is to remove k columns such that the sum over all rows of the maximum entry in each row is minimized. This combinatorial problem is closely related to bipartite network interdiction problem which can be applied to prioritize the border checkpoints in order to minimize the probability that an adversary can successfully cross the border. After introducing the matrix interdiction problem, we will prove the problem is NP-hard, and even NP-hard to approximate with an additive n{gamma} factor for a fixed constant {gamma}. We also present an algorithm for this problem that achieves a factor of (n-k) mUltiplicative approximation ratio.

45 MILITARY TECHNOLOGY, WEAPONRY, AND NATIONAL DEF↗

Effect of Diffusion Length in Modeling of Equiaxed Dendritic Solidification under Buoyancy Flow in a Configuration of Hebditch–Hunt Experiment

Modeling of equiaxed solidification is vital for understanding the solidification process of metallic alloys. In this work, an extended literature review is given for the models currently used for equiaxed solidification simulations. Based on this analysis, we present a three-phase multiscale equiaxed solidification model in which some approximations regarding solute transport at microscopic scale are put together in a new way and incorporated into macroscopic transport equations. For the latter, a term relating to the momentum exchange between the two phases is revised, and a modification for the grain packing algorithm is proposed. A modernized model for equiaxed dendrite growth is tested using a case of solidification of Sn-5 wt pct Pb alloy in a parallelepiped cavity that mimics the Hebditch–Hunt experiment. The results obtained using two approaches to calculate diffusion length are presented and compared both with each other and with numerical results from elsewhere. It is demonstrated that diffusion length has a crucial effect on the final segregation pattern.

36 MATERIALS SCIENCE↗

Distributed and communication-efficient solutions to linear equations with special sparse structure

In this paper we report two distributed and communication-efficient algorithms based on the multi-agent system are proposed to solve a system of linear equations with the Laplacian sparse system matrix. One algorithm is based on the gradient descent method in optimization. In this algorithm, the agents only share partial information instead of all of their collective state vectors to save significant communication. The other algorithm is obtained by approximating Newton’s method for a faster convergence rate. Although it requires twice as much communication as the first one, it is still communication-efficient given the low dimension of the information shared among agents. The convergence at a linear rate is proved for both algorithms, and a comprehensive comparison of their convergence rate, communication burden, and computation costs is also performed. The proposed algorithms can be applied to various systems to solve those problems that can be modeled as a system of linear equations with a Laplacian sparse system matrix. Simulation results with the electric power system illustrate their effectiveness.

42 ENGINEERING↗

Unifying parameter estimation and the Deutsch-Jozsa algorithm for continuous variables

We reveal a close relationship between quantum metrology and the Deutsch-Jozsa algorithm on continuous-variable quantum systems. We develop a general procedure, characterized by two parameters, that unifies parameter estimation and the Deutsch-Jozsa algorithm. Depending on which parameter we keep constant, the procedure implements either the parameter-estimation protocol or the Deutsch-Jozsa algorithm. The parameter-estimation part of the procedure attains the Heisenberg limit and is therefore optimal. Due to the use of approximate normalizable continuous-variable eigenstates, the Deutsch-Jozsa algorithm is probabilistic. The procedure estimates a value of an unknown parameter and solves the Deutsch-Jozsa problem without the use of any entanglement.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Inner Approximation of Minkowski Sums: A Union-Based Approach and Applications to Aggregated Energy Resources: Preprint

This paper develops and compares algorithms to compute the inner approximation of Minkowski sum of convex polytopes. We consider flexibility from distributed re- sources, such as solar photovoltaic (PV) inverters, demand side resources, etc. A polytopic representation of a single inverter's feasible operating region is proposed first. The aggregate flexibility can be computed using the Minkowski sum. Homothet and Zonotope-based approaches have been explored in literature. We show that as heterogeneity increases, such approaches lead to conservative estimates. Hence, we show how to exploit union-based Minkowski sum computation through successive homothetic decomposition of polytopes. While the union-based approach can lead to dimensionality issues, we show how to limit the complexity by predefining a candidate set. Efficiency, accuracy and trade-offs have been analyzed. Numerical examples have been presented to illustrate the effectiveness of the proposed algorithm.

14 SOLAR ENERGY↗

Gradient algorithm applied to laboratory quantum control

The exploration of a quantum control landscape, which is the physical observable as a function of the control variables, is fundamental for understanding the ability to perform observable optimization in the laboratory. For high control variable dimensions, trajectory-based methods provide a means for performing such systematic explorations by exploiting the measured gradient of the observable with respect to the control variables. This paper presents a practical, robust, easily implemented statistical method for obtaining the gradient on a general quantum control landscape in the presence of noise. In order to demonstrate the method's utility, the experimentally measured gradient is utilized as input in steepest-ascent trajectories on the landscapes of three model quantum control problems: spectrally filtered and integrated second harmonic generation as well as excitation of atomic rubidium. The gradient algorithm achieves efficiency gains of up to approximately three times that of the standard genetic algorithm and, as such, is a promising tool for meeting quantum control optimization goals as well as landscape analyses. The landscape trajectories directed by the gradient should aid in the continued investigation and understanding of controlled quantum phenomena.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Learning planar ising models

Inference and learning of graphical models are both well-studied problems in statistics and machine learning that have found many applications in science and engineering. However, exact inference is intractable in general graphical models, which suggests the problem of seeking the best approximation to a collection of random variables within some tractable family of graphical models. In this paper, we focus our attention on the class of planar Ising models, for which inference is tractable using techniques of statistical physics [Kac and Ward; Kasteleyn]. Based on these techniques and recent methods for planarity testing and planar embedding [Chrobak and Payne], we propose a simple greedy algorithm for learning the best planar Ising model to approximate an arbitrary collection of binary random variables (possibly from sample data). Given the set of all pairwise correlations among variables, we select a planar graph and optimal planar Ising model defined on this graph to best approximate that set of correlations. We present the results of numerical experiments evaluating the performance of our algorithm.

36 MATERIALS SCIENCE↗

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↗

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↗

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↗

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↗