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 109 records · Page 6

Statistical analysis of piloted simulation of real time trajectory optimization algorithms

A simulation of time-optimal intercept algorithms for on-board computation of control commands is described. The effects of three different display modes and two different computation modes on the pilots' ability to intercept a moving target in minimum time were tested. Both computation modes employed singular perturbation theory to help simplify the two-point boundary value problem associated with trajectory optimization. Target intercept time was affected by both the display and computation modes chosen, but the display mode chosen was the only significant influence on the miss distance.

Price, D. B.↗

Solving a system of linear equations: From centralized to distributed methods

For a wide range of control engineering applications, the problem of solving a system of linear equations is often encountered and has been well studied. Traditionally, this problem has been mainly solved in a centralized manner. However, for applications related to large-scale complex networked systems, centralized algorithms are often subjected to some practical issues due to limited computational power and communication bandwidth. As a promising and viable alternative, distributed algorithms can effectively address the issues associated with centralized algorithms by solving the problem efficiently in a multi-agent setting that accords with the distributed nature of networked systems. Distributed algorithms decompose the entire problem into many sub-problems that are solved by individual agents in a cooperative manner. In this survey paper, we provide a detailed overview of the state of the art relevant to distributed algorithms for solving a system of linear equations. We will first review basic distributed algorithms including both discrete-time and continuous-time algorithms. Then we will discuss the extended algorithms to achieve communication efficiency. Furthermore, we will also introduce distributed algorithms to obtain the minimum-norm solution for a system of linear equations with multiple solutions, as well as the least-squares solutions when there is no solution. Finally, the relationship of distributed algorithms for solving a system of linear equations to the existing distributed optimization algorithms is discussed.

Wang, Peng↗

Efficient parametric analysis of performance measures for communication networks

Efficient techniques for estimating performance measures in communication networks in a steady-state or transient setting are developed. These techniques may be used in a simulation environment or in connection with real-time observations. For Markov chain models, the recently proposed standard clock approach is extended, and a class of real-time algorithms for simultaneously generating multiple sample paths under different parameter sets is presented. Attention is focused on the link crash time estimation problem, where a 'crash' is defined as the first time a buffer overflows, given some initial conditions. An algorithm for estimating crash times under various traffic shocks is derived, where all estimates are obtained in parallel to an actual network's normal operation. An algorithm for crash time estimation of a G/D/1 link model is also derived using a different (perturbation-analysis-based) approach. Finally, extensive simulation results are provided to validate the proposed algorithms and compare them to brute-force simulation.

Cassandras, Christos G.↗

Algorithmic properties of the midpoint predictor-corrector time integrator.

Algorithmic properties of the midpoint predictor-corrector time integration algorithm are examined. In the case of a finite number of iterations, the errors in angular momentum conservation and incremental objectivity are controlled by the number of iterations performed. Exact angular momentum conservation and exact incremental objectivity are achieved in the limit of an infinite number of iterations. A complete stability and dispersion analysis of the linearized algorithm is detailed. The main observation is that stability depends critically on the number of iterations performed.

97 MATHEMATICS AND COMPUTING↗

Bi-Level Dynamic Optimization with Feedback

This paper considers a bi-level real-time algorithmic framework for networked systems, consisting of several local controllers and a central controller. The central controller issues setpoints to the local controllers to optimize their operational objectives while satisfying system-wide constraints. In this context, the paper develops an online algorithm for tracking the optimal solution of the underlying dynamic optimization problem. The design of the algorithm is based on a projected-gradient method, suitably modified to accommodate appropriate measurements (i.e., feedback). Optimality claims are established in terms of the dynamic regret of the algorithm; the latter is a natural performance criterion in nonstationary environments associated with real-time control problems. Finally, the application of the algorithm to real-time control of power setpoints in an electrical grid is illustrated.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Fast Multigrid Reduction-in-Time for Advection via Modified Semi-Lagrangian Coarse-Grid Operators

