ell_curve_isogeny initialization

[saraedum]

The import of sage/schemes/elliptic_curves/ell_curve_isogeny.py (which happens on every startup of sage) takes a relatively big amount of time

$ time ./sage -startuptime|grep ell_curve_isogeny:
          ell_curve_isogeny: 0.133 (ell_field)

real    0m0.994s
user    0m0.810s
sys     0m0.154s

Lazily computing the constants in this file helps a lot (see the attached patch):

$ time ./sage -startuptime|grep ell_curve_isogeny:
          ell_curve_isogeny: 0.001 (ell_field)

real    0m0.849s
user    0m0.672s
sys     0m0.164s

Apply:

1. attachment: trac_11683_ell_curve_isogeny_speedup_combined.patch
2. attachment: trac_11683_review.patch

to the sage repository.

CC: @sagetrac-fschulze

Component: elliptic curves

Keywords: startup, initialization, sd32, sd35

Author: Julian Rueth, John Cremona

Reviewer: Julian Rueth, Frithjof Schulze

Merged: sage-5.0.beta7

Issue created by migration from https://trac.sagemath.org/ticket/11683

[robertwb]

comment:1

Attachment: trac_11683_ell_curve_isogeny_speedup.patch.gz

I would like to see the initial comments placed in context, and perhaps a doctest for the actual computation of Psi5 (even if it takes 4s). In any case, you do need doctests.

[saraedum]

Changed upstream from Not yet reported upstream; Will do shortly. to none

[saraedum]

Author: Julian Rüth

[saraedum]

comment:2

Attachment: trac_11683_ell_curve_isogeny_speedup_docstrings.patch.gz

You're right. I turned the comments describing how to compute the precomputed things into docstrings. Unfortunately they don't seem to work anymore. The line

sage: Psi5 = sum([X**i * f.coefficient({x:i})(X,t) for i in range(3)]).monic()

fails with

AttributeError: 'sage.rings.polynomial.multi_polynomial_libsingular.MPolynomial_libsingular' object has no attribute 'monic'

Can this be fixed easily?

[saraedum]

Changed author from Julian Rüth to Julian Rueth

[williamstein]

comment:4

Complaint:

You completely deleted the following comment from the code:

3887	 	# Since these take some time to compute (480s for l=7, ?? for l=13) we 
3888	 	# precompute them.  Here is how they may be computed: 
...
[explanation of how precomputing can be done]

[williamstein]

comment:5

(and I think a comment about how big precomputations were done is the most important thing to keep.)

[williamstein]

comment:6

Wow, I completely missed the boat there. Never mind regarding my above comments. They are the same as Robert's.

[williamstein]

comment:7

The claimed code for pre-computing Psi does not work at all. Even changing the monic() part to do what is intended totally fails to give the claimed result. Some remarks:

1. This code was originally introduced by John Cremona and his undergrad student in Implement elliptic curve isogenies (continued) #6887, and given a positive review by Christian Wuthrich. At that point the comment about how to compute the polys should have been changed to a doctest. Oops.

2. One could not use the examples (if they worked) to compute more values of Psi, since they depend on the Fricke module table, which is only computed up to ell=13.

3. The definition and meaning of Psi should be documented. I spent maybe 30 minutes wondering and searching, and I still am not completely sure precisely what Psi even is...

