A Fast +Practical +Deterministic Algorithm for Triangularizing Integer Matrices
Arne Storjohann · Repository for Publications and Research Data (ETH Zurich) · 1996
This paper presents a new algorithm for computing the row reduced echelon form triangularization H of an n \\Theta m integer input matrix A. The cost of the algorithm is O(nmr 2 log 2 rjjAjj + r 4 log 3 rjjAjj) bit operations where r is the rank of A and jjAjj = max ij jA ij j. This complexity result assumes standard (quadratic) integer arithmetic but still matches, in the paramaters n, m and r, the best bit complexity we can reasonably hope for under the assumption of standard matrix arithmetic. A unimodular transforming matrix U which satisfies UA = H is also computed within the same running time. As a direct application of our triangularization algorithm we give a fast algorithm for solving a system A~x = ~ b of linear Diophantine equations. The algorithms presented here are both fast and practical. They are easily implemented, handle the case of input matrices having arbitrary shape and rank profile, and allow integer arithmetic to be performed in a residue number system. ...