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 199 records · Page 11
All sourcesNASA NTRSDOE OSTI
NASA NTRS2014

Next Generation Aura-OMI SO2 Retrieval Algorithm: Introduction and Implementation Status

We introduce our next generation algorithm to retrieve SO2 using radiance measurements from the Aura Ozone Monitoring Instrument (OMI). We employ a principal component analysis technique to analyze OMI radiance spectral in 310.5-340 nm acquired over regions with no significant SO2. The resulting principal components (PCs) capture radiance variability caused by both physical processes (e.g., Rayleigh and Raman scattering, and ozone absorption) and measurement artifacts, enabling us to account for these various interferences in SO2 retrievals. By fitting these PCs along with SO2 Jacobians calculated with a radiative transfer model to OMI-measured radiance spectra, we directly estimate SO2 vertical column density in one step. As compared with the previous generation operational OMSO2 PBL (Planetary Boundary Layer) SO2 product, our new algorithm greatly reduces unphysical biases and decreases the noise by a factor of two, providing greater sensitivity to anthropogenic emissions. The new algorithm is fast, eliminates the need for instrument-specific radiance correction schemes, and can be easily adapted to other sensors. These attributes make it a promising technique for producing long-term, consistent SO2 records for air quality and climate research. We have operationally implemented this new algorithm on OMI SIPS for producing the new generation standard OMI SO2 products.

Sulfur dioxide↗
NASA NTRS1975

Advances in Application of Fast Semidirect Computational Methods in Transonic Flow

This paper is intended as a review and summary of the advances made in a recently developed approach for rapid numerical solution of the equations of inviscid transonic aerodynamics. The investigation has been limited to two-dimensional, steady, inviscid flow over airfoils in a subsonic free stream, with emphasis on development of a rapid computational technique, rather than on generality of application. The approach uses finite-difference algorithms called "fast direct elliptic solvers" within an iteration scheme. "Direct" means that the entire computation field is solved at once, rather than in successive traverses over the field as in a point- or line-relaxation method. Such an iterative method is referred to as "semidirect." The iterative convergence can be faster than in other relaxation methods because changes are felt simultaneously at all points in each succeeding iteration. Direct elliptic solvers and semidirect methods have restrictions, but these are gradually being removed. Direct solvers were first developed for solving Poisson's equation on a rectangle without interior boundaries. A method to treat first-order systems, a direct Cauchy-Riemann solver has also been developed. Numerical treatment of part of a system of nonlinear equations by a Poisson solver has been reported. Also Poisson solvers in semidirect methods were used for nonseparable elliptic equations. The semidirect method was extended to the solution of a problem of mixed type, where the improved Murman-Cole transonic small-disturbance difference equations were solved. A slightly supercritical flow over a biconvex airfoil was treated successfully, but the iterations did not converge for more strongly supercritical conditions In another work the addition of terms ot both sides of the difference equations stabilized the iteration for supercritical conditions with large supersonic zones. For this, the Cauchy-Riemann solver was revised to incl,ude the needed terms. Most recently, the evaluation of parameters for rapid convergence and comparisons, with Murman's line-relaxation method was described. The method was extended to full second order accuracy in a fully conservative formulation in another work.

Martin, E. Dale↗
NASA NTRSDate not supplied

Quantum-Accelerated Distributed Algorithms for Approximate Steiner Trees and Directed Minimum Spanning Trees

We present two algorithms in the Quantum CONGEST-CLIQUE model of distributed computation that succeed with high probability; one for producing an approximately optimal Steiner Tree, and one for producing an exact spanning arborescence of minimum weight, the analog of a Minimum Spanning Tree in a directed graph, each of which uses O~(n^(1/4)) rounds of communication and O~(n^(9/4)) messages, achieving a lower round and message complexity than any known algorithms in the classical CONGEST-CLIQUE model. The CONGEST distributed computational model allows limited-sized messages to be transmitted within a network described by a communication graph of size n in a series of rounds to address a computational problem. The size limitation for such messages isO(log(n)) bits at each edge of the communication graph per round. The communication graph in the CONGEST-CLIQUE model is fully connected. In the Quantum CONGEST-CLIQUE model, at most O(log(n)) classical and quantum bits (qubits) can be communicated across each edge of the communication graph per round. At a high level, we achieve these results by combining classical algorithms with fast quantum subroutines. These speedups further contribute to understanding what problems can be solved more efficiently when we allow quantum communication in this CONGEST-CLIQUE model of distributed computation.

