Complexity of Reshaping Arrays on Boolean Cubes

摘要

Reshaping of arrays is a convenient programming primitive. For arrays encoded ina binary-reflected Gray code, reshaping implies code change. The authors show that an axis splitting, or combining of two axes, requires communication in exactly one dimension, and that for multiple axis splittings the exchanges in the different dimensions can be ordered arbitrarily. They present two algorithms that vary in complexity.