I've undertaken to do some timings of important functions in algebraic number theory, to see where open source software is at compared with say Magma.
The first problem to consider is computing the class group. I start with quadratic number fields and a comparison of Pari and Magma. Firstly, using the default settings in Magma, I was simply unable to obtain timings. Magma is so slow that it isn't even possible to time it. Apparently it uses the Minkowski bound, which is not even the best unconditional bound known. It complains in its documentation that Pari 2.0.20 uses an unproven bound, even assuming GRH. It then says that for quadratic fields Pari uses floor(BachBound(K)/20) and for other fields floor(BachBound(K)/ 40). It should be pointed out that no exceptions are known to these bounds. The documentation also notes that the Bach bound, proven under the GRH is much larger [sic] than the Minkowski bound. I've no idea why the Magma documentation wants to compare the latest version of Magma with an old version of Pari, but they claim that if one changes the bound to one similar to that used by Pari, then the times will be about the same. They give a single example where (surprise, surprise) Magma just happens to be ahead. Note that I am using the latest version of the Magma package and the documentation for this on the Magma website. Well, I must be doing something wrong, since if I use the bounds they suggest for quadratic fields (floor(BachBound(K)/20) - a bound which Magma does not actually allow in general and which needs to be adjusted), the times are nothing like the Pari times. Here are the results: deg, bits, iter : Pari Magma 2, 10, 10000 : 27s 86s 2, 20, 2000 : 25s 142s 2, 30, 300 : 25s 115s 2, 40, 100 : 50-80s 348s Here are some individual timings: x^2 - 678650306441557*x + 232491039415161 : 5.81s 243s x^2 + 400359911885097*x + 1023437292772615 : 8.33s .... x^2 + 788021445418312*x + 62108142321374 : 136s .... x^2 + 310104001090081*x + 526420096868844 : 2.18s 156s x^2 + 29148692184930*x + 697845351766239 : 1.45s 63.5s Monic polynomials were used in all cases and four dots indicates Magma took so long that I gave up waiting. It's possible I'm doing something wrong. But the Magma documentation is not good enough at this point for me to see what this may be. Bill. --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to [email protected] 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/ -~----------~----~----~----~------~----~------~--~---
