SEARCH · Engineering Papers

Results for “permutation”

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 469 records · Page 26

All sources NASA NTRS DOE OSTI

NASA NTRS1993

Soft decoding a self-dual (48, 24; 12) code

A self-dual (48,24;12) code comes from restricting a binary cyclic (63,18;36) code to a 6 x 7 matrix, adding an eighth all-zero column, and then adjoining six dimensions to this extended 6 x 8 matrix. These six dimensions are generated by linear combinations of row permutations of a 6 x 8 matrix of weight 12, whose sums of rows and columns add to one. A soft decoding using these properties and approximating maximum likelihood is presented here. This is preliminary to a possible soft decoding of the box (72,36;15) code that promises a 7.7-dB theoretical coding under maximum likelihood.

Solomon, G.↗

NASA NTRS1993

Point form relativistic quantum mechanics and relativistic SU(6)

The point form is used as a framework for formulating a relativistic quantum mechanics, with the mass operator carrying the interactions of underlying constituents. A symplectic Lie algebra of mass operators is introduced from which a relativistic harmonic oscillator mass operator is formed. Mass splittings within the degenerate harmonic oscillator levels arise from relativistically invariant spin-spin, spin-orbit, and tensor mass operators. Internal flavor (and color) symmetries are introduced which make it possible to formulate a relativistic SU(6) model of baryons (and mesons). Careful attention is paid to the permutation symmetry properties of the hadronic wave functions, which are written as polynomials in Bargmann spaces.

Klink, W. H.↗

NASA NTRS1992

A simple test of independence for truncated data with applications to redshift surveys

This paper presents an easily applied permutation test for H0, closely related to Lyden-Bell's (1971) estimate of the marginal distribution of truncated data. The test is applied to two redshift-magnitude surveys, one of galaxies and one of quasars. Assuming statistical independence, testing H0 amounts to testing validity of the cosmological model. Segal's (1986) chronomatic cosmological model is rejected under H0. On the other hand, for the quasar sample H0 is rejected strongly in a conventional cosmological model (and in a chronomatic model as well) indicating either incorrectness of the models or, as is more commonly assumed, indicating strong luminosity evolution.

Efron, Bradley↗

NASA NTRS1992

A Benes-like theorem for the shuffle-exchange graph

One of the first theorems on permutation routing, proved by V. E. Beness (1965), shows that given a set of source-destination pairs in an N-node butterfly network with at most a constant number of sources or destinations in each column of the butterfly, there exists a set of paths of lengths O(log N) connecting each pair such that the total congestion is constant. An analogous theorem yielding constant-congestion paths for off-line routing in the shuffle-exchange graph is proved here. The necklaces of the shuffle-exchange graph play the same structural role as the columns of the butterfly in Beness' theorem.

Schwabe, Eric J.↗

NASA NTRS1993

Subband/transform functions for image processing

Functions for image data processing written for use with the MATLAB(TM) software package are presented. These functions provide the capability to transform image data with block transformations (such as the Walsh Hadamard) and to produce spatial frequency subbands of the transformed data. Block transforms are equivalent to simple subband systems. The transform coefficients are reordered using a simple permutation to give subbands. The low frequency subband is a low resolution version of the original image, while the higher frequency subbands contain edge information. The transform functions can be cascaded to provide further decomposition into more subbands. If the cascade is applied to all four of the first stage subbands (in the case of a four band decomposition), then a uniform structure of sixteen bands is obtained. If the cascade is applied only to the low frequency subband, an octave structure of seven bands results. Functions for the inverse transforms are also given. These functions can be used for image data compression systems. The transforms do not in themselves produce data compression, but prepare the data for quantization and compression. Sample quantization functions for subbands are also given. A typical compression approach is to subband the image data, quantize it, then use statistical coding (e.g., run-length coding followed by Huffman coding) for compression. Contour plots of image data and subbanded data are shown.

Glover, Daniel↗

NASA NTRS1993

Analysis of multigrid methods on massively parallel computers: Architectural implications

We study the potential performance of multigrid algorithms running on massively parallel computers with the intent of discovering whether presently envisioned machines will provide an efficient platform for such algorithms. We consider the domain parallel version of the standard V cycle algorithm on model problems, discretized using finite difference techniques in two and three dimensions on block structured grids of size 10(exp 6) and 10(exp 9), respectively. Our models of parallel computation were developed to reflect the computing characteristics of the current generation of massively parallel multicomputers. These models are based on an interconnection network of 256 to 16,384 message passing, 'workstation size' processors executing in an SPMD mode. The first model accomplishes interprocessor communications through a multistage permutation network. The communication cost is a logarithmic function which is similar to the costs in a variety of different topologies. The second model allows single stage communication costs only. Both models were designed with information provided by machine developers and utilize implementation derived parameters. With the medium grain parallelism of the current generation and the high fixed cost of an interprocessor communication, our analysis suggests an efficient implementation requires the machine to support the efficient transmission of long messages, (up to 1000 words) or the high initiation cost of a communication must be significantly reduced through an alternative optimization technique. Furthermore, with variable length message capability, our analysis suggests the low diameter multistage networks provide little or no advantage over a simple single stage communications network.

