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 343 records · Page 19
All sourcesNASA NTRSDOE OSTI
NASA NTRS1993

Fast structural design and analysis via hybrid domain decomposition on massively parallel processors

A hybrid domain decomposition framework for static, transient and eigen finite element analyses of structural mechanics problems is presented. Its basic ingredients include physical substructuring and /or automatic mesh partitioning, mapping algorithms, 'gluing' approximations for fast design modifications and evaluations, and fast direct and preconditioned iterative solvers for local and interface subproblems. The overall methodology is illustrated with the structural design of a solar viewing payload that is scheduled to fly in March 1993. This payload has been entirely designed and validated by a group of undergraduate students at the University of Colorado using the proposed hybrid domain decomposition approach on a massively parallel processor. Performance results are reported on the CRAY Y-MP/8 and the iPSC-860/64 Touchstone systems, which represent both extreme parallel architectures. The hybrid domain decomposition methodology is shown to outperform leading solution algorithms and to exhibit an excellent parallel scalability.

Farhat, Charbel↗
NASA NTRS2012

Simulation and Flight Test Capability for Testing Prototype Sense and Avoid System Elements

NASA Langley Research Center (LaRC) and The MITRE Corporation (MITRE) have developed, and successfully demonstrated, an integrated simulation-to-flight capability for evaluating sense and avoid (SAA) system elements. This integrated capability consists of a MITRE developed fast-time computer simulation for evaluating SAA algorithms, and a NASA LaRC surrogate unmanned aircraft system (UAS) equipped to support hardware and software in-the-loop evaluation of SAA system elements (e.g., algorithms, sensors, architecture, communications, autonomous systems), concepts, and procedures. The fast-time computer simulation subjects algorithms to simulated flight encounters/ conditions and generates a fitness report that records strengths, weaknesses, and overall performance. Reviewed algorithms (and their fitness report) are then transferred to NASA LaRC where additional (joint) airworthiness evaluations are performed on the candidate SAA system-element configurations, concepts, and/or procedures of interest; software and hardware components are integrated into the Surrogate UAS research systems; and flight safety and mission planning activities are completed. Onboard the Surrogate UAS, candidate SAA system element configurations, concepts, and/or procedures are subjected to flight evaluations and in-flight performance is monitored. The Surrogate UAS, which can be controlled remotely via generic Ground Station uplink or automatically via onboard systems, operates with a NASA Safety Pilot/Pilot in Command onboard to permit safe operations in mixed airspace with manned aircraft. An end-to-end demonstration of a typical application of the capability was performed in non-exclusionary airspace in October 2011; additional research, development, flight testing, and evaluation efforts using this integrated capability are planned throughout fiscal year 2012 and 2013.

Howell, Charles T.↗
NASA NTRS1987

Fast-Polynomial-Transform Program

Computer program uses fast-polynomial-transformation (FPT) algorithm applicable to two-dimensional mathematical convolutions. Two-dimensional cyclic convolutions converted to one-dimensional convolutions in polynomial rings. Program decomposes cyclic polynomials into polynomial convolutions of same length. Only FPT's and fast Fourier transforms of same length required. Modular approach saves computional resources. Program written in C.

Truong, T. K.↗
NASA NTRS1987

Robotic vision/sensing for space applications

A review is presented of efforts currently in progress at the NASA/Johnson Space Center and Rice University, the accomplishments to date, and some of the anticipated future developments. Both systems and algorithms are discussed. The evolution of future vision/sensing is projected to included the fusion of multisensors ranging from microwave to optical with multimode capability to include position, attitude, recognition, and motion parameters. The algorithms for information extraction are expected to incorporate aspects of intelligence and knowledge for the interpolation and extrapolation of the needed data. The key features of the overall system design will be small size and weight, fast signal processing, robust algorithms, and accurate parameter determination. These aspects of vision/sensing are also discussed.

Krishen, Kumar↗
NASA NTRS1992

A fast, uncoupled, compressible, two-dimensional, unsteady boundary layer algorithm with separation for engine inlets

