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 325 records · Page 18
All sourcesNASA NTRSDOE OSTI
NASA NTRS1987

General purpose algorithms for characterization of slow and fast phase nystagmus

In the overall aim for a better understanding of the vestibular and optokinetic systems and their roles in space motion sickness, the eye movement responses to various dynamic stimuli are measured. The vestibulo-ocular reflex (VOR) and the optokinetic response, as the eye movement responses are known, consist of slow phase and fast phase nystagmus. The specific objective is to develop software programs necessary to characterize the vestibulo-ocular and optokinetic responses by distinguishing between the two phases of nystagmus. The overall program is to handle large volumes of highly variable data with minimum operator interaction. The programs include digital filters, differentiation, identification of fast phases, and reconstruction of the slow phase with a least squares fit such that sinusoidal or psuedorandom data may be processed with accurate results. The resultant waveform, slow phase velocity eye movements, serves as input data to the spectral analysis programs previously developed for NASA to analyze nystagmus responses to pseudorandom angular velocity inputs.

Lessard, Charles S.↗
NASA NTRS2005

A Fast Implementation of the ISODATA Clustering Algorithm

Clustering is central to many image processing and remote sensing applications. ISODATA is one of the most popular and widely used clustering methods in geoscience applications, but it can run slowly, particularly with large data sets. We present a more efficient approach to ISODATA clustering, which achieves better running times by storing the points in a kd-tree and through a modification of the way in which the algorithm estimates the dispersion of each cluster. We also present an approximate version of the algorithm which allows the user to further improve the running time, at the expense of lower fidelity in computing the nearest cluster center to each point. We provide both theoretical and empirical justification that our modified approach produces clusterings that are very similar to those produced by the standard ISODATA approach. We also provide empirical studies on both synthetic data and remotely sensed Landsat and MODIS images that show that our approach has significantly lower running times.

Memarsadeghi, Nargess↗
NASA NTRS2007

A Fast Implementation of the Isodata Clustering Algorithm

Clustering is central to many image processing and remote sensing applications. ISODATA is one of the most popular and widely used clustering methods in geoscience applications, but it can run slowly, particularly with large data sets. We present a more efficient approach to IsoDATA clustering, which achieves better running times by storing the points in a kd-tree and through a modification of the way in which the algorithm estimates the dispersion of each cluster. We also present an approximate version of the algorithm which allows the user to further improve the running time, at the expense of lower fidelity in computing the nearest cluster center to each point. We provide both theoretical and empirical justification that our modified approach produces clusterings that are very similar to those produced by the standard ISODATA approach. We also provide empirical studies on both synthetic data and remotely sensed Landsat and MODIS images that show that our approach has significantly lower running times.

Memarsadeghi, Nargess↗
NASA NTRS2019

A Tactical Scheduler for Surface Metering Under Minimum Departure Interval Restrictions

Minimum Departure Interval (MDI) and Miles-In-Trail (MIT) are common traffic management tools. They both require minimum separation between departures to meet specific traffic conditions. The MDI restriction is a time separation requirement between departures, usually on the same Standard Instrument Departure (SID), whereas the MIT restriction is a distance separation requirement between aircraft, including but not limited to departure flights, to meet specific criteria associated with flight path or destination. At Incheon International Airport (IATA code: ICN) in South Korea, MDIs are imposed on 92% of departure flights. They involve specific criteria including not only having identical SID, but also satisfying other conditions, imposed on the flight path and destination. To address complicated MDI constraints, Korea Aerospace Research Institute (KARI) has been developing and improving a tactical scheduler for surface metering at ICN to provide appropriate target times for pushbacks and takeoffs for departure flights under MDIs. This paper describes the MDI requirements at ICN, the development of a heuristic scheduling algorithm to work with the MDI restrictions, and the performance evaluation of the algorithm through fast-time simulations. The performance evaluation results indicate that the proposed heuristic algorithm can provide the surface metering schedules that comply with the MDI restrictions without significant performance degradation.