Many iterative parallel-in-time algorithms have been shown to be highly efficient for diffusion-dominated partial differential equations (PDEs) but are inefficient or even divergent when applied to advection-dominated PDEs. We consider the application of the multigrid reduction-in-time (MGRIT) algorithm to linear advection PDEs. Here, the key to efficient time integration with this method is using a coarse-grid operator that provides a sufficiently accurate approximation to the so-called ideal coarse-grid operator. For certain classes of semi-Lagrangian discretizations, we present a novel semi-Lagrangian-based coarse-grid operator that leads to fast and scalable multilevel time integration of linear advection PDEs. The coarse-grid operator is composed of a semi-Lagrangian discretization followed by a correction term, with the correction designed so that the leading-order truncation error of the composite operator is approximately equal to that of the ideal coarse-grid operator. Parallel results show substantial speed-ups over sequential time integration for variable-wave-speed advection problems in one and two spatial dimensions, and using high-order discretizations up to order five. The proposed approach establishes the first practical method that provides small and scalable MGRIT iteration counts for advection problems.

97 MATHEMATICS AND COMPUTING↗

A non-intrusive parallel-in-time adjoint solver with the XBraid library

In this paper, an adjoint solver for the multigrid-in-time software library XBraid is presented. XBraid provides a non-intrusive approach for simulating unsteady dynamics on multiple processors while parallelizing not only in space but also in the time domain (XBraid: Parallel multigrid in time, http://llnl.gov/casc/xbraid). It applies an iterative multigrid reduction in time algorithm to existing spatially parallel classical time propagators and computes the unsteady solution parallel in time. Techniques from Automatic Differentiation are used to develop a consistent discrete adjoint solver which provides sensitivity information of output quantities with respect to design parameter changes. The adjoint code runs backwards through the primal XBraid actions and accumulates gradient information parallel in time. It is highly non-intrusive as existing adjoint time propagators can easily be integrated through the adjoint interface. The adjoint code is validated on advection-dominated flow with periodic upstream boundary condition. We report it provides similar strong scaling results as the primal XBraid solver and offers great potential for speeding up the overall computational costs for sensitivity analysis using multiple processors.

97 MATHEMATICS AND COMPUTING↗

Efficient Multigrid Reduction-in-Time for Method-of-Lines Discretizations of Linear Advection

Parallel-in-time methods for partial differential equations (PDEs) have been the subject of intense development over recent decades, particularly for diffusion-dominated problems. It has been widely reported in the literature, however, that many of these methods perform quite poorly for advection-dominated problems. In this report we analyze the particular iterative parallel-in-time algorithm of multigrid reduction-in-time (MGRIT) for discretizations of constant-wave-speed linear advection problems. We focus on common method-of-lines discretizations that employ upwind finite differences in space and Runge-Kutta methods in time. Using a convergence framework we developed in previous work, we prove for a subclass of these discretizations that, if using the standard approach of rediscretizing the fine-grid problem on the coarse grid, robust MGRIT convergence with respect to CFL number and coarsening factor is not possible. This poor convergence and non-robustness is caused, at least in part, by an inadequate coarse-grid correction for smooth Fourier modes in space-time known as characteristic components. We propose an alternative coarse-grid operator that provides a better correction of these modes. This coarse-grid operator is related to previous work and uses a semi-Lagrangian discretization combined with an implicitly treated truncation error correction. Theory and numerical experiments show the proposed coarse-grid operator yields fast MGRIT convergence for many of the method-of-lines discretizations considered, including for both implicit and explicit discretizations of high order. Parallel results demonstrate speed-up over sequential time-stepping.

97 MATHEMATICS AND COMPUTING↗

Identification of heavy-flavour jets with the CMS detector in pp collisions at 13 TeV

Many measurements and searches for physics beyond the standard model at the LHC rely on the efficient identification of heavy-flavour jets, i.e. jets originating from bottom or charm quarks. In this paper, the discriminating variables and the algorithms used for heavy-flavour jet identification during the first years of operation of the CMS experiment in proton-proton collisions at a centre-of-mass energy of 13 TeV, are presented. Heavy-flavour jet identification algorithms have been improved compared to those used previously at centre-of-mass energies of 7 and 8 TeV. For jets with transverse momenta in the range expected in simulated events, these new developments result in an efficiency of 68% for the correct identification of a b jet for a probability of 1% of misidentifying a light-flavour jet. The improvement in relative efficiency at this misidentification probability is about 15%, compared to previous CMS algorithms. In addition, for the first time algorithms have been developed to identify jets containing two b hadrons in Lorentz-boosted event topologies, as well as to tag c jets. The large data sample recorded in 2016 at a centre-of-mass energy of 13 TeV has also allowed the development of new methods to measure the efficiency and misidentification probability of heavy-flavour jet identification algorithms. The b jet identification efficiency is measured with a precision of a few per cent at moderate jet transverse momenta (between 30 and 300 GeV) and about 5% at the highest jet transverse momenta (between 500 and 1000 GeV).

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

Automatic Step Size Selection in Random Walk Metropolis Algorithms

Practitioners of Markov chain Monte Carlo (MCMC) may hesitate to use random walk Metropolis- Hastings algorithms, especially variable-at-a-time algorithms with many parameters, because these algorithms require users to select values of tuning parameters (step sizes). These algorithms perform poorly if the step sizes are set to be too low or too high. We show in this paper that it is not difficult for an algorithm to tune these step sizes automatically to obtain a desired acceptance probability, since the logit of the acceptance probability is very nearly linear in the log of the step size, with known slope coefficient. These ideas work in most applications, including single parameter or block moves on the linear, log, or logit scales. We discuss the implementation of this algorithm in the software package YADAS.

97 MATHEMATICS AND COMPUTING↗

Real-time adaptive aircraft scheduling

One of the most important functions of any air traffic management system is the assignment of ground-holding times to flights, i.e., the determination of whether and by how much the take-off of a particular aircraft headed for a congested part of the air traffic control (ATC) system should be postponed in order to reduce the likelihood and extent of airborne delays. An analysis is presented for the fundamental case in which flights from many destinations must be scheduled for arrival at a single congested airport; the formulation is also useful in scheduling the landing of airborne flights within the extended terminal area. A set of approaches is described for addressing a deterministic and a probabilistic version of this problem. For the deterministic case, where airport capacities are known and fixed, several models were developed with associated low-order polynomial-time algorithms. For general delay cost functions, these algorithms find an optimal solution. Under a particular natural assumption regarding the delay cost function, an extremely fast (O(n ln n)) algorithm was developed. For the probabilistic case, using an estimated probability distribution of airport capacities, a model was developed with an associated low-order polynomial-time heuristic algorithm with useful properties.

Kolitz, Stephan E.↗

Rocket engine failure detection using system identification techiques

The theoretical foundation and application of two univariate failure detection algorithms to Space Shuttle Main Engine (SSME) test firing data is presented. Both algorithms were applied to data collected during steady state operation of the engine. One algorithm, the time series algorithm, is based on time series techniques and involves the computation of autoregressive models. Times series techniques have been previously applied to SSME data. The second algorithm is based on standard signal processing techniques. It consists of tracking the variations in the average signal power with time. The average signal power algorithm is a newly proposed SSME failure detection algorithm. Seven nominal test firings were used to develop failure indication thresholds for each algorithm. These thresholds were tested using four anomalous firings and one additional nominal firing. Both algorithms provided significantly earlier failure indication times than did the current redline limit system. Neither algorithm gave false failure indications for the nominal firing. The strengths and weaknesses of the two algorithms are discussed and compared. The average signal algorithm was found to have several advantages over the time series algorithm.

Meyer, Claudia M.↗

Rocket engine failure detection using system identification techniques

The theoretical foundation and application of two univariate failure detection algorithms to Space Shuttle Main Engine (SSME) test firing data is presented. Both algorithms were applied to data collected during steady state operation of the engine. One algorithm, the time series algorithm, is based on time series techniques and involves the computation of autoregressive models. Time series techniques have been previously applied to SSME data. The second algorithm is based on standard signal processing techniques. It consists of tracking the variations in the average signal power with time. The average signal power algorithm is a newly proposed SSME failure detection algorithm. Seven nominal test firings were used to develop failure indication thresholds for each algorithm. These thresholds were tested using four anomalous firings and one additional nominal firing. Both algorithms provided significantly earlier failure indication times than did the current redline limit system. Neither algorithm gave false failure indications for the nominal firing. The strengths and weaknesses of the two algorithms are discussed and compared. The average signal algorithm was found to have several advantages over the time series algorithm.

Meyer, Claudia M.↗

Comparison of Fault Detection Algorithms for Real-time Diagnosis in Large-Scale System

In this paper, we present a review of different real-time capable algorithms to detect and isolate component failures in large-scale systems in the presence of inaccurate test results. A sequence of imperfect test results (as a row vector of I's and O's) are available to the algorithms. In this case, the problem is to recover the uncorrupted test result vector and match it to one of the rows in the test dictionary, which in turn will isolate the faults. In order to recover the uncorrupted test result vector, one needs the accuracy of each test. That is, its detection and false alarm probabilities are required. In this problem, their true values are not known and, therefore, have to be estimated online. Other major aspects in this problem are the large-scale nature and the real-time capability requirement. Test dictionaries of sizes up to 1000 x 1000 are to be handled. That is, results from 1000 tests measuring the state of 1000 components are available. However, at any time, only 10-20% of the test results are available. Then, the objective becomes the real-time fault diagnosis using incomplete and inaccurate test results with online estimation of test accuracies. It should also be noted that the test accuracies can vary with time --- one needs a mechanism to update them after processing each test result vector. Using Qualtech's TEAMS-RT (system simulation and real-time diagnosis tool), we test the performances of 1) TEAMSAT's built-in diagnosis algorithm, 2) Hamming distance based diagnosis, 3) Maximum Likelihood based diagnosis, and 4) HidderMarkov Model based diagnosis.

