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 541 records · Page 30

Collaborative Project: Building improved optimized parameter estimation algorithms to improve methane and nitrogen fluxes in a climate model

Soils in natural and managed ecosystems and wetlands are well known sources of methane, nitrous oxides, and reactive nitrogen gases, but the magnitudes of gas flux to the atmosphere are still poorly constrained. Thus, the reasons for the large increases in atmospheric concentrations of methane and nitrous oxide since the preindustrial time period are not well understood. The low atmospheric concentrations of methane and nitrous oxide, despite being more potent greenhouse gases than carbon dioxide, complicate empirical studies to provide explanations. In addition to climate concerns, the emissions of reactive nitrogen gases from soils are important to the changing nitrogen balance in the earth system, subject to human management, and may change substantially in the future. Thus improved modeling of the emission fluxes of these species from the land surface is important. Currently, there are emission modules for methane and some nitrogen species in the Community Earth System Model’s Community Land Model (CLM-ME/N); however, there are large uncertainties and problems in the simulations, resulting in coarse estimates. In this proposal, we seek to improve these emission modules by combining state-of-the-art process modules for emissions, available data, and new optimization methods. In earth science problems, we often have substantial data and knowledge of processes in disparate systems, and thus we need to combine data and a general process level understanding into a model for projections of future climate that are as accurate as possible. The best methodologies for optimization of parameters in earth system models are still being developed. In this proposal we will develop and apply surrogate algorithms that a) were especially developed for computationally expensive simulations like CLM-ME/N models; b) were (in the earlier surrogate optimization Stochastic RBF) demonstrated to perform very well on computationally expensive complex partial differential equations in earth science with limited numbers of simulations; and, c) will be (as part of the proposed research) significantly improved both by adding asynchronous parallelism, early truncation of unsuccessful simulations, and the improvement of both serial and parallel performance by the use of derivative and sensitivity information from global and local surrogate approximations S(x) . The algorithm development and testing will be focused on the CLM-ME/N model application, but the methods are general and are expected to also perform well on optimization for parameter estimation of other climate models and other classes of continuous multimodal optimization problems arising from complex simulation models. In addition, this proposal will compile available datasets of emissions of methane, nitrous oxides and reactive nitrogen species and develop protocols for site level comparisons with the CLM-ME/N. Once the model parameters are optimized against site level data, the model will be simulated at the global level and compared to atmospheric concentration measurements for the current climate, and future emissions will be estimated using climate change as simulated by the CESM. This proposal combines experts in earth system modeling, optimization, computer science, and process level understanding of soil gas emissions in an interdisciplinary team in order to improve the modeling of methane and nitrogen gas emissions. This proposal thus meets the requirements of the SciDAC RFP, by integrating state-of-the-art computer science and earth system to build an improved earth system model.

54 ENVIRONMENTAL SCIENCES↗

Quantum-assisted quantum compiling

Compiling quantum algorithms for near-term quantum computers (accounting for connectivity and native gate alphabets) is a major challenge that has received significant attention both by industry and academia. Avoiding the exponential overhead of classical simulation of quantum dynamics will allow compilation of larger algorithms, and a strategy for this is to evaluate an algorithm's cost on a quantum computer. To this end, we propose a variational hybrid quantum-classical algorithm called quantum-assisted quantum compiling (QAQC). In QAQC, we use the overlap between a target unitary U and a trainable unitary V as the cost function to be evaluated on the quantum computer. More precisely, to ensure that QAQC scales well with problem size, our cost involves not only the global overlap T r ( V † U ) but also the local overlaps with respect to individual qubits. We introduce novel short-depth quantum circuits to quantify the terms in our cost function, and we prove that our cost cannot be efficiently approximated with a classical algorithm under reasonable complexity assumptions. We present both gradient-free and gradient-based approaches to minimizing this cost. As a demonstration of QAQC, we compile various one-qubit gates on IBM's and Rigetti's quantum computers into their respective native gate alphabets. Furthermore, we successfully simulate QAQC up to a problem size of 9 qubits, and these simulations highlight both the scalability of our cost function as well as the noise resilience of QAQC. Future applications of QAQC include algorithm depth compression, black-box compiling, noise mitigation, and benchmarking.

97 MATHEMATICS AND COMPUTING↗

Monte Carlo evaluation of the convolution/superposition algorithm of Hi-Art tomotherapy in heterogeneous phantoms and clinical cases

