Opened 8 years ago

Closed 7 years ago

#11683 closed enhancement (fixed)

ell_curve_isogeny initialization

Reported by: saraedum Owned by: cremona
Priority: minor Milestone: sage-5.0
Component: elliptic curves Keywords: startup, initialization, sd32, sd35
Cc: fschulze Merged in: sage-5.0.beta7
Authors: Julian Rueth, John Cremona Reviewers: Julian Rueth, Frithjof Schulze
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by fschulze)

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. trac_11683_ell_curve_isogeny_speedup_combined.patch
  2. trac_11683_review.patch

to the sage repository.

Attachments (4)

trac_11683_ell_curve_isogeny_speedup.patch (17.4 KB) - added by saraedum 8 years ago.
trac_11683_ell_curve_isogeny_speedup_docstrings.patch (3.7 KB) - added by saraedum 8 years ago.
trac_11683_ell_curve_isogeny_speedup_combined.patch (20.1 KB) - added by cremona 7 years ago.
Replaces both previous patches; applies to 4.7.2.alpha2
trac_11683_review.patch (3.4 KB) - added by saraedum 7 years ago.
fixes some typos

Download all attachments as: .zip

Change History (34)

Changed 8 years ago by saraedum

comment:1 Changed 8 years ago by robertwb

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.

comment:2 Changed 8 years ago by saraedum

  • Authors set to Julian Rüth
  • Report Upstream changed from Not yet reported upstream; Will do shortly. to N/A

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?

comment:3 Changed 8 years ago by saraedum

  • Authors changed from Julian Rüth to Julian Rueth

comment:4 Changed 8 years ago by was

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]

comment:5 Changed 8 years ago by was

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

comment:6 Changed 8 years ago by was

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

comment:7 Changed 8 years ago by was

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 #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.
  1. 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.
  1. 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.)

comment:8 Changed 8 years ago by was

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

comment:9 Changed 8 years ago by was

  • Keywords sd32 added

comment:10 Changed 8 years ago by cremona

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.

comment:11 Changed 7 years ago by cremona

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

comment:12 Changed 7 years ago by cremona

  • Authors changed from Julian Rueth to Julian Rueth, John Cremona
  • Description modified (diff)
  • Status changed from new to needs_review

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.)

Changed 7 years ago by cremona

Replaces both previous patches; applies to 4.7.2.alpha2

comment:13 Changed 7 years ago by cremona

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

comment:14 follow-up: Changed 7 years ago by cremona

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.

comment:15 in reply to: ↑ 14 Changed 7 years ago by saraedum

  • Keywords sd35 added

Replying to cremona:

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

comment:16 Changed 7 years ago by saraedum

  • Reviewers set to Julian Rueth, Frithjof Schulze

comment:17 follow-up: Changed 7 years ago by saraedum

  • Cc fschulze added
  • Status changed from needs_review to needs_info

[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?

Changed 7 years ago by saraedum

fixes some typos

comment:18 Changed 7 years ago by saraedum

  • Description modified (diff)

comment:19 in reply to: ↑ 17 Changed 7 years ago by cremona

  • Status changed from needs_info to needs_review

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".

comment:20 Changed 7 years ago by cremona

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"

comment:21 follow-up: Changed 7 years ago by cremona

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!!!!

comment:22 in reply to: ↑ 21 Changed 7 years ago by fschulze

Replying to cremona:

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

comment:23 follow-up: Changed 7 years ago by fschulze

  • Status changed from needs_review to needs_info

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).

comment:24 in reply to: ↑ 23 Changed 7 years ago by cremona

Replying to 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).

comment:25 Changed 7 years ago by fschulze

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.

comment:26 Changed 7 years ago by cremona

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.

comment:27 follow-up: Changed 7 years ago by fschulze

  • Status changed from needs_info to needs_review

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.

comment:28 Changed 7 years ago by fschulze

  • Description modified (diff)
  • Status changed from needs_review to positive_review

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

comment:29 in reply to: ↑ 27 Changed 7 years ago by cremona

Replying to 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.

comment:30 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.0.beta7
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.