On Tue, Sep 27, 2016 at 8:02 PM, William Stein <wst...@gmail.com> wrote:
> 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. > > Yes, I've had the same thought, which is actually part of the reason I took the time to write this. I hope that Clement, or someone else who knows, will notice and confirm or deny. Also, eventually I will probably try to read the Linbox source code. It is possible that I am wrong. (I guess that there is some certification step, and that it is somewhat heuristic, but maybe it is more definitive than that.) > 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. > -- 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.
