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 37 records · Page 2

An Orthogonal Recursive Bisection (ORB) Based Time Advancement Algorithm for CFD-DEM Solvers

The time integration of the granular phase in coupled computational fluid dynamics (CFD) – discrete element method (DEM) simulations presents a unique computational challenge brought about by the large variations in particle collisional time scales. Particles in the dilute regions of the computational domain can be advanced with large time steps while dense regions require much smaller time increments. However, the time step size in most solvers is globally set as the limit for accuracy and stability imposed by the collisions and is typically orders of magnitude less than that required away from collisions. This work addresses this precise issue and provides a strategy to avoid the use of a global conservative small time step size for the entire set of particles.A novel time stepping algorithm for CFD-DEM solvers using a partitioning approach using orthogonal recursive bisection (ORB) that allows for variable time steps among particles is described and its computational performance is compared against baseline explicit methods, typically used in several CFD-DEM solvers. ORB has advantages of being relatively quick and easy to update incrementally and has the required heuristic behavior (i.e., it will split the region in half with a cluster on each side) when groups of particles are well separated (clustered). The algorithm presented in this work uses a local time stepping approach to resolve collisional time scales for subsets of particles that are present at the leaves of the ORB, thereby resulting in substantial reduction of computational cost. The parallel implementation of this method where a ``knapsack” algorithm is used in tandem with ORB for effective load-balancing is also presented, where a best possible partitioning is obtained based on number of particles and local time-stepping costs. The algorithm is tested against benchmark problems with varying particle distributions that include fluidized bed and riser flow scenarios. Preliminary results indicate that the approach is 2-3X faster than traditional explicit methods for problems that involve both dense and dilute regions, while maintaining the same level of accuracy.

adaptive timestepping↗

A space-time parallel algorithm with adaptive mesh refinement for computational fluid dynamics