A finite difference boundary layer algorithm was developed to model viscous effects when an inviscid core flow solution is given. This algorithm solved each boundary layer equation separately, then iterated to find a solution. Solving the boundary layer equations sequentially was 2.4 to 4.0 times faster than solving the boundary layer equations simultaneously. This algorithm used a modified Baldwin-Lomax turbulence model, a weighted average of forward and backward differencing of the pressure gradient, and a backward sweep of the pressure. With these modifications, the boundary layer algorithm was able to model flows with and without separation. The number of grid points used in the boundary layer algorithm affected the stability of the algorithm as well as the accuracy of the predictions of friction coefficients and momentum thicknesses. Results of this boundary layer algorithm compared well with experimental observations of friction coefficients and momentum thicknesses. In addition, when used interactively with an inviscid flow algorithm, this boundary layer algorithm corrected for viscous effects to give a good match with experimental observations for pressures in a supersonic inlet.

Roach, Robert L.↗
NASA NTRS1992

A fast, uncoupled, compressible, two-dimensional, unsteady boundary layer algorithm with separation for engine inlets

A finite difference boundary layer algorithm was developed to model viscous effects when an inviscid core flow solution is given. This algorithm solved each boundary layer equation separately, then iterated to find a solution. Solving the boundary layer equations sequentially was 2.4 to 4.0 times faster than solving the boundary layer equations simultaneously. This algorithm used a modified Baldwin-Lomax turbulence model, a weighted average of forward and backward differencing of the pressure gradient, and a backward sweep of the pressure. With these modifications, the boundary layer algorithm was able to model flows with and without separation. The number of grid points used in the boundary layer algorithm affected the stability of the algorithm affected the stability of the algorithm as well as the accuracy of the predictions of friction coefficients and momentum thicknesses. Results of this boundary layer algorithm compared well with experimental observations of friction coefficients and momentum thicknesses. In addition, when used interactively with an inviscid flow algorithm, this boundary layer algorithm corrected for viscous effects to give a good match with experimental observations for pressures in a supersonic inlet.

Roach, Robert L.↗
NASA NTRS1985

Approximate-factorization schemes for solving the transonic full-potential equation

The present paper provides a general discussion of approximate-factorization techniques applied to the transonic full-potential equation. Giving particular attention to the AF2 approximate-factorization scheme. This scheme was first introduced by Ballhaus and Steger (1975) for solving the low-frequency (unsteady), transonic small-disturbance equation. The full-potential equation algorithm is examined, taking into account the governing equations, grid generation, the artificial density scheme (spatial differencing), the alternating direction implicit scheme, the AF2 iteration scheme, temporal damping, and boundary conditions. Computed results are also presented. It is shown that fast, fully-implicit algorithms of the approximate-factorization variety are both efficient and reliable for solving the conservative full-potential equation.

Holst, T. L.↗
NASA NTRS1984

CREKID: A computer code for transient, gas-phase combustion of kinetics

A new algorithm was developed for fast, automatic integration of chemical kinetic rate equations describing homogeneous, gas-phase combustion at constant pressure. Particular attention is paid to the distinguishing physical and computational characteristics of the induction, heat-release and equilibration regimes. The two-part predictor-corrector algorithm, based on an exponentially-fitted trapezoidal rule, includes filtering of ill-posed initial conditions, automatic selection of Newton-Jacobi or Newton iteration for convergence to achieve maximum computational efficiency while observing a prescribed error tolerance. The new algorithm was found to compare favorably with LSODE on two representative test problems drawn from combustion kinetics.

Pratt, D. T.↗
NASA NTRS1987

Vision technology/algorithms for space robotics applications

The thrust of automation and robotics for space applications has been proposed for increased productivity, improved reliability, increased flexibility, higher safety, and for the performance of automating time-consuming tasks, increasing productivity/performance of crew-accomplished tasks, and performing tasks beyond the capability of the crew. This paper provides a review of efforts currently in progress in the area of robotic vision. Both systems and algorithms are discussed. The evolution of future vision/sensing is projected to include the fusion of multisensors ranging from microwave to optical with multimode capability to include position, attitude, recognition, and motion parameters. The key feature of the overall system design will be small size and weight, fast signal processing, robust algorithms, and accurate parameter determination. These aspects of vision/sensing are also discussed.

Krishen, Kumar↗
NASA NTRS1991

Fast, efficient lossless data compression