quantum distributed algorithms↗
NASA NTRS2020

Search and Rescue under the Forest Canopy using Multiple UAS

We consider the problem of multi-robot search and rescue under the forest canopy. Forest is a particularly challenging environment for collaborative mapping and exploration, mainly due to the existence of severe perceptual aliasing, which hinders reliable mutual localization and map fusion. Our proposed system features unmanned aerial vehicles (UAVs) with onboard sensing and autonomy. Each UAV runs a lightweight filtering algorithm for local state estimation, and a dynamic-aware frontier selection algorithm for fast exploration. The essential and computationally intensive task of collaborative simultaneous localization and mapping (CSLAM) is performed at a central ground station. To handle perceptual aliasing, we make use of stable landmarks extracted from trees, which significantly improve precision and recall during place recognition. Furthermore, to recover from incorrect pairwise data associations during loop closure, we propose a novel procedure for global data association based on recently developed techniques on cycle consistent multiway matching. Our algorithm returns a global data association that is guaranteed to be cycle consistent, and is shown to significantly improve precision compared to the input pairwise associations. The overall multi-UAV system is extensively validated during real-world collaborative exploration missions in a forest at NASA Langley Research Center.

Multi-robot systems↗
NASA NTRS2008

Mapping Snow Grain Size over Greenland from MODIS

This paper presents a new automatic algorithm to derive optical snow grain size (SGS) at 1 km resolution using Moderate Resolution Imaging Spectroradiometer (MODIS) measurements. Differently from previous approaches, snow grains are not assumed to be spherical but a fractal approach is used to account for their irregular shape. The retrieval is conceptually based on an analytical asymptotic radiative transfer model which predicts spectral bidirectional snow reflectance as a function of the grain size and ice absorption. The analytical form of solution leads to an explicit and fast retrieval algorithm. The time series analysis of derived SGS shows a good sensitivity to snow metamorphism, including melting and snow precipitation events. Preprocessing is performed by a Multi-Angle Implementation of Atmospheric Correction (MAIAC) algorithm, which includes gridding MODIS data to 1 km resolution, water vapor retrieval, cloud masking and an atmospheric correction. MAIAC cloud mask (CM) is a new algorithm based on a time series of gridded MODIS measurements and an image-based rather than pixel-based processing. Extensive processing of MODIS TERRA data over Greenland shows a robust performance of CM algorithm in discrimination of clouds over bright snow and ice. As part of the validation analysis, SGS derived from MODIS over selected sites in 2004 was compared to the microwave brightness temperature measurements of SSM\I radiometer, which is sensitive to the amount of liquid water in the snowpack. The comparison showed a good qualitative agreement, with both datasets detecting two main periods of snowmelt. Additionally, MODIS SGS was compared with predictions of the snow model CROCUS driven by measurements of the automatic whether stations of the Greenland Climate Network. We found that CROCUS grain size is on average a factor of two larger than MODIS-derived SGS. Overall, the agreement between CROCUS and MODIS results was satisfactory, in particular before and during the first melting period in mid-June. Following detailed time series analysis of SGS for four permanent sites, the paper presents SGS maps over the Greenland ice sheet for the March-September period of 2004.

Lyapustin, Alexei↗
NASA NTRS1991

Fast Approximate Analysis Of Modified Antenna Structure

