Arghh, I'm very suspicious of this ginv. (Sorry to be hijacking the thread somewhat).
They timed Magma on a 32 bit 1 GHz Pentium III and ginv on a 64 bit AMD Turion 3400. 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 --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