Matheson, Lesley R.↗

NASA NTRS1994

An analysis of spectral envelope-reduction via quadratic assignment problems

A new spectral algorithm for reordering a sparse symmetric matrix to reduce its envelope size was described. The ordering is computed by associating a Laplacian matrix with the given matrix and then sorting the components of a specified eigenvector of the Laplacian. In this paper, we provide an analysis of the spectral envelope reduction algorithm. We described related 1- and 2-sum problems; the former is related to the envelope size, while the latter is related to an upper bound on the work involved in an envelope Cholesky factorization scheme. We formulate the latter two problems as quadratic assignment problems, and then study the 2-sum problem in more detail. We obtain lower bounds on the 2-sum by considering a projected quadratic assignment problem, and then show that finding a permutation matrix closest to an orthogonal matrix attaining one of the lower bounds justifies the spectral envelope reduction algorithm. The lower bound on the 2-sum is seen to be tight for reasonably 'uniform' finite element meshes. We also obtain asymptotically tight lower bounds for the envelope size for certain classes of meshes.

George, Alan↗

NASA NTRS1995

Minimal trellises for linear block codes and their duals

We consider the problem of finding a trellis for a linear block code that minimizes one or more measures of trellis complexity for a fixed permutation of the code. We examine constraints on trellises, including relationships between the minimal trellis of a code and that of the dual code. We identify the primitive structures that can appear in a minimal trellis and relate this to those for the minimal trellis of the dual code.

Kiely, A. B.↗

NASA NTRS1995

Transfer function bounds on the performance of turbo codes

In this article we apply transfer function bounding techniques to obtain upper bounds on the bit-error rate for maximum likelihood decoding of turbo codes constructed with random permutations. These techniques are applied to two turbo codes with constraint length 3 and later extended to other codes. The performance predicted by these bounds is compared with simulation results. The bounds are useful in estimating the 'error floor' that is difficult to measure by simulation, and they provide insight on how to lower this floor. More refined bounds are needed for accurate performance measures at lower signal-to-noise ratios.

Divsalar, D.↗

NASA NTRS2000

Highly Parallel Computing Architectures by using Arrays of Quantum-dot Cellular Automata (QCA): Opportunities, Challenges, and Recent Results

There has been significant improvement in the performance of VLSI devices, in terms of size, power consumption, and speed, in recent years and this trend may also continue for some near future. However, it is a well known fact that there are major obstacles, i.e., physical limitation of feature size reduction and ever increasing cost of foundry, that would prevent the long term continuation of this trend. This has motivated the exploration of some fundamentally new technologies that are not dependent on the conventional feature size approach. Such technologies are expected to enable scaling to continue to the ultimate level, i.e., molecular and atomistic size. Quantum computing, quantum dot-based computing, DNA based computing, biologically inspired computing, etc., are examples of such new technologies. In particular, quantum-dots based computing by using Quantum-dot Cellular Automata (QCA) has recently been intensely investigated as a promising new technology capable of offering significant improvement over conventional VLSI in terms of reduction of feature size (and hence increase in integration level), reduction of power consumption, and increase of switching speed. Quantum dot-based computing and memory in general and QCA specifically, are intriguing to NASA due to their high packing density (10(exp 11) - 10(exp 12) per square cm ) and low power consumption (no transfer of current) and potentially higher radiation tolerant. Under Revolutionary Computing Technology (RTC) Program at the NASA/JPL Center for Integrated Space Microelectronics (CISM), we have been investigating the potential applications of QCA for the space program. To this end, exploiting the intrinsic features of QCA, we have designed novel QCA-based circuits for co-planner (i.e., single layer) and compact implementation of a class of data permutation matrices, a class of interconnection networks, and a bit-serial processor. Building upon these circuits, we have developed novel algorithms and QCA-based architectures for highly parallel and systolic computation of signal/image processing applications, such as FFT and Wavelet and Wlash-Hadamard Transforms.

Fijany, Amir↗

NASA NTRS1995

Variational Calculations of Ro-Vibrational Energy Levels and Transition Intensities for Tetratomic Molecules

