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.

SourceResearch connectionFrom yearThrough year

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 577 records · Page 32

All sources NASA NTRS DOE OSTI

NASA NTRS1979

A parameter-estimation subroutine package

Estimation subroutine package comprises fast, efficient, and simple least-squares data-processing algorithms for use in orbit determination and related analyses. Very reliable and general algorithms have been documented. Package contains collection of streamlined subroutines that can be used to solve large variety of parameter-estimation and filtering problems. Special routines are included for problems with colored process noise and covariance (factor) mapping.

Bierman, G.↗

NASA NTRS1989

Methods for local gravity field approximation

The most widely known modern method for estimating gravity field values from observed data is least-squares collocation. Its advantages are that it can make estimates at arbitrary locations based on irregularly spaced observations, and that it makes use of statistical information about errors in the input data while providing corresponding information about the quality of the output estimates. Disadvantages of collocation include the necessity of inverting square matrices of dimension equal to the number of data values and the need to assume covariance models for the gravity field and the data errors. Fourier methods are an important alternative to collocation; having the advantage of greater computational efficiency, but requiring data estimates to be on a regular grid and not using or providing statistical accuracy information. The GEOFAST algorithm is an implementation of collocation that achieves high computational efficiency by transforming the estimation equations into the frequency domain where an accurate approximation may be made to reduce the workload. The forward and inverse Fast Fourier Transforms (FFTs) are utilized. The accuracy and computational efficiency of the GEOFAST algorithm is demonstrated using two sets of synthetic gravity data: marine gravity for an ocean trench region including wavelengths longer than 200 km; and local land gravity containing wavelengths as short as 5 km. These results are discussed along with issues such as the advantages of first removing reference field models before carrying out the estimation algorithm.

Sailor, R. V.↗

NASA NTRS1997

Communication Studies of DMP and SMP Machines

Understanding the interplay between machines and problems is key to obtaining high performance on parallel machines. This paper investigates the interplay between programming paradigms and communication capabilities of parallel machines. In particular, we explicate the communication capabilities of the IBM SP-2 distributed-memory multiprocessor and the SGI PowerCHALLENGEarray symmetric multiprocessor. Two benchmark problems of bitonic sorting and Fast Fourier Transform are selected for experiments. Communication-efficient algorithms are developed to exploit the overlapping capabilities of the machines. Programs are written in Message-Passing Interface for portability and identical codes are used for both machines. Various data sizes and message sizes are used to test the machines' communication capabilities. Experimental results indicate that the communication performance of the multiprocessors are consistent with the size of messages. The SP-2 is sensitive to message size but yields a much higher communication overlapping because of the communication co-processor. The PowerCHALLENGEarray is not highly sensitive to message size and yields a low communication overlapping. Bitonic sorting yields lower performance compared to FFT due to a smaller computation-to-communication ratio.

Sohn, Andrew↗

NASA NTRS2006

Grayscale Optical Correlator Workbench

Grayscale Optical Correlator Workbench (GOCWB) is a computer program for use in automatic target recognition (ATR). GOCWB performs ATR with an accurate simulation of a hardware grayscale optical correlator (GOC). This simulation is performed to test filters that are created in GOCWB. Thus, GOCWB can be used as a stand-alone ATR software tool or in combination with GOC hardware for building (target training), testing, and optimization of filters. The software is divided into three main parts, denoted filter, testing, and training. The training part is used for assembling training images as input to a filter. The filter part is used for combining training images into a filter and optimizing that filter. The testing part is used for testing new filters and for general simulation of GOC output. The current version of GOCWB relies on the mathematical software tools from MATLAB binaries for performing matrix operations and fast Fourier transforms. Optimization of filters is based on an algorithm, known as OT-MACH, in which variables specified by the user are parameterized and the best filter is selected on the basis of an average result for correct identification of targets in multiple test images.

Hanan, Jay↗

NASA NTRS2011

Semi-Supervised Novelty Detection with Adaptive Eigenbases, and Application to Radio Transients