The reliability of the convolution/superposition (C/S) algorithm of the Hi-Art tomotherapy system is evaluated by using the Monte Carlo model TomoPen, which has been already validated for homogeneous phantoms. The study was performed in three stages. First, measurements with EBT Gafchromic film for a 1.25x2.5 cm{sup 2} field in a heterogeneous phantom consisting of two slabs of polystyrene separated with Styrofoam were compared to simulation results from TomoPen. The excellent agreement found in this comparison justifies the use of TomoPen as the reference for the remaining parts of this work. Second, to allow analysis and interpretation of the results in clinical cases, dose distributions calculated with TomoPen and C/S were compared for a similar phantom geometry, with multiple slabs of various densities. Even in conditions of lack of lateral electronic equilibrium, overall good agreement was obtained between C/S and TomoPen results, with deviations within 3%/2 mm, showing that the C/S algorithm accounts for modifications in secondary electron transport due to the presence of a low density medium. Finally, calculations were performed with TomoPen and C/S of dose distributions in various clinical cases, from large bilateral head and neck tumors to small lung tumors with diameter of <3 cm. To ensure a ''fair'' comparison, identical dose calculation grid and dose-volume histogram calculator were used. Very good agreement was obtained for most of the cases, with no significant differences between the DVHs obtained from both calculations. However, deviations of up to 4% for the dose received by 95% of the target volume were found for the small lung tumors. Therefore, the approximations in the C/S algorithm slightly influence the accuracy in small lung tumors even though the C/S algorithm of the tomotherapy system shows very good overall behavior.

61 RADIATION PROTECTION AND DOSIMETRY↗

Novel Solver Algorithms for Nearly Singular Linear Systems Arising in Combustion Modelling

Direct Numerical Simulations of realistic combustion devices are extremely challenging due to the wide separation of scales in the simulation, for example an internal combustion (IC) engine chamber, and the flame thickness of a high-pressure flame. The PeleLMeX solver uses adaptive mesh refinement (AMR) to evolve multi-species reacting flows in the low Mach number limit at the Exascale and relies on an embedded boundary (EB) approach to represent complex geometries. In that framework, the EB geometries often give rise to very small cut-cells along the boundary, which translate into extreme ill-conditioning of the pressure-projection, with eigenvalues that span 15-16 orders of magnitude. In this talk, we focus on the case of a typical IC piston bowl geometry for which we present on a novel approach towards solving these nearly singular linear systems with ILU-based, C-AMG smoothers on massively parallel architectures. In particular, we use scaling and equilibration algorithms to handle the non-normality of the upper triangular factors. This enables us to approximate the highly sequential triangular solve algorithm, embedded in the AMG smoothing-solve phase, with Jacobi iterations. This approximation can be written as a convergent Neumann series whose terms are composed of highly parallel sparse matrix vector multiplications. The result is an algorithm that substantially decreases setup and solve time, compared to state-of-the-art, for these challenging linear systems.

combustion modelling↗

Phase space barriers and dividing surfaces in the absence of critical points of the potential energy: Application to roaming in ozone

We examine the phase space structures that govern reaction dynamics in the absence of critical points on the potential energy surface. We show that in the vicinity of hyperbolic invariant tori, it is possible to define phase space dividing surfaces that are analogous to the dividing surfaces governing transition from reactants to products near a critical point of the potential energy surface. We investigate the problem of capture of an atom by a diatomic molecule and show that a normally hyperbolic invariant manifold exists at large atom-diatom distances, away from any critical points on the potential. This normally hyperbolic invariant manifold is the anchor for the construction of a dividing surface in phase space, which defines the outer or loose transition state governing capture dynamics. We present an algorithm for sampling an approximate capture dividing surface, and apply our methods to the recombination of the ozone molecule. We treat both 2 and 3 degrees of freedom models with zero total angular momentum. We have located the normally hyperbolic invariant manifold from which the orbiting (outer) transition state is constructed. This forms the basis for our analysis of trajectories for ozone in general, but with particular emphasis on the roaming trajectories.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

A line search algorithm for wind field adjustment with incomplete data and RBF approximation

The problem of concern in this work is the construction of free divergence fields given scattered horizontal components. As customary, the problem is formulated as a PDE constrained least squares problem. The novelty of our approach is to construct the so-called adjusted field, as the unique solution along an appropriately chosen descent direction. The latter is obtained by the adjoint equation technique. It is shown that the classical adjusted field of Sasaki’s is a particular case. On choosing descent directions, the underlying mass consistent model leads to the solution of an elliptic problem which is solved by means of a radial basis functions method. Finally, some numerical results for wind field adjustment are presented.

