On the Injectivity of Modular Mappings

TitleOn the Injectivity of Modular Mappings
Publication TypeConference Paper
Year of Publication1994
AuthorsLee, HJ, Fortes, JAB
Conference NameApplication Specific Array Processors, 1994. Proceedings. International Conference
Date Published08/1994
AbstractAffine 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.