Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “fast algorithm”

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 55 records · Page 3
All sourcesNASA NTRSDOE OSTI
NASA NTRS1975

Chandrasekhar-type algorithms for fast recursive estimation in linear systems with constant parameters

In this recursive method proposed, the gain matrix for the Kalman filter and the convariance of the state vector are computed not via the Riccati equation, but from certain other equations. These differential equations are of Chandrasekhar-type. The 'invariant imbedding' idea resulted in the reduction of the basic boundary value problem of transport theory to an equivalent initial value system, a significant computational advance. Initial value experience showed that there is some computational savings in the method and the loss of positive definiteness of the covariance matrix is less vulnerable.

Choudhury, A. K.↗
NASA NTRS1987

A fast MPP algorithm for Ising spin exchange simulations

A very efficient massively parallel processor (MPP) algorithm is described for performing one important class of Ising spin simulations. Results and physical significance of MPP calculations using the method described is discussed elsewhere. A few comments, however, are made on the problem under study and results so far are reported. Ted Einstein provided guidance in interpreting the initial results and in suggesting calculations to perform.

Sullivan, Francis↗
NASA NTRS1988

A Fourier analysis for a fast simulation algorithm

This paper presents a derivation of compact expressions for the Fourier series analysis of the steady-state solution of a typical switching converter. The modeling procedure for the simulation and the steady-state solution is described, and some desirable traits for its matrix exponential subroutine are discussed. The Fourier analysis algorithm was tested on a phase-controlled parallel-loaded resonant converter, providing an experimental confirmation.

King, Roger J.↗
NASA NTRS1991

A fast, reliable algorithm for computing frequency responses of state space models

Computation of frequency responses for large order systems described by time invariant state space systems often provides a bottleneck in control system analysis. It is shown that banding the A-matrix in the state space model can effectively reduce the computation time for such systems while maintaining reliability in the results produced.

Wette, Matt↗
NASA NTRS1993

Fast parallel algorithms that compute transitive closure of a fuzzy relation

The notion of a transitive closure of a fuzzy relation is very useful for clustering in pattern recognition, for fuzzy databases, etc. The original algorithm proposed by L. Zadeh (1971) requires the computation time O(n(sup 4)), where n is the number of elements in the relation. In 1974, J. C. Dunn proposed a O(n(sup 2)) algorithm. Since we must compute n(n-1)/2 different values s(a, b) (a not equal to b) that represent the fuzzy relation, and we need at least one computational step to compute each of these values, we cannot compute all of them in less than O(n(sup 2)) steps. So, Dunn's algorithm is in this sense optimal. For small n, it is ok. However, for big n (e.g., for big databases), it is still a lot, so it would be desirable to decrease the computation time (this problem was formulated by J. Bezdek). Since this decrease cannot be done on a sequential computer, the only way to do it is to use a computer with several processors working in parallel. We show that on a parallel computer, transitive closure can be computed in time O((log(sub 2)(n))2).

Kreinovich, Vladik YA.↗
NASA NTRS1992

Fast projection algorithm for unstructured meshes

Two projection operators are presented which employ a very efficient point-location algorithm. For a wide variety of practical problems, the projection cost was reduced by a substantial factor when compared with simpler procedures. Problems involving high levels of local refinement do not impede the point-location algorithm, and the extension of these concept to three dimensions has been implemented with no additional difficulty. Nodal interpolation is noted to be an excellent projection operator when cost is a criterion, while consistent-mass L2-projection furnishes the highest accuracy.

Jansen, Kenneth↗
NASA NTRS1993

A fast recursive algorithm for molecular dynamics simulation

The present recursive algorithm for solving molecular systems' dynamical equations of motion employs internal variable models that reduce such simulations' computation time by an order of magnitude, relative to Cartesian models. Extensive use is made of spatial operator methods recently developed for analysis and simulation of the dynamics of multibody systems. A factor-of-450 speedup over the conventional O(N-cubed) algorithm is demonstrated for the case of a polypeptide molecule with 400 residues.

Jain, A.↗
NASA NTRS1999

Fast Quantum Algorithm for Predicting Descriptive Statistics of Stochastic Processes

Stochastic processes are used as a modeling tool in several sub-fields of physics, biology, and finance. Analytic understanding of the long term behavior of such processes is only tractable for very simple types of stochastic processes such as Markovian processes. However, in real world applications more complex stochastic processes often arise. In physics, the complicating factor might be nonlinearities; in biology it might be memory effects; and in finance is might be the non-random intentional behavior of participants in a market. In the absence of analytic insight, one is forced to understand these more complex stochastic processes via numerical simulation techniques. In this paper we present a quantum algorithm for performing such simulations. In particular, we show how a quantum algorithm can predict arbitrary descriptive statistics (moments) of N-step stochastic processes in just O(square root of N) time. That is, the quantum complexity is the square root of the classical complexity for performing such simulations. This is a significant speedup in comparison to the current state of the art.

Williams Colin P.↗
NASA NTRS1999

Fast Quantum Algorithms for Numerical Integrals and Stochastic Processes

We discuss quantum algorithms that calculate numerical integrals and descriptive statistics of stochastic processes. With either of two distinct approaches, one obtains an exponential speed increase in comparison to the fastest known classical deterministic algotithms and a quadratic speed increase incomparison to classical Monte Carlo methods.

