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,153 records · Page 64

TH-AB-207A-12: CT Lung Cancer Screening and the Effects of Further Dose Reduction On CAD Performance

Purpose: CT lung screening is already performed at low doses. In this study, we investigated the effects of further dose reduction on a lung-nodule CAD detection algorithm. Methods: The original raw CT data and images from 348 patients were obtained from our local database of National Lung Screening Trial (NLST) cases. 61 patients (17.5%) had at least one nodule reported on the NLST reader forms. All scans were acquired with fixed mAs (25 for standard-sized patients, 40 for large patients) on a 64-slice scanner (Sensation 64, Siemens Healthcare). All images were reconstructed with 1-mm slice thickness, B50 kernel. Based on a previously-published technique, we added noise to the raw data to simulate reduced-dose versions of each case at 50% and 25% of the original NLST dose (i.e. approximately 1.0 and 0.5 mGy CTDIvol). For each case at each dose level, a CAD detection algorithm was run and nodules greater than 4 mm in diameter were reported. These CAD results were compared to “truth”, defined as the approximate nodule centroids from the NLST forms. Sensitivities and false-positive rates (FPR) were calculated for each dose level, with a sub-analysis by nodule LungRADS category. Results: For larger category 4 nodules, median sensitivities were 100% at all three dose levels, and mean sensitivity decreased with dose. For the more challenging category 2 and 3 nodules, the dose dependence was less obvious. Overall, mean subject-level sensitivity varied from 38.5% at 100% dose to 40.4% at 50% dose, a difference of only 1.9%. However, median FPR quadrupled from 1 per case at 100% dose to 4 per case at 25% dose. Conclusions: Dose reduction affected nodule detectability differently depending on the LungRADS category, and FPR was very sensitive at sub-screening levels. Care should be taken to adapt CAD for the very challenging noise characteristics of screening. Funding support: NIH U01 CA181156; Disclosures (McNitt-Gray): Institutional research agreement, Siemens Healthcare; Past recipient, research grant support, Siemens Healthcare; Consultant, Toshiba America Medical Systems; Consultant, Samsung Electronics.

60 APPLIED LIFE SCIENCES↗

A Comparison of Monte Carlo Particle Transport Algorithms for an Interior Source Binary Stochastic Medium Benchmark Suite

Particle transport through binary stochastic mixtures has received considerable research attention in the last two decades. Zimmerman and Adams proposed a Monte Carlo algorithm (Algorithm A) that solves the Levermore-Pomraning equations and another Monte Carlo algorithm (Algorithm B) that should be more accurate as a result of improved local material realization modeling. Zimmerman and Adams numerically confirmed these aspects of the Monte Carlo algorithms by comparing the reflection and transmission values computed using these algorithms to a standard suite of planar geometry binary stochastic mixture benchmark transport solutions. The benchmark transport problems are driven by an isotropic angular flux incident on one boundary of a binary Markovian statistical planar geometry medium. In a recent paper, we extended the benchmark comparisons of these Monte Carlo algorithms to include the scalar flux distributions produced. This comparison is important, because as demonstrated, an approximate model that gives accurate reflection and transmission probabilities can produce unphysical scalar flux distributions. Brantley and Palmer recently investigated the accuracy of the Levermore-Pomraning model using a new interior source binary stochastic medium benchmark problem suite. In this paper, we further investigate the accuracy of the Monte Carlo algorithms proposed by Zimmerman and Adams by comparing to the benchmark results from the interior source binary stochastic medium benchmark suite, including scalar flux distributions. Because the interior source scalar flux distributions are of an inherently different character than the distributions obtained for the incident angular flux benchmark problems, the present benchmark comparison extends the domain of problems for which the accuracy of these Monte Carlo algorithms has been investigated.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Reproducibility of fixed-node diffusion Monte Carlo across diverse community codes: The case of water–methane dimer