Abbreviated algorithms developed for fast approximate analysis of effects of modifications in supporting structures upon root-mean-square (rms) path-length errors of paraboloidal-dish antennas. Involves combination of methods of structural-modification reanalysis with new extensions of correlation analysis to obtain revised rms path-length error. Full finite-element analysis, usually requires computer of substantial capacity, necessary only to obtain responses of unmodified structure to known external loads and to selected self-equilibrating "indicator" loads. Responses used in shortcut calculations, which, although theoretically "exact", simple enough to be performed on hand-held calculator. Useful in design, design-sensitivity analysis, and parametric studies.

Levy, Roy↗
NASA NTRS1996

Error and Complexity Analysis for a Collocation-Grid-Projection Plus Precorrected-FFT Algorithm for Solving Potential Integral Equations with LaPlace or Helmholtz Kernels

In this paper we derive error bounds for a collocation-grid-projection scheme tuned for use in multilevel methods for solving boundary-element discretizations of potential integral equations. The grid-projection scheme is then combined with a precorrected FFT style multilevel method for solving potential integral equations with 1/r and e(sup ikr)/r kernels. A complexity analysis of this combined method is given to show that for homogeneous problems, the method is order n natural log n nearly independent of the kernel. In addition, it is shown analytically and experimentally that for an inhomogeneity generated by a very finely discretized surface, the combined method slows to order n(sup 4/3). Finally, examples are given to show that the collocation-based grid-projection plus precorrected-FFT scheme is competitive with fast-multipole algorithms when considering realistic problems and 1/r kernels, but can be used over a range of spatial frequencies with only a small performance penalty.

Phillips, J. R.↗
NASA NTRS2006

Fast Lossless Compression of Multispectral-Image Data

An algorithm that effects fast lossless compression of multispectral-image data is based on low-complexity, proven adaptive-filtering algorithms. This algorithm is intended for use in compressing multispectral-image data aboard spacecraft for transmission to Earth stations. Variants of this algorithm could be useful for lossless compression of three-dimensional medical imagery and, perhaps, for compressing image data in general.

Klimesh, Matthew↗
NASA NTRS1976

Digital processing of satellite imagery application to jungle areas of Peru

The author has identified the following significant results. The use of clustering methods permits the development of relatively fast classification algorithms that could be implemented in an inexpensive computer system with limited amount of memory. Analysis of CCTs using these techniques can provide a great deal of detail permitting the use of the maximum resolution of LANDSAT imagery. Potential cases were detected in which the use of other techniques for classification using a Gaussian approximation for the distribution functions can be used with advantage. For jungle areas, channels 5 and 7 can provide enough information to delineate drainage patterns, swamp and wet areas, and make a reasonable broad classification of forest types.

Pomalaza, J. C.↗
NASA NTRS1980

Spectral analysis of GEOS-3 altimeter data and frequency domain collocation

The mathematical background in spectral analysis as applied to geodetic applications is summarized. The resolution (cut-off frequency) of the GEOS 3 altimeter data is examined by determining the shortest wavelength (corresponding to the cut-off frequency) recoverable. The data from some 18 profiles are used. The total power (variance) in the sea surface topography with respect to the reference ellipsoid as well as with respect to the GEM-9 surface is computed. A fast inversion algorithm for matrices of simple and block Toeplitz matrices and its application to least squares collocation is explained. This algorithm yields a considerable gain in computer time and storage in comparison with conventional least squares collocation. Frequency domain least squares collocation techniques are also introduced and applied to estimating gravity anomalies from GEOS 3 altimeter data. These techniques substantially reduce the computer time and requirements in storage associated with the conventional least squares collocation. Numerical examples given demonstrate the efficiency and speed of these techniques.

Eren, K.↗
NASA NTRS1979

Design of a 24-channel transmultiplexer