Kirubarajan, Thiagalingam↗

Comparison between variable and fixed dwell-time PN acquisition algorithms

Pseudo noise (PN) spread spectrum systems require a very accurate alignment between the PN code epochs at the transmitter and receiver. This synchronism is typically established through a two-step algorithm, including a coarse synchronization procedure and a fine synchronization procedure. A standard approach for the coarse synchronization is a sequential search over all code phases. The measurement of the power in the filtered signal is used to either accept or reject the code phase under test as the phase of the received PN code. This acquisition strategy, called a single dwell-time system, has been analyzed by Holmes and Chen (1977). A synopsis of the field of sequential analysis as it applies to the PN acquisition problem is provided. From this, the implementation of the variable dwell time algorithm as a sequential probability ratio test is developed. The performance of this algorithm is compared to the optimum detection algorithm and to the fixed dwell-time system.

Braun, W. R.↗

Numerical stability analysis of the pseudo-spectral analytical time-domain PIC algorithm

The pseudo-spectral analytical time-domain (PSATD) particle-in-cell (PIC) algorithm solves the vacuum Maxwell's equations exactly, has no Courant time-step limit (as conventionally defined), and offers substantial flexibility in plasma and particle beam simulations. It is, however, not free of the usual numerical instabilities, including the numerical Cherenkov instability, when applied to relativistic beam simulations. This paper derives and solves the numerical dispersion relation for the PSATD algorithm and compares the results with corresponding behavior of the more conventional pseudo-spectral time-domain (PSTD) and finite difference time-domain (FDTD) algorithms. In general, PSATD offers superior stability properties over a reasonable range of time steps. More importantly, one version of the PSATD algorithm, when combined with digital filtering, is almost completely free of the numerical Cherenkov instability for time steps (scaled to the speed of light) comparable to or smaller than the axial cell size.

97 MATHEMATICS AND COMPUTING↗

Automatic Transformation of MPI Programs to Asynchronous, Graph-Driven Form

The goals of this project are to develop new, scalable, high-fidelity algorithms for atomic-level simulations and program transformations that automatically restructure existing applications, enabling them to scale forward to Petascale systems and beyond. The techniques enable legacy MPI application code to exploit greater parallelism though increased latency hiding and improved workload assignment. The techniques were successfully demonstrated on high-end scalable systems located at DOE laboratories. Besides the automatic MPI program transformations efforts, the project also developed several new scalable algorithms for ab-initio molecular dynamics, including new massively parallel algorithms for hybrid DFT and new parallel in time algorithms for molecular dynamics and ab-initio molecular dynamics. These algorithms were shown to scale to very large number of cores, and they were designed to work in the latency hiding framework developed in this project. The effectiveness of the developments was enhanced by the direct application to real grand challenge simulation problems covering a wide range of technologically important applications, time scales and accuracies. These included the simulation of the electronic structure of mineral/fluid interfaces, the very accurate simulation of chemical reactions in microsolvated environments, and the simulation of chemical behavior in very large enzyme reactions.

97 MATHEMATICS AND COMPUTING↗