The p-adic algorithm is indeed very well known (and implemented in giac). But my point is that Bareiss is faster here (the matrix has huge coefficients but is small), even if you don't care to prove that the determinant is correct once you have (probably) found the last invariant factor and polished the determinant modulo a few primes.
> I wrote that det code in Sage (though in Sage-6.4 it'll likely be > replaced by a call to FLINT...). It computes det(A) in a very > interesting way, which is asymptotically massively faster than > Mathematica. To compute det(A), choose a random vector v and solve Ax > = v using a p-adic lifting algorithm (the one > inhttps://cs.uwaterloo.ca/~astorjoh/iml.html). One can prove --using > Cramer's rule--that the lcm of the denominators of the entries of x > will then be a divisor d of det(A), and with high probability one > expects that det(A)/d is a tiny integer. One can then provably (using > the Hadamard bound) find det(A) by working modulo a few additional > primes and using the Chinese Remainder theorem. > > -- William > > -- > William Stein > Professor of Mathematics > University of Washington > http://wstein.org > -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
