At some point, William wrote:
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.
At some other point, Volker wrote:
There have been subtle bugs in determinants of integer matrices in
Sage before, e.g. http://trac.sagemath.org/ticket/14032
"determinant() of integer matrices of size in [51,63] broken". Open
source doesn't make Sage magically bug-free.
The note on ticket 14032 about the bug's solution is:
"The problem was an infinite recursion where we compute a determinant
over ZZ by working mod p and we compute a determinant over GF(p) by
lifting to ZZ..."
Was the algorithm that should have been used here for finding a
determinant over GF(p) the same as the one that William is describing?
Or did it rely on a different way to compute a determinant over ZZ by
working mod p?
UAW
--
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.
