Search NASA⌕ Search

SEARCH · Search NASA

Results for “algorithm timings”

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 829 records · Page 46

THE QUASIPERIODIC AUTOMATED TRANSIT SEARCH ALGORITHM

We present a new algorithm for detecting transiting extrasolar planets in time-series photometry. The Quasiperiodic Automated Transit Search (QATS) algorithm relaxes the usual assumption of strictly periodic transits by permitting a variable, but bounded, interval between successive transits. We show that this method is capable of detecting transiting planets with significant transit timing variations without any loss of significance-{sup s}mearing{sup -}as would be incurred with traditional algorithms; however, this is at the cost of a slightly increased stochastic background. The approximate times of transit are standard products of the QATS search. Despite the increased flexibility, we show that QATS has a run-time complexity that is comparable to traditional search codes and is comparably easy to implement. QATS is applicable to data having a nearly uninterrupted, uniform cadence and is therefore well suited to the modern class of space-based transit searches (e.g., Kepler, CoRoT). Applications of QATS include transiting planets in dynamically active multi-planet systems and transiting planets in stellar binary systems.

79 ASTRONOMY AND ASTROPHYSICS↗

Parallel adaptive fluid-structure interaction simulation of explosions impacting on building structures

We pursue a level set approach to couple an Eulerian shock-capturing fluid solver with space-time refinement to an explicit solid dynamics solver for large deformations and fracture. The coupling algorithms considering recursively finer fluid time steps as well as overlapping solver updates are discussed in detail. Our ideas are implemented in the AMROC adaptive fluid solver framework and are used for effective fluid-structure coupling to the general purpose solid dynamics code DYNA3D. Beside simulations verifying the coupled fluid-structure solver and assessing its parallel scalability, the detailed structural analysis of a reinforced concrete column under blast loading and the simulation of a prototypical blast explosion in a realistic multistory building are presented.

Deiterding, Ralf↗

Optimizing Approximate Weighted Matching on Nvidia Kepler K40

Matching is a fundamental graph problem with numerous applications in science and engineering. While algorithms for computing optimal matchings are difficult to parallelize, approximation algorithms on the other hand generally compute high quality solutions and are amenable to parallelization. In this paper, we present efficient implementations of the current best algorithm for half-approximate weighted matching, the Suitor algorithm, on Nvidia Kepler K-40 platform. We develop four variants of the algorithm that exploit hardware features to address key challenges for a GPU implementation. We also experiment with different combinations of work assigned to a warp. Using an exhaustive set of $269$ inputs, we demonstrate that the new implementation outperforms the previous best GPU algorithm by $10$ to $100\times$ for over $100$ instances, and from $100$ to $1000\times$ for $15$ instances. We also demonstrate up to $20\times$ speedup relative to $2$ threads, and up to $5\times$ relative to $16$ threads on Intel Xeon platform with $16$ cores for the same algorithm. The new algorithms and implementations provided in this paper will have a direct impact on several applications that repeatedly use matching as a key compute kernel. Further, algorithm designs and insights provided in this paper will benefit other researchers implementing graph algorithms on modern GPU architectures.

GPU↗

Limitations for Quantum Algorithms to Solve Turbulent and Chaotic Systems

We investigate the limitations of quantum computers for solving nonlinear dynamical systems. In particular, we tighten the worst-case bounds of the quantum Carleman linearisation (QCL) algorithm answering one of their open questions. We provide a further significant limitation for any quantum algorithm that aims to output a quantum state that approximates the normalized solution vector. Given a natural choice of coordinates for a dynamical system with one or more positive Lyapunov exponents and solutions that grow sub-exponentially, we prove that any such algorithm has complexity scaling at least exponentially in the integration time. As such, an efficient quantum algorithm for simulating chaotic systems or regimes is likely not possible.

97 MATHEMATICS AND COMPUTING↗

Nuclear Fission Investigation with Twin Ionization Chamber

The purpose of the present paper was to report the recent results, obtained in development of digital pulse processing mathematics for prompt fission neutron (PFN) investigation using twin ionization chamber (TIC) along with fast neutron time-of-flight detector (ND). Due to well known ambiguities in literature (see refs. [4, 6, 9 and 11]), concerning a pulse induction on TIC electrodes by FF ionization, we first presented detailed mathematical analysis of fission fragment (FF) signal formation on TIC anode. The analysis was done using Ramo-Shockley theorem, which gives relation between charged particle motion between TIC electrodes and so called weighting potential. Weighting potential was calculated by direct numerical solution of Laplace equation (neglecting space charge) for the TIC geometry and ionization, caused by FF. Formulae for grid inefficiency (GI) correction and digital pulse processing algorithms for PFN time-of-flight measurements and pulse shape analysis are presented and discussed.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

