Galois representations over number fields speedup

JohnCremona commented 7 years ago

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.

Component: elliptic curves

Keywords: Galois representations

Author: John Cremona

Branch/Commit: 7ca67b0

Reviewer: Travis Scrimshaw, Frédéric Chapoton

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

JohnCremona commented 7 years ago

Branch: u/cremona/21776

JohnCremona commented 7 years ago

Commit: aa7c953

JohnCremona commented 7 years ago

New commits:

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

tscrim commented 7 years ago

comment:2

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.

JohnCremona commented 7 years ago

comment:3

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

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

41c708d #21776: minor changes after first review

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from aa7c953 to 41c708d

fchapoton commented 7 years ago

comment:5

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

JohnCremona commented 7 years ago

comment:6

OK, I am working on this.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from 41c708d to f203c24

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

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

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

JohnCremona commented 7 years ago

comment:8

Docstring and test added.

tscrim commented 7 years ago

Changed branch from u/cremona/21776 to u/tscrim/21776

tscrim commented 7 years ago

Changed commit from f203c24 to 39d9afb

tscrim commented 7 years ago

comment:9

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:

`cfd653a`	`Merge branch 'u/cremona/21776' of git://trac.sagemath.org/sage into u/tscrim/21776`
`39d9afb`	`Removing the maxnorm and some cosmetics.`

tscrim commented 7 years ago

Reviewer: Travis Scrimshaw, Frédéric Chapoton

fchapoton commented 7 years ago

comment:10

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from 39d9afb to 0881746

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

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

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

JohnCremona commented 7 years ago

comment:12

Replying to @fchapoton:

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?

fchapoton commented 7 years ago

comment:13

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

JohnCremona commented 7 years ago

comment:14

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from 0881746 to 7ca67b0

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

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

7ca67b0 Add the forgotten colon.

tscrim commented 7 years ago

comment:16

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.

fchapoton commented 7 years ago

comment:17

ok, looks good enough.

vbraun commented 7 years ago

Changed branch from u/tscrim/21776 to 7ca67b0

sagemath / sage

Galois representations over number fields speedup #21776