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,117 records · Page 62

Skyline based terrain matching

Skyline-based terrain matching, a new method for locating the vantage point of stereo camera or laser range-finding measurements on a global map previously prepared by satellite or aerial mapping is described. The orientation of the vantage is assumed known, but its translational parameters are determined by the algorithm. Skylines, or occluding contours, can be extracted from the sensory measurements taken by an autonomous vehicle. They can also be modeled from the global map, given a vantage estimate from which to start. The two sets of skylines, represented in cylindrical coordinates about either the true or the estimated vantage, are employed as 'features' or reference objects common to both sources of information. The terrain matching problem is formulated in terms of finding a translation between the respective representations of the skylines, by approximating the two sets of skylines as identical features (curves) on the actual terrain. The search for this translation is based on selecting the longest of the minimum-distance vectors between corresponding curves from the two sets of skylines. In successive iterations of the algorithm, the approximation that the two sets of curves are identical becomes more accurate, and the vantage estimate continues to improve. The algorithm was implemented and evaluated on a simulated terrain. Illustrations and examples are included.

Page, Lance A.↗

Efficient reactive Brownian dynamics

We develop a Split Reactive Brownian Dynamics (SRBD) algorithm for particle simulations of reaction-diffusion systems based on the Doi or volume reactivity model, in which pairs of particles react with a specified Poisson rate if they are closer than a chosen reactive distance. In our Doi model, we ensure that the microscopic reaction rules for various association and dissociation reactions are consistent with detailed balance (time reversibility) at thermodynamic equilibrium. The SRBD algorithm uses Strang splitting in time to separate reaction and diffusion and solves both the diffusion-only and reaction-only subproblems exactly, even at high packing densities. To efficiently process reactions without uncontrolled approximations, SRBD employs an event-driven algorithm that processes reactions in a time-ordered sequence over the duration of the time step. A grid of cells with size larger than all of the reactive distances is used to schedule and process the reactions, but unlike traditional grid-based methods such as reaction-diffusion master equation algorithms, the results of SRBD are statistically independent of the size of the grid used to accelerate the processing of reactions. We use the SRBD algorithm to compute the effective macroscopic reaction rate for both reaction-limited and diffusion-limited irreversible association in three dimensions and compare to existing theoretical predictions at low and moderate densities. We also study long-time tails in the time correlation functions for reversible association at thermodynamic equilibrium and compare to recent theoretical predictions. Finally, we compare different particle and continuum methods on a model exhibiting a Turing-like instability and pattern formation. Our studies reinforce the common finding that microscopic mechanisms and correlations matter for diffusion-limited systems, making continuum and even mesoscopic modeling of such systems difficult or impossible. We also find that for models in which particles diffuse off lattice, such as the Doi model, reactions lead to a spurious enhancement of the effective diffusion coefficients.

97 MATHEMATICS AND COMPUTING↗

Quantum Search Approaches to Sampling-Based Motion Planning

In this paper, we present a novel formulation of traditional sampling-based motion planners as database-oracle structures that can be solved via quantum search algorithms. We consider two complementary scenarios: for simpler sparse environments, we formulate the Quantum Full Path Search Algorithm (q-FPS), which creates a superposition of full random path solutions, manipulates probability amplitudes with Quantum Amplitude Amplification (QAA), and quantum measures a single obstacle free full path solution. For dense unstructured environments, we formulate the Quantum Rapidly Exploring Random Tree algorithm, q-RRT, that creates quantum superpositions of possible parent-child connections, manipulates probability amplitudes with QAA, and quantum measures a single reachable state, which is added to a tree. As performance depends on the number of oracle calls and the probability of measuring good quantum states, we quantify how these errors factor into the probabilistic completeness properties of the algorithm. We then numerically estimate the expected number of database solutions to provide an approximation of the optimal number of oracle calls in the algorithm. We compare the q-RRT algorithm with a classical implementation and verify quadratic run-time speedup in the largest connected component of a 2D dense random lattice. We conclude by evaluating a proposed approach to limit the expected number of database solutions and thus limit the optimal number of oracle calls to a given number.

97 MATHEMATICS AND COMPUTING↗

Robust inverse kinematics using damped least squares with dynamic weighting