This paper presents lossless data compression and decompression algorithms which can be easily implemented in software. The algorithms can be partitioned into their fundamental parts which can be implemented at various stages within a data acquisition system. This allows for efficient integration of these functions into systems at the stage where they are most applicable. The algorithms were coded in Forth to run on a Silicon Composers Single Board Computer (SBC) using the Harris RTX2000 Forth processor. The algorithms require very few system resources and operate very fast. The performance of the algorithms with the RTX enables real time data compression and decompression to be implemented for a wide range of applications.

Ross, Douglas↗
NASA NTRS2004

cWINNOWER algorithm for finding fuzzy dna motifs

The cWINNOWER algorithm detects fuzzy motifs in DNA sequences rich in protein-binding signals. A signal is defined as any short nucleotide pattern having up to d mutations differing from a motif of length l. The algorithm finds such motifs if a clique consisting of a sufficiently large number of mutated copies of the motif (i.e., the signals) is present in the DNA sequence. The cWINNOWER algorithm substantially improves the sensitivity of the winnower method of Pevzner and Sze by imposing a consensus constraint, enabling it to detect much weaker signals. We studied the minimum detectable clique size qc as a function of sequence length N for random sequences. We found that qc increases linearly with N for a fast version of the algorithm based on counting three-member sub-cliques. Imposing consensus constraints reduces qc by a factor of three in this case, which makes the algorithm dramatically more sensitive. Our most sensitive algorithm, which counts four-member sub-cliques, needs a minimum of only 13 signals to detect motifs in a sequence of length N = 12,000 for (l, d) = (15, 4). Copyright Imperial College Press.

Evaluation Studies↗
NASA NTRS2003

cWINNOWER Algorithm for Finding Fuzzy DNA Motifs

The cWINNOWER algorithm detects fuzzy motifs in DNA sequences rich in protein-binding signals. A signal is defined as any short nucleotide pattern having up to d mutations differing from a motif of length l. The algorithm finds such motifs if multiple mutated copies of the motif (i.e., the signals) are present in the DNA sequence in sufficient abundance. The cWINNOWER algorithm substantially improves the sensitivity of the winnower method of Pevzner and Sze by imposing a consensus constraint, enabling it to detect much weaker signals. We studied the minimum number of detectable motifs qc as a function of sequence length N for random sequences. We found that qc increases linearly with N for a fast version of the algorithm based on counting three-member sub-cliques. Imposing consensus constraints reduces qc, by a factor of three in this case, which makes the algorithm dramatically more sensitive. Our most sensitive algorithm, which counts four-member sub-cliques, needs a minimum of only 13 signals to detect motifs in a sequence of length N = 12000 for (l,d) = (15,4).

Liang, Shoudan↗
NASA NTRS2000

Wavelet-Based Interpolation and Representation of Non-Uniformly Sampled Spacecraft Mission Data

A well-documented problem in the analysis of data collected by spacecraft instruments is the need for an accurate, efficient representation of the data set. The data may suffer from several problems, including additive noise, data dropouts, an irregularly-spaced sampling grid, and time-delayed sampling. These data irregularities render most traditional signal processing techniques unusable, and thus the data must be interpolated onto an even grid before scientific analysis techniques can be applied. In addition, the extremely large volume of data collected by scientific instrumentation presents many challenging problems in the area of compression, visualization, and analysis. Therefore, a representation of the data is needed which provides a structure which is conducive to these applications. Wavelet representations of data have already been shown to possess excellent characteristics for compression, data analysis, and imaging. The main goal of this project is to develop a new adaptive filtering algorithm for image restoration and compression. The algorithm should have low computational complexity and a fast convergence rate. This will make the algorithm suitable for real-time applications. The algorithm should be able to remove additive noise and reconstruct lost data samples from images.

Bose, Tamal↗
NASA NTRS1985

Multigrid solutions to quasi-elliptic schemes

