Jonathan Bober wrote: > On Tue, Sep 27, 2016 at 8:34 PM, 'Bill Hart' via sage-devel > <sage-devel@googlegroups.com <mailto:sage-devel@googlegroups.com>> 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.
