Abstract:
We reexamine the Wiedemann–Coppersmith–Kaltofen–Villard algorithm for randomized computation of the determinant of integer matrices 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.