Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Algorithms”

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 1,531 records · Page 85
All sourcesNASA NTRSDOE OSTI
NASA NTRS1988

An improved simulated annealing algorithm for standard cell placement

Simulated annealing is a general purpose Monte Carlo optimization technique that was applied to the problem of placing standard logic cells in a VLSI ship so that the total interconnection wire length is minimized. An improved standard cell placement algorithm that takes advantage of the performance enhancements that appear to come from parallelizing the uniprocessor simulated annealing algorithm is presented. An outline of this algorithm is given.

Jones, Mark↗
NASA NTRS1988

Efficient multiplication algorithms over the finite fields GF(q sup m), where q equals 3,5

Finite field multiplication is central to coding theory. For this application, there is a need for a multiplication algorithm which can be realized easily on VLSI chips. A new algorithm is developed which is based on the Babylonian multiplication technique utilizing tables of squares. This algorithm is applied to the finite fields GF(q sup m), where q equals 3 and 5. It is also shown that this multiplier can be used to compute complex multiplications defined on the direct sum of two identical copies of such Galois fields.

Truong, T. K.↗
NASA NTRS1988

A streamwise upwind algorithm for the Euler and Navier-Stokes equations applied to transonic flows

A new algorithm was developed for the Euler and Navier-Stokes equations that uses upwind differencing based on the streawise direction. This algorithm is time accurate and can be used in codes for calculating unsteady transonic flows over wings. Such codes can be used for the flutter analysis of wings. In this algorithm, the coordinate system is locally rotated to align with the streamwise direction. For differencing the convective terms in the streamwise direction, a new form of flux splitting is employed, in which the biasing depends on the local Mach number. In the plane perpendicular to the stream direction, the new flux splitting uses the condition of no flow in that local plane. By using a locally rotated coordinate system, the convective flux vector biasing depends on the total Mach number. Hence, the switching of the flux vector biasing occurs across shock waves and the proper domain of dependence is used in supersonic regions. For comparison, many other upwind methods switch differencing based on Mach number of shock waves in multidimensional flows. The formulas for the convective flux vector differencing do not contain any user specified parameters. So, the amount of numerical dissipation is automatically determined.

Goorjian, Peter M.↗
NASA NTRS1987

Array architectures for iterative algorithms

Regular mesh-connected arrays are shown to be isomorphic to a class of so-called regular iterative algorithms. For a wide variety of problems it is shown how to obtain appropriate iterative algorithms and then how to translate these algorithms into arrays in a systematic fashion. Several 'systolic' arrays presented in the literature are shown to be specific cases of the variety of architectures that can be derived by the techniques presented here. These include arrays for Fourier Transform, Matrix Multiplication, and Sorting.

Jagadish, Hosagrahar V.↗
NASA NTRS1987

Performance of a parallel algorithm for standard cell placement on the Intel Hypercube

A parallel simulated annealing algorithm for standard cell placement on the Intel Hypercube is presented. A novel tree broadcasting strategy is used extensively for updating cell locations in the parallel environment. Studies on the performance of the algorithm on example industrial circuits show that it is faster and gives better final placement results than uniprocessor simulated annealing algorithms.

Jones, Mark↗
NASA NTRS1987

On a finite element CFD algorithm for compressible, viscous and turbulent aerodynamic flows

This paper develops and analyses individual construction aspects of an efficient and accurate finite element algorithm for prediction of viscous and turbulent flow fields of impact in aerodynamics. The theoretical construction employs a Taylor weak statement (TWS) for coincident embedding of stability mechanisms within a classic Galerkin finite element formulation of semidiscrete approximation error orthogonalization. A wide variety of the stabilizing mechanisms of independently derived CFD algorithms are contained within the TWS theory. An implicit construction that meets the requirement of efficient convergence to steady state is developed. The theoretical asymptotic error estimates of the TWS finite element algorithm for supersonic and viscous boundary layer flows are verified. Application to a three-dimensional turbulent flow is cited.

Baker, A. J.↗
NASA NTRS1988

