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 1,009 records · Page 56

Sensor placement for on-orbit modal testing

A systematic procedure of placing accelerometers for the on-orbit modal identification of large flexible space structures is addressed. Target modes for modal testing are selected by examining the modal cost of each mode. Assuming that a time-domain modal identification algorithm such as Eigensystem Realization Algorithm is employed to identify the modes from measured time response data, the sensors are placed to ensure the recovery of the target modes. As an application example of the procedure, an accelerometer placement study for the Space Station Freedom On-Orbit Modal Identification Experiment is presented.

Lim, Tae W.↗

A Blueprint for Demonstrating Quantum Supremacy with Superconducting Qubits

Long coherence times and high fidelity control recently achieved in scalable superconducting circuits paved the way for the growing number of experimental studies of many-qubit quantum coherent phenomena in these devices. Albeit full implementation of quantum error correction and fault tolerant quantum computation remains a challenge the near term pre-error correction devices could allow new fundamental experiments despite inevitable accumulation of errors. One such open question foundational for quantum computing is achieving the so called quantum supremacy, an experimental demonstration of a computational task that takes polynomial time on the quantum computer whereas the best classical algorithm would require exponential time and/or resources. It is possible to formulate such a task for a quantum computer consisting of less than a 100 qubits. The computational task we consider is to provide approximate samples from a non-trivial quantum distribution. This is a generalization for the case of superconducting circuits of ideas behind boson sampling protocol for quantum optics introduced by Arkhipov and Aaronson. In this presentation we discuss a proof-of-principle demonstration of such a sampling task on a 9-qubit chain of superconducting gmon qubits developed by Google. We discuss theoretical analysis of the driven evolution of the device resulting in output approximating samples from a uniform distribution in the Hilbert space, a quantum chaotic state. We analyze quantum chaotic characteristics of the output of the circuit and the time required to generate a sufficiently complex quantum distribution. We demonstrate that the classical simulation of the sampling output requires exponential resources by connecting the task of calculating the output amplitudes to the sign problem of the Quantum Monte Carlo method. We also discuss the detailed theoretical modeling required to achieve high fidelity control and calibration of the multi-qubit unitary evolution in the device. We use a novel cross-entropy statistical metric as a figure of merit to verify the output and calibrate the device controls. Finally, we demonstrate the statistics of the wave function amplitudes generated on the 9-gmon chain and verify the quantum chaotic nature of the generated quantum distribution. This verifies the implementation of the quantum supremacy protocol.

Kechedzhi, Kostyantyn↗

Implementation of (O-)CGR in The ONE

Routing in Delay-/Disruption-Tolerant Networking (DTN) requires specific solutions as link impairments prevent the use of ordinary Internet algorithms, based on a timely dissemination of network topology information. Among DTN routing algorithms there is a dichotomy between opportunistic and deterministic (scheduled) solutions. The former are numerous and apply to terrestrial environments; CGR is the most widely supported algorithm designed for scheduled connectivity, and it is usually applied to space networks. However, in an attempt to provide a unified approach, an opportunistic variant of CGR, Opportunistic CGR (OCGR) has been recently proposed by some of the authors. Performance evaluations are normally carried out for opportunistic solutions by means of simulators, such as The ONE considered in this paper. CGR by contrast is more often studied by means of small testbeds. As the simulation approach could be complementary for CGR, and essential for OCGR, the authors have recently ported both of them into The ONE, by developing and releasing as free software a specific additional package. The aim of this paper is to show the rationale of this choice and discuss the many challenges that needed to be tackled to achieve this primary goal.

Tempesta, G.↗

Harnessing the Power of AI: Status and Expansion of Current Domestic Transport Security Through Flexible Embedded Hardware

