Well I just read all the Pari source code very carefully for the case of a quadratic number field. The code is quite simple (less than 1000 lines) and about the only thing one needs to implement it is fast composition and powering of binary quadratic forms (ultimately one might want some Smith normal form code to manipulate the class group, but the basic answer can be returned without it).
The Pari implementation does not appear to use sieving. In the imaginary quadratic case it starts by computing a factor base of primes and simultaneously computes L(1,chi) to get hR. Then it appears to generate random binary quadratic forms with a specified factor and factors them over a factor base (up to some limit) and allows a single large prime beyond that limit which it keeps track of using a basic hash table. It generates relations according to Buchmann's algorithm, computing a provisional regulator as it goes, then uses the relations to compute the class group in a fairly straightforward way. The limit used is explicitly: Max(0.2*(log D)^2, exp(sqrt(log D loglog D) / 8)) where D is the discriminant. For sufficiently large discriminants that is at BachBound/20 as the Magma documentation claims. At some point Pari used BachBound/40, but that apparently slowed it down. So it seems that I am using the correct limit in my comparisons with Magma. For some of the randomised tests it is probably the case that I should ensure the limit is not too small, e.g. greater than 20 or something like that, but this does not explain the timings for explicit individual examples I gave, nor for the cases where the discriminant is fairly large generically. It really does seem like Magma is quite a bit slower for this problem for quadratic fields. Pari has dedicated code for both the imaginary and real quadratic cases, however I don't believe their algorithm to be anywhere near optimal especially for large discriminants. I will be interested to compare LiDIA on this one. I'll also be interested to compare Magma for larger fields. Magma also has a separate algorithm which is sometimes faster for this problem, but there are no known heuristics to tell when it is going to be faster. I will also have to time that in the case of some explicit fields. Bill. On 5 Sep, 14:07, "John Cremona" <[EMAIL PROTECTED]> wrote: > I certainly would not trust Magma's documentation to give an accurate > description of what pari does. Even if was accurate when written, it > would not have been updated since then (almost certainly) while pari > has seen continuous development and improvement. > > Go to the source's source: ask Karim Belabas! He will certailny be > able to tell you what methods and assumptions pari makes. > > It certainly used to be the case that magma was slower than pari on > class groups becuse pari assumes GRH by default while Kant (whose code > magma uses, or used, for this does not). But I do not know how > accurately that describes the situation at present. > > John > > On 9/5/07, Bill Hart <[EMAIL PROTECTED]> wrote: > > > > > > > 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. > > -- > John Cremona --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