We present a semi-supervised online method for novelty detection and evaluate its performance for radio astronomy time series data. Our approach uses adaptive eigenbases to combine 1) prior knowledge about uninteresting signals with 2) online estimation of the current data properties to enable highly sensitive and precise detection of novel signals. We apply the method to the problem of detecting fast transient radio anomalies and compare it to current alternative algorithms. Tests based on observations from the Parkes Multibeam Survey show both effective detection of interesting rare events and robustness to known false alarm anomalies.

anomaly detection↗

NASA NTRS2017

Feature Detection and Curve Fitting Using Fast Walsh Transforms for Shock Tracking: Applications

Walsh functions form an orthonormal basis set consisting of square waves. Square waves make the system well suited for detecting and representing functions with discontinuities. Given a uniform distribution of 2p cells on a one-dimensional element, it has been proven that the inner product of the Walsh Root function for group p with every polynomial of degree < or = (p - 1) across the element is identically zero. It has also been proven that the magnitude and location of a discontinuous jump, as represented by a Heaviside function, are explicitly identified by its Fast Walsh Transform (FWT) coefficients. These two proofs enable an algorithm that quickly provides a Weighted Least Squares fit to distributions across the element that include a discontinuity. The detection of a discontinuity enables analytic relations to locally describe its evolution and provide increased accuracy. Time accurate examples are provided for advection, Burgers equation, and Riemann problems (diaphragm burst) in closed tubes and de Laval nozzles. New algorithms to detect up to two C0 and/or C1 discontinuities within a single element are developed for application to the Riemann problem, in which a contact discontinuity and shock wave form after the diaphragm bursts.

Gnoffo, Peter A.↗

NASA NTRSDate not supplied

Runtime Monitoring with R2U2 for Aircraft Systems with Neural Networks

R2U2 (Realizable, Responsive, Unobtrusive Unit) is a hardware-supported tool and framework for real-time system monitoring and software health management of cyber-physical systems. During system operation, R2U2 continuously monitors properties about safety, performance, and security of the vehicle and its vital components and can perform diagnostic reasoning. Efficient observers for past-time and future-time Metric Temporal Logic, fast reasoners for Bayesian Networks, and model-based prognostics algorithms are key components of R2U2 and designed for minimal computational footprint. R2U2 has been implemented in software supporting ROS, NASA's cFS/cFE, and Simulink and as an FPGA configuration. The synergistic combination of monitors and observers in R2U2 makes it possible to design powerful models for system runtime monitoring, diagnostics, software health management, prognostics, and security monitoring. In this presentation, I will give a detailed overview of the R2U2 architecture and its features and will discuss the application of R2U2 for safety-monitoring of a neural-network based autonomous centerline tracking system (ACT) for autonomous aircraft.

Runtime Monitoring↗

NASA NTRS2010

Exhaustive Versus Randomized Searchers for Nonlinear Optimization in 21st Century Computing: Solar Application

We present a simple multi-dimensional exhaustive search method to obtain, in a reasonable time, the optimal solution of a nonlinear programming problem. It is more relevant in the present day non-mainframe computing scenario where an estimated 95% computing resources remains unutilized and computing speed touches petaflops. While the processor speed is doubling every 18 months, the band width is doubling every 12 months, and the hard disk space is doubling every 9 months. A randomized search algorithm or, equivalently, an evolutionary search method is often used instead of an exhaustive search algorithm. The reason is that a randomized approach is usually polynomial-time, i.e., fast while an exhaustive search method is exponential-time i.e., slow. We discuss the increasing importance of exhaustive search in optimization with the steady increase of computing power for solving many real-world problems of reasonable size. We also discuss the computational error and complexity of the search algorithm focusing on the fact that no measuring device can usually measure a quantity with an accuracy greater than 0.005%. We stress the fact that the quality of solution of the exhaustive search - a deterministic method - is better than that of randomized search. In 21 st century computing environment, exhaustive search cannot be left aside as an untouchable and it is not always exponential. We also describe a possible application of these algorithms in improving the efficiency of solar cells - a real hot topic - in the current energy crisis. These algorithms could be excellent tools in the hands of experimentalists and could save not only large amount of time needed for experiments but also could validate the theory against experimental results fast.