As applications of Artificial Intelligence (AI) continue to expand, there are increasing opportunities to leverage applied AI methodologies with mobile transportation focused embedded systems. Current applications of AI in transportation focus on a variety of areas, including fuel efficiency, safety, security, and other broad fields of optimization or detection. To leverage these AI workflows and methodologies in the field, teams must utilize complex embedded systems capable of implementing these AI-enabled algorithms in real-time. In this paper, we will investigate how these algorithms can be integrated into existing technologies leveraging vehicle data - such as the Controller Area Network Transport Security Tracking and Reporting Unit (C-STAR). The C-STAR technology is an embedded platform with onboard computation capable of running next generation algorithms in vehicle systems AI, such as preventative maintenance, driver authentication, and transport security. As deployed in the field, the C-STAR has a limited AI functionality –this paper will directly discuss how a device like C-STAR can be utilized and the advantages of integrating these new technologies. We will open with relevant background information and transportation projects that leverage AI, focusing specifically on those around transport security such as vehicle identification, anomaly detection, and deterrence. We will then extend this into potential opportunities and scaling for AI methodologies using platforms like the C-STAR. Finally, we will speak directly to the challenges of deploying AI-powered workflows, such as computing power needs, bandwidth, hallucinations, and other regulatory considerations.

Cook, Adian [ORNL] (ORCID:0000000160825395)↗

Generating Synthetic Time Series Photovoltaic Data with Real-World Physical Challenges and Noise for Use in Algorithm Test and Validation

The PV Fleet Data Initiative and other projects seek the develop algorithms for automated analysis of PV time series data for extraction of statistical information and other parameters of the data such as degradation rates, soiling loss information, tracker performance, clipping or curtailment, system availability and other valuable information. While there is a vast body of PV data available for application of said extraction algorithms it is difficult to validate these algorithms because the true parameters to be extracted are not known. There has been a wide use of synthetic data in the literature for algorithm validation but this synthetic data is typically very bounded by the problem or topic at hand. The PV Fleet Data Initiative project has demonstrated that real time series PV data almost always includes a host of data quality and physical problems that, in reality, any automated PV abstraction algorithm must handle appropriately. For this reason, this work describes the development of a complex synthetic PV times series data set that includes data quality and physical problems that have been experienced in real world PV data. The various quality and physical problems are documented in the synthetic data so that users can test the validity of various PV extraction algorithms as well as develop new algorithms to solve problems this data set can support.

14 SOLAR ENERGY↗

Explicit time integration of the stiff chemical Langevin equations using computational singular perturbation

A stable explicit time-scale splitting algorithm for stiff chemical Langevin equations (CLEs) is developed, based on the concept of computational singular perturbation. The drift term of the CLE is projected onto basis vectors that span the fast and slow subdomains. The corresponding fast modes exhaust quickly, in the mean sense, and the system state then evolves, with a mean drift controlled by slow modes, on a random manifold. The drift-driven time evolution of the state due to fast exhausted modes is modeled algebraically as an exponential decay process, while that due to slow drift modes and diffusional processes is integrated explicitly. This enables time integration step sizes much larger than those required by typical explicit numerical methods for stiff stochastic differential equations. The algorithm is motivated and reported on, and extensive numerical experiments are conducted to illustrate its accuracy and stability with a number of model systems.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Accurate Consensus-based Distributed Averaging with Variable Time Delay in Support of Distributed Secondary Control Algorithms

We report that distributed secondary control has been widely used in hierarchical control structures, where multiple distributed generators (DGs) need to coordinate to regulate system voltage and frequency. In these systems, consensus algorithms determine the average of a group of dynamic states (e.g. voltages measured by a group of DGs). To be useful, consensus algorithms must be computationally efficient, stable and accurate. In practice, numerous practical implementation challenges significantly affect the consensus equilibrium. In this paper, we quantify the accuracy deviations of the distributed average observer algorithms proposed in the literature to demonstrate the problems with the state-of-the-art distributed averaging techniques. A novel approach is proposed that achieves accurate average tracking in the presence of time-varying communication delays among agents. In our implementation, time synchronization of all distributed controllers is enabled by a novel software platform, called Resilient Information Architecture Platform for the Smart Grid (RIAPS). The proposed distributed average observer is implemented on hardware controllers and its effectiveness is validated in a controller hardware-in-the-loop testbed.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Verification of an energy-conserving semi-implicit electrostatic particle-in-cell scheme for modeling high-density plasma at scale

