#4525: [with patch, needs review] LLL-reduction of elliptic curve bases (with
resulting speed enhancement to integral_points())
---------------------------+------------------------------------------------
Reporter: cremona | Owner: was
Type: enhancement | Status: new
Priority: major | Milestone: sage-3.2.1
Component: number theory | Keywords: elliptic curve
---------------------------+------------------------------------------------
The integral_points() function for elliptic curves can be speeded up if
the Mordell-Weil basis used is first LLL-reduced, since this increases the
minimal eigenvalue of the height-pairing matrix. The patch achieves this.
For example, before:
{{{
sage: E = EllipticCurve([0, 1, 1, -2, 42])
sage: E.gens()
[(-4 : 1 : 1), (-3 : 5 : 1), (-11/4 : 43/8 : 1), (-2 : 6 : 1)]
sage: time len(E.integral_points())
CPU times: user 42.67 s, sys: 0.48 s, total: 43.15 s
Wall time: 43.50 s
24
}}}
and after:
{{{
sage: E = EllipticCurve([0, 1, 1, -2, 42])
sage: E.gens()
[(-4 : 1 : 1), (-3 : 5 : 1), (-11/4 : 43/8 : 1), (-2 : 6 : 1)]
sage: time len(E.integral_points())
CPU times: user 8.18 s, sys: 0.12 s, total: 8.29 s
Wall time: 8.37 s
24
}}}
(i.e. speedup by a factor of 5) and for a rank 5 example I had a speedup
factor of 50.
I implemented the LLL-reduction via pari's lllgram function, in a separate
function lll_reduce() since it will be useful elsewhere. There is a case
for applying it whenever we compute generators (since, for example, mwrank
does not LLL-reduce its generators, because the mwrank code has no access
to a floating point LLL routine!) but I have not done that -- many doctest
would need changing as generators would change.
The doctests include a long one on a curve of rank 24, which adds 2m to
the -long doctest time. If that is too long it could be deleted.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/4525>
Sage <http://sagemath.org/>
Sage - Open Source Mathematical Software: Building the Car Instead of
Reinventing the Wheel
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
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-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