Sen, Syamal K.↗

NASA NTRS2011

Fast Simulators for Satellite Cloud Optical Centroid Pressure Retrievals, 1. Evaluation of OMI Cloud Retrievals

We have developed a relatively simple scheme for simulating retrieved cloud optical centroid pressures (OCP) from satellite solar backscatter observations. We have compared simulator results with those from more detailed retrieval simulators that more fully account for the complex radiative transfer in a cloudy atmosphere. We used this fast simulator to conduct a comprehensive evaluation of cloud OCPs from the two OMI algorithms using collocated data from CloudSat and Aqua MODIS, a unique situation afforded by the A-train formation of satellites. We find that both OMI algorithms perform reasonably well and that the two algorithms agree better with each other than either does with the collocated CloudSat data. This indicates that patchy snow/ice, cloud 3D, and aerosol effects not simulated with the CloudSat data are affecting both algorithms similarly. We note that the collocation with CloudSat occurs mainly on the East side of OMI's swath. Therefore, we are not able to address cross-track biases in OMI cloud OCP retrievals. Our fast simulator may also be used to simulate cloud OCP from output generated by general circulation models (GCM) with appropriate account of cloud overlap. We have implemented such a scheme and plan to compare OMI data with GCM output in the near future.

Joiner, J.↗

NASA NTRS1976

A numerical comparison of discrete Kalman filtering algorithms - An orbit determination case study

An improved Kalman filter algorithm based on a modified Givens matrix triangularization technique is proposed for solving a nonstationary discrete-time linear filtering problem. The proposed U-D covariance factorization filter uses orthogonal transformation technique; measurement and time updating of the U-D factors involve separate application of Gentleman's fast square-root-free Givens rotations. Numerical stability and accuracy of the algorithm are compared with those of the conventional and stabilized Kalman filters and the Potter-Schmidt square-root filter, by applying these techniques to a realistic planetary navigation problem (orbit determination for the Saturn approach phase of the Mariner Jupiter-Saturn Mission, 1977). The new algorithm is shown to combine the numerical precision of square root filtering with the efficiency of the original Kalman algorithm.

Thornton, C. L.↗

NASA NTRS1996

A Formal Algorithm for Routing Traces on a Printed Circuit Board

This paper addresses the classical problem of printed circuit board routing: that is, the problem of automatic routing by a computer other than by brute force that causes the execution time to grow exponentially as a function of the complexity. Most of the present solutions are either inexpensive but not efficient and fast, or efficient and fast but very costly. Many solutions are proprietary, so not much is written or known about the actual algorithms upon which these solutions are based. This paper presents a formal algorithm for routing traces on a print- ed circuit board. The solution presented is very fast and efficient and for the first time speaks to the question eloquently by way of symbolic statements.

Hedgley, David R., Jr.↗

NASA NTRS1990

Universal Lambert and Kepler algorithms for autonomous rendezvous

This paper describes Lambert and Kepler algorithms designed to be the core of an autonomous rendezvous guidance system for an onboard computer. Applications include robotic and piloted missions to the moon and planets. Flight software must be compact, fast, and totally reliable. Although high accuracy is not essential for flight, in double precision these algorithms are accurate to at least 14 places almost everywhere. Both are universal; they apply to elliptic, parabolic, hyperbolic, and even rectilinear trajectories. The algorithms are improvements to those published by Battin (1987).

Klumpp, Allan R.↗

NASA NTRS2003

A Hierarchical and Distributed Approach for Mapping Large Applications to Heterogeneous Grids using Genetic Algorithms

In this paper, we propose a distributed approach for mapping a single large application to a heterogeneous grid environment. To minimize the execution time of the parallel application, we distribute the mapping overhead to the available nodes of the grid. This approach not only provides a fast mapping of tasks to resources but is also scalable. We adopt a hierarchical grid model and accomplish the job of mapping tasks to this topology using a scheduler tree. Results show that our three-phase algorithm provides high quality mappings, and is fast and scalable.