This work describes a space-time parallel algorithm with space-time adaptive mesh refinement (AMR). AMR with subcycling is added to multigrid reduction-in-time (MGRIT) in order to provide solution efficient adaptive grids with a reduction in work performed on coarser grids. This algorithm is achieved by integrating two software libraries: XBraid (Parallel time integration with multigrid. https://computation.llnl.gov/projects/parallel-timeintegration-multigrid) and Chombo (Chombo software package for AMR applications—design document, 2014). The former is a parallel time integration library using multigrid and the latter is a massively parallel structured AMR library. Employing this adaptive space-time parallel algorithm is Chord (Comput Fluids 123:202–217, 2015), a computational fluid dynamics (CFD) application code for solving compressible fluid dynamics problems. For the same solution accuracy, speedups are demonstrated from the use of space-time parallelization over the time-sequential integration on Couette flow and Stokes’ second problem. On a transient Couette flow case, at least a 1.5× speedup is achieved, and with a time periodic problem, a speedup of up to 13.7× over the time-sequential case is obtained. In both cases, the speedup is achieved by adding processors and exploring additional parallelization in time. The numerical experiments show the algorithm is promising for CFD applications that can take advantage of the time parallelism. Future work will focus on improving the parallel performance and providing more tests with complex fluid dynamics to demonstrate the full potential of the algorithm.

97 MATHEMATICS AND COMPUTING↗

A multilevel Cartesian non-uniform grid time domain algorithm

A multilevel Cartesian non-uniform grid time domain algorithm (CNGTDA) is introduced to rapidly compute transient wave fields radiated by time dependent three-dimensional source constellations. CNGTDA leverages the observation that transient wave fields generated by temporally bandlimited and spatially confined source constellations can be recovered via interpolation from appropriately delay- and amplitude-compensated field samples. This property is used in conjunction with a multilevel scheme, in which the computational domain is hierarchically decomposed into subdomains with sparse non-uniform grids used to obtain the fields. For both surface and volumetric source distributions, the computational cost of CNGTDA to compute the transient field at N{sub s} observation locations from N{sub s} collocated sources for N{sub t} discrete time instances scales as O(N{sub t}N{sub s}logN{sub s}) and O(N{sub t}N{sub s}log{sup 2}N{sub s}) in the low- and high-frequency regimes, respectively. Coupled with marching-on-in-time (MOT) time domain integral equations, CNGTDA can facilitate efficient analysis of large scale time domain electromagnetic and acoustic problems.

97 MATHEMATICS AND COMPUTING↗

A Polynomial-Time Classical Algorithm for Noisy Quantum Circuits

We provide a polynomial-time classical algorithm for noisy quantum circuits. The algorithm computes the expectation value of any observable for any circuit, with a small average error over input states drawn from an ensemble (e.g., the computational basis). Our approach is based upon the intuition that noise exponentially damps nonlocal correlations relative to local correlations. This enables one to classically simulate a noisy quantum circuit by keeping track of only the dynamics of local quantum information. Our algorithm also enables sampling from the output distribution of a circuit in quasipolynomial time, so long as the distribution anticoncentrates. A number of implications are discussed, including a fundamental limit on the efficacy of noise mitigation strategies: For constant noise rates, any quantum circuit for which error mitigation succeeds in polynomial-time on most input states can also be classically simulated in polynomial-time on most input states. Our algorithms scale exponentially in the inverse noise rate, which is fundamental and makes them impractical for current quantum devices.

decoherence↗

Advanced time integration algorithms for dislocation dynamics simulations of work hardening

Efficient time integration is a necessity for dislocation dynamics simulations of work hardening to achieve experimentally relevant strains. In this work, an efficient time integration scheme using a high order explicit method with time step subcycling and a newly-developed collision detection algorithm are evaluated. First, time integrator performance is examined for an annihilating Frank–Read source, showing the effects of dislocation line collision. The integrator with subcycling is found to significantly out-perform other integration schemes. The performance of the time integration and collision detection algorithms is then tested in a work hardening simulation. The new algorithms show a 100-fold speed-up relative to traditional schemes. As a result, subcycling is shown to improve efficiency significantly while maintaining an accurate solution, and the new collision algorithm allows an arbitrarily large time step size without missing collisions.

97 MATHEMATICS AND COMPUTING↗

Capturing the interactions between ice sheets, sea level and the solid Earth on a range of timescales: a new “time window” algorithm

Retreat and advance of ice sheets perturb the gravitational field, solid surface and rotation of the Earth, leading to spatially variable sea-level changes over a range of timescales $\textit{O}$ (10 0–6 years), which in turn feed back onto ice-sheet dynamics. Coupled ice-sheet–sea-level models have been developed to capture the interactive processes between ice sheets, sea level and the solid Earth, but it is computationally challenging to capture short-term interactions $\textit{O}$ (10 0–2 years) precisely within longer $\textit{O}$ (10 3–6 years) simulations. The standard forward sea-level modelling algorithm assigns a uniform temporal resolution in the sea-level model, causing a quadratic increase in total CPU time with the total number of input ice history steps, which increases with either the length or temporal resolution of the simulation. In this study, we introduce a new “time window” algorithm for 1D pseudo-spectral sea-level models based on the normal mode method that enables users to define the temporal resolution at which the ice loading history is captured during different time intervals before the current simulation time. Utilizing the time window, we assign a fine temporal resolution $\textit{O}$ (10 0–2 years) for the period of ongoing and recent history of surface ice and ocean loading changes and a coarser temporal resolution $\textit{O}$ (10 3–6 years) for earlier periods in the simulation. This reduces the total CPU time and memory required per model time step while maintaining the precision of the model results. We explore the sensitivity of sea-level model results to the model temporal resolution and show how this sensitivity feeds back onto ice-sheet dynamics in coupled modelling. We apply the new algorithm to simulate sea-level changes in response to global ice-sheet evolution over two glacial cycles and the rapid collapse of marine sectors of the West Antarctic Ice Sheet in the coming centuries and provide appropriate time window profiles for each application. The time window algorithm reduces the total CPU time by ~ 50 % in each of these examples and changes the trend of the total CPU time increase from quadratic to linear. This improvement would increase with longer simulations than those considered here. Our algorithm also allows for coupling time intervals of annual temporal scale for coupled ice-sheet–sea-level modelling of regions such as West Antarctica that are characterized by rapid solid Earth response to ice changes due to the thin lithosphere and low mantle viscosities.

59 BASIC BIOLOGICAL SCIENCES↗

Parallel-in-Time Simulation Algorithm for Power Electronics: MMC-HVdc System

The complexity in simulating power electronics like modular multilevel converters (MMCs) requires simulation algorithms to speed-up the process. Existing simulation algorithms exploit spatial parallelism to speed-up simulation. With rise in complexity of power electronics and presence of increased number of states within them, there are limits in the speed-up using spatial parallelism. In this paper, a temporal parallelism algorithm based on parallel-in-time methods is developed for simulation of power-electronics-systems. The temporal parallelism algorithm is based on computation of power-electronics-states on coarse and fine time-steps using different models. The models of power-electronics-systems used in coarse and fine time-steps are average-value and detailed models, respectively. The updates to states on coarse time-step are computed serially and are used to initialize the states on fine time-step. The updates on fine time-step are computed in parallel. A translation method is proposed in this paper to update the states on fine time-step from the simulations in the coarse time-step, and vice-versa. The proposed algorithm is applied to simulate MMCs and is validated with respect to a detailed reference MMC model. The proposed algorithm recorded a speed-up of up to 3.47× with 5 cores.

42 ENGINEERING↗

IMPROVEMENTS TO THE TIME STEPPING ALGORITHM OF RELAP5-3D

The RELAP5-3D time step method is used to perform thermo-hydraulic and neutronic simulations of nuclear reactors and other devices. It discretizes time and space by numerically solving several differential equations. Previously, time step size was controlled by halving or doubling the size of a previous time step. This process caused the code to run slower than it potentially could. In this research project, the RELAP5-3D time step method was modifi ed to allow a new method of changing time steps to improve execution speed and to control error. The new RELAP5-3D time step method being studied involves making the time step proportional to the material courant limit (MCL), while insuring that the time step does not increase by more than a factor of two between advancements. As before, if a step fails or mass error is excessive, the time step is cut in half. To examine performance of the new method, a measure of run time and a measure of error were plotted against a changing MCL proportionality constant (m) in seven test cases. The removal of the upper time step limit produced a small increase in error, but a large decrease in execution time. The best value of m was found to be 0.9. The new algorithm is capable of producing a signifi cant increase in execution speed, with a relatively small increase in mass error. The improvements made are now under consideration for inclusion as a special option in the RELAP5-3D production code.

Cumberland, R↗

Efficient and Scalable Time-Stepping Algorithms and Reduced-Order Modeling for Ocean System Simulations (Scientific/Technical Report)

This report provides a description of major accomplishments and results obtained by the University of South Carolina/Florida State University/Los Alamos National Laboratory team participating in the project "Efficient and Scalable Time-Stepping Algorithms and Reduced-Order Modeling for Ocean System Simulations" and the list of publications produced from the project.

54 ENVIRONMENTAL SCIENCES↗

A space-time tracking algorithm for high occupancy events at future colliders

We propose to explore the potential advantages of a newclass of tracking algorithms loosely inspired by the Hough transformconcept and where we include the time of arrival of each hit as anadditional coordinate to be treated in the same way as a spatialcoordinate. A remarkable property of this algorithm is that theexecution time is proportional to the total number of hits to beprocessed, making it particularly attractive for high occupancysituations expected at future colliders. The particular structureof the algorithm also lends itself naturally to parallel hardwareimplementations which, combined to its intrinsic flexibility, shouldprovide a powerful tool for triggering at future colliders. To probethe effectiveness of the algorithm, we apply it to a quasi-realisticsimulated environment of a possible future muon collider experimentand report the performance.

Casarsa, Massimo [INFN, Trieste; Royal Inst. Tech.↗

Implementation Plan for Combined Heat and Power Systems VOLTTRON Controller: Performance Monitoring and Real-Time Commissioning Algorithm Verification

Building-integrated cooling, heating, and power (CHP) systems are more efficient than conventional systems at providing local power and thermal energy, and favorable fuel prices are bound to spur their increased adoption. However, to realize the full benefit of the CHP systems, we must ensure persistence of energy efficient operations. Much of the inefficiency in the current building operations can be eliminated by use of automated performance monitoring (PM), real-time commissioning verification (CxV) and automated fault detection and diagnostic (AFDD) tools. Automation can help system operators make intelligent decisions. Remote and continuous monitoring of system conditions and performance will enable better management and integration of CHP with existing building systems. Continuous PM, real-time CxV, and AFDD could alleviate burdens for operations staff, enhance operations and maintenance (O&M), and improve reliability of building and CHP systems. To address the O&M challenges and to provide a means to maximize the rate-of-return of building-integrated CHP systems, the Building Technologies Office (BTO) within the U.S. Department of Energy’s (DOE’s) Office of Energy Efficiency and Renewable Energy (EERE) initiated a project to design, develop, and field test a VOLTTRON™-based supervisory controller and associated open-source algorithms. These algorithms will ensure real-time optimal operation of a building-integrated CHP system, support electric grid reliability, and lead to achieving the goal of clean, efficient, reliable, and affordable next-generation integrated energy system. Previous report listed the components for which PM, real-time CxV, and AFDD algorithms will be developed, how the algorithms will be tested, and the metrics that will be used to validate the algorithms and their ease of deployment. Deployment of these algorithms in the field will result in a reduction in energy consumption of between 10% and 20% (for both CHP and conventional building systems). This report builds upon the previous report by detailing the process by which PNNL will implement performance monitoring and real-time commissioning algorithms for CHP systems in conjunction with the use of the VOLTTRON CHP economic dispatch agent in host facilities.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗

Cable Damage Detection System and Algorithms Using Time Domain Reflectometry

This report describes the hardware system and the set of algorithms we have developed for detecting damage in cables for the Advanced Development and Process Technologies (ADAPT) Program. This program is part of the W80 Life Extension Program (LEP). The system could be generalized for application to other systems in the future. Critical cables can undergo various types of damage (e.g. short circuits, open circuits, punctures, compression) that manifest as changes in the dielectric/impedance properties of the cables. For our specific problem, only one end of the cable is accessible, and no exemplars of actual damage are available. This work addresses the detection of dielectric/impedance anomalies in transient time domain reflectometry (TDR) measurements on the cables. The approach is to interrogate the cable using time domain reflectometry (TDR) techniques, in which a known pulse is inserted into the cable, and reflections from the cable are measured. The key operating principle is that any important cable damage will manifest itself as an electrical impedance discontinuity that can be measured in the TDR response signal. Machine learning classification algorithms are effectively eliminated from consideration, because only a small number of cables is available for testing; so a sufficient sample size is not attainable. Nonetheless, a key requirement is to achieve very high probability of detection and very low probability of false alarm. The approach is to compare TDR signals from possibly damaged cables to signals or an empirical model derived from reference cables that are known to be undamaged. This requires that the TDR signals are reasonably repeatable from test to test on the same cable, and from cable to cable. Empirical studies show that the repeatability issue is the 'long pole in the tent' for damage detection, because it is has been difficult to achieve reasonable repeatability. This one factor dominated the project. The two-step model-based approach is summarized as follows: Step 1, Cable Modeling: Given input-output TDR signals s(n) and x{sub U}(n) for a cable known to be free of damage, system identification algorithms are used to compute a dynamic prediction-error cable model that has output {cflx x}{sub U}(n). The model is declared valid when the innovations e{sub U}(n) = x{sub U}(n) {cflx x}{sub U}(n) satisfy a statistical zero-mean whiteness test. This validated model output is then used as a known reference to which other cables can be compared. Step 2, Cable Testing: The TDR output signal x{sub D}(n) from a cable under test is compared with the model output {cflx x}{sub U}(n) by computing the innovations e{sub D}(n) = x{sub D}(n) {cflx x}{sub U}(n). The innovations are tested using a short-term whiteness test statistic, which employs a statistical confidence interval. If the cable passes the test, this implies that the model is valid and the cable is declared undamaged. If the cable fails the test, this indicates a model mismatch, which means that the cable's dielectric properties have changed; and this implies that the cable is damaged. The test threshold is adjusted to maximize probability of detection and minimize probability of false alarm according to an empirically determined receiver operating characteristic (ROC) curve. An associated confidence interval on the probability of correct classification is also provided. The effectiveness of the algorithm is demonstrated using measured TDR signals for undamaged and damaged cables. Experimental and algorithmic methods for coping with repeatability issues are presented. The model-based damage detection algorithms have been shown to perform well for some representative examples of real TDR signals acquired using the two-dimensional (2D) mockup fixture. If the damage causes a short circuit, then damage detection performance is generally good to excellent. Examples include the cases demonstrated in this report for cuts and pinholes. If the damage does not cause a short circuit, then damage detection performance is generally poor to fair. Examples include the cases demonstrated in this report for crushes and partial cuts.

42 ENGINEERING↗

Efficient Step-Merged Quantum Imaginary Time Evolution Algorithm for Quantum Chemistry

In this work, we develop a resource-efficient step-merged quantum imaginary time evolution approach (smQITE) to solve for the ground state of a Hamiltonian on quantum computers. This heuristic method features a fixed shallow quantum circuit depth along the state evolution path. We use this algorithm to determine the binding energy curves of a set of molecules, including H 2 , H 4 , H 6 , LiH, HF, H 2 O, and BeH 2 , and find highly accurate results. The required quantum resources of smQITE calculations can be further reduced by adopting the circuit form of the variational quantum eigensolver (VQE) technique, such as the unitary coupled cluster ansatz. We demonstrate that smQITE achieves a similar computational accuracy as VQE at the same fixed-circuit ansatz, without requiring a generally complicated high-dimensional nonconvex optimization. Finally, smQITE calculations are carried out on Rigetti quantum processing units, demonstrating that the approach is readily applicable on current noisy intermediate-scale quantum devices.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

QUASI-STELLAR OBJECT SELECTION ALGORITHM USING TIME VARIABILITY AND MACHINE LEARNING: SELECTION OF 1620 QUASI-STELLAR OBJECT CANDIDATES FROM MACHO LARGE MAGELLANIC CLOUD DATABASE

We present a new quasi-stellar object (QSO) selection algorithm using a Support Vector Machine, a supervised classification method, on a set of extracted time series features including period, amplitude, color, and autocorrelation value. We train a model that separates QSOs from variable stars, non-variable stars, and microlensing events using 58 known QSOs, 1629 variable stars, and 4288 non-variables in the MAssive Compact Halo Object (MACHO) database as a training set. To estimate the efficiency and the accuracy of the model, we perform a cross-validation test using the training set. The test shows that the model correctly identifies {approx}80% of known QSOs with a 25% false-positive rate. The majority of the false positives are Be stars. We applied the trained model to the MACHO Large Magellanic Cloud (LMC) data set, which consists of 40 million light curves, and found 1620 QSO candidates. During the selection none of the 33,242 known MACHO variables were misclassified as QSO candidates. In order to estimate the true false-positive rate, we crossmatched the candidates with astronomical catalogs including the Spitzer Surveying the Agents of a Galaxy's Evolution LMC catalog and a few X-ray catalogs. The results further suggest that the majority of the candidates, more than 70%, are QSOs.

79 ASTRONOMY AND ASTROPHYSICS↗

Improving the Convergence Rate of Parareal-in-time Power System Simulation using the Krylov Subspace

The performance of parareal-in-time algorithms is determined on the number of sequential, coarse step iterations. A common tradeoff in designing an efficient parareal-in-time algorithm is between accuracy of the coarse solver and the number of iterations. Traditional parareal implementation for the power system simulation can also have difficulties handling complex power systems. In this paper, we propose a Krylov subspace enhanced parareal algorithm to reduce the number of coarse iterations. The proposed approach is demonstrated on a single-machine-infinite-bus system and the IEEE 10-machine 39-bus system. Noticeable decrease of number of iterations is observed in both cases.

Duan, Nan↗

Faster approximate subgraph counts with privacy

One of the most common problems studied in the context of differential privacy for graph data is counting the number of non-induced embeddings of a subgraph in a given graph. These counts have very high global sensitivity. Therefore, adding noise based on powerful alternative techniques, such as smooth sensitivity and higher-order local sensitivity have been shown to give significantly better accuracy. However, all these alternatives to global sensitivity become computationally very expensive, and to date efficient polynomial time algorithms are known only for few selected subgraphs, such as triangles, k-triangles, and k-stars. In this paper, we show that good approximations to these sensitivity metrics can be still used to get private algorithms. Using this approach, we much faster algorithms for privately counting the number of triangles in real-world social networks, which can be easily parallelized. We also give a private polynomial time algorithm for counting any constant size subgraph using less noise than the global sensitivity; we show this can be improved significantly for counting paths in special classes of graphs

Nguyen, Dung↗

Modeling gamma radiation exposure rates using geologic and remote sensing data to locate radiogenic anomalies

Aerial Gamma-Ray Surveys (GRS) are ideal for tracking anthropogenic gamma radiation releases and transport. The interpretation of a GRS can be complicated by natural gamma-ray sources such as atmospheric radon, cosmic rays, geologic materials, and even the survey equipment itself. Some of these complicating factors can be accounted for or corrected by calibration or mathematic techniques. Real-time algorithms that attempt to enhance potential radiogenic anomalies over background are also in use. However, natural geology is a source of significant background gamma-ray production and neither mathematical corrections nor real-time algorithmic approaches directly account for geology and geochemistry. Here in this study, we advance techniques to predict geologic background exposure rates using rapid and practical methods which can be achieved in the field. In addition we generate models that focus specifically on highlighting radiogenic anomalies for emergency response or further investigation. Predictive models developed in this study were generally able to predict background with medians of ± 1.0 μR/h compared to measured data, and were also able to highlight anomalous areas even where radiation exposure rates were within the range of natural background.

58 GEOSCIENCES↗