This is not William's machines causing the delay. It's me. We are currently in the process of moving the sites and redesigning one of them. It's taking time due to multiple hardware failures (not the same one that caused the websites to go down) and tight deadlines for other projects. Hang tight.
Bill. On Wednesday, 28 September 2016 14:47:31 UTC+2, leif wrote: > > Jonathan Bober wrote: > > On Tue, Sep 27, 2016 at 8:34 PM, 'Bill Hart' via sage-devel > > <sage-...@googlegroups.com <javascript:> <mailto: > sage-...@googlegroups.com <javascript:>>> wrote: > > > > > > > > On Tuesday, 27 September 2016 20:53:28 UTC+2, Jonathan Bober wrote: > > > > On Tue, Sep 27, 2016 at 7:18 PM, 'Bill Hart' via sage-devel > > <sage-...@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. > > > > > > Sure, I realised the problem was in Sage. I just wasn't sure if the > > algorithm itself is implemented in Flint or 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 > > > > > > Yes, Sage/Linbox was about 2.5x times faster than the old charpoly > > routine in Flint, I believe. The new one is quite recent and much > > quicker. > > > > > > 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 primes. > > > > > > Ouch! > > > > Yes, in the new code we use an explicit proven bound. I can't quite > > recall all the details now, but I recall it is multimodular. > > > > I would give it a good amount of testing before trusting it. We've > > done quite a lot of serious testing of it and the test code is > > nontrivial, but some real world tests are much more likely to shake > > out any bugs, including the possibility I screwed up the > > implementation of the bound. > > > > > > Ah, yes, I'm wrong again, as the multimodular in Flint is pretty new. I > > didn't look at what Sage has until now (flint 2.5.2, which looks likes > > it uses a fairly simple O(n^4) algorithm). I had previously looked at > > the source code of the version of flint that I've actually been using > > myself, which is from June. As I now recall (after reading an email I > > sent in June) I'm using a "non-released" version precisely for the > > nmod_mat_charpoly() function, which doesn't exist in the most recent > > release (which I guess might be 2.5.2, but flintlib.org > > <http://flintlib.org> seems to be having problems at the moment). > > [OT:] flintlib.org (and mpir.org) is hosted at UW, where apparently > some hardware damage (William said a UPS, affecting some switch) makes > the connections at least that slow I cannot access anything there (e.g. > also files.sagemath.org) since last Saturday. (See some later posts on > the neighbour thread on trac not responding, although the latter is > hosted on GCE.) > > > -leif > > > > I've actually done some fairly extensive real world semi-testing of > > nmod_mat_charpoly() in the last few months (for almost the same reasons > > that have lead me to investigate Sage/Linbox) but not > > fmpz_mat_charpoly(). "semi" means that I haven't actually checked that > > the answers are correct. I'm actually computing characteristic > > polynomials of integer matrices, but writing down the integer matrices > > is too expensive, so I'm computing the polynomials more efficiently mod > > p and then CRTing. Also, I'm doing exactly what I think Linbox does, in > > that I am just waiting for the polynomials to stabilize. Step 2, when it > > eventually happens, will separately compute the roots of these > > polynomials numerically, which will (heuristically) verify that they are > > correct. (Step 3 might involve actually proving somehow that everything > > is correct, but I strongly fear that it might involve confessing that > > everything is actually only "obviously" correct.) Once step 2 happens, > > I'll either report some problems or let you know that everything went > well. > > > -- 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.
