Hi Nils, Thanks for the information and encouragement. I do expect Magma to come out ahead for large degree fields, since I recall timing it once before and finding it ahead of Pari in such instances. That depends on how much Pari has been improved recently of course.
I think you are right that the objection in the Magma documentation is moot for many fields since Pari bails out when it knows it has the correct value for hR. It obtains the correct value by examining the L- series. I have something else to present at ANTS :-) But thanks for encouraging me to present the details there. I will make the information available for number theorists to access. The problem is keeping it up to date, especially as Magma is likely to become a moving target in the near future. :-( I strongly suspect that Magma will not fare better for "real life" fields as opposed to random ones. But you are right that I should include such timings in my profiles. I've been thinking about ways one may get a slightly better result in the case of totally real fields, which Pari does not take advantage of except for the quadratic case. Bill. On 5 Sep, 20:15, Nils Bruin <[EMAIL PROTECTED]> wrote: > Congratulations on your result. This is a very useful project and I am > sure that nearly all computational number theorists will be very > interested in the outcomes. If you do it properly, you could even > considering submitting it to ANTS (it's not really mathematics, > because the objects of study are the programs, not the mathematics, > but because of the importance a good benchmarking will be very > interesting. At the least worth a poster at ANTS) > > t is really useful to do a fair comparison between Pari and Magma. I > would expect those two to be the leaders anyway. I would suggest > running the timings, including the magma code you are using, past, for > instance, Claus Fieker. It is in their interest to let magma come out > well and if your tests show that it is hard to let magma choose the > right parameters, they may improve the interface. The subexponential > algorithms are very similar to the number field sieve and tuning the > algorithms is very subtle and sensitive to the input. > > - I know the KANT/KASH project concentrated on larger degree, not > large discriminant. > Your fields do not really get into the large degree range (that would > be more like degree 6 and up I would think) > > - Degree 2 is really special. You may want to talk to Michael > Jacobson (University of Calgary) about that. He has worked on some > really big computations for those and may be willing to share code/ > ideas. > > - The "BachBound/40" should *only* come into play if *checking* that > the full class group has been found takes considerable time. For > higher degree or larger discriminant fields, you expect that you can > easily find enough relations on a factor base much smaller than the > minkowskibound, but at the same time, the factor basis should not be > chosen too small. Sure, you only have to find very few relations then, > but for a very small factor base they may be very hard to find. By > feeding magma a smaller bound, you may be putting it at a > disadvantage. Are you using SetClassGroupBounds? It takes two bounds: > one for the factor basis, the other for checking the class group. > > - Representation of the field can make a *huge* difference. Doing a > ClassGroup(LLL(MaximalOrder(K))) > is sometimes *much* faster than > ClassGroup(MaximalOrder(K)) > (note that you should be timing the LLL and MaximalOrder separately) > I have also seen examples where changing the representation of K (take > a different generating element) hugely > affects the running time (from not finising to finishing in a second)>From > what I understand from the experts, the heuristics for finding > > relations are largely black art. > > - If at all possible, you should split your timings in > 1) finding the class group (i.e., finding sufficient relations to > get consistent unit and class group info) > 2) verifying the class group information (checking that the ideals > not in the factor base but below the bach bound, minkowski bound or > whatever you want to use have classes that are already generated by > the factor basis) > since these are very distinct operations. > > - You seem to be picking your fields by choosing random generating > polynomials. The lattices of their integer rings may have very > different properties from fields that actually arise in practice > (composite fields etc.). I don't have a good alternative, but you may > invest some time in thinking about other kinds of fields and seeing if > the algorithms behave similarly on them. > > - I recall somebody telling me that the newest versions of pari are > using a customized GRH dependent bound. Apparently, they actually look > at the L-series of the field and analyze some zero-free region to > improve the Bach bound. If they are really doing that, and doing it > correctly, that would eliminate the objection brought forward in the > magma documentation (except that the results are still conditional on > GRH by default). --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