Autopilot for frequency-modulation atomic force microscopy

One of the most challenging aspects of operating an atomic force microscope (AFM) is finding optimal feedback parameters. This statement applies particularly to frequency-modulation AFM (FM-AFM), which utilizes three feedback loops to control the cantilever excitation amplitude, cantilever excitation frequency, and z-piezo extension. These loops are regulated by a set of feedback parameters, tuned by the user to optimize stability, sensitivity, and noise in the imaging process. Optimization of these parameters is difficult due to the coupling between the frequency and z-piezo feedback loops by the non-linear tip-sample interaction. Four proportional-integral (PI) parameters and two lock-in parameters regulating these loops require simultaneous optimization in the presence of a varying unknown tip-sample coupling. Presently, this optimization is done manually in a tedious process of trial and error. Here, we report on the development and implementation of an algorithm that computes the control parameters automatically. The algorithm reads the unperturbed cantilever resonance frequency, its quality factor, and the z-piezo driving signal power spectral density. It analyzes the poles and zeros of the total closed loop transfer function, extracts the unknown tip-sample transfer function, and finds four PI parameters and two lock-in parameters for the frequency and z-piezo control loops that optimize the bandwidth and step response of the total system. Implementation of the algorithm in a home-built AFM shows that the calculated parameters are consistently excellent and rarely require further tweaking by the user. The new algorithm saves the precious time of experienced users, facilitates utilization of FM-AFM by casual users, and removes the main hurdle on the way to fully automated FM-AFM.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

A Pattern Recognition Algorithm for Quantum Annealers

Abstract The reconstruction of charged particles will be a key computing challenge for the high-luminosity Large Hadron Collider (HL-LHC) where increased data rates lead to a large increase in running time for current pattern recognition algorithms. An alternative approach explored here expresses pattern recognition as a quadratic unconstrained binary optimization (QUBO), which allows algorithms to be run on classical and quantum annealers. While the overall timing of the proposed approach and its scaling has still to be measured and studied, we demonstrate that, in terms of efficiency and purity, the same physics performance of the LHC tracking algorithms can be achieved. More research will be needed to achieve comparable performance in HL-LHC conditions, as increasing track density decreases the purity of the QUBO track segment classifier.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗

Limited-memory adaptive snapshot selection for proper orthogonal decomposition

Reduced order models are useful for accelerating simulations in many-query contexts, such as optimization, uncertainty quantification, and sensitivity analysis. However, offline training of reduced order models can have prohibitively expensive memory and floating-point operation costs in high-performance computing applications, where memory per core is limited. To overcome this limitation for proper orthogonal decomposition, we propose a novel adaptive selection method for snapshots in time that limits offline training costs by selecting snapshots according an error control mechanism similar to that found in adaptive time-stepping ordinary differential equation solvers. The error estimator used in this work is related to theory bounding the approximation error in time of proper orthogonal decomposition-based reduced order models, and memory usage is minimized by computing the singular value decomposition using a single-pass incremental algorithm. Results for a viscous Burgers’ test problem demonstrate convergence in the limit as the algorithm error tolerances go to zero; in this limit, the full order model is recovered to within discretization error. The resulting method can be used on supercomputers to generate proper orthogonal decomposition-based reduced order models, or as a subroutine within hyperreduction algorithms that require taking snapshots in time, or within greedy algorithms for sampling parameter space.

97 MATHEMATICS AND COMPUTING↗

One-dimensional Lagrangian implicit hydrodynamic algorithm for Inertial Confinement Fusion applications

A new one-dimensional hydrodynamic algorithm, specifically developed for Inertial Confinement Fusion (ICF) applications, is presented. The scheme uses a fully conservative Lagrangian formulation in planar, cylindrical, and spherically symmetric geometries, and supports arbitrary equations of state with separate ion and electron components. Fluid equations are discretized on a staggered grid and stabilized by means of an artificial viscosity formulation. The space discretized equations are advanced in time using an implicit algorithm. The method includes several numerical parameters that can be adjusted locally. In regions with low Courant–Friedrichs–Lewy (CFL) number, where stability is not an issue, they can be adjusted to optimize the accuracy. In typical problems, the truncation error can be reduced by a factor between 2 to 10 in comparison with conventional explicit algorithms. On the other hand, in regions with high CFL numbers, the parameters can be set to guarantee unconditional stability. The method can be integrated into complex ICF codes. This is demonstrated through several examples covering a wide range of situations: from thermonuclear ignition physics, where alpha particles are managed as an additional species, to low intensity laser–matter interaction, where liquid–vapor phase transitions occur.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Power System Decomposition for Practical Implementation of Bulk-Grid Voltage Control Methods