Explicit upwind algorithm for the parabolized Navier-Stokes equations

A new explicit upwind algorithm based on Roe's flux-difference splitting (FDS) method has been developed for the three-dimensional Parabolized Navier-Stokes (PNS) equations. For three-dimensional flows, FDS's are determined separately for the two nonmarching directions and modified to account for the calculated shock angle in the crossflow plane. Second-order FDS is applied to the pressure and convection terms with the streamwise pressure gradient limited in the subsonic region to maintain a hyperbolic inviscid equation set. Second-order central differencing is obtained in the two-step algorithm for the shear and heat flux terms. The new algorithm is demonstrated for three laminar flow test cases: supersonic flow over a flat plate, hypersonic flow over a 15 deg ramp, and hypersonic flow past a 10 deg cone at a 24 deg angle of attack. The computed results agree well with experimental measurements.

Korte, John J.↗
NASA NTRS1988

Towards developing robust algorithms for solving partial differential equations on MIMD machines

Methods for efficient computation of numerical algorithms on a wide variety of MIMD machines are proposed. These techniques reorganize the data dependency patterns to improve the processor utilization. The model problem finds the time-accurate solution to a parabolic partial differential equation discretized in space and implicitly marched forward in time. The algorithms are extensions of Jacobi and SOR. The extensions consist of iterating over a window of several timesteps, allowing efficient overlap of computation with communication. The methods increase the degree to which work can be performed while data are communicated between processors. The effect of the window size and of domain partitioning on the system performance is examined both by implementing the algorithm on a simulated multiprocessor system.

Saltz, Joel H.↗
NASA NTRS1988

A sparse matrix algorithm on the Boolean vector machine

VLSI technology is being used to implement a prototype Boolean Vector Machine (BVM), which is a large network of very small processors with equally small memories that operate in SIMD mode; these use bit-serial arithmetic, and communicate via cube-connected cycles network. The BVM's bit-serial arithmetic and the small memories of individual processors are noted to compromise the system's effectiveness in large numerical problem applications. Attention is presently given to the implementation of a basic matrix-vector iteration algorithm for space matrices of the BVM, in order to generate over 1 billion useful floating-point operations/sec for this iteration algorithm. The algorithm is expressed in a novel language designated 'BVM'.

Wagner, Robert A.↗
NASA NTRS1988

Advances in dual algorithms and convex approximation methods

A new algorithm for solving the duals of separable convex optimization problems is presented. The algorithm is based on an active set strategy in conjunction with a variable metric method. This first order algorithm is more reliable than Newton's method used in DUAL-2 because it does not break down when the Hessian matrix becomes singular or nearly singular. A perturbation technique is introduced in order to remove the nondifferentiability of the dual function which arises when linear constraints are present in the approximate problem.

Smaoui, H.↗
NASA NTRS1987

An algorithm for a generalization of the Richardson extrapolation process

The paper presents a recursive method, designated the W exp (m)-algorithm, for implementing a generalization of the Richardson extrapolation process. Compared to the direct solution of the linear sytems of equations defining the extrapolation procedure, this method requires a small number of arithmetic operations and very little storage. The technique is also applied to solve recursively the coefficient problem associated with the rational approximations obtained by applying a d-transformation to power series. In the course of development a new recursive algorithm for implementing a very general extrapolation procedure is introduced, for solving the same problem. A FORTRAN program for the W exp (m)-algorithm is also appended.

Ford, William F.↗
NASA NTRS1987

Differential sampling for fast frequency acquisition via adaptive extended least squares algorithm

This paper presents a differential signal model along with appropriate sampling techinques for least squares estimation of the frequency and frequency derivatives and possibly the phase and amplitude of a sinusoid received in the presence of noise. The proposed algorithm is recursive in mesurements and thus the computational requirement increases only linearly with the number of measurements. The dimension of the state vector in the proposed algorithm does not depend upon the number of measurements and is quite small, typically around four. This is an advantage when compared to previous algorithms wherein the dimension of the state vector increases monotonically with the product of the frequency uncertainty and the observation period. Such a computational simplification may possibly result in some loss of optimality. However, by applying the sampling techniques of the paper such a possible loss in optimality can made small.