A description is given of an algorithm for computing ro-vibrational energy levels for tetratomic molecules. The expressions required for evaluating transition intensities are also given. The variational principle is used to determine the energy levels and the kinetic energy operator is simple and evaluated exactly. The computational procedure is split up into the determination of one dimensional radial basis functions, the computation of a contracted rotational-bending basis, followed by a final variational step coupling all degrees of freedom. An angular basis is proposed whereby the rotational-bending contraction takes place in three steps. Angular matrix elements of the potential are evaluated by expansion in terms of a suitable basis and the angular integrals are given in a factorized form which simplifies their evaluation. The basis functions in the final variational step have the full permutation symmetries of the identical particles. Sample results are given for HCCH and BH3.

Schwenke, David W.↗

NASA NTRS2002

Protein Kinase Classification with 2866 Hidden Markov Models and One Support Vector Machine

The main application considered in this paper is predicting true kinases from randomly permuted kinases that share the same length and amino acid distributions as the true kinases. Numerous methods already exist for this classification task, such as HMMs, motif-matchers, and sequence comparison algorithms. We build on some of these efforts by creating a vector from the output of thousands of structurally based HMMs, created offline with Pfam-A seed alignments using SAM-T99, which then must be combined into an overall classification for the protein. Then we use a Support Vector Machine for classifying this large ensemble Pfam-Vector, with a polynomial and chisquared kernel. In particular, the chi-squared kernel SVM performs better than the HMMs and better than the BLAST pairwise comparisons, when predicting true from false kinases in some respects, but no one algorithm is best for all purposes or in all instances so we consider the particular strengths and weaknesses of each.

Weber, Ryan↗

NASA NTRS2003

Quantum Adiabatic Algorithms and Large Spin Tunnelling

We provide a theoretical study of the quantum adiabatic evolution algorithm with different evolution paths proposed in this paper. The algorithm is applied to a random binary optimization problem (a version of the 3-Satisfiability problem) where the n-bit cost function is symmetric with respect to the permutation of individual bits. The evolution paths are produced, using the generic control Hamiltonians H (r) that preserve the bit symmetry of the underlying optimization problem. In the case where the ground state of H(0) coincides with the totally-symmetric state of an n-qubit system the algorithm dynamics is completely described in terms of the motion of a spin-n/2. We show that different control Hamiltonians can be parameterized by a set of independent parameters that are expansion coefficients of H (r) in a certain universal set of operators. Only one of these operators can be responsible for avoiding the tunnelling in the spin-n/2 system during the quantum adiabatic algorithm. We show that it is possible to select a coefficient for this operator that guarantees a polynomial complexity of the algorithm for all problem instances. We show that a successful evolution path of the algorithm always corresponds to the trajectory of a classical spin-n/2 and provide a complete characterization of such paths.

Boulatov, A.↗

NASA NTRS2001

Relationship between systolic and diastolic function with improvements in forward stroke volume following reduction in mitral regurgitation

Efforts to improve mitral regurgitation (MR) are often performed in conjunction with coronary revascularization. However, the independent effects of a reduced MR area (MRa) are difficult to quantify. Using a previously developed cardiovascular model, ventricular contractility (elastance 1-8 mmHg/ml) and relaxation (tau: 40-150 msec) were independently adjusted for four grades of MR orifice areas (0.0 to 0.8 cm2). Improvements in forward stroke volume (fSV) were determined for the permutations of reduced MRa. For all conditions, LV end-diastolic pressure and volumes ranged from 7.3-24.2 mmHg and 64.8-174.3 ml, respectively. Overall, fSV ranged from 36.0-89.4 (mean: 64.2 +/- 12.8) ml, improved between 6.4 and 35.3% (mean: 15.6 +/- 8.1%), and was best predicted by (r=0.97, p<0.01) %delta(fSV)[correction of fVS]=34[MRa initial] - 46[MRa final] -0.5[elastance]. Reduced MRa, independent of relaxation and minimally influence by contractility, yield improved fSVs.

NASA Discipline Cardiopulmonary↗

NASA NTRS2001

Variable practice with lenses improves visuo-motor plasticity

Novel sensorimotor situations present a unique challenge to an individual's adaptive ability. Using the simple and easily measured paradigm of visual-motor rearrangement created by the use of visual displacement lenses, we sought to determine whether an individual's ability to adapt to visuo-motor discordance could be improved through training. Subjects threw small balls at a stationary target during a 3-week practice regimen involving repeated exposure to one set of lenses in block practice (x 2.0 magnifying lenses), multiple sets of lenses in variable practice (x 2.0 magnifying, x 0.5 minifying and up-down reversing lenses) or sham lenses. At the end of training, adaptation to a novel visuo-motor situation (20-degree right shift lenses) was tested. We found that (1) training with variable practice can increase adaptability to a novel visuo-motor situation, (2) increased adaptability is retained for at least 1 month and is transferable to further novel visuo-motor permutations and (3) variable practice improves performance of a simple motor task even in the undisturbed state. These results have implications for the design of clinical rehabilitation programs and countermeasures to enhance astronaut adaptability, facilitating adaptive transitions between gravitational environments.