The design of a transmultiplexer capable of performing the bilateral conversion between one 1544 kbit/s digital signal (which represents 24 PCM coded voice channels) and two analog group signals (each one containing 12 voice channels in the 60-108 kHz band) is investigated. It is shown that an FIR filter bank required as part of such a transmultiplexer can be realized efficiently by cascading a discrete cosine transform processor and a weighting network. Fast convolution algorithms are derived for evaluating the cosine transform. A method of using the symmetry conditions to reduce the computation rate in the weighting network and an elegant hardware configuration for implementing it are also discussed.

Narasimha, M. J.↗
NASA NTRS1981

Geologic applications of thermal-inertia mapping from satellite

In the Powder River Basin, Wyo., narrow geologic units having thermal inertias which contrast with their surroundings can be discriminated in optimal images. A few subtle thermal inertia anomalies coincide with areas of helium leakage believed to be associated with deep oil and gas concentrations. The most important results involved delineation of tectonic framework elements some of which were not previously recognized. Thermal and thermal inertia images also permit mapping of geomorphic textural domains. A thermal lineament appears to reveal a basement discontinuity which involves the Homestake Mine in the Black Hill, a zone of Tertiary igneous activity and facies control in oil producing horizons. Applications of these data to the Cabeza Prieta, Ariz., area illustrate their potential for igneous rock type discrimination. Extension to Yellowstone National Park resulted in the detection of additional structural information but surface hydrothermal features could not be distinguished with any confidence. A thermal inertia mapping algorithm, a fast and accurate image registration technique, and an efficient topographic slope and elevation correction method were developed.

Offield, T. W.↗
NASA NTRS1981

Direct numerical simulations of turbulent shear flows

Numerical simulations of wakes of axisymmetric bodies and of turbulent mixing layers are reported. The flows were assumed to be statistically homogeneous in the mean flow direction, in concert with experimental data and the self-similarity theorem. The nonlinear Navier-Stokes equations were solved by a pseudo-spectral numerical method using a 32 x 32 x 33 point grid and an algorithm for fast Fourier transforms and inverse transforms. Leapfrog time differencing was employed on nonlinear terms and time differencing on viscous terms. Towed wakes and wakes behind a self-propelled body were simulated, showing that the towed wakes exhibited a proper temporal behavior after an initial period of adjustment, including the development of a kurtosis near the wake edge, which is experimentally verifiable. The mixing-layer simulation displayed the laboratory demonstrated presence of large scale features such as vortex cores, while the lateral coherence was weak.

Metcalfe, R. W.↗
NASA NTRS1983

Automated basin delineation from digital terrain data

While digital terrain grids are now in wide use, accurate delineation of drainage basins from these data is difficult to efficiently automate. A recursive order N solution to this problem is presented. The algorithm is fast because no point in the basin is checked more than once, and no points outside the basin are considered. Two applications for terrain analysis and one for remote sensing are given to illustrate the method, on a basin with high relief in the Sierra Nevada. This technique for automated basin delineation will enhance the utility of digital terrain analysis for hydrologic modeling and remote sensing.

Marks, D.↗
NASA NTRS1984

Coding for reliable satellite communications

Several error control coding techniques for reliable satellite communications were investigated to find algorithms for fast decoding of Reed-Solomon codes in terms of dual basis. The decoding of the (255,223) Reed-Solomon code, which is used as the outer code in the concatenated TDRSS decoder, was of particular concern.

Lin, S.↗
NASA NTRS1985

Identifying approximate linear models for simple nonlinear systems

This paper addresses the identification (realization) of approximate linear models from response data for certain nonlinear dynamic systems. Response characteristics for several typical nonlinear joints are analyzed mathematically and represented by series expansions. The parameters of the series expansion are then compared with the modal parameters of a linear model identified by the Eigensystem Realization Algorithm. The agreement of the identified model and the analytically derived representation is excellent for the cases studied. Also laboratory data from a model which exhibited stiffening behavior was analyzed using the Eigensystem Realization algorithm and Fast Fourier Transform. The laboratory experiment demonstrated the ability of the technique to recover the model characteristics using real data.

Horta, L. G.↗