Cool. Can I ask what if any profiles have been done of algebraic number theory functions yet in Magma and other packages?
It might be interesting to look at LiDIA in the roundup too. I understand a fair bit of effort went into that in the ANT area. Since it is definitely an issue which interests me, I'd be interested in doing some basic timings, but I don't want to duplicate what others have done. Bill. On 1 Sep, 20:59, "William Stein" <[EMAIL PROTECTED]> wrote: > On 9/1/07, Bill Hart <[EMAIL PROTECTED]> wrote: > > > I can't recall if I mentioned the following things related to > > performance already, apologies if I did, and apologies if some of it > > is out-of-date information to the SAGE group who've already been > > working on this: > > > 1) I'm told Magma uses some version of Kash/Kant for algebraic number > > theory, or at least did at some point (at least by mentioning this > > online someone from the Magma group may be able to correct my > > misconception if it is wrong). > > True. Magma started it's number fields using Kash/Kant, then > supported many of their developers (e.g., Klaus, Florian, etc.). > > > However Magma gets a lot of its speed > > from algorithms of Klaus Fieker (?) which I have heard talks on at U > > of Sydney. I seem to recall he embeds the number field in a very very > > large field which has a nice representation, then tries to get > > information that way. I'm sure he has numerous papers on the subject. > > I was a young undergraduate when I saw these and couldn't explain them > > if I tried. > > I hope he's written lots of papers. I was Klaus's office mate most of the > time when I visited Sydney -- he's a nice guy. > > > At any rate, the difficulty with this approach is you cannot always > > tell a priori whether this is going to beat the algorithms used by say > > Pari. And often it does not. > > Interesting. > > > Beware!!! I am told (hopefully reliably) the Magma group are currently > > working on dramatically improving the speed of their algebraic number > > theory. > > Good for them. SAGE is far far behind; even beginning to catch up would > be a significant improvement. Basically algebraic number theory -- our > research > area -- is perhaps one of the areas of mathematics where closed source is > vastly ahead of open source. > > > 2) Many algorithms rely critically on factoring the discriminant, > > which often dominates the runtime as I understand it. SAGE has a > > perfect opportunity to beat Magma by using a potent cocktail of > > factoring routines including GMP-ECM, an implementation of Sam > > Wagstaff's variations on the SQUFOF theme which I have implemented in > > FLINT (twice the speed of Pari and Magma at factoring) and of course, > > for larger discriminants without small factors, my quadratic sieve, > > once it is done. One should also have a good implementation of Pollard- > > Brent, which I don't have yet. > > :-) Very true. > > > 3) Clearly some routines require fast polynomial arithmetic. FLINT > > *cough cough*. The Magma group also claim to be broadly working on > > improving their "core arithmetic" over the next few years. But I am > > quite certain there isn't substantial work being done on improving the > > speed of polynomial arithmetic at this instant. I'd like to see them > > working on it, but I'm relatively sure Allan Steel has more > > interesting projects on the go at present. I look forward to the day > > he returns to polynomials. > > > FLINT is getting closer to being usable. I just finished profiles of > > FLINT polynomial division against NTL. It is fair to say FLINT is > > slaying NTL everywhere (up to 25 times faster at points and typically > > twice the speed). We can actually do *much* better, but this will wait > > until post FLINT 1.0. We certainly beat Magma everywhere. > > SAGE will definitely use FLINT for the underlying number field arithmetic > at some point in the not distant future. This is very high priority for me. > Even if we can't be better than magma in the high level algorithms quickly, > at least we can be very respectable at arithmetic. > > > That leaves only pseudo-division and poly GCD to go before FLINT 1.0 > > and I've already done the algorithm research for both. Pseudo-division > > can be done using a slight variant of the algorithm I came up with for > > doing polynomial division and poly GCD isn't that hard given all the > > work we've put into the lower level stuff. So as much as we've been > > saying FLINT will be released soon for many months now, it really is > > getting close now. So please consider using FLINT to implement some of > > the fast algebraic number theory routines. FLINT essentially has a > > development interface for doing even faster implementations of such > > things than might be possible via the eventual SAGEified interface to > > FLINT. Routines could be written in FLINT then be pyrexed into SAGE. > > Definitely! > > > If there is a substantial effort put into beating Magma at algebraic > > number theory, I'm pretty sure it is not going to be enough to pyrex > > existing open source packages. > > It's not even close to being enough. Magma is vastly ahead of all > open source packages at high-level algebraic number theory algorithms. > > >Magma really has done something special > > in this area and unfortunately the open source community have fallen > > woefully behind both in the range of algorithms available and in the > > performance arena. It's certainly something we have the tools to fix > > though. > > I agree 100%. It is a serious problem. Let's attack it head on. > > William --~--~---------~--~----~------------~-------~--~----~ 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://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
