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 109 records · Page 6
All sourcesNASA NTRSDOE OSTI
NASA NTRS1992

Estimation of the absolute position of mobile systems by an optoelectronic processor

A method that determine the absolute position of a mobile system with a hybrid optoelectronic processor has been developed. Position estimates are based on an analysis of circular landmarks that are detected by a TV camera attached to the mobile system. The difference between the known shape of the landmark and its image provides the information needed to determine the absolute position of the mobile system. For robust operation, the parameters of the landmark image are extracted at high speeds using an optical processor that performs an optical Hough transform. The coordinates of the mobile system are computed from these parameters in a digital co-processor using fast algorithms. Different sources of position estimation errors have also been analyzed, and consequent algorithms to improve the navigation performance of the mobile system have been developed and evaluated by both computer simulation and experiments.

Feng, Liqiang↗
NASA NTRS1992

Principled halftoning based on human vision models

When models of human vision adequately measure the relative quality of candidate halftonings of an image, the problem of halftoning the image becomes equivalent to the search problem of finding a halftone that optimizes the quality metric. Because of the vast number of possible halftones, and the complexity of image quality measures, this principled approach has usually been put aside in favor of fast algorithms that seem to perform well. We find that the principled approach can lead to a range of useful halftoning algorithms, as we trade off speed for quality by varying the complexity of the quality measure and the thoroughness of the search. High quality halftones can be obtained reasonably quickly, for example, by using as a measure the vector length of the error image filtered by a contrast sensitivity function, and, as the search procedure, the sequential adjustment of individual pixels to improve the quality measure. If computational resources permit, simulated annealing can find nearly optimal solutions.

Mulligan, Jeffrey B.↗
NASA NTRS1993

Generating local addresses and communication sets for data-parallel programs

Generating local addresses and communication sets is an important issue in distributed-memory implementations of data-parallel languages such as High Performance FORTRAN. We show that, for an array A affinely aligned to a template that is distributed across p processors with a cyclic(k) distribution and a computation involving the regular section A(l:h:s), the local memory access sequence for any processor is characterized by a finite state machine of at most k states. We present fast algorithms for computing the essential information about these state machines, and extend the framework to handle multidimensional arrays. We also show how to generate communication sets using the state machine approach. Performance results show that this solution requires very little run-time overhead and acceptable preprocessing time.

Chatterjee, Siddhartha↗
NASA NTRS1993

Generating local addresses and communication sets for data-parallel programs

Generating local addresses and communication sets is an important issue in distributed-memory implementations of data-parallel languages such as High Performance Fortran. We show that for an array A affinely aligned to a template that is distributed across p processors with a cyclic(k) distribution, and a computation involving the regular section A, the local memory access sequence for any processor is characterized by a finite state machine of at most k states. We present fast algorithms for computing the essential information about these state machines, and extend the framework to handle multidimensional arrays. We also show how to generate communication sets using the state machine approach. Performance results show that this solution requires very little runtime overhead and acceptable preprocessing time.

Chatterjee, Siddhartha↗
NASA NTRS1992

Reduction of blocking effects for the JPEG baseline image compression standard

Transform coding has been chosen for still image compression in the Joint Photographic Experts Group (JPEG) standard. Although transform coding performs superior to many other image compression methods and has fast algorithms for implementation, it is limited by a blocking effect at low bit rates. The blocking effect is inherent in all nonoverlapping transforms. This paper presents a technique for reducing blocking while remaining compatible with the JPEG standard. Simulations show that the system results in subjective performance improvements, sacrificing only a marginal increase in bit rate.

Zweigle, Gregary C.↗
NASA NTRS1995

SeaWiFS technical report series. Volume 31: Stray light in the SeaWiFS radiometer

Some of the measurements from the Sea-viewing Wide Field-of-view Sensor (SeaWiFS) will not be useful as ocean measurements. For the ocean data set, there are procedures in place to mask the SeaWiFS measurements of clouds and ice. Land measurements will also be masked using a geographic technique based on each measurment's latitude and longitude. Each of these masks involves a source of light much brighter than the ocean. Because of stray light in the SeaWiFS radiometer, light from these bright sources can contaminate ocean measurements located a variable number of pixels away from a bright source. In this document, the sources of stray light in the sensor are examined, and a method is developed for masking measurements near bright targets for stray light effects. In addition, a procedure is proposed for reducing the effects of stray light in the flight data from SeaWiFS. This correction can also reduce the number of pixels masked for stray light. Without these corrections, local area scenes must be masked 10 pixels before and after bright targets in the along-scan direction. The addition of these corrections reduces the along-scan masks to four pixels before and after bright sources. In the along-track direction, the flight data are not corrected, and are masked two pixels before and after. Laboratory measurements have shown that stray light within the instrument changes in a direct ratio to the intensity of the bright source. The measurements have also shown that none of the bands show peculiarities in their stray light response. In other words, the instrument's response is uniform from band to band. The along-scan correction is based on each band's response to a 1 pixel wide bright sources. Since these results are based solely on preflight laboratory measurements, their successful implementation requires compliance with two additional criteria. First, since SeaWiFS has a large data volume, the correction and masking procedures must be such that they can be converted into computationally fast algorithms. Second, they must be shown to operate properly on flight data. The laboratory results, and the corrections and masking procedures that derive from them, should be considered as zeroeth order estimates of the effects that will be found on orbit.