Kumar, Rajendra↗
NASA NTRS1988

Design and implementation of parallel multigrid algorithms

Techniques for mapping multigrid algorithms to solve elliptic PDEs on hypercube parallel computers are described and demonstrated. The need for proper data mapping to minimize communication distances is stressed, and an execution-time model is developed to show how algorithm efficiency is affected by changes in the machine and algorithm parameters. Particular attention is then given to the case of coarse computational grids, which can lead to idle processors, load imbalances, and inefficient performance. It is shown that convergence can be improved by using idle processors to solve a new problem concurrently on the fine grid defined by a splitting.

Chan, Tony F.↗
NASA NTRS1988

Development of an advanced failure detection algorithm for the SSME

Since ground testing of the Space Shuttle Main Engine began in 1975, a multifaceted detection/shutdown system has been used to detect engine anomalies and initiate shutdown. In spite of this system, 27 major incidents have occurred since testing began. Although a small percentage of over 1200 successful hot fire tests, such incidents can result in significant cost and schedule impacts. Therefore, an advanced failure detection algorithm has been developed which consists of three detection approaches designed for a failure characteristic that has been previously documented. Simulations using sensor data from five incident tests show the algorithm detecting an anomally and signalling shutdown prior to the redline cutoff time. The foundation elements of the algorithm and its functioning are described.

Norman, A.↗
NASA NTRS1989

Improved Algorithm For Finite-Field Normal-Basis Multipliers

Improved algorithm reduces complexity of calculations that must precede design of Massey-Omura finite-field normal-basis multipliers, used in error-correcting-code equipment and cryptographic devices. Algorithm represents an extension of development reported in "Algorithm To Design Finite-Field Normal-Basis Multipliers" (NPO-17109), NASA Tech Briefs, Vol. 12, No. 5, page 82.

Wang, C. C.↗
NASA NTRS1989

Network-Control Algorithm

Algorithm developed for optimal routing of packets of data along links of multilink, multinode digital communication network. Algorithm iterative and converges to cost-optimal assignment independent of initial assignment. Each node connected to other nodes through links, each containing number of two-way channels. Algorithm assigns channels according to message traffic leaving and arriving at each node. Modified to take account of different priorities among packets belonging to different users by using different delay constraints or imposing additional penalties via cost function.

Chan, Hak-Wai↗
NASA NTRS1988

Strategies for concurrent processing of complex algorithms in data driven architectures

The purpose is to document research to develop strategies for concurrent processing of complex algorithms in data driven architectures. The problem domain consists of decision-free algorithms having large-grained, computationally complex primitive operations. Such are often found in signal processing and control applications. The anticipated multiprocessor environment is a data flow architecture containing between two and twenty computing elements. Each computing element is a processor having local program memory, and which communicates with a common global data memory. A new graph theoretic model called ATAMM which establishes rules for relating a decomposed algorithm to its execution in a data flow architecture is presented. The ATAMM model is used to determine strategies to achieve optimum time performance and to develop a system diagnostic software tool. In addition, preliminary work on a new multiprocessor operating system based on the ATAMM specifications is described.

Stoughton, John W.↗
NASA NTRS1988

Cloud classification from satellite data using a fuzzy sets algorithm: A polar example

Where spatial boundaries between phenomena are diffuse, classification methods which construct mutually exclusive clusters seem inappropriate. The Fuzzy c-means (FCM) algorithm assigns each observation to all clusters, with membership values as a function of distance to the cluster center. The FCM algorithm is applied to AVHRR data for the purpose of classifying polar clouds and surfaces. Careful analysis of the fuzzy sets can provide information on which spectral channels are best suited to the classification of particular features, and can help determine likely areas of misclassification. General agreement in the resulting classes and cloud fraction was found between the FCM algorithm, a manual classification, and an unsupervised maximum likelihood classifier.

Key, J. R.↗