97 MATHEMATICS AND COMPUTING↗

Coupled cluster Green function: Model involving single and double excitations

In this paper, we report on the development of a parallel implementation of the coupled-cluster (CC) Green function formulation (GFCC) employing single and double excitations in the cluster operator (GFCCSD). A key aspect of this work is the determination of the frequency dependent self-energy, Σ(ω). The detailed description of the underlying algorithm is provided, including approximations used that preserve the pole structure of the full GFCCSD method, thereby reducing the computational costs while maintaining an accurate character of methodology. Furthermore, for systems with strong local correlation, our formulation reveals a diagonally dominate block structure where as the non-local correlation increases, the block size increases proportionally. Here, to demonstrate the accuracy of our approach, several examples including calculations of ionization potentials for benchmark systems are presented and compared against experiment.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Online Optimization as a Feedback Controller: Stability and Tracking

This paper develops and analyzes feedback-based online optimization methods to regulate the output of a linear time-invariant (LTI) dynamical system to the optimal solution of a time-varying convex optimization problem. The design of the algorithm is based on continuous-time primal-dual dynamics, properly modified to incorporate feedback from the LTI dynamical system, applied to a proximal augmented Lagrangian function. The resultant closed-loop algorithm tracks the solution of the time-varying optimization problem without requiring knowledge of (time-varying) disturbances in the dynamical system. The analysis leverages integral quadratic constraints to provide linear matrix inequality (LMI) conditions that guarantee global exponential stability and bounded tracking error. Analytical results show that, under a sufficient time-scale separation between the dynamics of the LTI dynamical system and the algorithm, the LMI conditions can be always satisfied. The paper further proposes a modified algorithm that can track an approximate solution trajectory of the constrained optimization problem under less restrictive assumptions. As an illustrative example, the proposed algorithms are showcased for power transmission systems, to compress the time scales between secondary and tertiary control, and allow to simultaneously power re-balancing and tracking of DC optimal power flow points.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Piecewise linear approximation with minimum number of linear segments and minimum error: A fast approach to tighten and warm start the hierarchical mixed integer formulation

In several areas of economics and engineering, it is often necessary to fit discrete data points or approximate nonlinear functions with continuous functions. Piecewise linear (PWL) functions are a convenient way to achieve this. PWL functions can be modeled in mathematical problems using only linear and integer variables. Moreover, there is a computational benefit in using PWL functions that have the least possible number of segments. This work proposes a novel hierarchical mixed integer linear programming (MILP) formulation that identifies a continuous PWL approximation with minimum number of linear segments for a given target maximum error. The proposed MILP formulation also identifies the solution with the least maximum error among the solutions with minimum number of segments. Then, this work proposes a fast iterative algorithm that identifies non necessarily continuous PWL approximations by solving O(S log N) linear programming (LP) problems, where N is the number of data points and S is the minimum number of segments in the non necessarily continuous case. This work demonstrates that tight bounds for the MILP problem can be derived from these approximations. Next, a fast algorithm is introduced to transform a non necessarily continuous PWL approximation into a continuous one. Finally, the tight bounds and the continuous PWL approximations are used to tighten and warm start the MILP problem. The tightened formulation is shown in experimental results to be more efficient, especially for large data sets, with a solution time that is up to two orders of magnitude less than the existing literature.

97 MATHEMATICS AND COMPUTING↗

High-precision quantum algorithms for partial differential equations

Quantum computers can produce a quantum encoding of the solution of a system of differential equations exponentially faster than a classical algorithm can produce an explicit description. However, while high-precision quantum algorithms for linear ordinary differential equations are well established, the best previous quantum algorithms for linear partial differential equations (PDEs) have complexity poly(1/ϵ), where ϵ is the error tolerance. By developing quantum algorithms based on adaptive-order finite difference methods and spectral methods, we improve the complexity of quantum algorithms for linear PDEs to be poly(d,log(1/ϵ)), where d is the spatial dimension. Our algorithms apply high-precision quantum linear system algorithms to systems whose condition numbers and approximation errors we bound. We develop a finite difference algorithm for the Poisson equation and a spectral algorithm for more general second-order elliptic equations.

