SEARCH · Search NASA

Results for “computational complexity”

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.

SourceResearch connectionFrom yearThrough year

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 325 records · Page 18

All sources NASA NTRS DOE OSTI

NASA NTRS1986

Research relative to a model of the Orion nebula

Research basically has been directed along two avenues. First of all, there is a long-standing interest in modeling H II regions in order to understand the physical processes involved and to extract important astrophysical information. This includes knowledge of chemical elemental abundances and properties of the exciting stars, such as their far ultraviolet spectrum. The Orion Nebula is a prime candidate to study because it is nearby, bright, the extinction is not large, and its appearance is reasonably circular. Such a shape is consistent with a geometrical structure that is spherically symmetric (1-D) or one that is axisymmetric (2-D) seen nearly face-on. Previously all detailed modeling of the ionization and thermal structure of H II regions has been confined to 1-D because of computational complexity. There is now the capability to treat the 2-D case with much of the level of physical sophistication as the 1-D case. The interpretation of the spectra of gaseous nebulae in terms of underlying physical processes requires measurements of line intensities at different points in the object and over as wide a set of excitation and ionization conditions as practical.Observations of nebulae have been made for many years in the optical and radio but only recently in the infrared and ultraviolet. These relatively new windows allow observations of lines of ionization states not available in the radio or optical--providing a much more complete set of known quantities to undertake a meaningful modeling effort.

Zuckerman, B. M.↗

NASA NTRS1986

A high quality image compression scheme for real-time applications

Many image compression or coding techniques have been developed to reduce the amount of bits of information needed to represent digital images. Among these, Vector Quantization (VQ) seems to have the edge; its theoretical distortion is lower than that of other block coding techniques at comparable bit rates. However, the application of Vector Quantization remains limited due to its high computational complexity. Presently, it is limited to low to medium quality image compression. In this paper it is shown that VQ can be mapped onto VLSI implementation via systolic type architecture, making real time application possible. In addition, it is shown that using multistage or cascade VQ high quality images can be obtained at very low bit rates for real time applications while using smaller codebooks than is necessary in single stage VQ. Examples of processed images are presented.

Ramamoorthy, P. A.↗

NASA NTRS1986

Advances and future directions of research on spectral methods

Recent advances in spectral methods are briefly reviewed and characterized with respect to their convergence and computational complexity. Classical finite element and spectral approaches are then compared, and spectral element (or p-type finite element) approximations are introduced. The method is applied to the full Navier-Stokes equations, and examples are given of the application of the technique to several transitional flows. Future directions of research in the field are outlined.

Patera, A. T.↗

NASA NTRS1987

Simplified solution for a class of fading memory filters

A fading memory filter is a least squares estimator (LSE) that applies an exponentially decaying weight to past measurements. When compared with a standard Kalman filter, its key advantages are asymptotic stability and reduced sensitivity to modeling errors. This paper derives a simple solution for a class of fading memory filters, resulting in a reduction in computational complexity. Steady state filter solutions are obtained for second- and third-order filters used in a global positioning system (GPS) receiver for high dynamic vehicles.

Statman, Joseph I.↗

NASA NTRS1987

Image coding of SAR imagery

Five coding techniques in the spatial and transform domains have been evaluated for SAR image compression: linear three-point predictor (LTPP), block truncation coding (BTC), microadaptive picture sequencing (MAPS), adaptive discrete cosine transform (ADCT), and adaptive Hadamard transform (AHT). These techniques have been tested with Seasat data. Both LTPP and BTC spatial domain coding techniques provide very good performance at rates of 1-2 bits/pixel. The two transform techniques, ADCT and AHT, demonstrate the capability to compress the SAR imagery to less than 0.5 bits/pixel without visible artifacts. Tradeoffs such as the rate distortion performance, the computational complexity, the algorithm flexibility, and the controllability of compression ratios are also discussed.

Chang, C. Y.↗

NASA NTRS1988

A simplified, general-purpose deep-space ranging correlator design

A much-simplified, yet more general-purpose multi-channel deep-space ranging system correlator design that was used in past JPL spacecraft ranging systems is described. The method applies to detection of both single-component and multiple-component ranging codes, in either sequential (mu) or composite (pi) transmitted forms, and using either pseudonoise or square-wave components. Using this design, the Phobos Probe ranging system correlator computational complexity was reduced by over three orders of magnitude in multiply-and-add circuits and 45,000 bits of accumulator storage.

Tausworthe, R. C.↗

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 NTRS1987

Trends in Space Station telemetry applications

Spacecraft telemetry systems have evolved from simple hardware devices to complex computer applications performing data acquisition and formatting tasks. This paper reviews the role of spacecraft computers in performing telemetry functions and examines computer-based telemetry systems being considered for use on the NASA Space Station.

Muratore, John F.↗

NASA NTRS1988

