Fast computation of Hermite normal forms of random integer matrices

Clément Pernet (1) , William Stein (2)

1 MOAIS - PrograMming and scheduling design fOr Applications in Interactive Simulation
2 University of Washington [Seattle]

This paper is about how to compute the Hermite normal form of a random integer matrix in practice. We propose significant improvements to the algorithm by Micciancio and Warinschi, and extend these techniques to the computation of the saturation of a matrix. We describe the fastest implementation for computing Hermite normal form for large matrices with large entries.

Domaines: Calcul parallèle, distribué et partagé [cs.DC]

Clément Pernet, William Stein. Fast computation of Hermite normal forms of random integer matrices. Journal of Number Theory, 2010, 130 (7), pp.1675―1683. ⟨10.1016/j.jnt.2010.01.017⟩. ⟨hal-00798442⟩