Sanyal, Soumya↗

NASA NTRS1992

Parallel computational fluid dynamics - Implementations and results

The present volume on parallel CFD discusses implementations on parallel machines, numerical algorithms for parallel CFD, and performance evaluation and computer science issues. Attention is given to a parallel algorithm for compressible flows through rotor-stator combinations, a massively parallel Euler solver for unstructured grids, a fast scheme to analyze 3D disk airflow on a parallel computer, and a block implicit multigrid solution of the Euler equations. Topics addressed include a 3D ADI algorithm on distributed memory multiprocessors, clustered element-by-element computations for fluid flow, hypercube FFT and the Fourier pseudospectral method, and an investigation of parallel iterative algorithms for CFD. Also discussed are fluid dynamics using interface methods on parallel processors, sorting for particle flow simulation on the connection machine, a large grain mapping method, and efforts toward a Teraflops capability for CFD.

Simon, Horst D.↗

NASA NTRS2002

Turbomachinery Airfoil Design Optimization Using Differential Evolution

An aerodynamic design optimization procedure that is based on a evolutionary algorithm known at Differential Evolution is described. Differential Evolution is a simple, fast, and robust evolutionary strategy that has been proven effective in determining the global optimum for several difficult optimization problems, including highly nonlinear systems with discontinuities and multiple local optima. The method is combined with a Navier-Stokes solver that evaluates the various intermediate designs and provides inputs to the optimization procedure. An efficient constraint handling mechanism is also incorporated. Results are presented for the inverse design of a turbine airfoil from a modern jet engine. The capability of the method to search large design spaces and obtain the optimal airfoils in an automatic fashion is demonstrated. Substantial reductions in the overall computing time requirements are achieved by using the algorithm in conjunction with neural networks.

Madavan, Nateri K.↗

NASA NTRS2002

Turbomachinery Airfoil Design Optimization Using Differential Evolution

An aerodynamic design optimization procedure that is based on a evolutionary algorithm known at Differential Evolution is described. Differential Evolution is a simple, fast, and robust evolutionary strategy that has been proven effective in determining the global optimum for several difficult optimization problems, including highly nonlinear systems with discontinuities and multiple local optima. The method is combined with a Navier-Stokes solver that evaluates the various intermediate designs and provides inputs to the optimization procedure. An efficient constraint handling mechanism is also incorporated. Results are presented for the inverse design of a turbine airfoil from a modern jet engine and compared to earlier methods. The capability of the method to search large design spaces and obtain the optimal airfoils in an automatic fashion is demonstrated. Substantial reductions in the overall computing time requirements are achieved by using the algorithm in conjunction with neural networks.

Madavan, Nateri K.↗

NASA NTRS2005

A Fast-Time Simulation Environment for Airborne Merging and Spacing Research

As part of NASA's Distributed Air/Ground Traffic Management (DAG-TM) effort, NASA Langley Research Center is developing concepts and algorithms for merging multiple aircraft arrival streams and precisely spacing aircraft over the runway threshold. An airborne tool has been created for this purpose, called Airborne Merging and Spacing for Terminal Arrivals (AMSTAR). To evaluate the performance of AMSTAR and complement human-in-the-loop experiments, a simulation environment has been developed that enables fast-time studies of AMSTAR operations. The environment is based on TMX, a multiple aircraft desktop simulation program created by the Netherlands National Aerospace Laboratory (NLR). This paper reviews the AMSTAR concept, discusses the integration of the AMSTAR algorithm into TMX and the enhancements added to TMX to support fast-time AMSTAR studies, and presents initial simulation results.

Bussink, Frank J. L.↗

NASA NTRS1987

Adaptive finite element methods for high-speed compressible flows

An adaptive finite element algorithm for solving the unsteady Euler equations is described. The finite element algorithm is based on a Taylor/Galerkin formulation and uses a very fast and efficient data structure to refine and unrefine the grid in order to optimize the approximation. A general version of the method which can be applied to moving grids with sliding interfaces is given, and results for a transient supersonic calculation of rotor-stator interaction are presented.

Oden, J. T.↗