Dypas: A dynamic payload scheduler for shuttle missions

Decision and analysis systems have had broad and very practical application areas in the human decision making process. These software systems range from the help sections in simple accounting packages, to the more complex computer configuration programs. Dypas is a decision and analysis system that aids prelaunch shutlle scheduling, and has added functionality to aid the rescheduling done in flight. Dypas is written in Common Lisp on a Symbolics Lisp machine. Dypas differs from other scheduling programs in that it can draw its knowledge from different rule bases and apply them to different rule interpretation schemes. The system has been coded with Flavors, an object oriented extension to Common Lisp on the Symbolics hardware. This allows implementation of objects (experiments) to better match the problem definition, and allows a more coherent solution space to be developed. Dypas was originally developed to test a programmer's aptitude toward Common Lisp and the Symbolics software environment. Since then the system has grown into a large software effort with several programmers and researchers thrown into the effort. Dypas is currently using two expert systems and three inferencing procedures to generate a many object schedule. The paper will review the abilities of Dypas and comment on its functionality.

Davis, Stephen↗

NASA NTRS1989

A computational challenge - Euler solution for ellipses

The Euler equations for flow past an ellipse are solved numerically. A computationally complex problem involving inviscid flow past an elliptical two-dimensional surface at subcritical Mach number and angle of attack is introduced. A lifting solution for any combination of grid and/or angle of attack which is nonsymmetric is obtained.

Pulliam, Thomas H.↗

NASA NTRS1990

Numerical simulation of the incompressible internal flow through a tilting disk valve

A numerical simulation of the incompressible viscous flow through a prosthetic tilting disk heart valve is presented in order to demonstrate the current capability to model unsteady flows with moving boundaries. Both steady and unsteady flow calculations are performed by solving the incompressible Navier-Stokes equations in three-dimensional generalized curvilinear coordinates. In order to handle the moving boundary problems, the chimera grid embedding scheme which decomposes a complex computational domain into several simple subdomains is used. An algebraic turbulence model for internal flows is incorporated to reach the physiological values of Reynolds number. Good agreement is obtained between the numerical results and experimental measurements. It is found that the tilting disk valve causes large regions of separated flow, and regions of high shear.

Chang, I-Dee↗

NASA NTRS1990

The Integrated Airframe/Propulsion Control System Architecture program (IAPSA)

The Integrated Airframe/Propulsion Control System Architecture program (IAPSA) is a two-phase program which was initiated by NASA in the early 80s. The first phase, IAPSA 1, studied different architectural approaches to the problem of integrating engine control systems with airframe control systems in an advanced tactical fighter. One of the conclusions of IAPSA 1 was that the technology to construct a suitable system was available, yet the ability to create these complex computer architectures has outpaced the ability to analyze the resulting system's performance. With this in mind, the second phase of IAPSA approached the same problem with the added constraint that the system be designed for validation. The intent of the design for validation requirement is that validation requirements should be shown to be achievable early in the design process. IAPSA 2 has demonstrated that despite diligent efforts, integrated systems can retain characteristics which are difficult to model and, therefore, difficult to validate.

Daniel L Palumbo↗

NASA NTRS1990

Applications of artificial intelligence to mission planning

The scheduling problem facing NASA-Marshall mission planning is extremely difficult for several reasons. The most critical factor is the computational complexity involved in developing a schedule. The size of the search space is large along some dimensions and infinite along others. It is because of this and other difficulties that many of the conventional operation research techniques are not feasible or inadequate to solve the problems by themselves. Therefore, the purpose is to examine various artificial intelligence (AI) techniques to assist conventional techniques or to replace them. The specific tasks performed were as follows: (1) to identify mission planning applications for object oriented and rule based programming; (2) to investigate interfacing AI dedicated hardware (Lisp machines) to VAX hardware; (3) to demonstrate how Lisp may be called from within FORTRAN programs; (4) to investigate and report on programming techniques used in some commercial AI shells, such as Knowledge Engineering Environment (KEE); and (5) to study and report on algorithmic methods to reduce complexity as related to AI techniques.

Ford, Donnie R.↗

NASA NTRS1991

Simulation of blood flow through an artificial heart

A numerical simulation of the incompressible viscous flow through a prosthetic tilting disk heart valve is presented in order to demonstrate the current capability to model unsteady flows with moving boundaries. Both steady state and unsteady flow calculations are done by solving the incompressible Navier-Stokes equations in 3-D generalized curvilinear coordinates. In order to handle the moving boundary problems, the chimera grid embedding scheme which decomposes a complex computational domain into several simple subdomains is used. An algebraic turbulence model for internal flows is incorporated to reach the physiological values of Reynolds number. Good agreement is obtained between the numerical results and experimental measurements. It is found that the tilting disk valve causes large regions of separated flow, and regions of high shear.

