On 11 November 2014 00:53, Fredrik Johansson <fredrik.johans...@gmail.com> wrote: > > > 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> 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.
Point of info: Alex Best graduated recently from Warwick with a 3-year degree in Discrete Mathematics though he had also covered several extra courses from our 4-year mathematics degree, As well as his amazing work for GSoC he was also simultabeously doing a summer research project with Lassina Dembele. He is now doing the Cambridge "Part III" course and will be looking for a PhD place for next year.... If he is reading this, I hope Alex does not mind me saying all this! John > > 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. -- 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.