NASA Discipline Neuroscience↗

NASA NTRS2005

Path Planning Algorithms for the Adaptive Sensor Fleet

The Adaptive Sensor Fleet (ASF) is a general purpose fleet management and planning system being developed by NASA in coordination with NOAA. The current mission of ASF is to provide the capability for autonomous cooperative survey and sampling of dynamic oceanographic phenomena such as current systems and algae blooms. Each ASF vessel is a software model that represents a real world platform that carries a variety of sensors. The OASIS platform will provide the first physical vessel, outfitted with the systems and payloads necessary to execute the oceanographic observations described in this paper. The ASF architecture is being designed for extensibility to accommodate heterogenous fleet elements, and is not limited to using the OASIS platform to acquire data. This paper describes the path planning algorithms developed for the acquisition phase of a typical ASF task. Given a polygonal target region to be surveyed, the region is subdivided according to the number of vessels in the fleet. The subdivision algorithm seeks a solution in which all subregions have equal area and minimum mean radius. Once the subregions are defined, a dynamic programming method is used to find a minimum-time path for each vessel from its initial position to its assigned region. This path plan includes the effects of water currents as well as avoidance of known obstacles. A fleet-level planning algorithm then shuffles the individual vessel assignments to find the overall solution which puts all vessels in their assigned regions in the minimum time. This shuffle algorithm may be described as a process of elimination on the sorted list of permutations of a cost matrix. All these path planning algorithms are facilitated by discretizing the region of interest onto a hexagonal tiling.

Stoneking, Eric↗

NASA NTRS2004

Surface Modeling and Grid Generation for Iced Airfoils (SmaggIce)

Many of the troubles associated with problem solving are alleviated when there is a model that can be used to represent the problem. Through the Advanced Graphics and Visualization (G-VIS) Laboratory and other facilities located within the Research Analysis Center, the Computer Services Division (CSD) is able to develop and maintain programs and software that allow for the modeling of various situations. For example, the Icing Research Branch is devoted to investigating the effect of ice that forms on the wings and other airfoils of airplanes while in flight. While running tests that physically generate ice and wind on airfoils within the laboratories and wind tunnels on site are done, it would be beneficial if most of the preliminary work could be done outside of the lab. Therefore, individuals from within CSD have collaborated with Icing Research in order to create SmaggIce. This software allows users to create ice patterns on clean airfoils or open files containing a variety of icing situations, manipulate and measure these forms, generate, divide, and merge grids around these elements for more explicit analysis, and specify and rediscretize subcurves. With the projected completion date of Summer 2005, the majority of the focus of the Smagglce team is user-functionality and error handling. My primary responsibility is to test the Graphical User Interface (GUI) in SmaggIce in order to ensure the usability and verify the expected results of the events (buttons, menus, etc.) within the program. However, there is no standardized, systematic way in which to test all the possible combinations or permutations of events, not to mention unsolicited events such as errors. Moreover, scripting tests, if not done properly and with a view towards inevitable revision, can result in more apparent errors within the software and in effect become useless whenever the developers of the program make a slight change in the way a specific process is executed. My task therefore requires a brief yet intense study into GUI coverage criteria and creating algorithms for GUI implementation. Nevertheless, there are still heavily graphical features of SmaggIceSmaggIce that must be either corrected or redesigned before its release. A particular feature of SmaggIce is the ability to smooth out curves created by control points that form an arbitrary shape into something more acquiescent to gridding (while maintaining the integrity of the data). This is done by a mathematical model known as Non-Uniform Rational B-Spline (NURBS) curves. Existing NURBS code is written in FORTRAN-77 with static arrays for holding information. My new assignment is to allow for dynamic memory allocation within the code and to make it possible for the developers to call out functions from the NURBS code using C.

Hammond, Brandy M.↗

NASA NTRS2005

Capacity of the Generalized Pulse-Position Modulation Channel

We show the capacity of a generalized pulse-position modulation (PPM) channel, where the input vectors may be any set that allows a transitive group of coordinate permutations, is achieved by a uniform input distribution. We derive a simple expression in terms of the Kullback Leibler distance for the binary case, and the asymptote in the PPM order. We prove a sub-additivity result for the PPM channel and use it to show PPM capacity is monotonic in the order.

Hamkins, J.↗