DMAN (Departure Management)↗
DOE OSTI2023

Fast Particle-based Anomaly Detection Algorithm with Variational Autoencoder

Model-agnostic anomaly detection is one of the promising approaches in the search for new beyond the standard model physics. In this paper, we present Set-VAE, a particle-based variational autoencoder (VAE) anomaly detection algorithm. We demonstrate a 2x signal efficiency gain compared with traditional subjettiness-based jet selection. Furthermore, with an eye to the future deployment to trigger systems, we propose the CLIP-VAE, which reduces the inference-time cost of anomaly detection by using the KL-divergence loss as the anomaly score, resulting in a 2x acceleration in latency and reducing the caching requirement.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
NASA NTRS1975

MITNYS-II - A digital program for on-line analysis of nystagmus

A digital computer program, MITNYS-II, has been developed for on-line analysis of nystagmus which results from visual, vestibular or caloric stimulation. The program accepts sampled records of eye position and yields cumulative slow phase position, slow phase velocity, instantaneous fast phase frequency and other parameters in 25 ms. In this paper the algorithms by which fast phases are detected, and by which slow phase cumulative eye position is extrapolated across the fast phase interval are described. Extensive tests with vestibular, optokinetic and caloric nystagmus yield reliability figures of the order of 2% for false identification of fast phases and missed fast phases. MITNYS-II has been successfully employed to interpret clinical EOG records, examples of which are presented.

Allum, J. H. J.↗
NASA NTRS2022

UAV Path Planning for Wildfires - Sustainably Fighting Wildfires with Automated Path Planning for UAVs

As the severity and frequency of wildfires increase, infrastructure, properties, national parks, animal habitats, and human lives (civilians and firefighters) are put at greater risk. This paper examines the possible application of algorithmic path planning for UAV reconnaissance to reduce damage and safety risks, as aforementioned. When the location of a wildfire is known, UAVs are immediately dispatched from an operating base to fly to the fire and support the firefighters as quickly as possible. Then, the algorithm incrementally analyzes different environmental factors to create a path for the UAV to follow. This work focuses on generating a path for the UAV to follow given a set of polygons representing obstacles. The most important features of this algorithm are its fast response time and obstacle maneuverability. The use of an efficient path planning algorithm could potentially save lives, infrastructure, and acres of forest destruction.

UAV↗
NASA NTRS1997

Constellation Coverage Analysis

The design of satellite constellations require an understanding of the dynamic global coverage provided by the constellations. We have developed a fast and simple algorithm for detemining the global constellation coverage dynamically using image processing techniques. This approach provides a fast, powerful and simple method for the anysis of global constellation coverage.

Satellite↗
NASA NTRS2012

GPU Lossless Hyperspectral Data Compression System for Space Applications

On-board lossless hyperspectral data compression reduces data volume in order to meet NASA and DoD limited downlink capabilities. At JPL, a novel, adaptive and predictive technique for lossless compression of hyperspectral data, named the Fast Lossless (FL) algorithm, was recently developed. This technique uses an adaptive filtering method and achieves state-of-the-art performance in both compression effectiveness and low complexity. Because of its outstanding performance and suitability for real-time onboard hardware implementation, the FL compressor is being formalized as the emerging CCSDS Standard for Lossless Multispectral & Hyperspectral image compression. The FL compressor is well-suited for parallel hardware implementation. A GPU hardware implementation was developed for FL targeting the current state-of-the-art GPUs from NVIDIA(Trademark). The GPU implementation on a NVIDIA(Trademark) GeForce(Trademark) GTX 580 achieves a throughput performance of 583.08 Mbits/sec (44.85 MSamples/sec) and an acceleration of at least 6 times a software implementation running on a 3.47 GHz single core Intel(Trademark) Xeon(Trademark) processor. This paper describes the design and implementation of the FL algorithm on the GPU. The massively parallel implementation will provide in the future a fast and practical real-time solution for airborne and space applications.

