Search NASA⌕ Search

SEARCH · Search NASA

Results for “hybrid 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 37 records · Page 2

Fast polar decomposition of an arbitrary matrix

The polar decomposition of an m x n matrix A of full rank, where m is greater than or equal to n, can be computed using a quadratically convergent algorithm. The algorithm is based on a Newton iteration involving a matrix inverse. With the use of a preliminary complete orthogonal decomposition the algorithm can be extended to arbitrary A. How to use the algorithm to compute the positive semi-definite square root of a Hermitian positive semi-definite matrix is described. A hybrid algorithm which adaptively switches from the matrix inversion based iteration to a matrix multiplication based iteration due to Kovarik, and to Bjorck and Bowie is formulated. The decision when to switch is made using a condition estimator. This matrix multiplication rich algorithm is shown to be more efficient on machines for which matrix multiplication can be executed 1.5 times faster than matrix inversion.

Higham, Nicholas J.↗

Analyses of large quasistatic deformations of inelastic bodies by a new hybrid-stress finite element algorithm

A new hybrid-stress finite element algorithm, suitable for analyses of large, quasistatic, inelastic deformations, is presented. The algorithm is base upon a generalization of de Veubeke's complementary energy principle. The principal variables in the formulation are the nominal stress rate and spin, and thg resulting finite element equations are discrete versions of the equations of compatibility and angular momentum balance. The algorithm produces true rates, time derivatives, as opposed to 'increments'. There results a complete separation of the boundary value problem (for stress rate and velocity) and the initial value problem (for total stress and deformation); hence, their numerical treatments are essentially independent. After a fairly comprehensive discussion of the numerical treatment of the boundary value problem, we launch into a detailed examination of the numerical treatment of the initial value problem, covering the topics of efficiency, stability and objectivity. The paper is closed with a set of examples, finite homogeneous deformation problems, which serve to bring out important aspects of the algorithm.

Reed, K. W.↗

A study of digital holographic filters generation. Phase 2: Digital data communication system, volume 1

An empirical study of the performance of the Viterbi decoders in bursty channels was carried out and an improved algebraic decoder for nonsystematic codes was developed. The hybrid algorithm was simulated for the (2,1), k = 7 code on a computer using 20 channels having various error statistics, ranging from pure random error to pure bursty channels. The hybrid system outperformed both the algebraic and the Viterbi decoders in every case, except the 1% random error channel where the Viterbi decoder had one bit less decoding error.

Ingels, F. M.↗

Prognostics for Systems Health Management - Model and Hybrid Based Approaches. Where are We Heading?

To facilitate and solve the prediction problem, awareness of the current state and health of the system is key, since it is necessary to perform condition-based system health predictions. To accurately predict the future state of any system, it is required to possess knowledge of its current health state and future operational conditional. In case of next generation electric aircrafts, computing remaining flying time is safety-critical, since an aircraft that runs out of power (battery charge) while in the air will eventually lose control leading to catastrophe. In order to tackle and solve the prediction problem, it is essential to have awareness of the current health state of the system, especially since it is necessary to perform condition-based predictions. To be able to predict the future state of the system, it is also required to possess knowledge of the current and future operational conditions and flight profiles for accurate estimation of end-of-discharge (EOD) for the batteries. Similar framework can be implemented to other complex systems and subsystems. Our research approach is to develop a system level health monitoring safety indicator which runs estimation and prediction algorithms to estimate remaining useful life predictions at system, subsystem swell as component levels. Given models of the current and future system behavior, a general approach of model-based prognostics is discussed as a solution to the prediction problem and further for decision making. Data driven prognostics approaches have been equally used with good results in the past, where respective approaches have their own challenges to tackle. This limits their applicability to complex real-world domains: (a) high complexity or incompleteness of physics-based models and (b) limited representativeness of the training dataset for data-driven models. With the advent of internet of things for data collection and increased use of ML algorithms, hybrid approaches are the next avenue to reduce the challenges and achieve better results. An hybrid framework for fusing information from physics-based performance models along with deep learning algorithms for prognostics of complex safety critical systems is presented. In this framework, we use physics-based performance models to infer unobservable model parameters related to the system's components health solving a calibration problem.

Prognostics↗

Survivable algorithms and redundancy management in NASA's distributed computing systems