This paper presents a general method for calculating the inverse kinematics with singularity and joint limit robustness for both redundant and non-redundant serial-link manipulators. Damped least squares inverse of the Jacobian is used with dynamic weighting matrices in approximating the solution. This reduces specific joint differential vectors. The algorithm gives an exact solution away from the singularities and joint limits, and an approximate solution at or near the singularities and/or joint limits. The procedure is here implemented for a six d.o.f. teleoperator and a well behaved slave manipulator resulted under teleoperational control.

Schinstock, D. E.↗

Quantum search algorithms on a regular lattice

Quantum algorithms for searching for one or more marked items on a d-dimensional lattice provide an extension of Grover's search algorithm including a spatial component. We demonstrate that these lattice search algorithms can be viewed in terms of the level dynamics near an avoided crossing of a one-parameter family of quantum random walks. We give approximations for both the level splitting at the avoided crossing and the effectively two-dimensional subspace of the full Hilbert space spanning the level crossing. This makes it possible to give the leading order behavior for the search time and the localization probability in the limit of large lattice size including the leading order coefficients. For d=2 and d=3, these coefficients are calculated explicitly. Closed form expressions are given for higher dimensions.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Real-time dynamics of the Schwinger model as an open quantum system with Neural Density Operators

Ab-initio simulations of multiple heavy quarks propagating in a Quark-Gluon Plasma are computationally difficult to perform due to the large dimension of the space of density matrices. This work develops machine learning algorithms to overcome this difficulty by approximating exact quantum states with neural network parametrisations, specifically Neural Density Operators. As a proof of principle demonstration in a QCD-like theory, the approach is applied to solve the Lindblad master equation in the 1 + 1d lattice Schwinger Model as an open quantum system. Neural Density Operators enable the study of in-medium dynamics on large lattice volumes, where multiple-string interactions and their effects on string-breaking and recombination phenomena can be studied. Thermal properties of the system at equilibrium can also be probed with these methods by variationally constructing the steady state of the Lindblad master equation. Scaling of this approach with system size is studied, and numerical demonstrations on up to 32 spatial lattice sites and with up to 3 interacting strings are performed.

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗

Mass inflation in Brans-Dicke gravity

A detailed nonlinear analysis of the internal structure of spherical, charged black holes that are accreting scalar matter is performed in the framework of the Brans-Dicke theory of gravity. We choose the lowest value of the Brans-Dicke parameter that is compatible with observational constraints. First, the homogeneous approximation is used. It indicates that mass inflation occurs and that the variations of the Brans-Dicke scalar inside the black hole, which could in principle be large in the absence of mass inflation, become small when mass inflation does occur. Then, a full nonlinear numerical study of the black hole interior perturbed by a self-gravitating massless uncharged scalar field is performed. We use an algorithm with adaptive mesh refinement capabilities. In this way, the changes in the internal structure of the black hole caused by mass inflation are determined, as well as the induced variations of the Brans-Dicke scalar, confirming, qualitatively, the indications given by the homogeneous approximation.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗

guppy i : a code for reducing the storage requirements of cosmological simulations

ABSTRACT As cosmological simulations have grown in size, the permanent storage requirements of their particle data have also grown. Even modest simulations present a major logistical challenge for the groups which run these boxes and researchers without access to high performance computing facilities often need to restrict their analysis to lower quality data. In this paper, we present guppy, a compression algorithm and code base tailored to reduce the sizes of dark matter-only cosmological simulations by approximately an order of magnitude. guppy is a ‘lossy’ algorithm, meaning that it injects a small amount of controlled and uncorrelated noise into particle properties. We perform extensive tests on the impact that this noise has on the internal structure of dark matter haloes, and identify conservative accuracy limits which ensure that compression has no practical impact on single-snapshot halo properties, profiles, and abundances. We also release functional prototype libraries in C, Python, and Go for reading and creating guppy data.

79 ASTRONOMY AND ASTROPHYSICS↗

CHOLLA: A NEW MASSIVELY PARALLEL HYDRODYNAMICS CODE FOR ASTROPHYSICAL SIMULATION