Graphic Processor Units↗
NASA NTRS1976

An algorithm to compute the sequency ordered Walsh transform

A fast sequency-ordered Walsh transform algorithm is presented; this sequency-ordered fast transform is complementary to the sequency-ordered fast Walsh transform introduced by Manz (1972) and eliminating gray code reordering through a modification of the basic fast Hadamard transform structure. The new algorithm retains the advantages of its complement (it is in place and is its own inverse), while differing in having a decimation-in time structure, accepting data in normal order, and returning the coefficients in bit-reversed sequency order. Applications include estimation of Walsh power spectra for a random process, sequency filtering and computing logical autocorrelations, and selective bit reversing.

Larsen, H.↗
DOE OSTI2022

A Quantum-Inspired Tensor Network Algorithm for Constrained Combinatorial Optimization Problems

Combinatorial optimization is of general interest for both theoretical study and real-world applications. Fast-developing quantum algorithms provide a different perspective on solving combinatorial optimization problems. In this paper, we propose a quantum-inspired tensor-network-based algorithm for general locally constrained combinatorial optimization problems. Our algorithm constructs a Hamiltonian for the problem of interest, effectively mapping it to a quantum problem, then encodes the constraints directly into a tensor network state and solves the optimal solution by evolving the system to the ground state of the Hamiltonian. We demonstrate our algorithm with the open-pit mining problem, which results in a quadratic asymptotic time complexity. Our numerical results show the effectiveness of this construction and potential applications in further studies for general combinatorial optimization problems.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
NASA NTRS1997

Constellation Coverage Analysis

The design of satellite constellations requires an understanding of the dynamic global coverage provided by the constellations. Even for a small constellation with a simple circular orbit propagator, the combinatorial nature of the analysis frequently renders the problem intractable. Particularly for the initial design phase where the orbital parameters are still fluid and undetermined, the coverage information is crucial to evaluate the performance of the constellation design. We have developed a fast and simple algorithm for determining the global constellation coverage dynamically using image processing techniques. This approach provides a fast, powerful and simple method for the analysis of global constellation coverage.

Martin W. Lo↗
NASA NTRS1998

Efficient dynamic constraints for animating articulated figures

This paper presents an efficient dynamics-based computer animation system for simulating and controlling the motion of articulated figures. A non-trivial extension of Featherstone's O(n) recursive forward dynamics algorithm is derived which allows enforcing one or more constraints on the animated figures. We demonstrate how the constraint force evaluation algorithm we have developed makes it possible to simulate collisions between articulated figures, to compute the results of impulsive forces, to enforce joint limits, to model closed kinematic loops, and to robustly control motion at interactive rates. Particular care has been taken to make the algorithm not only fast, but also easy to implement and use. To better illustrate how the constraint force evaluation algorithm works, we provide pseudocode for its major components. Additionally, we analyze its computational complexity and finally we present examples demonstrating how our system has been used to generate interactive, physically correct complex motion with small user effort.

NASA Discipline Space Human Factors↗
NASA NTRS1992

Efficient demultiplexing algorithm for noncontiguous carriers

A channel separation algorithm for the frequency division multiple access/time division multiplexing (FDMA/TDM) scheme is presented. It is shown that implementation using this algorithm can be more effective than the fast Fourier transform (FFT) algorithm when only a small number of carriers need to be selected from many, such as satellite Earth terminals. The algorithm is based on polyphase filtering followed by application of a generalized Walsh-Hadamard transform (GWHT). Comparison of the transform technique used in this algorithm with discrete Fourier transform (DFT) and FFT is given. Estimates of the computational rates and power requirements to implement this system are also given.

Thanawala, A. A.↗
DOE OSTI2022

CONGO²: Scalable Online Anomaly Detection and Localization in Power Electronics Networks