Kiris, Cetin↗

NASA NTRS1990

Modeling and stability of segmented reflector telescopes - A decentralized approach

The decentralization of a segmented reflector telescope based on a finite-element model of its structure is considered. The decentralization of the system at the panel level is considered. Each panel is originally treated as an isolated subsystem so that the controller design is performed independently at the local level, and then applied to the composite system for stability analysis. The panel-level control laws were designed by means of pole placement using local output feedback. Simulation results show a better 1000:1 vibration attenuation in panel position when compared to the open-loop system. It is shown that the overall closed-loop system is exponentially stable provided that certain conditions are met. The advantage to the decentralized approach is that the design is performed in terms of the low-dimensionality subsystems, thus drastically reducing the design computational complexities.

Ryaciotaki-Boussalis, Helen A.↗

NASA NTRS1990

Evaluating scheduling algorithms for traffic with heterogeneous performance objectives

Two types of network traffic are considered: traffic with deadlines, for which the most important performance objective is based on loss rate, and packets without deadlines, for which the most important performance objective is based on mean delay. An optimal scheduling algorithm is presented to minimize weighted loss rate and weighted mean delay in the queues that form at the switches and at the network access points of a packet-switched network, where weights reflect the relative importance of packets. Although not practical for implementation, the algorithm is intended as a standard for the comparison of the performance of other scheduling algorithms. The algorithm is more general and lower computational complexity than previously published algorithms, enabling performance evaluation of some important scenarios that could not previously have been considered. Using the optimal performance results of this algorithm, the performance of the first-come-first-served, static priority, and earliest deadline first scheduling algorithms is evaluated. The results suggest that network efficiency could be improved by using a more sophisticated heuristic scheduling algorithm rather than one of the aforementioned algorithms.

Peha, Jon M.↗

NASA NTRS1991

Frame Shift/warp Compensation for the ARID Robot System

The Automatic Radiator Inspection Device (ARID) is a system aimed at automating the tedious task of inspecting orbiter radiator panels. The ARID must have the ability to aim a camera accurately at the desired inspection points, which are in the order of 13,000. The ideal inspection points are known; however, the panel may be relocated due to inaccurate parking and warpage. A method of determining the mathematical description of a translated as well as a warped surface by accurate measurement of only a few points on this surface is developed here. The method uses a linear warp model whose effect is superimposed on the rigid body translation. Due to the angles involved, small angle approximations are possible, which greatly reduces the computational complexity. Given an accurate linear warp model, all the desired translation and warp parameters can be obtained by knowledge of the ideal locations of four fiducial points and the corresponding measurements of these points on the actual radiator surface. The method uses three of the fiducials to define a plane and the fourth to define the warp. Given this information, it is possible to determine a transformation that will enable the ARID system to translate any desired inspection point on the ideal surface to its corresponding value on the actual surface.

Latino, Carl D.↗

NASA NTRS1992

Real-time demonstration hardware for enhanced DPCM video compression algorithm

The lack of available wideband digital links as well as the complexity of implementation of bandwidth efficient digital video CODECs (encoder/decoder) has worked to keep the cost of digital television transmission too high to compete with analog methods. Terrestrial and satellite video service providers, however, are now recognizing the potential gains that digital video compression offers and are proposing to incorporate compression systems to increase the number of available program channels. NASA is similarly recognizing the benefits of and trend toward digital video compression techniques for transmission of high quality video from space and therefore, has developed a digital television bandwidth compression algorithm to process standard National Television Systems Committee (NTSC) composite color television signals. The algorithm is based on differential pulse code modulation (DPCM), but additionally utilizes a non-adaptive predictor, non-uniform quantizer and multilevel Huffman coder to reduce the data rate substantially below that achievable with straight DPCM. The non-adaptive predictor and multilevel Huffman coder combine to set this technique apart from other DPCM encoding algorithms. All processing is done on a intra-field basis to prevent motion degradation and minimize hardware complexity. Computer simulations have shown the algorithm will produce broadcast quality reconstructed video at an average transmission rate of 1.8 bits/pixel. Hardware implementation of the DPCM circuit, non-adaptive predictor and non-uniform quantizer has been completed, providing realtime demonstration of the image quality at full video rates. Video sampling/reconstruction circuits have also been constructed to accomplish the analog video processing necessary for the real-time demonstration. Performance results for the completed hardware compare favorably with simulation results. Hardware implementation of the multilevel Huffman encoder/decoder is currently under development along with implementation of a buffer control algorithm to accommodate the variable data rate output of the multilevel Huffman encoder. A video CODEC of this type could be used to compress NTSC color television signals where high quality reconstruction is desirable (e.g., Space Station video transmission, transmission direct-to-the-home via direct broadcast satellite systems or cable television distribution to system headends and direct-to-the-home).

Bizon, Thomas P.↗