Hooker, Stanford B.↗
NASA NTRS1997

Fast Fuzzy Arithmetic Operations

In engineering applications of fuzzy logic, the main goal is not to simulate the way the experts really think, but to come up with a good engineering solution that would (ideally) be better than the expert's control, In such applications, it makes perfect sense to restrict ourselves to simplified approximate expressions for membership functions. If we need to perform arithmetic operations with the resulting fuzzy numbers, then we can use simple and fast algorithms that are known for operations with simple membership functions. In other applications, especially the ones that are related to humanities, simulating experts is one of the main goals. In such applications, we must use membership functions that capture every nuance of the expert's opinion; these functions are therefore complicated, and fuzzy arithmetic operations with the corresponding fuzzy numbers become a computational problem. In this paper, we design a new algorithm for performing such operations. This algorithm is applicable in the case when negative logarithms - log(u(x)) of membership functions u(x) are convex, and reduces computation time from O(n(exp 2))to O(n log(n)) (where n is the number of points x at which we know the membership functions u(x)).

Hampton, Michael↗
NASA NTRS2001

Performance of the Wavelet Decomposition on Massively Parallel Architectures

Traditionally, Fourier Transforms have been utilized for performing signal analysis and representation. But although it is straightforward to reconstruct a signal from its Fourier transform, no local description of the signal is included in its Fourier representation. To alleviate this problem, Windowed Fourier transforms and then wavelet transforms have been introduced, and it has been proven that wavelets give a better localization than traditional Fourier transforms, as well as a better division of the time- or space-frequency plane than Windowed Fourier transforms. Because of these properties and after the development of several fast algorithms for computing the wavelet representation of any signal, in particular the Multi-Resolution Analysis (MRA) developed by Mallat, wavelet transforms have increasingly been applied to signal analysis problems, especially real-life problems, in which speed is critical. In this paper we present and compare efficient wavelet decomposition algorithms on different parallel architectures. We report and analyze experimental measurements, using NASA remotely sensed images. Results show that our algorithms achieve significant performance gains on current high performance parallel systems, and meet scientific applications and multimedia requirements. The extensive performance measurements collected over a number of high-performance computer systems have revealed important architectural characteristics of these systems, in relation to the processing demands of the wavelet decomposition of digital images.

El-Ghazawi, Tarek A.↗
NASA NTRS1997

Automation for Air Traffic Control: The Rise of a New Discipline

The current debate over the concept of Free Flight has renewed interest in automated conflict detection and resolution in the enroute airspace. An essential requirement for effective conflict detection is accurate prediction of trajectories. Trajectory prediction is, however, an inexact process which accumulates errors that grow in proportion to the length of the prediction time interval. Using a model of prediction errors for the trajectory predictor incorporated in the Center-TRACON Automation System (CTAS), a computationally fast algorithm for computing conflict probability has been derived. Furthermore, a method of conflict resolution has been formulated that minimizes the average cost of resolution, when cost is defined as the increment in airline operating costs incurred in flying the resolution maneuver. The method optimizes the trade off between early resolution at lower maneuver costs but higher prediction error on the one hand and late resolution with higher maneuver costs but lower prediction errors on the other. The method determines both the time to initiate the resolution maneuver as well as the characteristics of the resolution trajectory so as to minimize the cost of the resolution. Several computational examples relevant to the design of a conflict probe that can support user-preferred trajectories in the enroute airspace will be presented.

Erzberger, Heinz↗
NASA NTRS2003

Mining Distance Based Outliers in Near Linear Time with Randomization and a Simple Pruning Rule

Defining outliers by their distance to neighboring examples is a popular approach to finding unusual examples in a data set. Recently, much work has been conducted with the goal of finding fast algorithms for this task. We show that a simple nested loop algorithm that in the worst case is quadratic can give near linear time performance when the data is in random order and a simple pruning rule is used. We test our algorithm on real high-dimensional data sets with millions of examples and show that the near linear scaling holds over several orders of magnitude. Our average case analysis suggests that much of the efficiency is because the time to process non-outliers, which are the majority of examples, does not depend on the size of the data set.

