On the injectivity of modular mappings
H. J. Lee, J.A.B. Fortes · 2002
Affine space-time mappings have been extensively studied for systolic array design and parallelizing compilation. However, there are practical important cases that require other types of transformations. This paper considers so-called modular mappings described by linear transformations modulo a constant vector. Sufficient conditions for these mappings to be one-to-one are investigated for rectangular domains of arbitrary dimensions. It is shown that a sufficient condition for a modular mapping to be one-to-one is that its (n×n) coefficient matrix T has entries tii=±1 and tij=0 for i<j where < is a total order on {1,2,, n), n=domain dimension. These conditions are strengthened and extended for particular types of rectangular domains and affine transformations modulo a constant vector. The results of this paper can be used to identify a space of valid modular mappings of specific algorithms into time and space. They are illustrated by examples which include Cannon's matrix multiplication algorithm.