A Vector Space Framework for Parallel Stable Permutations
1997 (English)Conference paper (Refereed)
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, arithm...
Place, publisher, year, edition, pages
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-64547OAI: oai:DiVA.org:kth-64547DiVA: diva2:483114
In Second International Workshop on Formal Methods for Parallel Programming: Theory and Applications
NR 201408052012-01-242012-01-24Bibliographically approved