Opened 6 years ago

Closed 6 years ago

#21776 closed defect (fixed)

Galois representations over number fields speedup

Reported by: John Cremona Owned by:
Priority: major Milestone: sage-7.5
Component: elliptic curves Keywords: Galois representations
Cc: Merged in:
Authors: John Cremona Reviewers: Travis Scrimshaw, Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: 7ca67b0 (Commits, GitHub, GitLab) Commit: 7ca67b08b99e9a538633bc2df9a388755b6e74a4
Dependencies: Stopgaps:

Status badges

Description

The code for computing Galois representations of elliptic curves over number fields (which is used in isogeny computation) uses the default iterator over primes of degree 1 in the number field. Two problems: first, the method K.primes_of_degree_one_iter() only gives primes up to some norm bound, and that is not always large enough if left at the default. Second, where the function is used only principal primes are wanted but the iterator starts at 2 wheras there are no principal primes of norm less than discriminant/4!

I put in a custom iterator which helps a lot.

I will upload a patch when I have recovered an example which fails badly.

Change History (18)

comment:1 Changed 6 years ago by John Cremona

Branch: u/cremona/21776
Commit: aa7c95398fb2bb476a29c484f40a66ddf8dbf6c1
Status: newneeds_review

New commits:

aa7c953#21776: speed up elliptic curve galois reps & isogenies

comment:2 Changed 6 years ago by Travis Scrimshaw

Two small things:

-    for l in D:
+    for l in D.iterkeys():

This change is unnecessary as the iteration over a dictionary is the keys (and iterkeys is going away in Python3). Also, xrange is going away in Python3, so you should revert that change because the from six.moves import range already makes range an iterator, not a list.

comment:3 Changed 6 years ago by John Cremona

Thanks, will do. I have no idea why I put in the iterkeys().

comment:4 Changed 6 years ago by git

Commit: aa7c95398fb2bb476a29c484f40a66ddf8dbf6c141c708dfd8b4246c4412fbb6fa0686101604f2d2

Branch pushed to git repo; I updated commit sha1. New commits:

41c708d#21776: minor changes after first review

comment:5 Changed 6 years ago by Frédéric Chapoton

You should add documentation to the new "deg_one_prime_iter" function.

comment:6 Changed 6 years ago by John Cremona

Status: needs_reviewneeds_work

OK, I am working on this.

comment:7 Changed 6 years ago by git

Commit: 41c708dfd8b4246c4412fbb6fa0686101604f2d2f203c24d616692ae8b2d63a3b29c4450baee1c0e

Branch pushed to git repo; I updated commit sha1. New commits:

fa2596c#21776: add docstring to new function
f203c24#21776: add doctest too

comment:8 Changed 6 years ago by John Cremona

Status: needs_workneeds_review

Docstring and test added.

comment:9 Changed 6 years ago by Travis Scrimshaw

Branch: u/cremona/21776u/tscrim/21776
Commit: f203c24d616692ae8b2d63a3b29c4450baee1c0e39d9afb0bf538473e9c8d2a2e84603a6c41111d5
Reviewers: Travis Scrimshaw, Frédéric Chapoton

Looking at the primes documentation, it says you can pass oo as the second argument. So I removed the maxnorm argument. I also did a few cosmetic changes. If you agree with my changes, then you can set a positive review.


New commits:

cfd653aMerge branch 'u/cremona/21776' of git://trac.sagemath.org/sage into u/tscrim/21776
39d9afbRemoving the maxnorm and some cosmetics.

comment:10 Changed 6 years ago by Frédéric Chapoton

it.next() is not python3 compatible, use next(it) instead

comment:11 Changed 6 years ago by git

Commit: 39d9afb0bf538473e9c8d2a2e84603a6c41111d50881746045b963657e6aac2a9aeb0c50aec2656b

Branch pushed to git repo; I updated commit sha1. New commits:

0881746Fixing it.next() to next(it).

comment:12 in reply to:  10 Changed 6 years ago by John Cremona

Replying to chapoton:

it.next() is not python3 compatible, use next(it) instead

I did not know that -- and in fact one thing I had done was to make the reverse change, thinking it was somehow more efficient. Thanks.

I am happy with the changes since my commits. What next?

comment:13 Changed 6 years ago by Frédéric Chapoton

doc does not build, EXAMPLES: should be EXAMPLES::

comment:14 Changed 6 years ago by John Cremona

OK, I'll fix that and put it back into my branch... (building docs takes such a long time it discourages proper testing!)

comment:15 Changed 6 years ago by git

Commit: 0881746045b963657e6aac2a9aeb0c50aec2656b7ca67b08b99e9a538633bc2df9a388755b6e74a4

Branch pushed to git repo; I updated commit sha1. New commits:

7ca67b0Add the forgotten colon.

comment:16 Changed 6 years ago by Travis Scrimshaw

I just took care of it. (Partial doc builds can help for this kind of testing.) Feel free to put your branch if you make other changes.

comment:17 Changed 6 years ago by Frédéric Chapoton

Status: needs_reviewpositive_review

ok, looks good enough.

comment:18 Changed 6 years ago by Volker Braun

Branch: u/tscrim/217767ca67b08b99e9a538633bc2df9a388755b6e74a4
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.