We present Computational Hydrodynamics On ParaLLel Architectures (Cholla ), a new three-dimensional hydrodynamics code that harnesses the power of graphics processing units (GPUs) to accelerate astrophysical simulations. Cholla models the Euler equations on a static mesh using state-of-the-art techniques, including the unsplit Corner Transport Upwind algorithm, a variety of exact and approximate Riemann solvers, and multiple spatial reconstruction techniques including the piecewise parabolic method (PPM). Using GPUs, Cholla evolves the fluid properties of thousands of cells simultaneously and can update over 10 million cells per GPU-second while using an exact Riemann solver and PPM reconstruction. Owing to the massively parallel architecture of GPUs and the design of the Cholla code, astrophysical simulations with physically interesting grid resolutions (≳256{sup 3}) can easily be computed on a single device. We use the Message Passing Interface library to extend calculations onto multiple devices and demonstrate nearly ideal scaling beyond 64 GPUs. A suite of test problems highlights the physical accuracy of our modeling and provides a useful comparison to other codes. We then use Cholla to simulate the interaction of a shock wave with a gas cloud in the interstellar medium, showing that the evolution of the cloud is highly dependent on its density structure. We reconcile the computed mixing time of a turbulent cloud with a realistic density distribution destroyed by a strong shock with the existing analytic theory for spherical cloud destruction by describing the system in terms of its median gas density.

79 ASTRONOMY AND ASTROPHYSICS↗

Multilevel Convergence Analysis of Multigrid-Reduction-in-Time

This study presents a multilevel convergence framework for multigrid-reduction-in-time (MGRIT) as a generalization of previous two-grid estimates. The framework provides a priori upper bounds on the convergence of MGRIT V- and F-cycles, with different relaxation schemes, by deriving the respective residual and error propagation operators. The residual and error operators are functions of the time-stepping operator, analyzed directly and bounded in the norm, both numerically and analytically. We present various upper bounds of different computational cost and varying sharpness. These upper bounds are complemented by proposing analytic formulae for the approximate convergence factor of V-cycle algorithms that take the number of fine grid time points, the temporal coarsening factors, and the eigenvalues of the time-stepping operator as parameters. The paper concludes with supporting numerical investigations of parabolic (anisotropic diffusion) and hyperbolic (wave equation) model problems. We assess the sharpness of the bounds and the quality of the approximate convergence factors. Observations from these numerical investigations demonstrate the value of the proposed multilevel convergence framework for estimating MGRIT convergence a priori and for the design of a convergent algorithm. We further highlight that observations in the literature are captured by the theory, including that two-level Parareal and multilevel MGRIT with F-relaxation do not yield scalable algorithms and the benefit of a stronger relaxation scheme. An important observation is that with increasing numbers of levels MGRIT convergence deteriorates for the hyperbolic model problem, while constant convergence factors can be achieved for the diffusion equation. The theory also indicates that L-stable Runge--Kutta schemes are more amendable to multilevel parallel-in-time integration with MGRIT than A-stable Runge--Kutta schemes.

97 MATHEMATICS AND COMPUTING↗

Multigrid acceleration of the flux split Euler equations

Multigrid acceleration is applied to a flux-split algorithm for solving the Euler equations in two and three dimensions. The basic algorithm is an implicit spatially-split approximate factorization method. The stability of the scheme in comparison to other factorization is examined. Results are presented for two-dimensional airfoil flows and three-dimensional wing flows which demonstrate substantially improved convergence with the multigrid algorithm. An asymptotic spectral radius of 0.89 and 0.93 is attained for a 97 x 17 x 17 wing solution at subcritical and supercritical conditions, respectively.

Anderson, W. K.↗

PLANC: Parallel Low-rank Approximation with Nonnegativity Constraints

In this work, we consider the problem of low-rank approximation of massive dense nonnegative tensor data, for example, to discover latent patterns in video and imaging applications. As the size of data sets grows, single workstations are hitting bottlenecks in both computation time and available memory. We propose a distributed-memory parallel computing solution to handle massive data sets, loading the input data across the memories of multiple nodes, and performing efficient and scalable parallel algorithms to compute the low-rank approximation. We present a software package called Parallel Low-rank Approximation with Nonnegativity Constraints, which implements our solution and allows for extension in terms of data (dense or sparse, matrices or tensors of any order), algorithm (e.g., from multiplicative updating techniques to alternating direction method of multipliers), and architecture (we exploit GPUs to accelerate the computation in this work). We describe our parallel distributions and algorithms, which are careful to avoid unnecessary communication and computation, show how to extend the software to include new algorithms and/or constraints, and report efficiency and scalability results for both synthetic and real-world data sets.

