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 1,351 records · Page 75

A Numerical Comparison of Rule Ensemble Methods and Support Vector Machines

Machine or statistical learning is a growing field that encompasses many scientific problems including estimating parameters from data, identifying risk factors in health studies, image recognition, and finding clusters within datasets, to name just a few examples. Statistical learning can be described as 'learning from data' , with the goal of making a prediction of some outcome of interest. This prediction is usually made on the basis of a computer model that is built using data where the outcomes and a set of features have been previously matched. The computer model is called a learner, hence the name machine learning. In this paper, we present two such algorithms, a support vector machine method and a rule ensemble method. We compared their predictive power on three supernova type 1a data sets provided by the Nearby Supernova Factory and found that while both methods give accuracies of approximately 95%, the rule ensemble method gives much lower false negative rates.

97 MATHEMATICS AND COMPUTING↗

A primal–dual algorithm for risk minimization

In this paper, we develop an algorithm to efficiently solve risk-averse optimization problems posed in reflexive Banach space. Such problems often arise in many practical applications as, e.g., optimization problems constrained by partial differential equations with uncertain inputs. Unfortunately, for many popular risk models including the coherent risk measures, the resulting risk-averse objective function is nonsmooth. Here, this lack of differentiability complicates the numerical approximation of the objective function as well as the numerical solution of the optimization problem. To address these challenges, we propose a primal–dual algorithm for solving large-scale nonsmooth risk-averse optimization problems. This algorithm is motivated by the classical method of multipliers and by epigraphical regularization of risk measures. As a result, the algorithm solves a sequence of smooth optimization problems using derivative-based methods. We prove convergence of the algorithm even when the subproblems are solved inexactly and conclude with numerical examples demonstrating the efficiency of our method.

97 MATHEMATICS AND COMPUTING↗

Scalable Programming Workflows for Validation of Quantum Computers

Hybrid quantum-classical workflows have become standard methods for executing variational algorithms and other quantum simulation techniques, which are key applications for noisy intermediate scale quantum (NISQ) computers. Validating these simulations is an important task which helps gauge the progress of quantum computer development, and classical simulation can serve as a tool to this end. Both exact and more scalable approximate methods with quantifiable error bounds can be used in validation tasks where the applicable metrics include the distance from a calculable ground truth, the quality of an error model fit to data, etc. Here we present a library extension that includes methods for validation of quantum simulations based on scalable hybrid workflows executable on high performance computers. We provide examples that use approximate methods based on tensor networks and stabilizer simulators to bound the error of quantum simulations on NISQ hardware.

Nguyen, Thien↗

Metaplectic geometrical optics for ray-based modeling of caustics: Theory and algorithms

The optimization of radio frequency-wave (RF) systems for fusion experiments is often performed using ray-tracing codes, which rely on the geometrical-optics (GO) approximation. However, GO fails at caustics such as cutoffs and focal points, erroneously predicting the wave intensity to be infinite. This is a critical shortcoming of GO, since the caustic wave intensity is often the quantity of interest, e.g., RF heating. Full-wave modeling can be used instead, but the computational cost limits the speed at which such optimizations can be performed. Here, we have developed a less expensive alternative called metaplectic geometrical optics (MGO). Instead of evolving waves in the usual x (coordinate) or k (spectral) representation, MGO uses a mixed X$\equiv$Ax+Bk representation. By continuously adjusting the matrix coefficients A and B along the rays, one can ensure that GO remains valid in the X coordinates without caustic singularities. The caustic-free result is then mapped back onto the original x space using metaplectic transforms. Here, we overview the MGO theory and review algorithms that will aid the development of an MGO-based ray-tracing code. We show how using orthosymplectic transformations leads to considerable simplifications compared to previously published MGO formulas. We also prove explicitly that MGO exactly reproduces standard GO when evaluated far from caustics (an important property that until now has only been inferred from numerical simulations), and we relate MGO to other semiclassical caustic-removal schemes published in the literature. Finally this discussion is then augmented by an explicit comparison of the computed spectrum for a wave bounded between two cutoffs.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