The design of survivable algorithms requires a solid foundation for executing them. While hardware techniques for fault-tolerant computing are relatively well understood, fault-tolerant operating systems, as well as fault-tolerant applications (survivable algorithms), are, by contrast, little understood, and much more work in this field is required. We outline some of our work that contributes to the foundation of ultrareliable operating systems and fault-tolerant algorithm design. We introduce our consensus-based framework for fault-tolerant system design. This is followed by a description of a hierarchical partitioning method for efficient consensus. A scheduler for redundancy management is introduced, and application-specific fault tolerance is described. We give an overview of our hybrid algorithm technique, which is an alternative to the formal approach given.

Malek, Miroslaw↗

Path Attenuation Estimates for the DPR

The algorithm for the Surface Reference Technique (SRT) has been updated from version V6A to version V6X. The modified algorithm is designed to process dual-frequency radar data which are now available over the full swath. Comparisons between V6A and V6X show that the dual-wavelength version of the SRT (DSRT) eliminates some of the overestimates of path attenuation in the outer swath that occurred in the earlier version of the algorithm when dual-frequency data was unavailable in the outer swath. However, the DSRT is not reliable in cases of light rain rates where only the Ku-band channel detects rain, nor is it reliable in high rain rate cases where the Ka-band surface signal is lost through attenuation. A modified hybrid algorithm is planned for version 7 that can combine the best features of single- and dual-frequency path attenuation methods.

Meneghini, Robert↗

Redundancy management for efficient fault recovery in NASA's distributed computing system

The management of redundancy in computer systems was studied and guidelines were provided for the development of NASA's fault-tolerant distributed systems. Fault recovery and reconfiguration mechanisms were examined. A theoretical foundation was laid for redundancy management by efficient reconfiguration methods and algorithmic diversity. Algorithms were developed to optimize the resources for embedding of computational graphs of tasks in the system architecture and reconfiguration of these tasks after a failure has occurred. The computational structure represented by a path and the complete binary tree was considered and the mesh and hypercube architectures were targeted for their embeddings. The innovative concept of Hybrid Algorithm Technique was introduced. This new technique provides a mechanism for obtaining fault tolerance while exhibiting improved performance.

Malek, Miroslaw↗

A fast computation of complex convolution using a hybrid transform

The cyclic convolution of complex values was obtained by a hybrid transform that is a combination of a Winograd transform and a fast complex integer transform. This new hybrid algorithm requires fewer multiplications than any previously known algorithm.

Reed, I. S.↗

An implicit flux-difference splitting scheme for three-dimensional, incompressible Navier-Stokes solutions to leading edge vortex flows

A new, implicit finite-difference scheme designed to solve the conservative, flux-difference split Navier-Stokes equations is used to compute incompressible vortex flows around delta wings. The completely vectorizable hybrid algorithm is constructed in delta form for steady state solutions independent of the time-step sizes. The scheme combines approximate factorization in crossflow planes with a symmetric planar Gauss-Seidel relaxation in the remaining spatial direction. The governing equations are solved in curvilinear, body-fitted coordinates for treating complex geometries. The computed flow field results are compared with other theoretical and experimental data.

Hartwich, P.-M.↗

Implicit hybrid schemes for the flux-difference split, three-dimensional Navier-Stokes equations

Implicit hybrid algorithms employing symmetric planar Gauss-Seidel (SPGS) relaxation and either block-tridiagonally structured coefficient matrices (AF-SPGS) or block-triangular coefficient matrices (LU-SPGS) are derived to solve the flux-difference-split Navier-Stokes equations for three-dimensional incompressible flow in an upwind scheme. The physical basis of the approach is discussed, and results for problems involving vortex flow around a thin delta wing at Reynolds numbers 900,000 and 10,000 are presented graphically. It is found that AF-SPGS converges faster on vector computers which depend on long vector lengths to achieve optimum performance, whereas LU-SPGS is preferable on sequentially operating machines and vector computers using shorter vector lengths.

Hartwich, P.-M.↗

The effect of Mach number on the stability of a plane supersonic wave

The influence of compressibility on the mechanisms governing the various stages of transition in a supersonic wake is investigated. Results from linear stability theory are used to provide physical insights into the observed reduction in growth rate at high Mach numbers. A newly developed hybrid algorithm is used to solve the compressible inviscid linear disturbance equations. Growth rates for both antisymmetric and symmetric modes of two-dimensional and oblique waves are computed for a wide range of Mach numbers. Results from two and three-dimensional direct numerical simulations of a forced compressible time-developing wake are presented in order to understand the nonlinear stages of transition at high Mach numbers. Observed nonlinear growth rate comparisons are made for wakes at two different Mach numbers. The reduction in growth rate at high Mach numbers is explained by examining contour plots of baroclinic torques and the product of dilatation and vorticity.