97 MATHEMATICS AND COMPUTING↗

A Simplified Algorithm for Statistical Investigation of Damage Spreading

On the way to simulating adaptive evolution of complex system describing a living object or human developed project, a fitness should be defined on node states or network external outputs. Feedbacks lead to circular attractors of these states or outputs which make it difficult to define a fitness. The main statistical effects of adaptive condition are the result of small change tendency and to appear, they only need a statistically correct size of damage initiated by evolutionary change of system. This observation allows to cut loops of feedbacks and in effect to obtain a particular statistically correct state instead of a long circular attractor which in the quenched model is expected for chaotic network with feedback. Defining fitness on such states is simple. We calculate only damaged nodes and only once. Such an algorithm is optimal for investigation of damage spreading i.e. statistical connections of structural parameters of initial change with the size of effected damage. It is a reversed-annealed method--function and states (signals) may be randomly substituted but connections are important and are preserved. The small damages important for adaptive evolution are correctly depicted in comparison to Derrida annealed approximation which expects equilibrium levels for large networks. The algorithm indicates these levels correctly. The relevant program in Pascal, which executes the algorithm for a wide range of parameters, can be obtained from the author.

99 GENERAL AND MISCELLANEOUS↗

A mathematical model of the passage of an asteroid-comet body through the Earth’s atmosphere

In the paper, a mathematical model and a numerical algorithm are proposed for modeling the complex of phenomena which accompany the passage of a friable asteroid-comet body through the Earth’s atmosphere: the material ablation, the dissociation of molecules, and the radiation. The proposed model is constructed on the basis of the Navier-Stokes equations for viscous heat-conducting gas with an additional equation for the motion and propagation of a friable lumpy-dust material in air. The energy equation is modified for the relation between two its kinds: the usual energy of the translation of molecules (which defines the temperature and pressure) and the combined energy of their rotation, oscillation, electronic excitation, dissociation, and radiation. For the mathematical model of atmosphere, the distribution of density, pressure, and temperature in height is taken as for the standard atmosphere. An asteroid-comet body is taken initially as a round body consisting of a friable lumpy-dust material with corresponding density and significant viscosity which far exceed those for the atmosphere gas. A numerical algorithm is proposed for solving the initial-boundary problem for the extended system of Navier-Stokes equations. The algorithm is the combination of the semi-Lagrangian approximation for Lagrange transport derivatives and the conforming finite element method for other terms. The implementation of these approaches is illustrated by a numerical example.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Fast and Scalable Implementations of Influence Maximization Algorithms

The Influence Maximization problem has been extensively studied in the past decade because of its practical applications in finding the key influencers in social networks. Due to the hardness of the underlying problem, existing algorithms have tried to trade off practical efficiency with approximation guarantees. However, even such approximate solutions take several hours of compute time on modest sized real world inputs. On the other hand, there is a lack of effective parallel and distributed algorithms to solve this problem. In this paper, we present efficient parallel algorithms for multithreaded and distributed systems to solve the influence maximization with approximation guarantee. Our algorithms extend state-of-the-art sequential approach based on computing reverse reachability sets. We present a detailed experimental evaluation, and analyze their performance and their sensitivity to input parameters, using real world inputs. Our experimental results demonstrate significant speedup on parallel architectures. We further show a speedup of up to 586X relative to the state-of-the-art sequential baseline using 1024 nodes of a supercomputer at far greater accuracy and twice the seed set size. To the best of our knowledge, this is the first effort in parallelizing the influence maximization operation at scale.

Minutoli, Marco↗

A persistent adjoint method with dynamic time-scaling and an application to mass action kinetics

In this article, we consider an optimization problem where the objective function is evaluated at the fixed-point of a contraction mapping parameterized by a control variable, and optimization takes place over this control variable. Since the derivative of the fixed-point with respect to the parameter can usually not be evaluated exactly, an adjoint dynamical system can be used to estimate gradients. Using this estimation procedure, the optimization algorithm alternates between derivative estimation and an approximate gradient descent step. We analyze a variant of this approach involving dynamic time-scaling, where after each parameter update the adjoint system is iterated until a convergence threshold is passed. Here, we prove that, under certain conditions, the algorithm can find approximate stationary points of the objective function. We demonstrate the approach in the settings of an inverse problem in chemical kinetics, and learning in attractor networks.

97 MATHEMATICS AND COMPUTING↗

Network Community Detection on Small Quantum Computers

