Computation with No Memory, and Rearrangeable Multicast Networks

Emeric Gioan 1 Serge Burckel 2, 3 Emmanuel Thomé 4
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
4 CARAMEL - Cryptology, Arithmetic: Hardware and Software
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
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, hence using no extra memory. In this paper, we survey this problem introduced in previous papers by the authors, we detail its close relation with rearrangeable multicast networks, and we provide new results for both viewpoints. A bijective mapping can be computed by 2n-1 component modifications, that is by a program of length 2n-1, a result equivalent to the rearrangeability of the concatenation of two reversed butterfly networks. For a general arbitrary mapping, we give two methods to build a program with maximal length 4n-3. Equivalently, this yields rearrangeable multicast routing methods for the network formed by four successive butterflies with alternating reversions. The first method is available for any set S and practically equivalent to a known method in network theory. The second method, a refinment of the first, described when |S| is a power of 2, is new and allows more flexibility than the known method. For a linear mapping, when S is any field, or a quotient of an Euclidean domain (e.g Z/sZ for any integer s), we build a program with maximal length 2n-1. In this case the assignments are also linear, thereby particularly efficient from the algorithmic viewpoint, and giving moreover directly a program for the inverse when it exists. This yields also a new result on matrix decompositions, and a new result on the multicast properties of two successive reversed butterflies. Results of this flavour were known only for the boolean field Z/2Z.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, 16 (1), pp.121-142
Liste complète des métadonnées


https://hal-lirmm.ccsd.cnrs.fr/lirmm-00959964
Contributeur : Emeric Gioan <>
Soumis le : mercredi 22 juillet 2015 - 11:07:19
Dernière modification le : vendredi 9 juin 2017 - 10:42:27
Document(s) archivé(s) le : vendredi 23 octobre 2015 - 10:33:22

Fichier

dmtcs-16-1-8.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

  • HAL Id : lirmm-00959964, version 1

Citation

Emeric Gioan, Serge Burckel, Emmanuel Thomé. Computation with No Memory, and Rearrangeable Multicast Networks. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, 16 (1), pp.121-142. <lirmm-00959964>

Partager

Métriques

Consultations de
la notice

445

Téléchargements du document

245