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 451 records · Page 25
All sourcesNASA NTRSDOE OSTI
NASA NTRS2006

A Discussion of the Discrete Fourier Transform Execution on a Typical Desktop PC

This paper will discuss and compare the execution times of three examples of the Discrete Fourier Transform (DFT). The first two examples will demonstrate the direct implementation of the algorithm. In the first example, the Fourier coefficients are generated at the execution of the DFT. In the second example, the coefficients are generated prior to execution and the DFT coefficients are indexed at execution. The last example will demonstrate the Cooley- Tukey algorithm, better known as the Fast Fourier Transform. All examples were written in C executed on a PC using a Pentium 4 running at 1.7 Ghz. As a function of N, the total complex data size, the direct implementation DFT executes, as expected at order of N2 and the FFT executes at order of N log2 N. At N=16K, there is an increase in processing time beyond what is expected. This is not caused by implementation but is a consequence of the effect that machine architecture and memory hierarchy has on implementation. This paper will include a brief overview of digital signal processing, along with a discussion of contemporary work with discrete Fourier processing.

White, Michael J.↗
NASA NTRS2015

SOSS User Guide

This User Guide describes SOSS (Surface Operations Simulator and Scheduler) software build and graphic user interface. SOSS is a desktop application that simulates airport surface operations in fast time using traffic management algorithms. It moves aircraft on the airport surface based on information provided by scheduling algorithm prototypes, monitors separation violation and scheduling conformance, and produces scheduling algorithm performance data.

air traffic control↗
NASA NTRS2016

Optimized Route Capability (ORC) Intelligent Offloading of Congested Arrival Routes

The Optimized Route Capability (ORC) concept is designed to enable intelligent offloading of congested arrival routes. When ORC predicts arrival route congestion as projected excess arrival meter fix delay, automation offers decision support to traffic managers by identifying candidate flights to strategically reroute to alternate meter fixes and alleviate the congestion. This concept was applied to a model of arrival operations into Houston International Airport. An arrival rush from the Northeast was simulated in fast-time to analyze ORC algorithm behavior. The results demonstrate how strategically rerouting a few flights to alternate meter fixes not only has the potential to manage meter fix delay (and possibly the need for traffic management initiatives applied upstream), but may also increase airport capacity utilization and reduce total flight delay.

Zelinski, Shannon↗
NASA NTRSDate not supplied

Evaluation of Climate Fingerprinting Sounder Product (ClimFiSP) Air Temperature and H2O Trends

Climate fingerprinting Sounder Product (ClimFiSP) provides gridded (0.5x0.5) daily skin temperature, surface emissivity, air temperature, water vapor, trace gases, and cloud properties, which derived from IR hyper-spectral radiance measured by AIRS on Aqua and CrIS on SNPP and JPSS series. In this work, the ClimFiSP daily air temperature and H2O were retrieved on 98 pressure levels by applying the spectral fingerprint algorithm on 0.5x0.5 gridded daily mean radiances from Climate Hyperspectral Infrared Radiance Product (CHIRP). CHIRP is a stable climate-quality radiance time series spanning AIRS and CrIS. The air temperature and H2O monthly data and trends were calculated from the more than two decades long CHIRP AIRS data. Troposphere warming and stratosphere cooling can be seen in both ClimFiSP and ERA5 air temperature data. The ClimFiSP air temperature trends are also compared with the MW sounding air temperature trends to validate the ClimFiSP air temperature results. The H2O trends on upper troposphere are evaluated by comparing with the ERA5 H2O trends, and results show a reasonable agreement with two sets of results. The ClimFiSP algorithm provides a unique and fast way to retrieve the spatial-temporal change in climate variables from the corresponding change in radiances, gridded at the same spatial-temporal scale. This greatly facilitates the procession of long-term climate data records.

ClimFiSP↗
NASA NTRS1989

Parallel processing environment for multi-flexible body dynamics

The implementation of a dynamics solution algorithm with inherent parallelism which is applicable to the dynamics of large flexible space structures is described. The algorithm is unique in that parts of the solution can be computed simultaneously by working with different branches of its tree topology. The algorithm exhibits close to 0(n) type behavior. The data flow within the solution algorithm is discussed along with results from its implementation in a multiprocessing environment. A model of the United States Space Station is used as an example. The results show that, with fast multiple scalar processors, an efficient algorithm, and symbolically generated equations of motion, real-time performance can be achieved with present-day hardware technology, even with complex dynamical models.

Venugopal, Ravi↗
NASA NTRS2017

Computationally Efficient Motion Planning Algorithms for Agile Autonomous Vehicles in Cluttered Environments