quantum algorithms numerical integrals↗
NASA NTRS2017

Fast Optimization for Aircraft Descent and Approach Trajectory

We address problem of on-line scheduling of the aircraft descent and approach trajectory. We formulate a general multiphase optimal control problem for optimization of the descent trajectory and review available methods of its solution. We develop a fast algorithm for solution of this problem using two key components: (i) fast inference of the dynamical and control variables of the descending trajectory from the low dimensional flight profile data and (ii) efficient local search for the resulting reduced dimensionality non-linear optimization problem. We compare the performance of the proposed algorithm with numerical solution obtained using optimal control toolbox General Pseudospectral Optimal Control Software. We present results of the solution of the scheduling problem for aircraft descent using novel fast algorithm and discuss its future applications.

Luchinsky, Dmitry G.↗
NASA NTRS1996

Fast Parallel Computation Of Multibody Dynamics

Constraint-force algorithm fast, efficient, parallel-computation algorithm for solving forward dynamics problem of multibody system like robot arm or vehicle. Solves problem in minimum time proportional to log(N) by use of optimal number of processors proportional to N, where N is number of dynamical degrees of freedom: in this sense, constraint-force algorithm both time-optimal and processor-optimal parallel-processing algorithm.

Fijany, Amir↗
NASA NTRS1990

Robust control of systems with real parameter uncertainty and unmodelled dynamics

Two significant contributions have been made during this research period in the research 'Robust Control of Systems with Real Parameter Uncertainty and Unmodelled Dynamics' under NASA Research Grant NAG-1-1102. They are: (1) a fast algorithm for computing the optimal H(sub infinity) norm for the four-block, the two block, or the one-block optimal H(sub infinity) optimization problem; and (2) a construction of an optimal H infinity controller without numerical difficulty. In using GD (Glover and Doyle) or DGKF (Doyle, Glover, Khargonekar, and Francis) approach to solve the standard H infinity norm which required bisection search. In this research period, we developed a very fast iterative algorithm for this computation. Our algorithm was developed based on hyperbolic interpolations which is much faster than any existing algorithm. The lower bound of the parameter, gamma, in the H infinity Riccati equation for solution existence is shown to be the square root of the supremum over all frequencies of the maximum eigenvalue of a given transfer matrix which can be computed easily. The lower band of gamma such that the H infinity Riccati equation has positive semidefinite solution can be also obtained by hyperbolic interpolation search. Another significant result in this research period is the elimination of the numerical difficulties arising in the construction of an optimal H infinity controller by directly applying the Glover and Doyle's state-space formulas. With the fast iterative algorithm for the computation of the optimal H infinity norm and the reliable construction of an optimal H infinity controller, we are ready to apply these tools in the design of robust controllers for the systems with unmodelled uncertainties. These tools will be also very useful when we consider systems with structured uncertainties.

Chang, Bor-Chin↗
NASA NTRS1989

Totally parallel multilevel algorithms for sparse elliptic systems

The fastest known algorithms for the solution of a large elliptic boundary value problem on a massively parallel hypercube all require O(log(n)) floating point operations and O(log(n)) distance-1 communications, if massively parallel is defined to mean a number of processors proportional to the size n of the problem. The Totally Parallel Multilevel Algorithm (TPMA) that has, as special cases, four of these fast algorithms is described. These four algorithms are Parallel Superconvergent Multigrid (PSMG), Robust Multigrid, the Fast Fourier Transformation (FFT) based Spectral Algorithm, and Parallel Cyclic Reduction. The algorithm TPMA, when described recursively, has four steps: (1) project to a collection of interlaced, coarser problems at the next lower level; (2) apply TPMA, recursively, to each of these lower level problems, solving directly at the lowest level; (3) interpolate these approximate solutions to the finer grid, and to verage them to form an approximate solution on this grid; and (4) refine this approximate solution with a defect-correction step, using a local approximate inverse. Choice of the projection operator (P), the interpolation operator (Q), and the smoother (S) determines the class of problems on which TPMA is most effective. There are special cases in which the first three steps produce an exact solution, and the smoother is not needed (e.g., constant coefficient operators).

Frederickson, Paul O.↗
NASA NTRS1994

Algorithms For A Fast Universal Noiseless Coder

Report discusses some algorithms for fast, high-performance universal noiseless coder adaptively generating nearly optimal variable-length codes. Coders based on principles discussed in reports described in "Some Practical Universal Noiseless Coding Techniques" (NPO-18833) and "Optimality of Variable-Length Codes" (NPO-18834). Coding algorithms of present report independently implemented in custom-made very-large-scale integrated-circuit coding modules.

Yeh, Pen-Shu↗
NASA NTRS2002

A Discontinuous Galerkin Discretization of the Eikonal Equation on Curved Piecewise Isoparametric Triangulated Manifolds

This viewgraph presentation provides information on optimizing the travel distance between two points on a curved surface. The presentation addresses the single source shortest path problem, fast algorithms for estimating the eikonal equation, fast schemes and barrier theorems, and the discontinuous Galerkin method, including hyperbolic causality, finite element method, scalars, and marching the discontinuous Galerkin Eikonal approximation.

Barth, TIm↗