Distributed-memory Parallel Algorithms for Matching and Coloring

Graph matching and coloring constitute two fundamental classes of combinatorial problems having numerous established as well as emerging applications in computational science and engineering, high-performance computing, and informatics. We provide a snapshot of an on-going work on the design and implementation of new highly-scalable distributed-memory parallel algorithms for two prototypical problems from these classes, edge-weighted matching and distance-1 vertex coloring. Graph algorithms in general have low concurrency and poor data locality, making it challenging to achieve scalability on massively parallel machines. We overcome this challenge by employing a variety of techniques, including approximation, speculation and iteration, optimized communication, and randomization, in concert. We present preliminary results on weak and strong scalability studies conducted on an IBM Blue Gene/P machine employing up to tens of thousands of processors. The results show that the algorithms hold strong potential for computing at petascale.

Combinatorial scientific computing↗

Model-Free Primal-Dual Methods for Network Optimization with Application to Real-Time Optimal Power Flow: Preprint

This paper examines the problem of real-time optimization of networked systems and develops online algorithms that steer the system towards the optimal trajectory without explicit knowledge of the system model. The problem is modeled as a dynamic optimization problem with time-varying performance objectives and engineering constraints. The design of the algorithms leverages the online zero-order primal-dual projected-gradient method. In particular, the primal step that involves the gradient of the objective function (and hence requires networked systems model) is replaced by its zero-order approximation with two function evaluations using a deterministic perturbation signal. The evaluations are performed using the measurements of the system output, hence giving rise to a feedback interconnection, with the optimization algorithm serving as a feedback controller. The paper provides some insights on the stability and tracking properties of this interconnection. Finally, the paper applies this methodology to a real-time optimal power flow problem in power systems, and shows its efficacy on the IEEE 37-node distribution test feeder for reference power tracking and voltage regulation.

61 RADIATION PROTECTION AND DOSIMETRY↗

An Easy Algorithm to Generate Colored Noise Sequences

The need for accurate and efficient simulation of the noise background arises in statistical significance tests for periodic signals buried in colored noise. This paper discusses techniques for generating colored-noise sequences which simulate processes with a given spectral density. Matlab routines based on the fast fractional difference algorithm are presented. These routines can create various stochastic models (e.g., first-order autoregressive (AR(1)), power law (PL), autoregressive fractionally integrated moving average ((1, d, 0)), and generalized Gauss Markov (GGM)) that serve as possible candidate null hypotheses to test against in various scenarios. Allan variance and power spectral density (PSD) show that our algorithms are accurate and efficient, and can be easily implemented for stationary noise models and non-stationary PLs with spectral indices up to 2. Our algorithms can also be extended to produce a non-stationary PL with a range-limited steeper PSD (spectral indices up to about 4) using a GGM approximation with a proper break frequency. The red-noise leakage effect on the periodogram is further discussed. The result shows that our GGM approximation has a potential for alleviating the red-noise leakage in the PSD estimates. The Timmer and Koenig procedure is also included for comparison.

79 ASTRONOMY AND ASTROPHYSICS↗

Sequential Kalman tuning of the t -preconditioned Crank-Nicolson algorithm: efficient, adaptive and gradient-free inference for Bayesian inverse problems

Ensemble Kalman Inversion (EKI) has been proposed as an efficient method for the approximate solution of Bayesian inverse problems with expensive forward models. However, when applied to the Bayesian inverse problem EKI is only exact in the regime of Gaussian target measures and linear forward models. Here, in this work we propose embedding EKI and Flow Annealed Kalman Inversion, its normalizing flow (NF) preconditioned variant, within a Bayesian annealing scheme as part of an adaptive implementation of the t-preconditioned Crank-Nicolson (tpCN) sampler. The tpCN sampler differs from standard pCN in that its proposal is reversible with respect to the multivariate t-distribution. The more flexible tail behaviour allows for better adaptation to sampling from non-Gaussian targets. Within our Sequential Kalman Tuning (SKT) adaptation scheme, EKI is used to initialize and precondition the tpCN sampler for each annealed target. The subsequent tpCN iterations ensure particles are correctly distributed according to each annealed target, avoiding the accumulation of errors that would otherwise impact EKI. We demonstrate the performance of SKT for tpCN on three challenging numerical benchmarks, showing significant improvements in the rate of convergence compared to adaptation within standard SMC with importance weighted resampling at each temperature level, and compared to similar adaptive implementations of standard pCN. The SKT scheme applied to tpCN offers an efficient, practical solution for solving the Bayesian inverse problem when gradients of the forward model are not available. Code implementing the SKT schemes for tpCN is available at https://github.com/RichardGrumitt/KalmanMC.