A verification study of a semi-implicit energy-conserving electrostatic particle-in-cell algorithm is presented. The algorithm relaxes the time-step and mesh-size constraints that require resolution of the plasma period and Debye length associated with traditional explicit momentum-conserving particle-in-cell algorithms. Physical implications and applicability of using the semi-implicit scheme for modeling high-density plasmas are discussed. Where possible, numerical results are compared against analytical solutions. The simulation results indicate that the algorithm is stable at time steps larger than twice the inverse plasma frequency and cell sizes larger than the Debye length. It is found that the algorithm gives adequate results, provided that the distribution function and the spatiotemporal scales dictating the physics of the problem are resolved. As such, the algorithm may provide a robust method for kinetic modeling of high-density plasmas at scale.

Cyclotron resonance↗

Supporting ARPA-E Power Grid Optimization (Final Report)

Pacific Northwest National Laboratory (PNNL), Arizona State University (ASU), Georgia Institute of Technology (Georgia Tech), Los Alamos National Laboratory (LANL), National Renewable Energy Laboratory (NREL), Texas A&M University (TAMU), The University of Texas at Austin (UT), and the University of Wisconsin-Madison (UW-M) supported the ARPA-E Grid Optimization (GO) Competition by providing a common problem formulation, data format, datasets, evaluation mechanism, scoring, rules, and results that resulted in the awarding of $\$9.24$ million dollars to teams from academia, industry, and national labs for solving three sets of increasingly difficult non-linear, security- constrained AC Optimal Powerflow (AC-OPF) optimization problems in order to increase the efficiency of the US Electric Grid. It is estimated that a 1% increase in efficiency can save $\$1$ billion. Current industry practices typically use a linear DC model (DC-OPF) in order solve the OPF problem within the time constraints of the operation schedule. The GO Competition challenges the best power engineers, mathematicians, and computer scientists to make possible operational decisions based on accurate physical models. To accomplish this, the GO Competition created a series of Challenges and funded teams to produce the best solver. Challenge 1 was to solve the security constrained Alternating Current Optimal Power Flow (ACOPF) problem. Challenge 2 extended that to by adding adjustable transformer tap ratios, phase shifting transformers, switchable shunts, price-responsive demand, ramp rate constrained generators and loads, and fast-start unit commitment (UC). Furthermore, Challenge 2 was a maximization problem while Challenge 1 was a minimization problem. While Challenge 3 was being developed, the entrants were invited to find better solutions to the Challenge 2 synthetic datasets with no restrictions on time, hardware, or algorithms. The Challenge 2 solutions turned out to be very good. Challenge 3 expanded the Challenge 2 problem further by using multiperiod dynamic markets, including advisory models for extreme weather events, day-ahead markets, and the real-time markets with an extended look-ahead. These problems included active bid-in demand and topology optimization. Together the Challenges used nearly 30 million CPU hours. Since each team was working on the same problem, using the same data, and running on the same hardware, fair comparisons could be drawn as to the best solver. The datasets were varied enough, however, that the best solver for one dataset was not necessarily the best at another, so cumulative scores were used. The process was managed by the PNNL maintained website https://GOCompetition.energy.gov, where Entrants could find information about the problem, the data, the rules, submit their solver for evaluation, and see the scores of all the competing teams on a Leaderboard. Interest was world-wide but only American teams were eligible for prizes. The Competition has produced 34 journal articles 115 papers and been cited over 500 times in the literature, including 12 dissertations (4 from foreign countries; Columbia (2), Germany, and Italy) and 3 from the DOE ExaScale project. Software developed by Pearl Street Technologies for Challenges 1 and 2 is now deployed by Southwest Power Pool (SPP) and Midcontinent Independent Service Operator (MISO). Other teams have received inquiries from venture capitalists. Google DeepMind has thanked the Competition for making the datasets developed for the Competition public. They are using it to train machine learning models. The larger datasets have billions of unknowns to be solved for, but only a small percent matter in the final solution. Knowing what unknowns are important can dramatically speedup the solution.