Fast, real-time motion planning of an agile, autonomous vehicle in a cluttered environment, with many geometrically-fixed obstacles, is a very complex problem, especially because of the vehicle dynamics constraints and resource constrained computational capabilities onboard the vehicle. In this paper, we present computationally-efficient versions of our novel motion planning algorithm called the Spherical Expansion and Sequential Convex Programming (SE–SCP) algorithm. The SE–SCP algorithm first uses a spherical-expansion-based randomized sampling algorithm to explore the workspace. Oncea path is found from the start position to the goal position, the algorithm computes a locally optimal trajectory, within its homotopy class for a desired cost function, by solving a sequence of convex optimization problems. Thus, the SE–SCP algorithm is anytime locally optimal and the trajectory is globally optimal if the number of samples tends to infinity. In this paper, we further enhance the computational efficiency of the SE–SCP algorithm using uni-directional and bi-directional rewiring techniques. We also present a detailed proof of the local optimality characteristics of the new SE–SCP algorithms for aspecial case of vehicle dynamics. Simulation examples involving quadrotor and spacecraft help demonstrate the effectiveness of our new algorithms.

Bandyopadhyay, Saptarshi↗
NASA NTRS2015

Wideband Digital Signal Processing Test-Bed for Radiometric RFI Mitigation

Radio Frequency Interference (RFI) is a persistent and growing problem experienced by spaceborne microwave radiometers. Recent missions such as SMOS, SMAP, and GPM has detected RFI in L, C, X, and K bands. To proactively deal with this issue, microwave radiometers must (1) Utilize new algorithms for RFI detection (2) Utilize fast digital back-ends that sample at hundreds of MHz. The wideband digital signal processing testbed (WB-RFI) is a platform that allows rapid deelopment and testing various RFI detection and mitigation algorithms.

signal processing↗
NASA NTRS2015

Wideband Digital Signal Processing Test-Bed for Radiometric RFI Mitigation

Radio Frequency Interference (RFI) is a persistent and growing problem experienced by spaceborne microwave radiometers. Recent missions such as SMOS, SMAP, and GPM have detected RFI in L, C, X, and K bands. To proactively deal with this issue, microwave radiometers must (1) Utilize new algorithms for RFI detection (2) Utilize fast digital back-ends that sample at hundreds of MHz. The wideband digital signal processing testbed (WB-RFI) is a platform that allows rapid development and testing various RFI detection and mitigation algorithms.

Bradley, Damon C.↗
NASA NTRS1997

Efficient Calculation of a Jitter/Stability Metric

A tool for computing a jitter/stability metric used in NASA requirements statements is developed. An efficient algorithm is given for computing this metric. Two ways of implementing it on a computer are discussed. One is optimized for computational speed while the other sacrifices some speed to conserve memory. Timing studies are given to show that the improvement of computation times using the present algorithm over previously existing techniques can run to several orders of magnitude, and that previous techniques were so costly that the present algorithm represents enabling technology. Further comparisons show that the memory conservative implementation runs at about half the speed of the fast implementation, but can cut the major data storage requirement of the fast implementation by 95-99%, making the algorithm implementable on much smaller computers, such as PC's, than it would be otherwise. Software for both implementations is included in version 2 of the NASA time and frequency domain analysis program PLATSIM.

Giesy, Daniel P.↗
NASA NTRS2021

Dense 3D-Reconstruction from Monocular Image Sequences for Computationally Constrained UAS

The ability to find safe landing sites over complex 3D terrain is an essential safety feature for fully autonomous small unmanned aerial systems (UAS), which requires on-board perception for 3D reconstruction and terrain analysis if the overflown terrain is unknown. This is a challenge for UAS that are limited in size, weight and computational power, such as small rotorcrafts executing autonomous missions on Earth, or in planetary applications such as the Mars Helicopter. For such a computationally constraint system, we propose a structure from motion approach that uses inputs from a single downward facing camera to produce dense point clouds of the overflown terrain in real time. In contrast to existing approaches, our method uses metric pose information from a visual-inertial odometry algorithm as camera pose priors, which allows deploying a fast pose refinement step to align camera frames such that a conventional stereo algorithm can be used for dense 3D reconstruction. We validate the performance of our approach with extensive evaluations in simulation, and demonstrate the feasibility with data from UAS flights.

Brockers, Roland↗
NASA NTRS1985

A General-applications Direct Global Matrix Algorithm for Rapid Seismo-acoustic Wavefield Computations