97 MATHEMATICS AND COMPUTING↗

Attenuation of wall disturbances in an electron cyclotron resonance oxygen–argon plasma using real time control

Present practice in plasma-assisted semiconductor manufacturing specifies recipes in terms of inputs such as gas flow rates, power and pressure. However, ostensibly identical chambers running identical recipes may produce very different results. Extensive chamber matching, i.e., initial iterative, empirical tuning of the process recipe, which entails time-consuming, ex situ statistical analysis of process metrics such as etch depth, uniformity, anisotropy and selectivity, is required to ensure acceptable results. Once matched, chambers are run open loop and are thus sensitive to disturbances such as actuator drift, wall seasoning and substrate loading, which may impact negatively on process reproducibility. An alternative approach, which may obviate the need for chamber matching and reduce the sensitivity of process metrics to exogenous disturbances, would be to specify a recipe in terms of quantities such as active species densities, and to regulate these in real time by adjusting the inputs with a suitable control algorithm. In this work, real time control of an electron cyclotron resonance O{sub 2}/Ar plasma used for photoresist ashing has been implemented. The design of elementary, model-based algorithms for the control of the argon 750 and oxygen 844 line intensities measured by optical emission spectroscopy is described. Fluorination of the chamber walls by means of an SF{sub 6} plasma prior to ashing inhibits wall recombination of oxygen radicals resulting in an approximately 20% increase in ash rate in the open loop case. However, closed loop control almost completely attenuates the effect of fluorination, thus demonstrating the efficacy of the control algorithms in ensuring a reproducible ash rate in the face of a wall disturbance.

42 ENGINEERING↗

Two-stage State Estimation Algorithm for Distribution Network Analysis

Practical distribution system contains many nodes and short branches. As a result, a more efficient and stable distribution state estimation (DSE) algorithm is needed to properly handle the inverse operation of its large-scale ill-conditioned information matrix. This paper proposed a two-stage DSE algorithm to transform the inverse operation into addition and multiplication operations in a recursive manner. It includes pseudo measurement preprocessing in the offline stage where an approximate linear estimator is adopted to relieve most of computation burdens, and real-time correction in the online stage where a nonlinear estimator is used to update the estimation. Numerical results of the method applied to both IEEE standard test systems and an actual distribution system show the accuracy and effectiveness of the proposed algorithm.

Dong, Jiaojiao↗

Event Reconstruction Algorithms for the ATLAS Trigger

The ATLAS experiment under construction at CERN is due to begin operation at the end of 2007. The detector will record the results of proton-proton collisions at a center-of-mass energy of 14 TeV. The trigger is a three-tier system designed to identify in real-time potentially interesting events that are then saved for detailed offline analysis. The trigger system will select approximately 200 Hz of potentially interesting events out of the 40 MHz bunch-crossing rate (with 10{sup 9} interactions per second at the nominal luminosity). Algorithms used in the trigger system to identify different event features of interest will be described, as well as their expected performance in terms of selection efficiency, background rejection and computation time per event. The talk will concentrate on recent improvements and on performance studies, using a very detailed simulation of the ATLAS detector and electronics chain that emulates the raw data as it will appear at the input to the trigger system.

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗

Global Solution Strategies for the Network-Constrained Unit Commitment Problem with AC Transmission Constraints

