I noticed something in the code i wrote which can be improved. This is something which was not in Chris Wuthrich's original implementation, so it is my fault.
Here's what we do: (1) find an upper bound on the torsion order, i.e. a positive integer N such that the torsion order is certainly a divisor of N. This uses the function _torsion_bound() in ell_number_field.py. (2) For each prime dividing N, find a basis for the p-primary torsion. This is done in _p_primary_torsion_basis() in ell_generic.py. (3) Put together the primary parts. Here's the inefficiency. In step (2) I ignore the bound we have on the exponent of each prime. This wastes time in computing the p-primary torsion basis. So I will change the function _p_primary_torsion_basis() to take an optional parameter which is a bound on the exponent of the order (not the exponent of the p-primary subgroup). e.g. in Jim's example, the bound is 49 and teh actual torion is C7xC7. But when we compute the 7-primary torsion, after finding that the 7-torsion is complete and of order 49, we do not stop, but test 8 points in the 7-torsion subgroup to see if they can be divided further by 7. that last part is obiously a waste of time since we have already reached the bound. I have a bad feeling that I first thought of this within an hour of the relevant patches at trac #3377 being merged, but never got around to doing anything about it. I will do so now. John 2009/5/7 Jim Stankewicz <[email protected]>: > Dear Dr. Cremona, > > On Thu, May 7, 2009 at 11:22 AM, John Cremona <[email protected]> wrote: >> [Note to other sage-devel readers: Jim initially emailed me about >> this, being a case where (apparently) Sage was very much faster than >> Magma, though I could not reproduce the large difference. I suggested >> to him that if he had comments about Sage then he should email >> sage-devel rather than the individual whose name appears in the source >> code for the function in question.] >> >> 2009/5/7 Jim Stankewicz <[email protected]>: >>> Dear Dr. Cremona, >>> >>> After the last message I wanted to test if it was MAGMA 2.14-15(the >>> current version on UGA's server) or the computer. I installed sage via >>> vmware on my severely underpowered winxp eee laptop and even then it >>> took 78 seconds. >> >> Do you mean that the Sage function took 78 seconds? > > Yes, the sage function torsion_subgroup() took 78 seconds on an intel > atom powered eee laptop. In a reasonably powered computer it takes > 10-12 seconds. > >> This is perhaps more of a magma bugshooting >>> conversation at this point >> >> I think it is, in which case you should be addressing your comments to >> magma-bugs (though being slow is not a bug, and if there used to be a >> bug but it has been fixed in the latest release then they will not be >> interested.). >> > > I know, I just included the information I had for completeness. > > Best, > Jim > --~--~---------~--~----~------------~-------~--~----~ 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://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