Bay, Stephen D.↗
NASA NTRS2007

A Simple Stochastic Model for Generating Broken Cloud Optical Depth and Top Height Fields

A simple and fast algorithm for generating two correlated stochastic twodimensional (2D) cloud fields is described. The algorithm is illustrated with two broken cumulus cloud fields: cloud optical depth and cloud top height retrieved from Moderate Resolution Imaging Spectrometer (MODIS). Only two 2D fields are required as an input. The algorithm output is statistical realizations of these two fields with approximately the same correlation and joint distribution functions as the original ones. The major assumption of the algorithm is statistical isotropy of the fields. In contrast to fractals and the Fourier filtering methods frequently used for stochastic cloud modeling, the proposed method is based on spectral models of homogeneous random fields. For keeping the same probability density function as the (first) original field, the method of inverse distribution function is used. When the spatial distribution of the first field has been generated, a realization of the correlated second field is simulated using a conditional distribution matrix. This paper is served as a theoretical justification to the publicly available software that has been recently released by the authors and can be freely downloaded from http://i3rc.gsfc.nasa.gov/Public codes clouds.htm. Though 2D rather than full 3D, stochastic realizations of two correlated cloud fields that mimic statistics of given fields have proved to be very useful to study 3D radiative transfer features of broken cumulus clouds for better understanding of shortwave radiation and interpretation of the remote sensing retrievals.

Prigarin, Sergei M.↗
NASA NTRS2010

NASA Tech Briefs, May 2010

Topics covered include: Instrument for Analysis of Greenland's Glacier Mills Cryogenic Moisture Apparatus; A Transportable Gravity Gradiometer Based on Atom Interferometry; Three Methods of Detection of Hydrazines; Crossed, Small-Deflection Energy Analyzer for Wind/Temperature Spectrometer; Wavefront Correction for Large, Flexible Antenna Reflector; Novel Micro Strip-to-Waveguide Feed Employing a Double-Y Junction; Thin-Film Ferro Electric-Coupled Microstripline Phase Shifters With Reduced Device Hysteresis; Two-Stage, 90-GHz, Low-Noise Amplifier; A 311-GHz Fundamental Oscillator Using InP HBT Technology; FPGA Coprocessor Design for an Onboard Multi-Angle Spectro-Polarimetric Imager; Serrating Nozzle Surfaces for Complete Transfer of Droplets; Turbomolecular Pumps for Holding Gases in Open Containers; Triaxial Swirl Injector Element for Liquid-Fueled Engines; Integrated Budget Office Toolbox; PLOT3D Export Tool for Tecplot; Math Description Engine Software Development Kit; Astronaut Office Scheduling System Software; ISS Solar Array Management; Probabilistic Structural Analysis Program; SPOT Program; Integrated Hybrid System Architecture for Risk Analysis; System for Packaging Planetary Samples for Return to Earth; Offset Compound Gear Drive; Low-Dead-Volume Inlet for Vacuum Chamber; Simple Check Valves for Microfluidic Devices; A Capillary-Based Static Phase Separator for Highly Variable Wetting Conditions; Gimballing Spacecraft Thruster; Finned Carbon-Carbon Heat Pipe with Potassium Working Fluid; Lightweight Heat Pipes Made from Magnesium; Ceramic Rail-Race Ball Bearings; Improved OTEC System for a Submarine Robot; Reflector Surface Error Compensation in Dual-Reflector Antennas; Enriched Storable Oxidizers for Rocket Engines; Planar Submillimeter-Wave Mixer Technology with Integrated Antenna; Widely Tunable Mode-Hop-Free External-Cavity Quantum Cascade Laser; Non-Geiger-Mode Single-Photon Avalanche Detector with Low Excess Noise; Using Whispering-Gallery-Mode Resonators for Refractometry; RF Device for Acquiring Images of the Human Body; Reactive Collision Avoidance Algorithm; Fast Solution in Sparse LDA for Binary Classification; Modeling Common-Sense Decisions in Artificial Intelligence; Graph-Based Path-Planning for Titan Balloons; Nanolaminate Membranes as Cylindrical Telescope Reflectors; Air-Sea Spray Airborne Radar Profiler Characterizes Energy Fluxes in Hurricanes; Large Telescope Segmented Primary Mirror Alignment; and Simplified Night Sky Display System.

Source record↗
NASA NTRS2006

Biochemical Detection and Identification False Alarm Rate Dependence on Wavelength Using Laser Induced Fluorescence