In recent years, a number of quantum computing devices with small numbers of qubits have become available. A hybrid quantum local search (QLS) approach that combines a classical machine and a small quantum device to solve problems of practical size is presented. Herein, the proposed approach is applied to the network community detection problem. QLS is hardware-agnostic and easily extendable to new quantum computing devices as they become available. It is demonstrated to solve the 2-community detection problem on graphs of sizes of up to 410 vertices using the 16-qubit IBM quantum computer and D-Wave 2000Q, and compare their performance with the optimal solutions. The results herein demonstrate that QLS performs similarly in terms of quality of the solution and the number of iterations to convergence on both types of quantum computers and it is capable of achieving results comparable to state-of-the-art solvers in terms of quality of the solution including reaching the optimal solutions.

97 MATHEMATICS AND COMPUTING↗

Data-driven efficient network and surveillance-based immunization

Given a contact network and coarse-grained diagnostic information such as electronic Healthcare Reimbursement Claims (eHRC) data, can we develop efficient intervention policies from data to control an epidemic? Immunization is an important problem in multiple areas, especially epidemiology and public health. However, most existing studies rely on assuming prior epidemiological models to develop pre-emptive strategies, which may fail to adapt to the change in new epidemiological patterns and the availability of rich data such as eHRC. In practice, disease spread is usually complicated, hence assuming an underlying model may deviate from true spreading patterns, leading to possibly inaccurate interventions. Additionally, the abundance of health care surveillance data (such as eHRC) makes it possible to study data-driven strategies without too many restrictive assumptions. Therefore, such a data-driven intervention approach can help public-health experts take more practical decisions. In this work, we take into account propagation log and contact networks for controlling propagation. Furthermore, different from previous model-based approaches, our solutions are solely data driven in a sense that we develop immunization strategies directly from the network and eHRC without assuming classical epidemiological models. In particular, we formulate the novel and challenging data-driven immunization problem. To solve it, we first propose an efficient sampling approach to align surveillance data with contact networks, then develop an efficient algorithm with the provably approximate guarantee for immunization. Finally, we show the effectiveness and scalability of our methods via extensive experiments on multiple datasets, and conduct case studies on nation-wide real medical surveillance data.

60 APPLIED LIFE SCIENCES↗

Large-scale harmonic balance simulations with Krylov subspace and preconditioner recycling

The multi-harmonic balance method combined with numerical continuation provides an efficient framework to compute a family of time-periodic solutions, or response curves, for large-scale, nonlinear mechanical systems. The predictor and corrector steps repeatedly solve a sequence of linear systems that scale by the model size and number of harmonics in the assumed Fourier series approximation. In this paper, a novel Newton–Krylov iterative method is embedded within the multi-harmonic balance and continuation algorithm to efficiently compute the approximate solutions from the sequence of linear systems that arise during the prediction and correction steps. Further, the method recycles, or reuses, both the preconditioner and the Krylov subspace generated by previous linear systems in the solution sequence. A delayed frequency preconditioner refactorizes the preconditioner only when the performance of the iterative solver deteriorates. The GCRO-DR iterative solver recycles a subset of harmonic Ritz vectors to initialize the solution subspace for the next linear system in the sequence. The performance of the iterative solver is demonstrated on two exemplars with contact-type nonlinearities and benchmarked against a direct solver with traditional Newton–Raphson iterations.

97 MATHEMATICS AND COMPUTING↗

Model selection and parameter estimation in tumor growth models using approximate Bayesian computation-ABC

Cancer is one of the most fatal diseases in the world. Governments and researchers from various areas have continuously concentrated efforts to better understand the disease and propose diagnostic and treatment techniques. The use of mathematical models of tumor growth is of great importance for the development of such techniques. Due to the variety of models nowadays available in the literature, the problems of model selection and parameter estimation come into picture, aiming at suitably predicting the patient’s status of the disease. As the available data on dependent variables of existing models might not justify the use of common likelihood functions, approximate Bayesian computation (ABC) becomes a very attractive tool for model selection and model calibration (parameter estimation) in tumor growth models. In the present study, a Monte Carlo approximate Bayesian computation (ABC) algorithm is applied to select among competing models of tumor growth, with and without chemotherapy treatment. Simulated measurements are used in this work. The results obtained show that the algorithm correctly selects the model and estimates the parameters used to generate the simulated measurements.

60 APPLIED LIFE SCIENCES↗