@Article{cormen:jbmmc,
  author = {T.~H. Cormen and T. Sundquist and L.~F. Wisniewski},
  title = {Asymptotically tight bounds for performing {BMMC} permutations on
  parallel disk systems},
  journal = {SIAM Journal on Computing},
  year = {1998},
  volume = {28},
  number = {1},
  pages = {105--136},
  publisher = {SIAM},
  copyright = {SIAM},
  keywords = {parallel I/O, parallel I/O algorithms, pario-bib},
  abstract = {This paper presents asymptotically equal lower and upper bounds
  for the number of parallel I/O operations required to perform
  bit-matrix-multiply/complement (BMMC) permutations on the Parallel Disk Model
  proposed by J.S. Vitter and E.A.M. Shriver (1994). A BMMC permutation maps a
  source index to a target index by an affine transformation over GF(2), where
  the source and target indices are treated as bit vectors. The class of BMMC
  permutations includes many common permutations, such as matrix transposition
  (when dimensions are powers of 2), bit-reversal permutations, vector-reversal
  permutations, hypercube permutations, matrix reblocking, Gray-code
  permutations, and inverse Gray-code permutations. The upper bound improves
  upon the asymptotic bound in the previous best known BMMC algorithm and upon
  the constant factor in the previous best known bit-permute/complement (BPC)
  permutation algorithm. The algorithm achieving the upper bound uses basic
  linear-algebra techniques to factor the characteristic matrix for the BMMC
  permutation into a product of factors, each of which characterizes a
  permutation that can be performed in one pass over the data. The factoring
  uses new subclasses of BMMC permutations: memoryload-dispersal (MLD)
  permutations and their inverses. These subclasses extend the catalog of
  one-pass permutations. Although many BMMC permutations of practical interest
  fall into subclasses that might be explicitly invoked within the source code,
  this paper shows how to quickly detect whether a given vector of target
  addresses specifies a BMMC permutation. Thus, one can determine efficiently
  at run time whether a permutation to be performed is BMMC and then avoid the
  general-permutation algorithm and save parallel I/Os by using the BMMC
  permutation algorithm herein}
}