Chen, Jacqueline H.↗

Numerical Studies of Collisionless Current Layers

The purpose of this proposal was to investigate collisionless current layers using a variety of analytic and numerical tools. The first year of the contract was dedicated to analytical studies, to the porting and adaption of codes being used in this study, and to the numerical simulation of collisionless current layers. The second year entailed the development of multi-dimensional hybrid algorithms as well as the re-examination of the problem of integro-differential equations that occur in the linear stage of plasma instabilities.

Quest, Kevin B.↗

The analysis of control trajectories using symbolic and database computing

This final report comprises the formal semi-annual status reports for this grant for the periods June 30-December 31, 1993, January 1-June 30, 1994, and June 1-December 31, 1994. The research supported by this grant is broadly concerned with the symbolic computation, mixed numeric-symbolic computation, and database computation of trajectories of dynamical systems, especially control systems. A review of work during the report period covers: trajectories and approximating series, the Cayley algebra of trees, actions of differential operators, geometrically stable integration algorithms, hybrid systems, trajectory stores, PTool, and other activities. A list of publications written during the report period is attached.

Grossman, Robert↗

The Development of the Puerto Rico Lightning Detection Network for Meteorological Research

A land-based Puerto Rico Lightning Detection Network (PR-LDN) dedicated to the academic research of meteorological phenomena has being developed. Five Boltek StormTracker PCI-Receivers with LTS-2 Timestamp Cards with GPS and lightning detectors were integrated to Pentium III PC-workstations running the CentOS linux operating system. The Boltek detector linux driver was compiled under CentOS, modified, and thoroughly tested. These PC-workstations with integrated lightning detectors were installed at five of the University of Puerto Rico (UPR) campuses distributed around the island of PR. The PC-workstations are left on permanently in order to monitor lightning activity at all times. Each is networked to their campus network-backbone permitting quasi-instantaneous data transfer to a central server at the UPR-Bayam n campus. Information generated by each lightning detector is managed by a C-program developed by us called the LDN-client. The LDN-client maintains an open connection to the central server operating the LDN-server program where data is sent real-time for analysis and archival. The LDN-client also manages the storing of data on the PC-workstation hard disk. The LDN-server software (also an in-house effort) analyses the data from each client and performs event triangulations. Time-of-arrival (TOA) and related hybrid algorithms, lightning-type and event discriminating routines are also implemented in the LDN-server software. We also have developed software to visually monitor lightning events in real-time from all clients and the triangulated events. We are currently monitoring and studying the spatial, temporal, and type distribution of lightning strikes associated with electrical storms and tropical cyclones in the vicinity of Puerto Rico.

Legault, Marc D.↗

Second-Generation Six-Limbed Experimental Robot

The figure shows the LEMUR II - the second generation of the Limbed Excursion Mechanical Utility Robot (LEMUR), which was described in "Six-Legged Experimental Robot" (NPO-20897), NASA Tech Briefs, Vol. 25, No. 12 (December 2001), page 58. The LEMUR II incorporates a number of improvements, including new features, that extend its capabilities beyond those of its predecessor, which is now denoted the LEMUR I. To recapitulate: the LEMUR I was a six-limbed robot for demonstrating robotic capabilities for assembly, maintenance, and inspection. The LEMUR I was designed to be capable of walking autonomously along a truss structure toward a mechanical assembly at a prescribed location and to perform other operations. The LEMUR I was equipped with stereoscopic video cameras and image-data-processing circuitry for navigation and mechanical operations. It was also equipped with a wireless modem, through which it could be commanded remotely. Upon arrival at a mechanical assembly, the LEMUR I would perform simple mechanical operations with one or both of its front limbs. It could also transmit images to a host computer. Each of the six limbs of the LEMUR I was operated independently. Each of the four rear limbs had three degrees of freedom (DOFs), while each of the front two limbs had four DOFs. The front two limbs were designed to hold, operate, and/or be integrated with tools. The LEMUR I included an onboard computer equipped with an assortment of digital control circuits, digital input/output circuits, analog-to-digital converters for input, and digital-to-analog (D/A) converters for output. Feedback from optical encoders in the limb actuators was utilized for closed-loop microcomputer control of the positions and velocities of the actuators. The LEMUR II incorporates the following improvements over the LEMUR I: a) The drive trains for the joints of the LEMUR II are more sophisticated, providing greater torque and accuracy. b) The six limbs are arranged symmetrically about a hexagonal body platform instead of in straight lines along the sides. This symmetrical arrangement is more conducive to omnidirectional movement in a plane. c) The number of degrees of freedom of each of the rear four limbs has been increased by one. Now, every limb has four degrees of freedom: three at the hip (or shoulder, depending on one s perspective) and one at the knee (or elbow, depending on one s perspective). d) Now every limb (instead of only the two front limbs) can perform operations. For this purpose, each limb is tipped with an improved quick-release mechanism for swapping of end-effector tools. e) New end-effector tools have been developed. These include an instrumented rotary driver that accepts all tool bits that have 0.125-in. (3.175-mm)-diameter shanks, a charge-coupled-device video camera, a super bright light-emitting diode for illuminating the work area of the robot, and a generic collet tool that can be quickly and inexpensively modified to accept any cylindrical object up to 0.5 in. (12.7 mm) in diameter. f) The stereoscopic cameras are mounted on a carriage that moves along a circular track, thereby providing for omnidirectional machine vision. g) The control software has been augmented with software that implements innovations reported in two prior NASA Tech Briefs articles: the HIPS algorithm ["Hybrid Image-Plane/Stereo Manipulation" (NPO-30492), Vol. 28, No. 7 (July 2004), page 55] and the CAMPOUT architecture ["An Architecture for Controlling Multiple Robots" (NPO-30345), Vol. 28, No. 10 (October 2004), page 65].

