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). 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. 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. Beware!!! I am told (hopefully reliably) the Magma group are currently working on dramatically improving the speed of their algebraic number theory. 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. Magma are apparently working on improving their quadratic sieve. But I really can't see them beating us there. Good luck :-) 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. 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. 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. 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. Bill. --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