Here, we propose a novel global solution algorithm for the network-constrained unit commitment problem that incorporates a nonlinear alternating current (AC) model of the transmission network, which is a nonconvex mixed-integer nonlinear programming (MINLP) problem. Our algorithm is based on the multi-tree global optimization methodology, which iterates between a mixed-integer lower-bounding problem and a nonlinear upper-bounding problem. We exploit the mathematical structure of the unit commitment problem with AC power flow constraints (UC-AC) and leverage second-order cone relaxations, piecewise outer approximations, and optimization-based bounds tightening to guarantee a globally optimal solution at convergence. Numerical results on four benchmark problems illustrate the effectiveness of our algorithm, both in terms of convergence rate and solution quality.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Simulation of Nonequilibrium Dynamics on a Quantum Computer

We present a hybrid quantum-classical algorithm for the time evolution of out-of-equilibrium thermal states. Here, the method depends on classically computing a sparse approximation to the density matrix and, then, time-evolving each matrix element via the quantum computer. For this exploratory study, we investigate a time-dependent Ising model with five spins on the Rigetti Forest quantum virtual machine and a one spin system on the Rigetti 8Q-Agave quantum processor.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

On Two Algorithms of Wavelet Decomposition for Spaces of Linear Splines

The purpose of this paper is to construct new types of wavelets for minimal splines on an irregular grid. The approach applied to construct spline-wavelet decompositions uses approximation relations as an initial structure for constructing the spaces of minimal splines. The advantages of this approach are the possibilities of using irregular grids and sufficiently arbitrary nonpolynomial spline-wavelets.

97 MATHEMATICS AND COMPUTING↗

Low Mach number fluctuating hydrodynamics for electrolytes

Here, we formulate and study computationally the low Mach number fluctuating hydrodynamic equations for electrolyte solutions. We are also interested in studying transport in mixtures of charged species at the mesoscale, down to scales below the Debye length, where thermal fluctuations have a significant impact on the dynamics. Continuing our previous work on fluctuating hydrodynamics of multicomponent mixtures of incompressible isothermal miscible liquids (A. Donev, et al., Physics of Fluids, 27, 3, 2015), we now include the effect of charged species using a quasielectrostatic approximation. Localized charges create an electric field, which in turn provides additional forcing in the mass and momentum equations. Our low Mach number formulation eliminates sound waves from the fully compressible formulation and leads to a more computationally efficient quasi-incompressible formulation. Furthermore, we demonstrate our ability to model saltwater (NaCl) solutions in both equilibrium and nonequilibrium settings. We show that our algorithm is second-order in the deterministic setting, and for length scales much greater than the Debye length gives results consistent with an electroneutral/ambipolar approximation. In the stochastic setting, our model captures the predicted dynamics of equilibrium and nonequilibrium fluctuations. We also identify and model an instability that appears when diffusive mixing occurs in the presence of an applied electric field.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Polynomial meta-models with canonical low-rank approximations: Numerical insights and comparison to sparse polynomial chaos expansions

The growing need for uncertainty analysis of complex computational models has led to an expanding use of meta-models across engineering and sciences. The efficiency of meta-modeling techniques relies on their ability to provide statistically-equivalent analytical representations based on relatively few evaluations of the original model. Polynomial chaos expansions (PCE) have proven a powerful tool for developing meta-models in a wide range of applications; the key idea thereof is to expand the model response onto a basis made of multivariate polynomials obtained as tensor products of appropriate univariate polynomials. The classical PCE approach nevertheless faces the “curse of dimensionality”, namely the exponential increase of the basis size with increasing input dimension. To address this limitation, the sparse PCE technique has been proposed, in which the expansion is carried out on only a few relevant basis terms that are automatically selected by a suitable algorithm. An alternative for developing meta-models with polynomial functions in high-dimensional problems is offered by the newly emerged low-rank approximations (LRA) approach. By exploiting the tensor–product structure of the multivariate basis, LRA can provide polynomial representations in highly compressed formats. Through extensive numerical investigations, we herein first shed light on issues relating to the construction of canonical LRA with a particular greedy algorithm involving a sequential updating of the polynomial coefficients along separate dimensions. Specifically, we examine the selection of optimal rank, stopping criteria in the updating of the polynomial coefficients and error estimation. In the sequel, we confront canonical LRA to sparse PCE in structural-mechanics and heat-conduction applications based on finite-element solutions. Canonical LRA exhibit smaller errors than sparse PCE in cases when the number of available model evaluations is small with respect to the input dimension, a situation that is often encountered in real-life problems. By introducing the conditional generalization error, we further demonstrate that canonical LRA tend to outperform sparse PCE in the prediction of extreme model responses, which is critical in reliability analysis.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Exact exchange potential evaluated from occupied Kohn-Sham and Hartree-Fock solutions

