A fast Las Vegas algorithm for computing the Smith normal form of a polynomial matrix (Q677132)

A fast Las Vegas sequential algorithm for computing the Smith normal form of a square nonsingular matrix \(A\in{\mathbb{F}}[x]\) is presented. \({\mathbb{F}}[x]\) denotes a field. A Las Vegas algorithm means that an incorrect result will never be returned, but the algorithm may fail with small probability and requires repetition. The key step is preconditioning \(A'\) of the input matrix \(A\). It avoids the usual technique of diagonalizing the input matrix with a succession of unimodular row and column operations. The main computation is the (nonunimodular) triangularization of a polynomial matrix of the same dimension and with similar size of entries as the input matrix. The cost of one pass of the algorithm requires \(O\sim (n^5d(d+\log|A|)\log(|A|))\) bit operations using standard integer, polynomial, and matrix arithmetic plus no more than \(O(n^2)\) trial divisions, multiplications, and gcd computations (where \(|A|\) bounds the magnitude of all integer coefficients in \(A\), \(d\) bounds the degree of entries of \(A\)). Using fast integer and polynomial multiplication, the algorithm requires an expected number of \(O\sim (n^3d(d+n^2\log|A|))\) bit operations which significantly improves previous complexity results. The correctness of the algorithm is proved.