Quasi-elliptic schemes arise from central differencing or finite element discretization of elliptic systems with odd order derivatives on non-staggered grids. They are somewhat unstable and less accurate then corresponding staggered-grid schemes. When usual multigrid solvers are applied to them, the asymptotic algebraic convergence is necessarily slow. Nevertheless, it is shown by mode analyses and numerical experiments that the usual FMG algorithm is very efficient in solving quasi-elliptic equations to the level of truncation errors. Also, a new type of multigrid algorithm is presented, mode analyzed and tested, for which even the asymptotic algebraic convergence is fast. The essence of that algorithm is applicable to other kinds of problems, including highly indefinite ones.

Brandt, A.↗
NASA NTRS1985

Multigrid solutions to quasi-elliptic schemes

Quasi-elliptic schemes arise from central differencing or finite element discretization of elliptic systems with odd order derivatives on non-staggered grids. They are somewhat unstable and less accurate than corresponding staggered-grid schemes. When usual multigrid solvers are applied to them, the asymptotic algebraic convergence is necessarily slow. Nevertheless, it is shown by mode analyses and numerical experiments that the usual FMG algorithm is very efficient in solving quasi-elliptic equations to the level of truncation errors. Also, a new type of multigrid algorithm is presented, mode analyzed and tested, for which even the asymptotic algebraic convergence is fast. The essence of that algorithm is applicable to other kinds of problems, including highly indefinite ones.

Brandt, A.↗
NASA NTRS1993

High performance MPEG-audio decoder IC

The emerging digital audio and video compression technology brings both an opportunity and a new challenge to IC design. The pervasive application of compression technology to consumer electronics will require high volume, low cost IC's and fast time to market of the prototypes and production units. At the same time, the algorithms used in the compression technology result in complex VLSI IC's. The conflicting challenges of algorithm complexity, low cost, and fast time to market have an impact on device architecture and design methodology. The work presented in this paper is about the design of a dedicated, high precision, Motion Picture Expert Group (MPEG) audio decoder.

Thorn, M.↗
NASA NTRS1992

Real-time processing of radar return on a parallel computer

NASA is working with the FAA to demonstrate the feasibility of pulse Doppler radar as a candidate airborne sensor to detect low altitude windshears. The need to provide the pilot with timely information about possible hazards has motivated a demand for real-time processing of a radar return. Investigated here is parallel processing as a means of accommodating the high data rates required. A PC based parallel computer, called the transputer, is used to investigate issues in real time concurrent processing of radar signals. A transputer network is made up of an array of single instruction stream processors that can be networked in a variety of ways. They are easily reconfigured and software development is largely independent of the particular network topology. The performance of the transputer is evaluated in light of the computational requirements. A number of algorithms have been implemented on the transputers in OCCAM, a language specially designed for parallel processing. These include signal processing algorithms such as the Fast Fourier Transform (FFT), pulse-pair, and autoregressive modelling, as well as routing software to support concurrency. The most computationally intensive task is estimating the spectrum. Two approaches have been taken on this problem, the first and most conventional of which is to use the FFT. By using table look-ups for the basis function and other optimizing techniques, an algorithm has been developed that is sufficient for real time. The other approach is to model the signal as an autoregressive process and estimate the spectrum based on the model coefficients. This technique is attractive because it does not suffer from the spectral leakage problem inherent in the FFT. Benchmark tests indicate that autoregressive modeling is feasible in real time.

Aalfs, David D.↗
NASA NTRS1989

Operator induced multigrid algorithms using semirefinement

A variant of multigrid, based on zebra relaxation, and a new family of restriction/prolongation operators is described. Using zebra relaxation in combination with an operator-induced prolongation leads to fast convergence, since the coarse grid can correct all error components. The resulting algorithms are not only fast, but are also robust, in the sense that the convergence rate is insensitive to the mesh aspect ratio. This is true even though line relaxation is performed in only one direction. Multigrid becomes a direct method if an operator-induced prolongation is used, together with the induced coarse grid operators. Unfortunately, this approach leads to stencils which double in size on each coarser grid. The use of an implicit three point restriction can be used to factor these large stencils, in order to retain the usual five or nine point stencils, while still achieving fast convergence. This algorithm achieves a V-cycle convergence rate of 0.03 on Poisson's equation, using 1.5 zebra sweeps per level, while the convergence rate improves to 0.003 if optimal nine point stencils are used. Numerical results for two and three dimensional model problems are presented, together with a two level analysis explaining these results.

Decker, Naomi↗