Emeric GIOAN, Serge BURCKEL and Emmanuel THOMÉ
Abstract. We investigate the computation of mappings from a set S^n to itself with "in situ programs", that is using no extra variables than the input, and performing modifications of one component at a time. Several types of mappings are considered, for which we obtain effective computation and decomposition methods, together with upper bounds on the program length (number of assignments). Our technique is combinatorial and algebraic (graph coloration, partition ordering, modular arithmetics). For general mappings, we build a program with maximal length 5n-4, or 2n-1 for bijective mappings. The length is reducible to 4n-3 when |S| is a power of 2. This is the main combinatorial result of the paper, which can be stated equivalently in terms of multistage interconnection networks as: any mapping of {0,1}^n can be performed by a routing in a double n-dimensional Benes network. Moreover, the maximal length is 2n-1 for linear mappings when S is any field, or a quotient of an Euclidean domain (e.g. Z/sZ). In this case the assignments are also linear, thereby particularly efficient from the algorithmic viewpoint. The "in situ" trait of the programs constructed here applies to optimization of program and chip design with respect to the number of variables, since no extra writing memory is used. More philosophically, the unconventional computation claim underlying this approach is that any transformation of a signal can be done efficiently by elementary local transformations with no need of a larger amount of space during the transformation.