Compressed Modular Matrix Multiplication

Jean-Guillaume Dumas (1) , Laurent Fousse (1) , Bruno Salvy (2)

1 CASYS - Calculs Algébriques et Systèmes Dynamiques
2 ALGORITHMS - Algorithms

We propose to store several integers modulo a small prime into a single machine word. Modular addition is performed by addition and possibly subtraction of a word containing several times the modulo. Modular Multiplication is not directly accessible but modular dot product can be performed by an integer multiplication by the reverse integer. Modular multiplication by a word containing a single residue is a also possible. Therefore matrix multiplication can be performed on such a compressed storage. We here give bounds on the sizes of primes and matrices for which such a compression is possible. We also explicit the details of the required compressed arithmetic routines.

Mots clés: matrix format; small prime field; exact matrix multiplication; polynomial multiplication; dot product

Domaines: Calcul formel [cs.SC]

Jean-Guillaume Dumas, Laurent Fousse, Bruno Salvy. Compressed Modular Matrix Multiplication. MICA'2008 - Milestones in Computer Algebra, May 2008, Tobago, Trinidad and Tobago. pp.133-140. ⟨hal-00259950v2⟩