On Thu, Aug 21, 2008 at 6:10 AM, Bill Hart <[EMAIL PROTECTED]> wrote: > > Arghh, I'm very suspicious of this ginv. (Sorry to be hijacking the > thread somewhat).
No problem that you're hijacking the thread -- I'm glad ginv is getting discussed. I'm removing the mention of it from my talk, though, since clearly I was misled about its capabilities. Thanks again for your feedback! William > > Bill. > > On 21 Aug, 13:57, Bill Hart <[EMAIL PROTECTED]> wrote: >> OK, I see the gcd functions and factorisation, thanks. I was of course >> looking in the polynomial module in the documentation and source code, >> not the coefficient module. >> >> GCD seems somewhat developed, with the Zippel algorithm for sparse >> GCD, Brown's modular GCD and the Heuristic GCD. There's no half gcd >> that I can see, so if that is the case, it wouldn't be asymptotically >> fast or as fast as something based on NTL for example. >> >> I see Cantor-Zassenhaus for factorisation, from which they appear to >> Hensel lift to get factors. But there is no Berlekamp, von zur Gathen- >> Shoup or van Hoeij, that I can see, all of which are essential to even >> compete with NTL. I don't see anything fancy or modern, and certainly >> nothing that can compete with Magma. >> >> Of course it is multivariate, which is something we've been looking >> for, but I don't see why it would replace Singular or why it would be >> better than something custom written and built on top of NTL. >> >> Most worrying perhaps is that mpz_t's and mpz_q's seem to be used for >> coefficients. That has zero chance of competing with Magma. >> >> On the other hand, the benchmarks for Groebner bases look promising. >> See the end of the paper: >> >> http://arxiv.org/pdf/math/0603161v2 >> >> I don't know what representation is used for the multivariable >> polynomials for Groebner bases. But either the algorithm they use is >> amazing, or they use their vectorisation (up to an unsigned int, which >> is a bit small). >> >> I'll be very interested to see how it goes once it is in SAGE and we >> can play with it a little. A brief glance at code can be very >> misleading. >> >> If it is under active development, particularly in the areas that SAGE >> needs speeding up, then that is a major plus. However if a library >> needs to be rewritten from scratch in order to be competitive, I >> question whether it will save all that much development time. >> >> Bill. >> >> On 21 Aug, 11:57, Burcin Erocal <[EMAIL PROTECTED]> wrote: >> >> >> >> > On Thu, 21 Aug 2008 03:28:25 -0700 (PDT) >> >> > Bill Hart <[EMAIL PROTECTED]> wrote: >> >> > <snip> >> >> > > Also at the end of the pdf you mention that SAGE will use the new >> > > russian library ginv for poly gcd and factorisation. I didn't seem to >> > > be able to find functions in the user's guide in the tarball for the >> > > latest version which mentioned poly gcd or factorisation, though I may >> > > have missed them. I also had a look through the source code and >> > > couldn't find them either, though again I didn't look all that >> > > thoroughly. >> >> > Look in the files named igcd* in src/ginv/coeff. >> >> > I looked at the slides after this remark, and that statement about GINV >> > should be changed. >> >> > GINV [1] is a not so new library for involutive basis algorithms. The >> > copyright statements in the files suggest it was started in 2004. >> >> > [1]http://invo.jinr.ru/ginv/index.html >> >> > The factorization code was added by some people from Aachen (the >> > copyright on the files points to Sebastian Jambor), and there is talk >> > about making that part into a separate library. Maybe we should invite >> > them to the Sage days in Nancy? >> >> > Regarding the "fastest in the world" statement on the slides, GINV >> > unfortunately can't beat magma. I haven't timed it myself yet, but >> > Vladimir Gerdt claims that it's faster than maple. >> >> > I'll try to post some code to use the ginv gcd from Sage soon. >> >> > Cheers, >> >> > Burcin > > > -- William Stein Associate Professor of Mathematics University of Washington http://wstein.org --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
