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 145 records · Page 8
All sourcesNASA NTRSDOE OSTI
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↗
NASA NTRSDate not supplied

TPSAS-NF1676L-33433-DND

Reducing aircraft noise is a major objective in the field of computational aeroacoustics. When designing next generation quiet aircraft, it is important to be able to accurately and efficiently predict the acoustic scattering by an aircraft body from a given noise source. Acoustic liners are an effective tool for aircraft noise reduction, and are characterized by a complex valued frequency-dependent impedance. Converted into the time-domain using Fourier transforms, an impedance boundary condition can be used to simulate the acoustic scattering of geometric bodies treated with acoustic liners. This work considers using either an impedance boundary condition or admittance boundary condition to allow acoustic scattering problems to be modeled with geometries consisting of both un-lined and lined surfaces; admittance is defined to be the inverse of impedance. Three different acoustic liner models will be discussed: the Extended Helmholtz Resonator Model, the Three-Parameter Impedance Model, and a Broadband Model. In the Extended Helmholtz Resonator Model and Three-Parameter Impedance Model, the liner impedance is specified at a single frequency; the Broadband Model allows for the investigation of multiple frequencies simultaneously. The impedance and admittance boundary conditions for each model will be derived and coupled with a time-domain boundary integral equation. The scattering solution will be obtained iteratively using spatial and temporal basis functions. Stability will be demonstrated through eigenvalue analysis. Moreover, fast algorithms and high performance computing are considered to both assess and reduce the computational cost of the simulation.

Michelle E Rodio↗
NASA NTRS1982

A fast hidden line algorithm for plotting finite element models

Effective plotting of finite element models requires the use of fast hidden line plot techniques that provide interactive response. A high speed hidden line technique was developed to facilitate the plotting of NASTRAN finite element models. Based on testing using 14 different models, the new hidden line algorithm (JONES-D) appears to be very fast: its speed equals that for normal (all lines visible) plotting and when compared to other existing methods it appears to be substantially faster. It also appears to be very reliable: no plot errors were observed using the new method to plot NASTRAN models. The new algorithm was made part of the NPLOT NASTRAN plot package and was used by structural analysts for normal production tasks.

Jones, G. K.↗
NASA NTRS1991

Improved FFT-based numerical inversion of Laplace transforms via fast Hartley transform algorithm

The disadvantages of numerical inversion of the Laplace transform via the conventional fast Fourier transform (FFT) are identified and an improved method is presented to remedy them. The improved method is based on introducing a new integration step length Delta(omega) = pi/mT for trapezoidal-rule approximation of the Bromwich integral, in which a new parameter, m, is introduced for controlling the accuracy of the numerical integration. Naturally, this method leads to multiple sets of complex FFT computations. A new inversion formula is derived such that N equally spaced samples of the inverse Laplace transform function can be obtained by (m/2) + 1 sets of N-point complex FFT computations or by m sets of real fast Hartley transform (FHT) computations.

Hwang, Chyi↗
DOE OSTI2020

CLUE: A Fast Parallel Clustering Algorithm for High Granularity Calorimeters in High-Energy Physics

One of the challenges of high granularity calorimeters, such as that to be built to cover the endcap region in the CMS Phase-2 Upgrade for HL-LHC, is that the large number of channels causes a surge in the computing load when clustering numerous digitized energy deposits (hits) in the reconstruction stage. In this article, we propose a fast and fully parallelizable density-based clustering algorithm, optimized for high-occupancy scenarios, where the number of clusters is much larger than the average number of hits in a cluster. The algorithm uses a grid spatial index for fast querying of neighbors and its timing scales linearly with the number of hits within the range considered. We also show a comparison of the performance on CPU and GPU implementations, demonstrating the power of algorithmic parallelization in the coming era of heterogeneous computing in high-energy physics.

Rovere, Marco↗
NASA NTRS2007

Hybrid-dual-fourier tomographic algorithm for a fast three-dimensionial optical image reconstruction in turbid media

A reconstruction technique for reducing computation burden in the 3D image processes, wherein the reconstruction procedure comprises an inverse and a forward model. The inverse model uses a hybrid dual Fourier algorithm that combines a 2D Fourier inversion with a 1D matrix inversion to thereby provide high-speed inverse computations. The inverse algorithm uses a hybrid transfer to provide fast Fourier inversion for data of multiple sources and multiple detectors. The forward model is based on an analytical cumulant solution of a radiative transfer equation. The accurate analytical form of the solution to the radiative transfer equation provides an efficient formalism for fast computation of the forward model.

Alfano, Robert R.↗