Fixed-node diffusion quantum Monte Carlo (FN-DMC) is a widely trusted many-body method for solving the Schrödinger equation, known for its reliable predictions of material and molecular properties. Furthermore, its excellent scalability with system complexity and near-perfect utilization of computational power make FN-DMC ideally positioned to leverage new advances in computing to address increasingly complex scientific problems. Even though the method is widely used as a computational gold standard, reproducibility across the numerous FN-DMC code implementations has yet to be demonstrated. This difficulty stems from the diverse array of DMC algorithms and trial wave functions, compounded by the method’s inherent stochastic nature. Here, this study represents a community-wide effort to assess the reproducibility of the method, affirming that yes, FN-DMC is reproducible (when handled with care). Using the water–methane dimer as the canonical test case, we compare results from eleven different FN-DMC codes and show that the approximations to treat the non-locality of pseudopotentials are the primary source of the discrepancies between them. In particular, we demonstrate that, for the same choice of determinantal component in the trial wave function, reliable and reproducible predictions can be achieved by employing the T-move, the determinant locality approximation, or the determinant T-move schemes, while the older locality approximation leads to considerable variability in results. These findings demonstrate that, with appropriate choices of algorithmic details, fixed-node DMC is reproducible across diverse community codes—highlighting the maturity and robustness of the method as a tool for open and reliable computational science.