24 POWER TRANSMISSION AND DISTRIBUTION↗

The application of preconditioning in viscous flows

The present time-derivative preconditioning algorithm is effective in flow conditions ranging from inviscid to very diffusive flows, as well as low subsonic to supersonic flow velocities. By means of a preconditioning matrix that (1) introduces well-conditioned eigenvalues and (2) avoids nonphysical time reversals for viscous flows, a mechanism is obtained which controls the inviscid and viscous time-step parameters at very diffusive flows. These capabilities are demonstrated for a variety of sample problems; convergence rates of solutions that are indistinguishable from those obtained without preconditioning are shown to be accelerated by as much as two orders of magnitude.

Choi, Y.-H.↗

Multi-region unstructured volume segmentation using tetrahedron filling

Segmentation is one of the most common operations in image processing, and while there are several solutions already present in the literature, they each have their own benefits and drawbacks that make them well-suited for some types of data and not for others. We focus on the problem of breaking an image into multiple regions in a single segmentation pass, while supporting both voxel and scattered point data. To solve this problem, we begin with a set of potential boundary points and use a Delaunay triangulation to complete the boundaries. We use heuristic- and interaction-driven Voronoi clustering to find reasonable groupings of tetrahedra. Apart from the computation of the Delaunay triangulation, our algorithm has linear time complexity with respect to the number of tetrahedra.

97 MATHEMATICS AND COMPUTING↗

Time-reversal of an unknown quantum state

For decades, researchers have sought to understand how the irreversibility of the surrounding world emerges from the seemingly time-symmetric, fundamental laws of physics. Quantum mechanics conjectured a clue that final irreversibility is set by the measurement procedure and that the time-reversal requires complex conjugation of the wave function, which is overly complex to spontaneously appear in nature. Building on this Landau-Wigner conjecture, it became possible to demonstrate that time-reversal is exponentially improbable in a virgin nature and to design an algorithm artificially reversing a time arrow for a given quantum state on the IBM quantum computer. However, the implemented arrow-of-time reversal embraced only the known states initially disentangled from the thermodynamic reservoir. Here we develop a procedure for reversing the temporal evolution of an arbitrary unknown quantum state. This opens the route for general universal algorithms sending temporal evolution of an arbitrary system backward in time.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

A Bayesian approach to real-time 3D tumor localization via monoscopic x-ray imaging during treatment delivery

Purpose: Monoscopic x-ray imaging with on-board kV devices is an attractive approach for real-time image guidance in modern radiation therapy such as VMAT or IMRT, but it falls short in providing reliable information along the direction of imaging x-ray. By effectively taking consideration of projection data at prior times and/or angles through a Bayesian formalism, the authors develop an algorithm for real-time and full 3D tumor localization with a single x-ray imager during treatment delivery. Methods: First, a prior probability density function is constructed using the 2D tumor locations on the projection images acquired during patient setup. Whenever an x-ray image is acquired during the treatment delivery, the corresponding 2D tumor location on the imager is used to update the likelihood function. The unresolved third dimension is obtained by maximizing the posterior probability distribution. The algorithm can also be used in a retrospective fashion when all the projection images during the treatment delivery are used for 3D localization purposes. The algorithm does not involve complex optimization of any model parameter and therefore can be used in a ''plug-and-play'' fashion. The authors validated the algorithm using (1) simulated 3D linear and elliptic motion and (2) 3D tumor motion trajectories of a lung and a pancreas patient reproduced by a physical phantom. Continuous kV images were acquired over a full gantry rotation with the Varian TrueBeam on-board imaging system. Three scenarios were considered: fluoroscopic setup, cone beam CT setup, and retrospective analysis. Results: For the simulation study, the RMS 3D localization error is 1.2 and 2.4 mm for the linear and elliptic motions, respectively. For the phantom experiments, the 3D localization error is < 1 mm on average and < 1.5 mm at 95th percentile in the lung and pancreas cases for all three scenarios. The difference in 3D localization error for different scenarios is small and is not statistically significant. Conclusions: The proposed algorithm eliminates the need for any population based model parameters in monoscopic image guided radiotherapy and allows accurate and real-time 3D tumor localization on current standard LINACs with a single x-ray imager.

