A Vector Space Framework for Parallel Stable Permutations

Abstract

We establish a formal foundation for stable permutations in the domain of a parallel model of computation applicable to a customized set of complexity metrics. By means of vector spaces, we develop an algebrao-geometric representation that is expressive, flexible and simple to use, and present a taxonomy categorizing stable permutations into classes of index-digit, linear, translation, affine and polynomial permutations. For each class, we demonstrate its general behavioral properties and then analyze particular examples in each class, where we derive results about its inverse, fixed instances, number of instances local and nonlocal to a processor, as well as its compositional relationships to other permutations. Such examples are bit-reversal, radix-Q exchange, radix-Q shuffle and unshuffle within the index-digit class, radix-Q butterfly and 1's complement within the translation class, binary-to-Gray and Gray-to-binary within the linear class, and arithmetic add 1, arithmetic subtract 1 and 2's complement in the polynomial class. These were primarily chosen due to their importance in implementing orthogonal transforms, such as Cooley-Tukey Fast Fourier Transforms (FFT), real-to-complex (complex-to-real) FFT, and sine and cosine transforms on distributed memory parallel processing systems.