A new matrix method for rapid wave propagation modeling in generalized stratified media, which has recently been applied to numerical simulations in diverse areas of underwater acoustics, solid earth seismology, and nondestructive ultrasonic scattering is explained and illustrated. A portion of recent efforts jointly undertaken at NATOSACLANT and NORDA Numerical Modeling groups in developing, implementing, and testing a new fast general-applications wave propagation algorithm, SAFARI, formulated at SACLANT is summarized. The present general-applications SAFARI program uses a Direct Global Matrix Approach to multilayer Green's function calculation. A rapid and unconditionally stable solution is readily obtained via simple Gaussian ellimination on the resulting sparsely banded block system, precisely analogous to that arising in the Finite Element Method. The resulting gains in accuracy and computational speed allow consideration of much larger multilayered air/ocean/Earth/engineering material media models, for many more source-receiver configurations than previously possible. The validity and versatility of the SAFARI-DGM method is demonstrated by reviewing three practical examples of engineering interest, drawn from ocean acoustics, engineering seismology and ultrasonic scattering.

Schmidt, H.↗
NASA NTRS1989

Asynchronous multilevel adaptive methods for solving partial differential equations on multiprocessors - Performance results

The fast adaptive composite grid method (FAC) is an algorithm that uses various levels of uniform grids (global and local) to provide adaptive resolution and fast solution of PDEs. Like all such methods, it offers parallelism by using possibly many disconnected patches per level, but is hindered by the need to handle these levels sequentially. The finest levels must therefore wait for processing to be essentially completed on all the coarser ones. A recently developed asynchronous version of FAC, called AFAC, completely eliminates this bottleneck to parallelism. This paper describes timing results for AFAC, coupled with a simple load balancing scheme, applied to the solution of elliptic PDEs on an Intel iPSC hypercube. These tests include performance of certain processes necessary in adaptive methods, including moving grids and changing refinement. A companion paper reports on numerical and analytical results for estimating convergence factors of AFAC applied to very large scale examples.

Mccormick, S.↗
NASA NTRS1993

Structured adaptive grid generation using algebraic methods

The accuracy of the numerical algorithm depends not only on the formal order of approximation but also on the distribution of grid points in the computational domain. Grid adaptation is a procedure which allows optimal grid redistribution as the solution progresses. It offers the prospect of accurate flow field simulations without the use of an excessively timely, computationally expensive, grid. Grid adaptive schemes are divided into two basic categories: differential and algebraic. The differential method is based on a variational approach where a function which contains a measure of grid smoothness, orthogonality and volume variation is minimized by using a variational principle. This approach provided a solid mathematical basis for the adaptive method, but the Euler-Lagrange equations must be solved in addition to the original governing equations. On the other hand, the algebraic method requires much less computational effort, but the grid may not be smooth. The algebraic techniques are based on devising an algorithm where the grid movement is governed by estimates of the local error in the numerical solution. This is achieved by requiring the points in the large error regions to attract other points and points in the low error region to repel other points. The development of a fast, efficient, and robust algebraic adaptive algorithm for structured flow simulation applications is presented. This development is accomplished in a three step process. The first step is to define an adaptive weighting mesh (distribution mesh) on the basis of the equidistribution law applied to the flow field solution. The second, and probably the most crucial step, is to redistribute grid points in the computational domain according to the aforementioned weighting mesh. The third and the last step is to reevaluate the flow property by an appropriate search/interpolate scheme at the new grid locations. The adaptive weighting mesh provides the information on the desired concentration of points to the grid redistribution scheme. The evaluation of the weighting mesh is accomplished by utilizing the weight function representing the solution variation and the equidistribution law. The selection of the weight function plays a key role in grid adaptation. A new weight function utilizing a properly weighted boolean sum of various flowfield characteristics is defined. The redistribution scheme is developed utilizing Non-Uniform Rational B-Splines (NURBS) representation. The application of NURBS representation results in a well distributed smooth grid by maintaining the fidelity of the geometry associated with boundary curves. Several algebraic methods are applied to smooth and/or nearly orthogonalize the grid lines. An elliptic solver is utilized to smooth the grid lines if there are grid crossings. Various computational examples of practical interest are presented to demonstrate the success of these methods.

Yang, Jiann-Cherng↗
NASA NTRS2012

SURF IA Conflict Detection and Resolution Algorithm Evaluation

