On Tue, Sep 27, 2016 at 11:53 AM, Jonathan Bober <jwbo...@gmail.com> wrote: > On Tue, Sep 27, 2016 at 7:18 PM, 'Bill Hart' via sage-devel > <sage-devel@googlegroups.com> wrote: >> >> I'm pretty sure the charpoly routine in Flint is much more recent that 2 >> years. Are you referring to a Sage implementation on top of Flint arithmetic >> or something? > > > It is just a problem with Sage. Sorry, I thought I was clear about that. I > assume that no one has been using the algorithm='flint' option in Sage in > the last two years, which makes sense, because most people aren't going to > bother changing the default. > >> >> The only timing that I can find right at the moment had us about 5x faster >> than Sage. It's not in a released version of Flint though, just in master. > > > That sounds really nice. On my laptop with current Sage, it might be the > other way around. With Sage 7.3 on my laptop, with this particular matrix, I > get > > sage: %time f = A.charpoly(algorithm='flint') > CPU times: user 1min 24s, sys: 24 ms, total: 1min 24s > Wall time: 1min 24s > > sage: %time f = A.charpoly(algorithm='linbox') > CPU times: user 13.3 s, sys: 4 ms, total: 13.3 s > Wall time: 13.3 s > > However, perhaps the average runtime with linbox is infinity. (Also, this in > an out of date Linbox.) > > I think that Linbox may be "cheating" in a way that Flint is not. I'm pretty > sure both implementations work mod p (or p^n?) for a bunch of p and > reconstruct. From my reading of the Flint source code (actually, I didn't > check the version in Sage) and comments from Clement Pernet, I think that > Flint uses an explicit Hadamard bound to determine how many primes to use, > while Linbox just waits for the CRT'd polynomial to stabilize for a few
If it is really doing this, then it should definitely not be the default algorithm for Sage, unless proof=False is explicitly specified. Not good. William > primes. I have no idea how much of a difference that makes in this case. > >> >> Bill. >> >> On Tuesday, 27 September 2016 05:49:47 UTC+2, Jonathan Bober wrote: >>> >>> On Tue, Sep 27, 2016 at 4:18 AM, William Stein <wst...@gmail.com> wrote: >>>> >>>> On Mon, Sep 26, 2016 at 6:55 PM, Jonathan Bober <jwb...@gmail.com> >>>> wrote: >>>> > On Mon, Sep 26, 2016 at 11:52 PM, William Stein <wst...@gmail.com> >>>> > wrote: >>>> >>>> >> >>>> >> On Mon, Sep 26, 2016 at 3:27 PM, Jonathan Bober <jwb...@gmail.com> >>>> >> wrote: >>>> >> > In the matrix_integer_dense charpoly() function, there is a note in >>>> >> > the >>>> >> > docstring which says "Linbox charpoly disabled on 64-bit machines, >>>> >> > since >>>> >> > it >>>> >> > hangs in many cases." >>>> >> > >>>> >> > As far as I can tell, that is not true, in the sense that (1) I >>>> >> > have >>>> >> > 64-bit >>>> >> > machines, and Linbox charpoly is not disabled, (2) >>>> >> > charpoly(algorithm='flint') is so horribly broken that if it were >>>> >> > ever >>>> >> > used >>>> >> > it should be quickly noticed that it is broken, and (3) I can't see >>>> >> > anywhere >>>> >> > where it is actually disabled. >>>> >> > >>>> >> > So I actually just submitted a patch which removes this note while >>>> >> > fixing >>>> >> > point (2). (Trac #21596). >>>> >> > >>>> >> > However... >>>> >> > >>>> >> > In some testing I'm noticing problems with charpoly(), so I'm >>>> >> > wondering >>>> >> > where that message came from, and who knows something about it. >>>> >> >>>> >> Do you know about "git blame", or the "blame" button when viewing any >>>> >> file here: https://github.com/sagemath/sage/tree/master/src >>>> > >>>> > >>>> > Ah, yes. Of course I know about that. And it was you! >>>> > >>>> > You added that message here: >>>> >>>> Dang... I had a bad feeling that would be the conclusion :-) >>> >>> >>> Well, I'm sure you've done one or two things in the meantime that will >>> allow me to forgive this one oversight. >>> >>>> >>>> In my defense, Linbox/FLINT have themselves changed a lot over the >>>> years... We added Linbox in 2007, I think. >>>> >>> >>> Yes. As I said, this comment, and the design change, is ancient. In some >>> limiting testing, linbox tends to be faster than flint, but has very high >>> variance in the timings. (I haven't actually checked flint much.) Right now >>> I'm running the following code on 64 cores, which should test linbox: >>> >>> import time >>> >>> @parallel >>> def test(n): >>> start = time.clock() >>> f = B.charpoly() >>> end = time.clock() >>> runtime = end - start >>> if f != g: >>> print n, 'ohno' >>> return runtime, 'ohno' >>> else: >>> return runtime, 'ok' >>> >>> A = load('hecke_matrix') >>> A._clear_cache() >>> B, denom = A._clear_denom() >>> g = B.charpoly() >>> B._clear_cache() >>> >>> import sys >>> >>> for result in test(range(100000)): >>> print result[0][0][0], ' '.join([str(x) for x in result[1]]) >>> sys.stdout.flush() >>> >>> where the file hecke_matrix was produced by >>> >>> sage: M = ModularSymbols(3633, 2, -1) >>> sage: S = M.cuspidal_subspace().new_subspace() >>> sage: H = S.hecke_matrix(2) >>> sage: H.save('hecke_matrix') >>> >>> and the results are interesting: >>> >>> jb12407@lmfdb5:~/sage-bug$ sort -n -k 2 test_output3 | head >>> 30 27.98 ok >>> 64 28.0 ok >>> 2762 28.02 ok >>> 2790 28.02 ok >>> 3066 28.02 ok >>> 3495 28.03 ok >>> 3540 28.03 ok >>> 292 28.04 ok >>> 437 28.04 ok >>> 941 28.04 ok >>> >>> jb12407@lmfdb5:~/sage-bug$ sort -n -k 2 test_output3 | tail >>> 817 2426.04 ok >>> 1487 2466.3 ok >>> 1440 2686.43 ok >>> 459 2745.74 ok >>> 776 2994.01 ok >>> 912 3166.9 ok >>> 56 3189.98 ok >>> 546 3278.22 ok >>> 1008 3322.74 ok >>> 881 3392.73 ok >>> >>> jb12407@lmfdb5:~/sage-bug$ python analyze_output.py test_output3 >>> average time: 53.9404572616 >>> unfinished: [490, 523, 1009, 1132, 1274, 1319, 1589, 1726, 1955, 2019, >>> 2283, 2418, 2500, 2598, 2826, 2979, 2982, 3030, 3057, 3112, 3166, 3190, >>> 3199, 3210, 3273, 3310, 3358, 3401, 3407, 3434, 3481, 3487, 3534, 3546, >>> 3593, 3594, 3681, 3685, 3695, 3748, 3782, 3812, 3858, 3864, 3887] >>> >>> There hasn't yet been an ohno, but on a similar run of 5000 tests >>> computing A.charpoly() instead of B I have 1 ohno and 4 still running after >>> 5 hours. (So I'm expecting an error in the morning...) >>> >>> I think that maybe I was getting a higher error rate in Sage 7.3. The >>> current beta is using a newer linbox, so maybe it fixed something, but maybe >>> it isn't quite fixed. >>> >>> Maybe I should use a small matrix to run more tests more quickly, but >>> this came from a "real world" example. >>> >>>> >>>> -- >>>> William (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+...@googlegroups.com. >>>> To post to this group, send email to sage-...@googlegroups.com. >>>> Visit this group at https://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 https://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 https://groups.google.com/group/sage-devel. > For more options, visit https://groups.google.com/d/optout. -- William (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 https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