Power system algorithms such as AC optimal power flow and coordinated volt/var control of the bulk power system are computationally intensive and become difficult to solve in operational time frames. The computational time required to run these algorithms increases exponentially as the size of the power system increases. The solution time for multiple subsystems is less than that for solving the entire system simultaneously, and the local nature of the voltage problem lends itself to such decomposition. This paper describes an algorithm that can be used to perform power system decomposition from the point of view of the voltage control problem. Our approach takes advantage of the dominant localized effect of voltage control and is based on clustering buses according to the electrical distances between them. One of the contributions of the paper is to use multidimensional scaling to compute n-dimensional Euclidean coordinates for each bus based on electrical distance to perform algorithms like K-means clustering. A simple coordinated reactive power control of photovoltaic inverters for voltage regulation is used to demonstrate the effectiveness of the proposed decomposition algorithm and its components. The proposed decomposition method is demonstrated on the IEEE 118-bus system.

multidimensional scaling↗

New particle pusher with hadronic interactions for modeling multimessenger emission from compact objects

We propose novel numerical schemes based on the Boris method in curved spacetime, incorporating both hadronic and radiative interactions for the first time. Once the proton has lost significant energy due to radiative and hadronic losses, and its gyroradius has decreased below typical scales on which the electromagnetic field varies, we apply a guiding center approximation (GCA). We fundamentally simulate collision processes either with a Monte-Carlo method or, where applicable, as a continuous energy loss, contingent on the local optical depth. To test our algorithm for the first time combining the effects of electromagnetic, gravitational, and radiation fields including hadronic interactions, we simulate highly relativistic protons traveling through various electromagnetic fields and proton backgrounds. We provide unit tests in various spatially dependent electromagnetic and gravitational fields and background photon and proton distributions, comparing the trajectory against analytic results. We propose that our method can be used to analyze hadronic interactions in black hole accretion disks, jets, and coronae to study the neutrino abundance from active galactic nuclei.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗

Efficient quantum algorithm for dissipative nonlinear differential equations

Significance Nonlinear differential equations appear in many domains and are notoriously difficult to solve. Whereas previous quantum algorithms for general nonlinear differential equations have complexity exponential in the evolution time, we give the first quantum algorithm for dissipative nonlinear differential equations that is efficient provided the dissipation is sufficiently strong relative to nonlinear and forcing terms and the solution does not decay too rapidly. We also establish a lower bound showing that differential equations with sufficiently weak dissipation have worst-case complexity exponential in time, giving an almost tight classification of the quantum complexity of simulating nonlinear dynamics. Furthermore, numerical results for the Burgers equation suggest that our algorithm may potentially address complex nonlinear phenomena even in regimes with weaker dissipation.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Relaxation algorithms for matrix completion, with applications to seismic travel-time data interpolation

Travel time tomography is used to infer the underlying three-dimensional wavespeed structure of the Earth by fitting seismic travel time data collected at surface stations. Data interpolation and denoising techniques are important pre-processing steps that use prior knowledge about the data, including parsimony in the frequency and wavelet domains, low-rank structure of matricizations, and local smoothness. In this work, we show how local smoothness structure can be combined with low rank constraints using level-set optimization formulations, and develop a new relaxation algorithm that can efficiently solve these joint problems. In the seismology setting, we use the approach to interpolate missing stations and de-noise observed stations. The new approach is competitive with alternative algorithms, and offers new functionality to interpolate observed data using both smoothness and low rank structure in the presence of data fitting constraints.

constrained optimization↗

The iQID Camera: An Ionizing-Radiation Quantum Imaging Detector

