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 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/ -~----------~----~----~----~------~----~------~--~---