Della Pia, Flaviano [Univ. of Cambridge (United Ki↗

Analyzing Prospects for Quantum Advantage in Topological Data Analysis

Lloyd [Nat. Commun. , 10138 (2016)] were first to demonstrate the promise of quantum algorithms for computing Betti numbers, a way to characterize topological features of data sets. Here, we propose, analyze, and optimize an improved quantum algorithm for topological data analysis (TDA) with reduced scaling, including a method for preparing Dicke states based on inequality testing, a more efficient amplitude estimation algorithm using Kaiser windows, and an optimal implementation of eigenvalue projectors based on Chebyshev polynomials. We compile our approach to a fault-tolerant gate set and estimate constant factors in the Toffoli complexity. Our analysis reveals that superquadratic quantum speedups are only possible for this problem when targeting a multiplicative error approximation and the Betti number grows asymptotically. Further, we propose a dequantization of the quantum TDA algorithm that shows that having exponentially large dimension and Betti number are necessary, but insufficient conditions, for superpolynomial advantage. We then introduce and analyze specific problem examples which have parameters in the regime where superpolynomial advantages may be achieved, and argue that quantum circuits with tens of billions of Toffoli gates can solve seemingly classically intractable instances. Published by the American Physical Society 2024

97 MATHEMATICS AND COMPUTING↗

Trust-Region Approximation of Extreme Trajectories in Power System Dynamics

In this work we present a novel technique, based on a trust-region optimization algorithm and second-order trajectory sensitivities, to compute the extreme trajectories of power system dynamic simulations given a bounded set that represents parametric uncertainty. Furthermore, we show how this method, while remaining computationally efficient compared with sampling-based techniques, overcomes the limitations of previous sensitivity-based techniques to approximate the bounds of the trajectories when the local approximation loses validity because of the nonlinearity. We present several numerical experiments that showcase the accuracy and scalability of the technique, including a demonstration on the IEEE New England test system.

42 ENGINEERING↗

Minimising the error in eigenvalue calculations involving the Boltzmann transport equation using goal-based adaptivity on unstructured meshes

This article presents a method for goal-based anisotropic adaptive methods for the finite element method applied to the Boltzmann transport equation. The neutron multiplication factor, k{sub eff}, is used as the goal of the adaptive procedure. The anisotropic adaptive algorithm requires error measures for k{sub eff} with directional dependence. General error estimators are derived for any given functional of the flux and applied to k{sub eff} to acquire the driving force for the adaptive procedure. The error estimators require the solution of an appropriately formed dual equation. Forward and dual error indicators are calculated by weighting the Hessian of each solution with the dual and forward residual respectively. The Hessian is used as an approximation of the interpolation error in the solution which gives rise to the directional dependence. The two indicators are combined to form a single error metric that is used to adapt the finite element mesh. The residual is approximated using a novel technique arising from the sub-grid scale finite element discretisation. Two adaptive routes are demonstrated: (i) a single mesh is used to solve all energy groups, and (ii) a different mesh is used to solve each energy group. The second method aims to capture the benefit from representing the flux from each energy group on a specifically optimised mesh. The k{sub eff} goal-based adaptive method was applied to three examples which illustrate the superior accuracy in criticality problems that can be obtained.

22 GENERAL STUDIES OF NUCLEAR REACTORS↗

Ensemble Learning Based Convex Approximation of Three-Phase Power Flow

Though the convex optimization has been widely used in power systems, it still cannot guarantee to yield a tight (accurate) solution to some problems. To mitigate this issue, this paper proposes an ensemble learning based convex approximation for alternating current (AC) power flow equations that differs from the existing convex relaxations. The proposed approach is based on three-phase quadratic power flow equations in rectangular coordinates. To develop this data-driven convex approximation of power flows, the polynomial regression (PR) is first deployed as a basic learner to fit convex relationships between the independent and dependent variables. Then, ensemble learning algorithms such as gradient boosting (GB) and bagging are introduced to combine learners to boost model performance. Based on the learned convex approximation of power flow, optimal power flow (OPF) is formulated as a convex quadratic programming problem. The simulation results on IEEE standard cases of both balanced and unbalanced systems show that, in the context of solving OPF, the proposed data-driven convex approximation outperforms the conventional semi-definite programming (SDP) relaxation in both accuracy and computational efficiency, especially in the cases that the conventional SDP relaxation fails

Convex approximation↗

An improved hyperbolic embedding algorithm

Because hyperbolic space has properties that make it amenable to graph representations, there is significant interest in scalable hyperbolic-space embedding methods. These embeddings enable constant-time approximation of shortest-path distances, and so are significantly more efficient than full shortest-path computations. In this article, we improve on existing landmark-based hyperbolic embedding algorithms for large-scale graphs. Whereas previous methods compute the embedding by using the derivative-free Nelder–Mead simplex optimization method, our approach uses the limited-memory BFGS (LBFGS) method, which is quasi-Newton optimization, with analytic gradients. Our method is not only significantly faster but also produces higher-quality embeddings. Moreover, we are able to include the hyperbolic curvature as a variable in the optimization. We compare our hyperbolic embedding method implementation in Python (called Hypy) against the best publicly available software, Rigel. Our method is an order of magnitude faster and shows significant improvements in the accuracy of the shortest-path distance calculations. Furthermore, tests are performed on a variety of real-world networks, and we show the scalability of our method by embedding a graph with 1.8 billion edges and 65 million nodes.

97 MATHEMATICS AND COMPUTING↗

Achieving algorithmic resilience for temporal integration through spectral deferred corrections

Spectral deferred corrections (SDC) is an iterative approach for constructing higher-order-accurate numerical approximations of ordinary differential equations. SDC starts with an initial approximation of the solution defined at a set of Gaussian or spectral collocation nodes over a time interval and uses an iterative application of lower-order time discretizations applied to a correction equation to improve the solution at these nodes. Each deferred correction sweep increases the formal order of accuracy of the method up to the limit inherent in the accuracy defined by the collocation points. In this paper, we demonstrate that SDC is well suited to recovering from soft (transient) hardware faults in the data. A strategy where extra correction iterations are used to recover from soft errors and provide algorithmic resilience is proposed. Specifically, in this approach the iteration is continued until the residual (a measure of the error in the approximation) is small relative to the residual of the first correction iteration and changes slowly between successive iterations. Here, we demonstrate the effectiveness of this strategy for both canonical test problems and a comprehensive situation involving a mature scientific application code that solves the reacting Navier-Stokes equations for combustion research.

97 MATHEMATICS AND COMPUTING↗

Iterative algorithms for processing experimental data

The need to solve linear and nonlinear integral equations arise, e.g., in recovering plasma parameters from the data of multichannel diagnostics. The paper presents an iterative method for solving integral equations with a singularity at the upper limit of integration. The method consists in constructing successive approximations and calculating the integral by quadrature formulas in each integration interval. An example of application of the iterative algorithm to numerically solve an integral equation similar to those arising in recovering the plasma density profile from reflectometry data is presented.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

Extended Lagrangian Born–Oppenheimer molecular dynamics using a Krylov subspace approximation

It is shown how the electronic equations of motion in extended Lagrangian Born–Oppenheimer molecular dynamics simulations can be integrated using low-rank approximations of the inverse Jacobian kernel. This kernel determines the metric tensor in the harmonic oscillator extension of the Lagrangian that drives the evolution of the electronic degrees of freedom. The proposed kernel approximation is derived from a pseudoinverse of a low-rank estimate of the Jacobian, which is expressed in terms of a generalized set of directional derivatives with directions that are given from a Krylov subspace approximation. The approach allows a tunable and adaptive approximation that can take advantage of efficient preconditioning techniques. The proposed kernel approximation for the integration of the electronic equations of motion makes it possible to apply extended Lagrangian first-principles molecular dynamics simulations to a broader range of problems, including reactive chemical systems with numerically sensitive and unsteady charge solutions. This can be achieved without requiring exact full calculations of the inverse Jacobian kernel in each time step or relying on iterative non-linear self-consistent field optimization of the electronic ground state prior to the force evaluations as in regular direct Born–Oppenheimer molecular dynamics. We note the low-rank approximation of the Jacobian is directly related to Broyden’s class of quasi-Newton algorithms and Jacobian-free Newton–Krylov methods and provides a complementary formulation for the solution of nonlinear systems of equations.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

A mathematical and numerical framework for the analysis of compressible thermal convection in gases at very high temperatures

The relevance of non-equilibrium phenomena, nonlinear behavior, gravitational effects and fluid compressibility in a wide range of problems related to high-temperature gas-dynamics, especially in thermal, mechanical and nuclear engineering, calls for a concerted approach using the tools of the kinetic theory of gases, statistical physics, quantum mechanics, thermodynamics and mathematical modeling in synergy with advanced numerical strategies for the solution of the Navier–Stokes equations. The reason behind such a need is that in many instances of relevance in this field one witnesses a departure from canonical models and the resulting inadequacy of standard CFD approaches, especially those traditionally used to deal with thermal (buoyancy) convection problems. Starting from microscopic considerations and typical concepts of molecular dynamics, passing through the Boltzmann equation and its known solutions, we show how it is possible to remove past assumptions and elaborate an algorithm capable of targeting the broadest range of applications. Moving beyond the Boussinesq approximation, the Sutherland law and the principle of energy equipartition, the resulting method allows most of the fluid properties (density, viscosity, thermal conductivity, heat capacity and diffusivity, etc.) to be derived in a rational and natural way while keeping empirical contamination to the minimum. Special attention is deserved as well to the well-known pressure issue. With the application of the socalled multiple pressure variables concept and a projection-like numerical approach, difficulties with such a term in the momentum equation are circumvented by allowing the hydrodynamic pressure to decouple from its thermodynamic counterpart. The final result is a flexible and modular framework that on the one hand is able to account for all the molecule (translational, rotational and vibrational) degrees of freedom and their effective excitation, and on the other hand can guarantee adequate interplay between molecular and macroscopic-level entities and processes. Performances are demonstrated by computing some incompressible and compressible benchmark test cases for thermal (gravitational) convection, which are then extended to the high-temperature regime taking advantage of the newly developed features.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Robust Spectral Unmixing of Sparse Multispectral Lidar Waveforms using Gamma Markov Random Fields

Here, this paper presents a new Bayesian spectral un-mixing algorithm to analyse remote scenes sensed via sparse multispectral Lidar measurements. To a first approximation, in the presence of a target, each Lidar waveform consists of a main peak, whose position depends on the target distance and whose amplitude depends on the wavelength of the laser source considered (i.e, on the target reflectivity). Besides, these temporal responses are usually assumed to be corrupted by Poisson noise in the low photon count regime. When considering multiple wavelengths, it becomes possible to use spectral information in order to identify and quantify the main materials in the scene, in addition to estimation of the Lidar-based range profiles. Due to its anomaly detection capability, the proposed hierarchical Bayesian model, coupled with an efficient Markov chain Monte Carlo algorithm, allows robust estimation of depth images together with abundance and outlier maps associated with the observed 3D scene. The proposed methodology is illustrated via experiments conducted with real multispectral Lidar data acquired in a controlled environment. The results demonstrate the possibility to unmix spectral responses constructed from extremely sparse photon counts (less than 10 photons per pixel and band).

97 MATHEMATICS AND COMPUTING↗

Variational preparation of the thermofield double state of the Sachdev-Ye-Kitaev model

Here, we provide an algorithm for preparing the thermofield double (TFD) state of the Sachdev-Ye-Kitaev (SYK) model without the need for an auxiliary bath. Following previous work, the TFD can be cast as the approximate ground state of a Hamiltonian, H TFD . Using variational quantum circuits, we propose and implement a gradient-based algorithm for learning parameters that find this ground state, an application of the variational quantum eigensolver. Concretely, we find shallow quantum circuits that prepare the ground state of H TFD for the q = 4 SYK model for N = 8 Majoranas per side. For N = 12, we achieve a variational energy within 1% of the true ground-state energy.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Extraction of Hydrological Proximity Measures from DEMs using Parallel Processing

Land surface topography is one of the most important terrain properties which impact hydrological, geomorphological, and ecological processes active on a landscape. In our previous efforts to develop a soil depth model based upon topographic and land cover variables, we extracted a set of hydrological proximity measures (HPMs) from a Digital Elevation Model (DEM) as potential explanatory variables for soil depth. These HPMs may also have other, more general modeling applicability in hydrology, geomorphology and ecology, and so are described here from a general perspective. The HPMs we derived are variations of the distance up to ridge points (cells with no incoming flow) and variations of the distance down to stream points (cells with a contributing area greater than a threshold), following the flow path. These HPMs were computed using the D-infinity flow model that apportions flow between adjacent neighbors based on the direction of steepest downward slope on the eight triangular facets constructed in a 3 x 3 grid cell window using the center cell and each pair of adjacent neighboring grid cells in turn. The D-infinity model typically results in multiple flow paths between 2 points on the topography, with the result that distances may be computed as the minimum, maximum or average of the individual flow paths. In addition, each of the HPMs, are calculated vertically, horizontally, and along the land surface. Previously, these HPMs were calculated using recursive serial algorithms which suffered from stack overflow problems when used to process large datasets, limiting the size of DEMs that could be analyzed using that method to approximately 7000 x 7000 cells. To overcome this limitation, we developed a message passing interface (MPI) parallel approach for calculating these HPMs. The parallel algorithms of the HPMs spatially partition the input grid into stripes which are each assigned to separate processes for computation. Each of those processes then uses a queue data structure to order the processing of cells so that each cell is visited only once and the cross-process communications that are a standard part of MPI are handled in an efficient manner. This parallel approach allows analysis of much larger DEMs as compared to the serial recursive algorithms. In this paper, we present the definitions of the HPMs, the serial and parallel algorithms used in their extraction and their potential applications in hydrology, geomorphology and ecology.

54 ENVIRONMENTAL SCIENCES↗

Event-Based Parareal: A data-flow based implementation of parareal

Parareal is an iterative algorithm that, in effect, achieves temporal decomposition for a time-dependent system of differential or partial differential equations. A solution is obtained in a shorter wall-clock time, but at the expense of increased compute cycles. The algorithm combines a fine solver that solves the system to acceptable accuracy with an approximate coarse solver. The critical task for the successful implementation of parareal on any system is the development of a coarse solver that leads to convergence in a small number of iterations compared to the number of time slices in the full time interval, and is, at the same time, much faster than the fine solver. Fast coarse solvers may not lead to sufficiently rapid convergence, and slow coarse solvers may not lead to significant gains even if the number of iterations to convergence is satisfactory. We find that the difficulty of meeting these conflicting demands can be substantially eased by using a data-driven, event-based implementation of parareal instead of the conventional algorithm where solver tasks are executed sequentially. For given convergence properties, the event-based approach relaxes the speed requirements on the coarse solver by a factor of , where is the number of iterations required for a converged solution. This may, for many problems, lead to an efficient parareal implementation that would otherwise not be possible or would require substantial coarse solver development.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Analog Systems for Edge Optimization

Over the past decade, analog computing has the subject of substantial research interest providing a path toward improved computational efficiency in the post-Dennard era. Analog matrix vector multiplication (MVM) accelerators provide a popular approach given the ubiquity of MVM operations in numerous applications. However, historically analog computing systems can struggle with applications requiring high precision due to the inherent susceptibility of these systems to analog non-idealities. Therefore, prior work on analog systems has focused either on applications known to be tolerant of limited precision (e.g., neural network inference), or using expensive techniques to emulate high-precision using many analog MVM operations. In this work, we propose an alternative approach. Motivated by recent advances in inexact nonlinear solvers and optimizers, we explore the potential of co-designing optimization algorithms which can take full advantage of the fundamentally inexact analog MVM operations. To enable these co-designed algorithms we also develop a general mathematical theory of the precision and energy efficiency of analog operations, and a new system architecture for tightly-coupled analog and digital computation. Finally, we examine the applicability of analog computing to a wider class of symmetric positive definite systems and find potential in using analog operations as a sparse approximate inverse preconditioner. With these core innovations, this project provides a path toward effectively implementing optimization algorithms on power-constrained autonomous and semi-autonomous systems.

97 MATHEMATICS AND COMPUTING↗

Class II algorithm for charged-particle transport simulation - Paper 142

Simulation of the transport of high-energy charged particles is difficult because of the large number of interactions experienced by these particles before being brought to rest. Possible strategies to deal with this difficulty were analyzed by Berger. Most modern Monte Carlo codes use a mixture of complete-grouping (class I) and mixed (class II) schemes. In class I simulations, the global effect of all the interactions that occur along a trajectory segment of a given length s is described by means of precalculated distributions derived from multiple-scattering theories. In class II simulations, hard (or catastrophic) interactions (with energy loss W or polar scattering angle {theta} larger than given cutoff values) are sampled individually, while the effect of soft interactions (with energy losses and scattering angles smaller than the respective cutoffs) is described using a multiple-scattering approach. Although Berger effectively employed class II simulation only for energy-loss events, he did recognize the advantages of class II over class I also for multiple elastic scattering. On the one hand, because hard interactions are described exactly according to the adopted differential cross sections (DCSs), class II schemes are more accurate. On the other hand, multiple-scattering approximations, which are still required to describe the cumulative effect of soft interactions, are simpler and more accurate when individual interactions are limited to small energy transfers and angular deflections. For instance, for path lengths that are not too small, but still much less than the CSDA range, the energy-loss distribution due to multiple soft events is approximately Gaussian, by virtue of the central limit theorem. Similarly, the angular distribution caused by multiple small-angle deflections is also approximately Gaussian. However, class II schemes are more difficult to implement because of their dependence on specificities of the DCSs. In this article we briefly present the essentials of the class II algorithm for charged particles implemented in the last version of the penelope code, and provide evidence of its accuracy and stability with the simulation parameters. (authors)

61 RADIATION PROTECTION AND DOSIMETRY↗