Kennedy, Brett↗

Analyses of large quasistatic deformations of inelastic bodies by a new hybrid-stress finite element algorithm - Applications

A new hybrid-stress finite element algorithm suitable for analyzing large quasistatic deformations of inelastic solids is presented and its feasibility and performance are demonstrated with examples. The algorithm provides extremely accurate bifurcation analysis which is stable with respect to variation in the finite element mesh, so long as the same type of element is used in every mesh. When the mesh element is varied, the result changes in a predictable manner. The method does not necessarily lead to an upper or lower bound for the critical load. An explicit forward gradient scheme is used to improve stability and is shown to be useful also for elongation-dominated deformations. The application of the method to the onset of necking in plane extension and to deformation and stress in plane extension of an elasticoviscous fluid with an array of cylindrical voids is given in detail.

Reed, K. W.↗

Two Improved Algorithms for Envelope and Wavefront Reduction

Two algorithms for reordering sparse, symmetric matrices or undirected graphs to reduce envelope and wavefront are considered. The first is a combinatorial algorithm introduced by Sloan and further developed by Duff, Reid, and Scott; we describe enhancements to the Sloan algorithm that improve its quality and reduce its run time. Our test problems fall into two classes with differing asymptotic behavior of their envelope parameters as a function of the weights in the Sloan algorithm. We describe an efficient 0(nlogn + m) time implementation of the Sloan algorithm, where n is the number of rows (vertices), and m is the number of nonzeros (edges). On a collection of test problems, the improved Sloan algorithm required, on the average, only twice the time required by the simpler Reverse Cuthill-Mckee algorithm while improving the mean square wavefront by a factor of three. The second algorithm is a hybrid that combines a spectral algorithm for envelope and wavefront reduction with a refinement step that uses a modified Sloan algorithm. The hybrid algorithm reduces the envelope size and mean square wavefront obtained from the Sloan algorithm at the cost of greater running times. We illustrate how these reductions translate into tangible benefits for frontal Cholesky factorization and incomplete factorization preconditioning.

Kumfert, Gary↗

A hybrid M-algorithm/sequential decoder for convolutional and trellis codes

The Viterbi Algorithm (VA) is optimum in the sense of being maximum likelihood for decoding codes with a trellis structure. However, since the VA is in fact an exhaustive search of the code trellis, the complexity of the VA grows exponentially with the constraint length upsilon. This limits its application to codes with small values of upsilon and relatively modest coding gains. The M-Algorithm (MA) is a limited search scheme which carries forward M paths in the trellis, all of the same length. All successors of the M paths are extended at the next trellis depth, and all but the best M of these are dropped. Since a limited search convolutional decoder will flounder indefinitely if one of the paths in storage is not the correct one, the data are usually transmitted in blocks. It has been shown that the performance of the MA approaches the VA at high signal to noise ratios (SNR's) with an M which is far less than the 2 sup upsilon states in the full trellis. Thus the MA can be used with larger values of upsilon, making larger coding gains possible at high SNR's. However, it still requires a relatively large fixed computational effort to achieve good performance.

Wang, Fu-Quan↗