Index transformation algorithms in a linear algebra framework
Authors:
- A. EdelmanAEA. Edelman
- S. HellerSHS. Heller
- S. Lennart JohnssonSJS. Lennart Johnsson
- 1 January 1994
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 5 (12) , 1302-1309
Abstract
We present a linear algebraic formulation for a class of index transformations such asGray code encoding and decoding, matrix transpose, bit reversal, vector reversal,shuffles, and other index or dimension permutations. This formulation unifies, simplifies,and can be used to derive algorithms for hypercube multiprocessors. We show how all the widely known properties of Gray codes, and some not so well-known properties as well, can be derived using this framework. Using this framework, we relate hypercube communications algorithms to Gauss-Jordan elimination on a matrix of 0's and 1's.Keywords
This publication has 17 references indexed in Scilit:
- Generalized shuffle permutations on boolean cubesJournal of Parallel and Distributed Computing, 1992
- A fast algorithm for transposing large multidimensional image data setsUltramicroscopy, 1991
- Optimal matrix transposition and bit reversal on hypercubes: All-to-all personalized communicationJournal of Parallel and Distributed Computing, 1991
- Algorithms for Matrix Transposition on Boolean N-Cube Configured Ensemble ArchitecturesSIAM Journal on Matrix Analysis and Applications, 1988
- Communication efficient basic linear algebra computations on hypercube architecturesJournal of Parallel and Distributed Computing, 1987
- A Unified Approach to a Class of Data Movements on an Array ProcessorIEEE Transactions on Computers, 1982
- Array Permutation by Index-Digit PermutationJournal of the ACM, 1976
- Origins of the Binary CodeScientific American, 1972
- Mathematical GamesScientific American, 1972
- Gray Codes and Paths on the n-CubeBell System Technical Journal, 1958