On Tuesday, November 11, 2014 12:21:12 AM UTC+1, William wrote: > > On Mon, Nov 10, 2014 at 3:08 PM, Ursula Whitcher <whit...@uwec.edu > <javascript:>> wrote: > > On 11/5/2014 8:24 AM, William Stein wrote: > > > >> * By "we write up" above, I mean you write up something very, very > >> rough, post it here, and get feedback. > > > > > > Done! > > > > http://people.uwec.edu/whitchua/notes/sagebugprocess.pdf > > Wow, that's really nice! I really like the tone and length. > > > I stuck with Ticket 14032 as my example; I think the tradeoff of > interesting > > algorithm vs. boring bug is OK for a general math audience. > > > > Questions: > > > > * Who found the bug corresponding to ticket 14032? Was the computation > in > > service of an interesting research question? > > > > Jeroen Demeyer reported it -- did you also *find* it Jeroen? > > > * Originally, William said "working modulo a few additional primes". > Does > > this mean doing p-adic lifting again, or just black-box computing det A > (mod > > p), as I have implied? > > Just black-box computing det A, as you implied. > > One thing that isn't technically 100% correct about the p-adic lifting > part of what you say is that one in fact > works modulo several distinct primes lifting p-adically a bit, rather > than modulo only one prime. You might just say in parens that the > actual implementation is slightly more subtle than what you describe > and cite https://cs.uwaterloo.ca/~astorjoh/iml.html > I've cc'd Arne Storjohann (co-author of IML) and Clement Pernet on this > message. > > As Sage is switching to FLINT very soon by default for integer matrix > determinants (due to Marc Masdue's recent patch), I wonder what > algorithm FLINT uses for this problem? It would be good to be aware > at least. > > I wrote the determinant code in FLINT. It uses cofactor expansion up to size 4, the Bareiss algorithm (fraction-free Gaussian elimination) up to size 24, and the multimodular algorithm (compute modulo small primes whose product exceeds twice the Hadamard bound) up to size 59. The determinants mod p are computed using recursive LU decomposition, with Strassen matrix multiplication for sufficiently large matrices, and some tricks like delayed reduction to make the mod p arithmetic fast.
>From size 60, FLINT uses the multimodular algorithm, but if the matrix has small entries (max bits <= matrix size) it uses the trick of computing a divisor of the determinant by solving a "random" linear system using p-adic lifting -- some quick testing I did suggested that this trick is slower than the straight multimodular algorithm when the matrix has very large entries. Either the p-adic lifting or the determinants modulo small primes can be a bottleneck. IML is faster for very large matrices (from around size 500-1000 and up the last time I checked). One reason for this is that FLINT does not yet use BLAS for mod p linear algebra. I think IML also uses a better lifting strategy. The determinant code in FLINT isn't optimized for singular matrices. Instead of going all the way up to the Hadamard bound, you could stop if the determinant is zero modulo the first prime you try, and then verify that the matrix really is singular by computing a certified rref. At least I think this might be faster in practice. One of our two GSoC students this year, Alex Best, implemented the mod p + certification algorithm for the fmpz_mat_rref, fmpz_mat_rank and fmpz_mat_nullspace functions, which makes them vastly faster than what we had before for large matrices. Alex's code has been merged into the git trunk and will be included in the next FLINT release. Another thing FLINT doesn't optimize for is matrices that are triangular, diagonal, or extremely sparse. These probably constitute a decent fraction of real-world input, so it would probably be worth the very slight overhead to check for them... Fredrik -- 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.