The reported algorithm determines the exact exchange potential v{sub x} in an iterative way using energy shifts (ESs) and orbital shifts (OSs) obtained with finite-difference formulas from the solutions (occupied orbitals and their energies) of the Hartree-Fock-like equation and the Kohn-Sham-like equation, the former used for the initial approximation to v{sub x} and the latter for increments of ES and OS due to subsequent changes of v{sub x}. Thus, the need for solution of the differential equations for OSs, used by Kuemmel and Perdew [Phys. Rev. Lett. 90, 043004 (2003)], is bypassed. The iterated exchange potential, expressed in terms of ESs and OSs, is improved by modifying ESs at odd iteration steps and OSs at even steps. The modification formulas are related to the optimized-effective-potential equation (satisfied at convergence) written as the condition of vanishing density shift (DS). They are obtained, respectively, by enforcing its satisfaction through corrections to approximate OSs and by determining the optimal ESs that minimize the DS norm. The proposed method, successfully tested for several closed-(sub)shell atoms, from Be to Kr, within the density functional theory exchange-only approximation, proves highly efficient. The calculations using the pseudospectral method for representing orbitals give iterative sequences of approximate exchange potentials (starting with the Krieger-Li-Iafrate approximation) that rapidly approach the exact v{sub x} so that, for Ne, Ar, and Zn, the corresponding DS norm becomes less than 10{sup -6} after 13, 13, and 9 iteration steps for a given electron density. In self-consistent density calculations, orbital energies of 10{sup -4} hartree accuracy are obtained for these atoms after, respectively, 9, 12, and 12 density iteration steps, each involving just two steps of v{sub x} iteration, while the accuracy limit of 10{sup -6} to 10{sup -7} hartree is reached after 20 density iterations.

74 ATOMIC AND MOLECULAR PHYSICS↗

A Surrogate-based Adaptive Sampling Approach for History Matching and Uncertainty Quantification

A critical procedure in reservoir simulations is history matching (or data assimilation in a broader sense), which calibrates model parameters such that the simulation results are consistent with field measurements, and hence improves the credibility of the predictions given by the simulations. Often there exist non-unique combinations of parameter values that all yield the simulation results matching the measurements. For such ill-posed history matching problems, Bayesian theorem provides a theoretical foundation to represent different solutions and to quantify the uncertainty with the posterior PDF. Lacking an analytical solution in most situations, the posterior PDF may be characterized with a sample of realizations, each representing a possible scenario. A novel sampling algorithm is presented here for the Bayesian solutions to history matching problems. We aim to deal with two commonly encountered issues: 1) as a result of the nonlinear input-output relationship in a reservoir model, the posterior distribution could be in a complex form, such as multimodal, which violates the Gaussian assumption required by most of the commonly used data assimilation approaches; 2) a typical sampling method requires intensive model evaluations and hence may cause unaffordable computational cost. In the developed algorithm, we use a Gaussian mixture model as the proposal distribution in the sampling process, which is simple but also flexible to approximate non-Gaussian distributions and is particularly efficient when the posterior is multimodal. Also, a Gaussian process is utilized as a surrogate model to speed up the sampling process. Furthermore, an iterative scheme of adaptive surrogate refinement and re-sampling ensures sampling accuracy while keeping the computational cost at a minimum level. The developed approach is demonstrated with an illustrative example and shows its capability in handling the above-mentioned issues. Multimodal posterior of the history matching problem is captured and are used to give a reliable production prediction with uncertainty quantification. The new algorithm reveals a great improvement in terms of computational efficiency comparing previously studied approaches for the sample problem.

Li, Weixuan↗