We have developed and tested a novel, ionizing-radiation Quantum Imaging Detector (iQID). This scintillation-based detector was originally developed as a high-resolution gamma-ray imager, called BazookaSPECT, for use in single-photon emission computed tomography (SPECT). Recently, we have investigated the detectors response and imaging potential with other forms of ionizing radiation including alpha, neutron, beta, and fission fragment particles. The detector’s response to a broad range of ionizing radiation has prompted its new title. The principle operation of the iQID camera involves coupling a scintillator to an image intensifier. The scintillation light generated particle interactions is optically amplified by the intensifier and then re-imaged onto a CCD/CMOS camera sensor. The intensifier provides sufficient optical gain that practically any CCD/CMOS camera can be used to image ionizing radiation. Individual particles are identified and their spatial position (to sub-pixel accuracy) and energy are estimated on an event-by-event basis in real time using image analysis algorithms on high-performance graphics processing hardware. Distinguishing features of the iQID camera include portability, large active areas, high sensitivity, and high spatial resolution (tens of microns). Although modest, iQID has energy resolution that is sufficient to discrimate between particles. Additionally, spatial features of individual events can be used for particle discrimination. An important iQID imaging application that has recently been developed is single-particle, real-time digital autoradiography. In conclusion, we present the latest results and discuss potential applications.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

State estimation of an acid gas removal (AGR) plant as part of an integrated gasification combined cycle (IGCC) plant with CO2 capture

An accurate estimation of process state variables not only can increase the effectiveness and reliability of process measurement technology, but can also enhance plant efficiency, improve control system performance, and increase plant availability. Future integrated gasification combined cycle (IGCC) power plants with CO2 capture will have to satisfy stricter operational and environmental constraints. To operate the IGCC plant without violating stringent environmental emission standards requires accurate estimation of the relevant process state variables, outputs, and disturbances. Unfortunately, a number of these process variables cannot be measured at all, while some of them can be measured, but with low precision, low reliability, or low signal-to-noise ratio. As a result, accurate estimation of the process variables is of great importance to avoid the inherent difficulties associated with the inaccuracy of the data. Motivated by this, the current paper focuses on the state estimation of an acid gas removal (AGR) process as part of an IGCC plant with CO2 capture. This process has extensive heat and mass integration and therefore is very suitable for testing the efficiency of the designed estimators in the presence of complex interactions between process variables. The traditional Kalman filter (KF) (Kalman, 1960) algorithm has been used as a state estimator which resembles that of a predictor-corrector algorithm for solving numerical problems. In traditional KF implementation, good guesses for the process noise covariance matrix (Q) and the measurement noise covariance matrix (R) are required to obtain satisfactory filter performance. However, in the real world, these matrices are unknown and it is difficult to generate good guesses for them. In this paper, use of an adaptive KF will be presented that adapts Q and R at every time step of the algorithm. Results show that very accurate estimations of the desired process states, outputs or disturbances can be achieved by using the adaptive KF.

97 MATHEMATICS AND COMPUTING↗

An advanced algorithm for construction of Integral Transport Matrix Method operators using accumulation of single cell coupling factors

The Integral Transport Matrix Method (ITMM) has been shown to be an effective method for solving the neutron transport equation in large domains on massively parallel architectures. In the limit of very large number of processors, the speed of the algorithm, and its suitability for unstructured meshes, i.e. other than an ordered Cartesian grid, is limited by the construction of four matrix operators required for obtaining the solution in each sub-domain. The existing algorithm used for construction of these matrix operators, termed the differential mesh sweep, is computationally expensive and was developed for a structured grid. This work proposes the use of a new algorithm for construction of these operators based on the construction of a single, fundamental matrix representing the transport of a particle along every possible path throughout the sub-domain mesh. Each of the operators is constructed by multiplying an element of this fundamental matrix by two factors dependent only upon the operator being constructed and on properties of the emitting and incident cells. The ITMM matrix operator construction time for the new algorithm is demonstrated to be shorter than the existing algorithm in all tested cases with both isotropic and anisotropic scattering considered. While also being a more efficient algorithm on a structured Cartesian grid, the new algorithm is promising in its geometric robustness and potential for being applied to an unstructured mesh, with the ultimate goal of application to an unstructured tetrahedral mesh on a massively parallel architecture. (authors)

97 MATHEMATICS AND COMPUTING↗

Application of Backward Differentiation Formulas to Neutron Kinetics Problems

The neutron kinetics equations belong to the class of stiff equations for numerical time integration schemes. In this work, the accuracy and speed of algorithms based on backward differentiation formulas (BDFs) are studied with regard to point and spatial neutron kinetics problems. Using a BDF algorithm with the automatic selection of time step and order, solutions to a number of model problems with both a positive and negative reactivity insertion are analyzed. Plots of numerical cost dependences on local and global errors are presented. The results indicate that algorithms based on BDFs are highly efficient and that their application to nuclear reactor simulation is justified.

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