So I suggest removing these broken examples from the second patch, then setting this patch as "needs review". I'll ping John Cremona and request that he add an appropriate doctest illustrating how to compute Psi, and documenting what it is. I'm betting this will be really trivial for him to do. (I'm surprised it wasn't for me, because I just did a lot with explicit isogenies for an REU this summer... but it wasn't.)

[williamstein]

comment:8

I pinged John Cremona, whose computer responded "I am away and will not have internet access until 31 August."

[williamstein]

Changed keywords from startup, initialization to startup, initialization, sd32

[JohnCremona]

comment:10

Sorry for the delay. I'll document this better and make sure that the current documentation and description of the precomputation fits the existing code -- there are some choice to be made. Meanwhile, here's a small amount of explanatory theory:

For l=2,3,5,7,13, the curve X_0(l) has genus zero, so its function field is pure transcendental. The Fricke Module, denoted t, is a generator of the function field such that t=0 and t=oo lie above j=oo; the normalization here is completely classical, and the situation is fully defined by giving j as a degree l+1 rational function in t, which is what the Fricke_module dict in the code does (though not for l=2 which is simpler and handled entirely separately).

Next one writes down a "universal elliptic curve with l-isogeny", say E_t, as a curve over Q(t) with j-invariant j (viewed as an element of Q(t)). This is not unique! I have used different choices in the past and this needs sorting out since the later formulas depend on the choice. A good choice is one such that E_t is defined and with good reduction at all t except t=0 and t=oo (which are irrelevant since those values correspond to j=oo); but one is forced to also have bad reduction at values of t above j=0 and j=1728 when l=1 (mod 3, resp. 4). Once the model for E_t is chosen, Psi is the monic factor of degree (l-1)/2 of the l-division polynomial of E_t which defined the isogeny, and which is used in the isogeny code.

I am writing this up -- there's an old preprint of me and Mark Watkins which never got finished, and now there's more delay since with my student Kimi I am extending all this to the cases where X_0(l) is hyperelliptic.

[JohnCremona]

comment:11

I am currently working on this and will upload a patch when done.

[JohnCremona]

comment:12

The new patch includes the first two. I have added doctests which show that the cached values are correctly computed. At the same time I simplified the generic kernels a lot by using a better model for the universal elliptic curve with l-isogeny (you should be able to see that a lot more is deleted than added in the patch).

I added substantial explanation in the docstrings. So I hope this will be acceptable! (I forgot to check rebuilding the docs, and will do that now to try to catch any ReST markup problems.)

[JohnCremona]

Changed author from Julian Rueth to Julian Rueth, John Cremona

[JohnCremona]

Replaces both previous patches; applies to 4.7.2.alpha2

[JohnCremona]

comment:13

Attachment: trac_11683_ell_curve_isogeny_speedup_combined.patch.gz

There were some markup problems, now fixed and the patch replaced.

[JohnCremona]

comment:14

I can now compute the generic kernels in negligible time for l=2,3,5,7 and only 18s for l=13 (compared to over 10 hours!). If people think it is worth it I will revise the patch accordingly. Then we can test 2,3,5,7 every time and l=13 with a # long time tag.

[saraedum]

Changed keywords from startup, initialization, sd32 to startup, initialization, sd32, sd35

[saraedum]

comment:15

Replying to @JohnCremona:

I can now compute the generic kernels in negligible time for l=2,3,5,7 and only 18s for l=13 (compared to over 10 hours!). If people think it is worth it I will revise the patch accordingly. Then we can test 2,3,5,7 every time and l=13 with a # long time tag.

Just a remark, it seems sage improved quite a bit on the underlying computation. It is quite a bit faster than 13 hours (that is what the docstring says) already:

sage: time a,b=Psi(13, use_stored=True),Psi(13, use_stored=False)
Time: CPU 178.47 s, Wall: 178.51 s
sage: a==b
True

[saraedum]

Reviewer: Julian Rueth, Frithjof Schulze

[saraedum]

comment:17

[the docstring said "10" hours of course]

We fixed a few typos. Looking at the changes to isogenies_prime_degree_genus_0() we're wondering if this actually adds any new functionality/fixes a problem? If so, shouldn't there be a doctest for it?

[saraedum]

fixes some typos

[saraedum]

comment:18

Attachment: trac_11683_review.patch.gz

[JohnCremona]

comment:19

Replying to @saraedum:

[the docstring said "10" hours of course]

We fixed a few typos. Looking at the changes to isogenies_prime_degree_genus_0() we're wondering if this actually adds any new functionality/fixes a problem? If so, shouldn't there be a doctest for it?

The algorithm has been slightly simplified in the following ways: it works with the Fricke polynomials which are ZZ[t] rather than the actual Fricke modules (which are rational functions with denominator t), thus avoiding the creation of rational functions. Secondly, it uses a different model for the universal elliptic curve defined over Q(t), which is integral over Z[t] and has good reduction at as many places as possible. This makes the generic kernel polynomials lie in Z[t][x] rather than Q(t)[x], and also makes them simpler.

The previous version was not incorrect at all, but this seemed to be the right time to replace the older models with new ones, since the code was being refactored anyway.

Thanks for fixing the typos; I have set the ticket back to "needs review".

[JohnCremona]

comment:20

Please re-review this patch so that it can go into 5.0!!!! The last review was positive apart from some trivial typos, but several months later it has not yet been merged just because it was reset to "needs review"

[JohnCremona]

comment:21

The patches apply fine to 5.0.beta5 and all the tests in elliptic_curves pass, so please will someone give this a positive review!!!!

[sagetrac-fschulze]

comment:22

Replying to @JohnCremona:

I have very little time right now, but will re-review the patch tomorrow evening.

[sagetrac-fschulze]

comment:23

The documentation for Psi is missing some of the information from your comment above: It states the places of bad reduction of E_t but doesn't mention that E_t is a 'universal elliptic curve with l-isogeny' and that the model was specifically chosen for it's reduction behaviour. Shouldn't this information also be in the docstring?

Everything else looks OK (with the doctests still running).

[JohnCremona]

comment:24

Replying to @sagetrac-fschulze:

The documentation for Psi is missing some of the information from your comment above: It states the places of bad reduction of E_t but doesn't mention that E_t is a 'universal elliptic curve with l-isogeny' and that the model was specifically chosen for it's reduction behaviour. Shouldn't this information also be in the docstring?

You may be right, but it's a docstring not a textbook or thesis...we are currently finishing similar (though more complicated) code for all the cases where X_0(l) is hyperelliptic, and also getting these genus 0 cases to apply in characteristics 2 and 3, so there will be a lot more to say then (at which point we'll move this code into a separate file too).