97 MATHEMATICS AND COMPUTING↗

Accuracy of pencil-beam redefinition algorithm dose calculations in patient-like cylindrical phantoms for bolus electron conformal therapy

Purpose: The purpose of this study was to document the improved accuracy of the pencil beam redefinition algorithm (PBRA) compared to the pencil beam algorithm (PBA) for bolus electron conformal therapy using cylindrical patient phantoms based on patient computed tomography (CT) scans of retromolar trigone and nose cancer.Methods: PBRA and PBA electron dose calculations were compared with measured dose in retromolar trigone and nose phantoms both with and without bolus. For the bolus treatment plans, a radiation oncologist outlined a planning target volume (PTV) on the central axis slice of the CT scan for each phantom. A bolus was designed using the planning.decimal{sup Registered-Sign} (p.d) software (.decimal, Inc., Sanford, FL) to conform the 90% dose line to the distal surface of the PTV. Dose measurements were taken with thermoluminescent dosimeters placed into predrilled holes. The Pinnacle{sup 3} (Philips Healthcare, Andover, MD) treatment planning system was used to calculate PBA dose distributions. The PBRA dose distributions were calculated with an in-house C++ program. In order to accurately account for the phantom materials a table correlating CT number to relative electron stopping and scattering powers was compiled and used for both PBA and PBRA dose calculations. Accuracy was determined by comparing differences in measured and calculated dose, as well as distance to agreement for each measurement point.Results: The measured doses had an average precision of 0.9%. For the retromolar trigone phantom, the PBRA dose calculations had an average {+-}1{sigma} dose difference (calculated - measured) of -0.65%{+-} 1.62% without the bolus and -0.20%{+-} 1.54% with the bolus. The PBA dose calculation had an average dose difference of 0.19%{+-} 3.27% without the bolus and -0.05%{+-} 3.14% with the bolus. For the nose phantom, the PBRA dose calculations had an average dose difference of 0.50%{+-} 3.06% without bolus and -0.18%{+-} 1.22% with the bolus. The PBA dose calculations had an average dose difference of 0.65%{+-} 6.21% without bolus and 1.75%{+-} 5.94% with the bolus. From a clinical perspective an agreement of 5% or better between planned (calculated) and delivered (measured) dose is desired. Statistically, this was true for 99% ({+-}2{sigma}) of the dose points for three of the four cases for the PBRA dose calculations, the exception being the nose without bolus for which this was true for 89% ({+-}1.6{sigma}) of the dose points. For the retromolar trigone, with and without bolus, the PBA showed agreement of 5% or better for approximately 86% ({+-}1.5{sigma}) of the dose points. For the nose, with and without bolus, the PBA showed agreement of 5% or better for only approximately 58% ({+-}0.8{sigma}) of the dose points.Conclusions: The measured data, whose high precision makes them useful for evaluation of the accuracy of electron dose algorithms, will be made publicly available. Based on the spread in dose differences, the PBRA has at least twice the accuracy of the PBA. From a clinical perspective the PBRA accuracy is acceptable in the retromolar trigone and nose for electron therapy with and without bolus.

61 RADIATION PROTECTION AND DOSIMETRY↗

Sparsity Prior Computed Tomography Reconstruction Using a Nonstandard Simultaneous X-ray Acquisition Model

In this article we systematically evaluate the performance of several state-of-the-art, sparsity prior computed tomography (CT) reconstruction algorithms, using a nonstandard simultaneous x-ray acquisition method. Sparsity prior is an efficient strategy in CT reconstruction, relying on iterative algorithms such as the algebraic reconstruction technique to produce a crude reconstruction, based on which sparse approximation is performed. The simultaneous x-ray acquisition model ensures rapid capture of x-rays; however, it captures a significantly fewer number of attenuation measurements, and the projections are nonuniform. We propose a weighted average filter in the reconstruction framework to ensure better quality reconstruction by minimizing the effect of nonuniform projections. The performance of the state-of-the-art algorithms is analyzed with and without weighted averaging before sparse approximation, in simulated and real environments. Experiments in the simulated environment are conducted with and without the presence of noise. From the results, it is evident that sparsity prior algorithms are capable of producing cross-sectional reconstruction using the simultaneous x-ray acquisition model, and better reconstruction quality is achievable with the incorporation of weighted averaging in the reconstruction framework.