62 RADIOLOGY AND NUCLEAR MEDICINE↗

Asynchronous and Distributed Tracking of Time-Varying Fixed Points

NREL researcher Andrey Bernstein discusses asynchronous and distributed tracking of time-varying fixed points as part of the Innovative Optimization and Control Methods for Highly Distributed Autonomous Systems workshop. NREL hosted the workshop to exchange ideas on state-of-the-art control and optimization strategies as well as get feedback on work being done at NREL.

97 MATHEMATICS AND COMPUTING↗

Parallel algorithms for mapping pipelined and parallel computations

Many computational problems in image processing, signal processing, and scientific computing are naturally structured for either pipelined or parallel computation. When mapping such problems onto a parallel architecture it is often necessary to aggregate an obvious problem decomposition. Even in this context the general mapping problem is known to be computationally intractable, but recent advances have been made in identifying classes of problems and architectures for which optimal solutions can be found in polynomial time. Among these, the mapping of pipelined or parallel computations onto linear array, shared memory, and host-satellite systems figures prominently. This paper extends that work first by showing how to improve existing serial mapping algorithms. These improvements have significantly lower time and space complexities: in one case a published O(nm sup 3) time algorithm for mapping m modules onto n processors is reduced to an O(nm log m) time complexity, and its space requirements reduced from O(nm sup 2) to O(m). Run time complexity is further reduced with parallel mapping algorithms based on these improvements, which run on the architecture for which they create the mappings.

Nicol, David M.↗

Estimation, Navigation and Control of Multi-Rotor Drones in an Urban Wind Field

The paper presents an on-board estimation, navigation and control architecture for multi-rotor drones flying in urban environment. It consists of adaptive algorithms to estimate vehicle's aerodynamic drag coefficients with respect to still air and the urban wind components along the flight trajectory, with guaranteed fast and reliable convergence to the true values; navigation algorithms to generate feasible trajectories between given way-points that take into account the estimated wind; and of control algorithms to track the generated trajectories as long as the vehicle retains sufficient number of functioning rotors capable of compensating for the estimated wind. All components of this on-board system are computationally effective and are intended for a real time implementation. The algorithms were tested in simulations.

Stepanyan, Vahram↗

Indoor Wireless Localization of Uncooperative Sources Using a Ray Tracing Model

Indoor geolocation of radio frequency (RF) trans- mitters is challenging due to site-specific multipath effects, especially when the sources are uncooperative. A source being uncooperative means that a-priori the transmit time, location, and power are unknown. It is proposed to use a site-specific ray tracing model to generate realistic indoor RF responses, perform geolocation using multiple methods, and compare their performance. This work will look at two types of geolocation algorithms: (1) time-difference of arrival (TDOA) and (2) re- ceived signal strength Indicator (RSSI) fingerprinting or pattern- matching-based methods. An indoor space will be simulated with a grid of fixed receivers and a grid of transmit locations using Remcom’s Wireless InSite. Using the output of the Wireless InSite simulation the response from any given transmit location can be generated and used to evaluate geolocation performance.

indoor source localization, Wireless InSite, re- c↗

Precise 3D Track Reconstruction Algorithm for the ICARUS T600 Liquid Argon Time Projection Chamber Detector

Liquid Argon Time Projection Chamber (LAr TPC) detectors offer charged particle imaging capability with remarkable spatial resolution. Precise event reconstruction procedures are critical in order to fully exploit the potential of this technology. In this paper we present a new, general approach to 3D reconstruction for the LAr TPC with a practical application to the track reconstruction. The efficiency of the method is evaluated on a sample of simulated tracks. We present also the application of the method to the analysis of stopping particle tracks collected during the ICARUS T600 detector operation with the CNGS neutrino beam.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