SEARCH · Engineering Papers
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.
This thesis describes several new quantum algorithms. These include a polynomial time algorithm that uses a quantum fast Fourier transform to find eigenvalues and eigenvectors of a Hamiltonian operator, and that can be applied in cases for which all know classical algorithms require exponential time.
A method is proposed to streamline the transform decoding algorithm for Reed-Solomon (RS) codes of length equal to 2 raised to the power 2n. It is shown that a high-radix fast Fourier transform (FFT) type algorithm with generator equal to 3 on GF(F sub n), where F sub n is a Fermat prime, can be used to decode RS codes of this length. For a 256-symbol RS code, a radix 4 and radix 16 FFT over GF(F sub 3) require, respectively, 30 and 70% fewer modulo F sub n multiplications than the usual radix 2 FFT.
Temporal gaps in discrete sampling sequences produce spurious Fourier components at the intermodulation frequencies of an oscillatory signal and the temporal gaps, thus significantly complicating spectral analysis of such sparsely sampled data. A new fast Fourier transform (FFT)-based algorithm has been developed, suitable for spectral analysis of sparsely sampled data with a relatively small number of oscillatory components buried in background noise. The algorithm's principal idea has its origin in the so-called 'clean' algorithm used to sharpen images of scenes corrupted by atmospheric and sensor aperture effects. It identifies as the signal's 'true' frequency that oscillatory component which, when passed through the same sampling sequence as the original data, produces a Fourier image that is the best match to the original Fourier space. The algorithm has generally met with succession trials with simulated data with a low signal-to-noise ratio, including those of a type similar to hourly residuals for Earth orientation parameters extracted from VLBI data. For eight oscillatory components in the diurnal and semidiurnal bands, all components with an amplitude-noise ratio greater than 0.2 were successfully extracted for all sequences and duty cycles (greater than 0.1) tested; the amplitude-noise ratios of the extracted signals were as low as 0.05 for high duty cycles and long sampling sequences. When, in addition to these high frequencies, strong low-frequency components are present in the data, the low-frequency components are generally eliminated first, by employing a version of the algorithm that searches for non-integer multiples of the discrete FET minimum frequency.
The Single Field-of-view Sounder Atmospheric Products (SiFSAP) answer the need for a novel high spatial resolution atmospheric data product for major hyper-spectral infrared (IR) sounder missions. SiFSAP include a complete set of atmospheric vertical profiles, cloud, and surface properties, which are physically retrieved from top-of-atmosphere (TOA) spectral radiances under all-sky conditions via a rigorously defined radiative transfer relationship. By using a state-of-art fast radiative transfer model and a carefully designed optimal estimation based physical retrieval scheme, the SiFSAP algorithm ensures both an ultra-fast data processing speed needed for operational weather applications and the radiometric consistency desired by long-term climate studies. SiFSAP supplement existing operational products by providing data at the native resolution of the sounder instruments, the direct and accurate retrieval of cloud scattering properties, and the establishment of ‘radiance closure.’
The Single Field-of-view Sounder Atmospheric Products (SiFSAP) answer the need for a novel high spatial resolution atmospheric data product for major hyper-spectral infrared (IR) sounder missions. SiFSAP include a complete set of atmospheric vertical profiles, cloud, and surface properties, which are physically retrieved from top-of-atmosphere (TOA) spectral radiances under all-sky conditions via a rigorously defined radiative transfer relationship. By using a state-of-art fast radiative transfer model and a carefully designed optimal estimation based physical retrieval scheme, the SiFSAP algorithm ensures both an ultra-fast data processing speed needed for operational weather applications and the radiometric consistency desired by long-term climate studies. SiFSAP supplement existing operational products by providing data at the native spatial resolution of the sounder instruments, the direct and accurate retrieval of cloud scattering properties, and the establishment of ‘radiance closure.’
Three adaptive line enhancer (ALE) algorithms and architectures, namely conventional ALE, ALE with Double Filtering (ALEDF), and ALE with Coherent Accumulation (ALECA) are investigated for fast carrier acquisition in time-domain.
Richards' equation, which models the flow of liquid through unsaturated porous media, is highly nonlinear and difficult to solve. Step gradients in the field variables require the use of fine grids and small time step sizes. The numerical instabilities caused by the nonlinearities often require the use of iterative methods such as Picard or Newton interation. These difficulties result in large CPU requirements in solving Richards equation. With this in mind, adaptive and multigrid methods are investigated for use with nonlinear equations such as Richards' equation. Attention is focused on one-dimensional transient problems. To investigate the use of multigrid and adaptive grid methods, a series of problems are studied. First, a multigrid program is developed and used to solve an ordinary differential equation, demonstrating the efficiency with which low and high frequency errors are smoothed out. The multigrid algorithm and an adaptive grid algorithm is used to solve one-dimensional transient partial differential equations, such as the diffusive and convective-diffusion equations. The performance of these programs are compared to that of the Gauss-Seidel and tridiagonal methods. The adaptive and multigrid schemes outperformed the Gauss-Seidel algorithm, but were not as fast as the tridiagonal method. The adaptive grid scheme solved the problems slightly faster than the multigrid method. To solve nonlinear problems, Picard iterations are introduced into the adaptive grid and tridiagonal methods. Burgers' equation is used as a test problem for the two algorithms. Both methods obtain solutions of comparable accuracy for similar time increments. For the Burgers' equation, the adaptive grid method finds the solution approximately three times faster than the tridiagonal method. Finally, both schemes are used to solve the water content formulation of the Richards' equation. For this problem, the adaptive grid method obtains a more accurate solution in fewer work units and less computation time than required by the tridiagonal method. The performance of the adaptive grid method tends to degrade as the solution process proceeds in time, but still remains faster than the tridiagonal scheme.
A model to assess the value of improved information regarding the inventories, productions, exports, and imports of crop on a worldwide basis is discussed. A previously proposed model is interpreted in a stochastic control setting and the underlying assumptions of the model are revealed. In solving the stochastic optimization problem, the Markov programming approach is much more powerful and exact as compared to the dynamic programming-simulation approach of the original model. The convergence of a dual variable Markov programming algorithm is shown to be fast and efficient. A computer program for the general model of multicountry-multiperiod is developed. As an example, the case of one country-two periods is treated and the results are presented in detail. A comparison with the original model results reveals certain interesting aspects of the algorithms and the dependence of the value of information on the incremental cost function.
The problem of uniformly distributing the load of a parallel program over a multiprocessor system was considered. A program was analyzed whose structure permits the computation of the optimal static solution. Then four strategies for load balancing were described and their performance compared. The strategies are: (1) the optimal static assignment algorithm which is guaranteed to yield the best static solution, (2) the static binary dissection method which is very fast but suboptimal, (3) the greedy algorithm, a static fully polynomial time approximation scheme, which estimates the optimal solution to arbitrary accuracy, and (4) the predictive dynamic load balancing heuristic which uses information on the precedence relationships within the program and outperforms any of the static methods. It is also shown that the overhead incurred by the dynamic heuristic is reduced considerably if it is started off with a static assignment provided by either of the three strategies.
An operational mapping algorithm was developed to process measurements of individual species observed by different satellite instruments on board UARS. Based on Fast Fourier Synoptic Mapping (FFSM), the algorithm accounts for the precessing orbit of UARS, the error of individual instruments, and gaps associated with instrument duty cycle and the satellite yaw maneuver. It provides synoptic structure and evolution on periods as short as 1 day, derived collectively from all observations of an individual species. The algorithm was applied to synoptically map temperature, thickness, and several chemical constituents observed by the instruments: MLS, CLAES, ISAMS, and HALOE. Each field variable observed by these instruments was mapped twice-daily in continuous global time series several months long. Mapped behavior produced via FFSM was compared against standard archived products generated via Kalman filtering. The standard map products reveal similar behavior, but are limited to features of larger scale. Tracer structure that develops through flow deformation and attending transport is therefore represented in those products more coarsely, eventually being sheared down to scales that are no longer represented properly. The synoptic time series also reveal a diurnal cycle for several of the constituents, one that emerges clearly in their space-time spectra. The zonal and meridional structure of diurnal variability was mapped by filtering the space-time spectrum, an intermediate product of FFSM, to those scales resolved by the UARS sampling. Geographical variations of the diurnal cycle have also been evaluated in its seasonal-mean structure by compositing distributions at individual local times. Both were compared to diurnal variations in chemical models and in dynamical models that account for transport by the diurnal tide. Diurnal variations were found to introduce spurious behavior into the archived products generated via Kalman filtering, behavior that is misrepresented in those synoptic time series. Aliasing by under-sampled diurnal variations introduces a bias into the time-mean structure of archived products. That systematic error is manifested as anomalous wave structure in the time-mean fields. By contrast, synoptic time series generated via FFSM faithfully represent such behavior as varying diurnally, so it does not corrupt time-mean structure. Tracer structure mapped via the above algorithm was being applied to determine the Brewer-Dobson circulation of the stratosphere through Lagrangian considerations. Preliminary results are encouraging: They reveal diabatic ascent in the tropics, balanced by diabatic descent over the winter hemisphere. This Lagrangian description of transport derived from UARS tracer measurements would be potentially valuable for diagnosing interannual changes of transport, specifically, in relation to interannual changes of total ozone. Regrettably, support was reduced to 50% of the approved funding level, leaving this component incomplete.
Hyperspectral IR sounders such as AIRS on Aqua, CrIS on S-NPP, NOAA20 and JPSS-2, IASI on Metop A, B, and C provide high-quality atmospheric temperature, water, vapor, and greenhouse gas vertical profiles. Additionally, they provide atmospheric cloud properties, surface emissivity, and surface skin temperatures. We have developed two algorithms which can consistently derive these products from multiple IR sounders. The first one is a Single Field-of-view Sounder Atmospheric Product (SIFSAP) algorithm and the second one is a Climate Fingerprinting Sounder Product (ClimFiSP) algorithm. The SiFSAP algorithm performs one retrieval for each FOV using an all-sky optimal estimation approach. The core of the SiFSAP algorithm is an accurate and fast Principal Component-based Radiative Transfer Model (PCRTM), which can calculate hyperspectral radiance spectra under both clear and cloudy conditions. The PCRTM was developed in the past decade using consistent reference line-by-line radiative transfer model and spectroscopy for hyperspectral sounders such as AIRS, CrIS, IASI, NAST-I, and S-HIS. The ClimFiSP algorithm, which performs retrievals from spatiotemporally averaged L1 hyperspectral radiances directly, will be orders of magnitude faster than traditional method. he ClimFiSP algorithm uses consistent radiative kernels and a robust spectral fingerprinting method. It provides accurate data climate data fusion products from multiple satellite sensors. Both SiFSAP and ClimFiSP will be available at NASA GES DISC data center for public access.
Hyperspectral IR sounders such as AIRS on Aqua, CrIS on S-NPP, NOAA20 and JPSS-2, IASI on Metop A, B, and C provide high-quality atmospheric temperature, water, vapor, and greenhouse gas vertical profiles. Additionally, they provide atmospheric cloud properties, surface emissivity, and surface skin temperatures. We have developed two algorithms which can consistently derive these products from multiple IR sounders. The first one is a Single Field-of-view Sounder Atmospheric Product (SIFSAP) algorithm and the second one is a Climate Fingerprinting Sounder Product (ClimFiSP) algorithm. The SiFSAP algorithm performs one retrieval for each FOV using an all-sky optimal estimation approach. The core of the SiFSAP algorithm is an accurate and fast Principal Component-based Radiative Transfer Model (PCRTM), which can calculate hyperspectral radiance spectra under both clear and cloudy conditions. The PCRTM was developed in the past decade using consistent reference line-by-line radiative transfer model and spectroscopy for hyperspectral sounders such as AIRS, CrIS, IASI, NAST-I, and S-HIS. The ClimFiSP algorithm, which performs retrievals from spatiotemporally averaged L1 hyperspectral radiances directly, will be orders of magnitude faster than traditional method. he ClimFiSP algorithm uses consistent radiative kernels and a robust spectral fingerprinting method. It provides accurate data climate data fusion products from multiple satellite sensors. Both SiFSAP and ClimFiSP will be available at NASA GES DISC data center for public access.
Hyperspectral IR sounders such as AIRS on Aqua, CrIS on S-NPP, NOAA20 and JPSS-2, IASI on Metop A, B, and C provide high-quality atmospheric temperature, water, vapor, and greenhouse gas vertical profiles. Additionally, they provide atmospheric cloud properties, surface emissivity, and surface skin temperatures. We have developed two algorithms which can consistently derive these products from multiple IR sounders. The first one is a Single Field-of-view Sounder Atmospheric Product (SIFSAP) algorithm and the second one is a Climate Fingerprinting Sounder Product (ClimFiSP) algorithm. Compared to current operational AIRS and CrIS Level-2 (L2) algorithms, which perform one retrieval for each 3 by 3 field of views (FOVs) using a cloud-clearing approach, the SiFSAP algorithm, on the other hand, performs one retrieval for each FOV using an all-sky optimal estimation approach. The SiFSAP algorithm retrieves all the above-mentioned atmosphere and surface properties simultaneously including cloud properties with 3-time higher spatial resolution and 9-times more products. The core of the SiFSAP algorithm is an accurate and fast Principal Component-based Radiative Transfer Model (PCRTM), which can calculate hyperspectral radiance spectra under both clear and cloudy conditions. The PCRTM was developed in the past decade using consistent reference line-by-line radiative transfer model and spectroscopy for hyperspectral sounders such as AIRS, CrIS, IASI, NAST-I, and S-HIS. The SiFSAP retrieval algorithm also uses the same climatology a priori and associated covariances, which makes it ideal for generating high quality products for both weather and climate applications. Climate products are typically derived by performing spatial and temporal averaging of L2 products. It is a time-consuming process to generate L2 data products since AIRS, CrIS, and IASI have millions of observations each day with thousands of spectral channels for each observation. Additionally, differences in L2 retrieval algorithms for different satellite sensors can lead to errors in the climate products. Our ClimFiSP algorithm, which performs retrievals from spatiotemporally averaged L1 hyperspectral radiances directly, will be orders of magnitude faster than traditional method. he ClimFiSP algorithm uses consistent radiative kernels and a robust spectral fingerprinting method. It provides accurate data climate data fusion products from multiple satellite sensors. We have applied this method to both AIRS and CrIS (on SNPP and on NOAA 20) data and generated two decades climate data records for atmospheric temperature, water vapor, cloud, trace gases, and surface skin temperature. Both SiFSAP and ClimFiSP will be available at NASA GES DISC data center for public access.
The Air Traffic Monotonic Lagrangian Grid (ATMLG) is presented as a tool to evaluate new air traffic system concepts. The model, based on an algorithm called the Monotonic Lagrangian Grid (MLG), can quickly sort, track, and update positions of many aircraft, both on the ground (at airports) and in the air. The underlying data structure is based on the MLG, which is used for sorting and ordering positions and other data needed to describe N moving bodies and their interactions. Aircraft that are close to each other in physical space are always near neighbors in the MLG data arrays, resulting in a fast nearest-neighbor interaction algorithm that scales as N. Recent upgrades to ATMLG include adding blank place-holders within the MLG data structure, which makes it possible to dynamically change the MLG size and also improves the quality of the MLG grid. Additional upgrades include adding FAA flight plan data, such as way-points and arrival and departure times from the Enhanced Traffic Management System (ETMS), and combining the MLG with the state-of-the-art strategic and tactical conflict detection and resolution algorithms from the NASA-developed Stratway software. In this paper, we present results from our early efforts to couple ATMLG with the Stratway software, and we demonstrate that it can be used to quickly simulate air traffic flow for a very large ETMS dataset.
The fast adaptive composite grid method (FAC) is an algorithm that uses various levels of uniform grids to provide adaptive resolution and fast solution of PDEs. An asynchronous version of FAC, called AFAC, that completely eliminates the bottleneck to parallelism is presented. This paper describes the advantage that this algorithm has in adaptive refinement for moving singularities on multiprocessor computers. This work is applicable to the parallel solution of two- and three-dimensional shock tracking problems.
Conscan is commonly used by DSN antennas to allow adaptive tracking of a target whose position is not precisely known. This article describes an algorithm that is based on a Kalman filter and is proposed to replace the existing fast Fourier transform based (FFT-based) algorithm for conscan. Advantages of this algorithm include better pointing accuracy, continuous update information, and accommodation of missing data. Additionally, a strategy for adaptive selection of the conscan radius is proposed. The performance of the algorithm is illustrated through computer simulations and compared to the FFT algorithm. The results show that the Kalman filter algorithm is consistently superior.
As systems designers design communication systems with digital rather than analog components to reduce noise and increase channel capacity, they must have the ability to perform traditional communication algorithms digitally. The use of trellis coded modulation as well as the extensive use of convolutional encoding for error detection and correction requires an efficient digital implementation of the Viterbi Algorithm for real time demodulation and decoding. Digital signal processors are now fast enough to implement Viterbi decoding in conjunction with the normal receiver/transmitter functions for lower speed channels on a single chip as well as performing fast decoding for higher speed channels, if the algorithm is implemented efficiently. The purpose of this paper is to identify a good way to implement the Viterbi Algorithm (VA) on the Motorola DSP56001, balancing performance considerations with speed and memory efficiency.
The simulation of changes in the Earth's climate due to solar and thermal radiative processes with global climate models (GCMs) is highly complex, depending on the parameterization of a multitude of nonlinearly coupled physical processes. In contrast, the germ of global climate change, the radiative forcing from enhanced abundances of greenhouse gases, is relatively well understood. The impressive agreement between detailed radiation calculations and highly resolved spectral radiation measurements in the thermal infrared under cloudless conditions (see, for example, Fig. 1) instills confidence in our knowledge of the sources of gaseous absorption. That the agreement spans a broad range of temperature and humidity regimes using instruments mounted on surface, aircraft, and satellite platforms not only attests to our capability to accurately calculate radiative fluxes under present conditions, but also provides confidence in the spectroscopic basis for computation of fluxes under conditions that might characterize future global climate (e.g., radiative forcing). Alas, the computational costs of highly resolved spectral radiation calculations cannot be afforded presently in GCMs. Such calculations have instead been used as the foundation for approximations implemented in fast but generally less accurate algorithms performing the needed radiative transfer (RT) calculations in GCMs. Credible climate simulations by GCMs cannot be ensured without accurate solar and thermal radiative flux calculations under all types of sky conditions: pristine cloudless, aerosol-laden, and cloudy. The need for accuracy in RT calculations is not only important for greenhouse gas forcing scenarios, but is also profoundly needed for the robust simulation of many other atmospheric phenomena, such as convective processes.