62 RADIOLOGY AND NUCLEAR MEDICINE↗

Flux-difference split parabolized Navier-Stokes algorithm for non-equilibrium chemically reacting flows

A flux-difference split explicit finite-difference algorithm is presented for solving the parabolized form of the equations governing three-dimensional nonequilibrium chemically reacting flows. The algorithm is based on an explicit noniterative, upwind space-marching scheme developed by Korte, but differs in that the unsteady Riemann problem, rather than the steady Riemann problem, is solved. The algorithm allows either a second or an approximately third-order accurate upwind treatment of the convection terms by employing the unsteady approximate Riemann solver of Roe. The source terms of the species transport equations are treated in either an explicit or implicit manner, and the species diffusion terms are modeled with either a Fickian or a multicomponent model. A validation of the algorithm is performed by comparing computational results with the 2-D Mach 14, 15 degree compression-corner data of Holden. The three-dimensional capability of the algorithm is demonstrated by computing Mach 2.7 flow over a swept wedge scramjet fuel injector, and three-dimensional reacting flow capability is demonstrated by a computing a shock-jet interaction concept for mixing and combustion enhancement.

White, J. A.↗

Probabilistic N - k failure-identification for power systems

This work considers a probabilistic generalization of the N - k failure-identification problem in power transmission networks, where the probability of failure of each component in the network is known a priori and the goal of the problem is to find a set of k components that maximizes disruption to the system loads weighted by the probability of simultaneous failure of the k components. The resulting problem is formulated as a bilevel mixed-integer nonlinear program. Convex relaxations, linear approximations, and heuristics are developed to obtain feasible solutions that are close to the optimum. A general cutting-plane algorithm is proposed to solve the convex relaxation and linear approximations of the N - k problem. Extensive numerical results corroborate the effectiveness of the proposed algorithms on small-, medium-, and large-scale test instances; the test instances include the IEEE 14-bus system, the IEEE single-area and three-area RTS96 systems, the IEEE 118-bus system, the WECC 240-bus test system, the 1354-bus PEGASE system, and the 2383-bus Polish winter-peak test system.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Differential and total cross sections and astrophysical S-factors for {sup 2}H(d,n){sup 3}He and {sup 2}H(d,p){sup 3}H reactions in a wide energy range

Differential cross sections of deuteron–deuteron fusion reactions are needed in astrophysics, precision cosmology, nuclear physics, and controlled nuclear fusion research. New parametrizations for center of mass differential cross sections, total cross sections and astrophysical S-factors in a wide range of specific energy from 0.5 keV/u to about 0.5 GeV/u have been obtained. Straightforward approximating formulae readily suitable for multithreaded algorithmization are given here for {sup 2}H(d,n){sup 3}He and {sup 2}H(d,p){sup 3}H reactions. The energy range is about two orders of magnitude broader than that in the tables published earlier for neutron branch.

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗

Are better combinations of DERs more profitable?: Combinatorial optimization for aggregation of DERs in wholesale electricity markets

Recently, regulatory changes in various countries have enabled the participation of small-scale distributed energy resources (DERs) aggregated in virtual power plants (VPPs) in wholesale electricity markets. The inherent uncertainty and variability of resources comprising VPPs can lead to imbalances between forecasted and metered outputs, potentially resulting in the deficient settlement of generation under imbalance settlement rules. To address this challenge, it is essential to manage variability in the planning phase and uncertainty in the operation phase. Most current research focuses on managing forecasting errors in the operational phase, with insufficient attention given to the planning phase. Here, to bridge this gap, this paper proposes an optimal combination strategy for DERs to maximize the market participation revenue of VPPs by proactively managing variability in the planning phase. To estimate the expected revenue, we conducted analyses for homogeneous and heterogeneous DERs using Monte Carlo simulations and genetic algorithms. Remarkably, the proposed method demonstrated approximately 8 % higher revenue compared to the neighboring group case when considering diversity in DER set configuration with equal proportions of photovoltaics and wind.

24 POWER TRANSMISSION AND DISTRIBUTION↗