Rapid and accurate detection and localization of electronic disturbances simultaneously are important for preventing its potential damages and determining potential remedies. Existing anomaly detection methods are severely limited by the low accuracy, the expensive computational cost and the need for highly trained personnel. There is an urgent need for a scalable online algorithm for in-field analysis of large-scale power electronics networks. Here in this paper, we propose a fast and accurate algorithm for anomaly detection and localization of power electronics networks: stratified colored-node graph (CONGO2). This algorithm hierarchically models the change of correlated waveforms and then correlated sensors using the colored-node graph. By aggregating the change of each sensor with its neighbors’ inputs, we can spontaneously identify and localize the anomaly that cannot be detected by data collected from a single sensor. As our proposed method only focuses on the changes within a short time frame, it is highly computational efficient and only needs small data storage. Thus, our method is ideal for online and reliable anomaly detection and localization of large-scale power electronic networks. Compared to existing anomaly detection methods, our method is entirely data-driven without training data, highly accurate and reliable for wide-spectrum anomalies detection, and more importantly, capable of both detection and localization. Thus, it is ideal for infield deployment for large-scale power electronic networks. As illustrated by a distributed energy resources (DERs) power grid with 37-node, our method can effectively detect and localize various cyber and physical attacks.

42 ENGINEERING↗
NASA NTRS1990

On recursive least-squares filtering algorithms and implementations

In many real-time signal processing applications, fast and numerically stable algorithms for solving least-squares problems are necessary and important. In particular, under non-stationary conditions, these algorithms must be able to adapt themselves to reflect the changes in the system and take appropriate adjustments to achieve optimum performances. Among existing algorithms, the QR-decomposition (QRD)-based recursive least-squares (RLS) methods have been shown to be useful and effective for adaptive signal processing. In order to increase the speed of processing and achieve high throughput rate, many algorithms are being vectorized and/or pipelined to facilitate high degrees of parallelism. A time-recursive formulation of RLS filtering employing block QRD will be considered first. Several methods, including a new non-continuous windowing scheme based on selectively rejecting contaminated data, were investigated for adaptive processing. Based on systolic triarrays, many other forms of systolic arrays are shown to be capable of implementing different algorithms. Various updating and downdating systolic algorithms and architectures for RLS filtering are examined and compared in details, which include Householder reflector, Gram-Schmidt procedure, and Givens rotation. A unified approach encompassing existing square-root-free algorithms is also proposed. For the sinusoidal spectrum estimation problem, a judicious method of separating the noise from the signal is of great interest. Various truncated QR methods are proposed for this purpose and compared to the truncated SVD method. Computer simulations provided for detailed comparisons show the effectiveness of these methods. This thesis deals with fundamental issues of numerical stability, computational efficiency, adaptivity, and VLSI implementation for the RLS filtering problems. In all, various new and modified algorithms and architectures are proposed and analyzed; the significance of any of the new method depends crucially on specific application.

Hsieh, Shih-Fu↗
NASA NTRS1997

Unsupervised, Robust Estimation-based Clustering for Multispectral Images

To prepare for the challenge of handling the archiving and querying of terabyte-sized scientific spatial databases, the NASA Goddard Space Flight Center's Applied Information Sciences Branch (AISB, Code 935) developed a number of characterization algorithms that rely on supervised clustering techniques. The research reported upon here has been aimed at continuing the evolution of some of these supervised techniques, namely the neural network and decision tree-based classifiers, plus extending the approach to incorporating unsupervised clustering algorithms, such as those based on robust estimation (RE) techniques. The algorithms developed under this task should be suited for use by the Intelligent Information Fusion System (IIFS) metadata extraction modules, and as such these algorithms must be fast, robust, and anytime in nature. Finally, so that the planner/schedule module of the IlFS can oversee the use and execution of these algorithms, all information required by the planner/scheduler must be provided to the IIFS development team to ensure the timely integration of these algorithms into the overall system.

Netanyahu, Nathan S.↗