The Enhanced Traffic Situational Awareness on the Airport Surface with Indications and Alerts (SURF IA) algorithm was evaluated in a fast-time batch simulation study at the National Aeronautics and Space Administration (NASA) Langley Research Center. SURF IA is designed to increase flight crew situation awareness of the runway environment and facilitate an appropriate and timely response to potential conflict situations. The purpose of the study was to evaluate the performance of the SURF IA algorithm under various runway scenarios, multiple levels of conflict detection and resolution (CD&R) system equipage, and various levels of horizontal position accuracy. This paper gives an overview of the SURF IA concept, simulation study, and results. Runway incursions are a serious aviation safety hazard. As such, the FAA is committed to reducing the severity, number, and rate of runway incursions by implementing a combination of guidance, education, outreach, training, technology, infrastructure, and risk identification and mitigation initiatives [1]. Progress has been made in reducing the number of serious incursions - from a high of 67 in Fiscal Year (FY) 2000 to 6 in FY2010. However, the rate of all incursions has risen steadily over recent years - from a rate of 12.3 incursions per million operations in FY2005 to a rate of 18.9 incursions per million operations in FY2010 [1, 2]. The National Transportation Safety Board (NTSB) also considers runway incursions to be a serious aviation safety hazard, listing runway incursion prevention as one of their most wanted transportation safety improvements [3]. The NTSB recommends that immediate warning of probable collisions/incursions be given directly to flight crews in the cockpit [4].

Jones, Denise R.↗
NASA NTRS1989

Positive position control of robotic manipulators

The present, simple and accurate position-control algorithm, which is applicable to fast-moving and lightly damped robot arms, is based on the positive position feedback (PPF) strategy and relies solely on position sensors to monitor joint angles of robotic arms to furnish stable position control. The optimized tuned filters, in the form of a set of difference equations, manipulate position signals for robotic system performance. Attention is given to comparisons between this PPF-algorithm controller's experimentally ascertained performance characteristics and those of a conventional proportional controller.

Baz, A.↗
NASA NTRS2017

Low-Thrust Trajectory Optimization with Simplified SQP Algorithm

The problem of low-thrust trajectory optimization in highly perturbed dynamics is a stressing case for many optimization tools. Highly nonlinear dynamics and continuous thrust are each, separately, non-trivial problems in the field of optimal control, and when combined, the problem is even more difficult. This paper de-scribes a fast, robust method to design a trajectory in the CRTBP (circular restricted three body problem), beginning with no or very little knowledge of the system. The approach is inspired by the SQP (sequential quadratic programming) algorithm, in which a general nonlinear programming problem is solved via a sequence of quadratic problems. A few key simplifications make the algorithm presented fast and robust to initial guess: a quadratic cost function, neglecting the line search step when the solution is known to be far away, judicious use of end-point constraints, and mesh refinement on multiple shooting with fixed-step integration.In comparison to the traditional approach of plugging the problem into a “black-box” NLP solver, the methods shown converge even when given no knowledge of the solution at all. It was found that the only piece of information that the user needs to provide is a rough guess for the time of flight, as the transfer time guess will dictate which set of local solutions the algorithm could converge on. This robustness to initial guess is a compelling feature, as three-body orbit transfers are challenging to design with intuition alone. Of course, if a high-quality initial guess is available, the methods shown are still valid.We have shown that endpoints can be efficiently constrained to lie on 3-body repeating orbits, and that time of flight can be optimized as well. When optimizing the endpoints, we must make a trade between converging quickly on sub-optimal endpoints or converging more slowly on end-points that are arbitrarily close to optimal. It is easy for the mission design engineer to adjust this trade based on the problem at hand.The biggest limitation to the algorithm at this point is that multi-revolution transfers (greater than 2 revolutions) do not work nearly as well. This restriction comes in because the relationship between node 1 and node N becomes increasingly nonlinear as the angular distance grows. Trans-fers with more than about 1.5 complete revolutions generally require the line search to improve convergence. Future work includes: Comparison of this algorithm with other established tools; improvements to how multiple-revolution transfers are handled; parallelization of the Jacobian computation; in-creased efficiency for the line search; and optimization of many more trajectories between a variety of 3-body orbits.

Parrish, Nathan L.↗
NASA NTRS1983

Fast Computational Kinetics Program

Batch kinetics (1-D) algorithm development, stirred reactor (O-D) algorithm development, and interactive computer programs are summarized.

Pratt, D. T.↗
NASA NTRS1991

New developments in astrodynamics algorithms for autonomous rendezvous

A the core of any autonomous rendezvous guidance system must be two algorithms for solving Lambert's and Kepler's problems, the two fundamental problems in classical astrodynamics. Lambert's problem is to determine the trajectory connecting specified initial and terminal position vectors in a specified transfer time. The solution is the initial and terminal velocity vectors. Kepler's problem is to determine the trajectory that stems from a given initial state (position and velocity). The solution is the state of an earlier or later specified time. To be suitable for flight software, astrodynamics algorithms must be totally reliable, compact, and fast. Although solving Lambert's and Kepler's problems has challenged some of the world's finest minds for over two centuries, only in the last year have algorithms appeared that satisfy all three requirements just stated. This paper presents an evaluation of the most highly regarded Lambert and Kepler algorithms.

Klumpp, Allan R.↗