Most organic and many inorganic materials absorb strongly in specific wavelength ranges in the deep UV between about 220nm and 300nm. Excitation within these absorption bands results in native fluorescence emission. Each compound or composite material, such as a bacterial spore, has a unique excitation-emission fingerprint that can be used to provide information about the material. The sensitivity and specificity with which these materials can be detected and identified depends on the excitation wavelength and the number and location of observation wavelengths.We will present data on our deep ultraviolet Targeted Ultraviolet Chemical Sensors that demonstrate the sensitivity and specificity of the sensors. In particular, we will demonstrate the ability to quantitatively differentiate a wide range of biochemical agent targets against a wide range of background materials. We will describe the relationship between spectral resolution and specificity in target identification, as well as simple, fast, algorithms to identify materials.Hand-held, battery operated instruments using a deep UV laser and multi-band detection have been developed and deployed on missions to the Antarctic, the Arctic, and the deep ocean with the capability of detecting a single bacterial spore and to differentiate a wide range of organic and biological compounds.

native flourescence↗
NASA NTRS2005

Two Methods for Efficient Solution of the Hitting-Set Problem

A paper addresses much of the same subject matter as that of Fast Algorithms for Model-Based Diagnosis (NPO-30582), which appears elsewhere in this issue of NASA Tech Briefs. However, in the paper, the emphasis is more on the hitting-set problem (also known as the transversal problem), which is well known among experts in combinatorics. The authors primary interest in the hitting-set problem lies in its connection to the diagnosis problem: it is a theorem of model-based diagnosis that in the set-theory representation of the components of a system, the minimal diagnoses of a system are the minimal hitting sets of the system. In the paper, the hitting-set problem (and, hence, the diagnosis problem) is translated from a combinatorial to a computational problem by mapping it onto the Boolean satisfiability and integer- programming problems. The paper goes on to describe developments nearly identical to those summarized in the cited companion NASA Tech Briefs article, including the utilization of Boolean-satisfiability and integer- programming techniques to reduce the computation time and/or memory needed to solve the hitting-set problem.

Vatan, Farrokh↗
NASA NTRS2014

Dynamic Controllability and Dispatchability Relationships

An important issue for temporal planners is the ability to handle temporal uncertainty. Recent papers have addressed the question of how to tell whether a temporal network is Dynamically Controllable, i.e., whether the temporal requirements are feasible in the light of uncertain durations of some processes. We present a fast algorithm for Dynamic Controllability. We also note a correspondence between the reduction steps in the algorithm and the operations involved in converting the projections to dispatchable form. This has implications for the complexity for sparse networks.

controllability↗
NASA NTRS2014

CloudSat-Constrained Cloud Ice Water Path and Cloud Top Height Retrievals from MHS 157 and 183.3 GHz Radiances

Ice water path (IWP) and cloud top height (ht) are two of the key variables in determining cloud radiative and thermodynamical properties in climate models. Large uncertainty remains among IWP measurements from satellite sensors, in large part due to the assumptions made for cloud microphysics in these retrievals. In this study, we develop a fast algorithm to retrieve IWP from the 157, 183.3+/-3 and 190.3 GHz radiances of the Microwave Humidity Sounder (MHS) such that the MHS cloud ice retrieval is consistent with CloudSat IWP measurements. This retrieval is obtained by constraining the empirical forward models between collocated and coincident measurements of CloudSat IWP and MHS cloud-induced radiance depression (Tcir) at these channels. The empirical forward model is represented by a lookup table (LUT) of Tcir-IWP relationships as a function of ht and the frequency channel.With ht simultaneously retrieved, the IWP is found to be more accurate. The useful range of the MHS IWP retrieval is between 0.5 and 10 kg/sq m, and agrees well with CloudSat in terms of the normalized probability density function (PDF). Compared to the empirical model, current operational radiative transfer models (RTMs) still have significant uncertainties in characterizing the observed Tcir-IWP relationships. Therefore, the empirical LUT method developed here remains an effective approach to retrieving ice cloud properties from the MHS-like microwave channels.

cloud top height↗
NASA NTRS2015

Citizen Science

Scientists and engineers constantly face new challenges, despite myriad advances in computing. More sets of data are collected today from earth and sky than there is time or resources available to carefully analyze them. Some problems either don't have fast algorithms to solve them or have solutions that must be found among millions of options, a situation akin to finding a needle in a haystack. But all hope is not lost: advances in technology and the Internet have empowered the general public to participate in the scientific process via individual computational resources and brain cognition, which isn't matched by any machine. Citizen scientists are volunteers who perform scientific work by making observations, collecting and disseminating data, making measurements, and analyzing or interpreting data without necessarily having any scientific training. In so doing, individuals from all over the world can contribute to science in ways that wouldn't have been otherwise possible.

distributed computing↗