Everything else looks OK (with the doctests still running).

[sagetrac-fschulze]

comment:25

I think that the docstrings already are very long too.

Is there maybe a reference one could add? Julian and I tried to understand this patch and didn't found many references. The preprint you mentioned above only has 'Fricke, Not sure which book'. I believe adding such a reference would be a lot of help for other people in the future.

[JohnCremona]

comment:26

One reason the docstrings are long is that I was asked (e.g. on this ticket) to give an explanation. So please do not now ask me to shorten them. As for references, as I have already said, there is an old unpublished preprint by me and Mark Watkins, which has now been superceded (we now use better models), and there will be a PhD thesis by Kimi Tsukazaki, but he has not written it yet. I hope you are not suggesting that the code cannot be accepted into Sage until his thesis has been written and examined and passed? On the contrary, I was hoping that the code based on his thesis (which includes many more prime l as I have already said) would be accepted into Sage -- on its merits because it works -- before he submits the thesis.

I feel I am going round in circles here. This ticket was created because the old code was causing an unnecessary delay in Sage startup time, and the patch fixes that, and clarifies how the code works at the same time.

[sagetrac-fschulze]

comment:27

I didn't mean to suggest that the code can not be accepted. It obviously is an improvement and I just wanted to know if the documentation could be improved by adding a reference.

I will give the patch a positive review now. Further improvements to the documentation will probably happen when your more general code arrives.

[sagetrac-fschulze]

comment:28

Tested with sage-5.0.beta5. The patch applies fine and all doctests pass.

[JohnCremona]

comment:29

Replying to @sagetrac-fschulze:

I didn't mean to suggest that the code can not be accepted. It obviously is an improvement and I just wanted to know if the documentation could be improved by adding a reference.

I will give the patch a positive review now. Further improvements to the documentation will probably happen when your more general code arrives.

Thanks.

[jdemeyer]

Merged: sage-5.0.beta7