On Wed, Oct 29, 2014 at 7:14 AM, Harald Schilly <harald.schi...@gmail.com> wrote: > > > On Wednesday, October 29, 2014 1:25:08 PM UTC+1, parisse wrote: >> >> Just curious: what is the algorithm used by sage here? >> I have tried Bareiss, modular and p-adic with giac, and Bareiss seems the >> fastest: 0.02s on my Mac, vs about 1s for (proven) modular/p-adic. >> sage 6.3 returns the answer in 0.12s on my computer, while Maxima takes >> 15s. > > > Sage uses different algorithms based on difficulty. > http://git.sagemath.org/sage.git/tree/src/sage/matrix/matrix_integer_dense.pyx#n3252 > > I'm guessing in this case it's this branch: > http://git.sagemath.org/sage.git/tree/src/sage/matrix/matrix_integer_dense_hnf.py#n184 >
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.
