On Wed, Nov 5, 2014 at 3:15 PM, Ursula Whitcher <whitc...@uwec.edu> wrote: > 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?
Yes. Note that though Volker called it a "subtle bug" it wasn't anything like the Mathematica bug. It just failed with "RuntimeError: maximum recursion depth exceeded". It's not wrong answers popping out. The problem was that we upgraded Linbox, which changed to require working modulo bigger primes than we were previous requesting to work modulo. There wasn't anything mathematically wrong. I really think the statement "There have been subtle bugs in determinants of integer matrices in Sage" in reference to this is misleading. Perhaps Jereon who fixed the bug feels differently. I looked at the patch on 14032 and introduces a typo that's still there now. Search for "efficienct" in src/sage/matrix/matrix_integer_dense_hnf.py; maybe the referee of the patch (Volker) will be amused. > Or did it rely on > a different way to compute a determinant over ZZ by working mod p? The last part of what I describe above is "One can then provably (using the Hadamard bound) find det(A) by working modulo a few additional primes..." and that step involves calling whatever black box you have available for finding determinants mod p. -- William > > 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. -- 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.
