ON THEORETICAL AND PRACTICAL ACCELERATION OF RANDOMIZED COMPUTATION OF THE DETERMINANT OF AN INTEGER MATRIX

摘要

We reexamine the Wiedemann-Coppersmith-Kaltofen-Villard algorithm for randomized computation of the determinant of an integer matrix and substantially simplify and accelerate its bottleneck stage of computing the minimum generating matrix polynomial, to make the algorithm practically promising while keeping it asymptotically fast.