Speed up NumberField_generic.zeta() and DirichletGroup()

[elarson314]

The runtime of the Newforms function is unacceptable for large conductors. To fix this, we speed up both the DirichletGroup constructor and the zeta(n) method of number fields by avoiding the computation of the group of all roots of unity or its order.

For a benchmark --- This reduces the runtime of Newforms(719, names='a') to 3--4 sec... from its previous value of over a day (interrupted before completion)!

Depends on #15898
Depends on #15767

Component: modular forms

Keywords: roots of unity dirichlet group

Author: Peter Bruin

Branch/Commit: 0bbfc15

Reviewer: Frédéric Chapoton

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

[elarson314]

comment:1

Attachment: trac_15486_lazy_R_character.patch.gz

[fchapoton]

comment:3

Here is a git branch

---

New commits:

dc4df25

Rewrote the __R_character variable of the ModularFormsAmbient_R function in modular/modform/ambient_R.py with lazy evaluation.

[fchapoton]

Commit: dc4df25

[fchapoton]

Author: Eric Larson

[fchapoton]

Branch: public/15486

[pjbruin]

comment:4

I remember running into this slowness issue as well; most of the time was spent in PARI on something like a class group and unit group computation for the coefficient fields. It's nice that this computation does not always have to be done.

[pjbruin]

Reviewer: Peter Bruin

[vbraun]

comment:5

sage -t --long src/sage/modular/modform/ambient_eps.py
**********************************************************************
File "src/sage/modular/modform/ambient_eps.py", line 187, in sage.modular.modform.ambient_eps.ModularFormsAmbient_eps.change_ring
Failed example:
    m.change_ring(QQ)
Expected:
    Traceback (most recent call last):
    ...
    ValueError: cannot coerce element of order 6 into self
Got:
    Modular Forms space of dimension 3, character [zeta6] and weight 2 over Rational Field

[pjbruin]

comment:6

Hmm, I did create a local branch to doctest this ticket, but it seems I was so convinced that this couldn't break anything that I didn't even check the branch out from Trac. The failing doctest shows that the current patch removes the check for whether there are enough roots of unity.

My comment above was not completely accurate; it was actually PARI's nfinit() that was taking forever. This is called when constructing the Dirichlet group modulo N with values in the group of roots of unity of a number field K. It turns out that by being a bit more careful about which roots of unity one asks for, one can avoid nfinit() and just look for roots of cyclotomic polynomials of degree dividing the degree of K.

I made a new patch for this approach, which is now doctesting. If successful, we can see if it would be a suitable alternative fix.

[pjbruin]

comment:7

The new branch makes both the DirichletGroup constructor and the zeta(n) method of number fields more intelligent by avoiding the computation of the group of all roots of unity or its order. Would this be a suitable alternative solution? It is unfortunately completely disjoint from Eric's original solution, but I do not see how that approach can easily detect invalid base rings as in the above doctest failure.

[pjbruin]

Changed branch from public/15486 to u/pbruin/15486-roots_of_unity

[pjbruin]

Dependencies: #15898

[pjbruin]

Changed commit from dc4df25 to f849274

[pjbruin]

Changed keywords from none to roots of unity dirichlet group

[pjbruin]

Changed author from Eric Larson to Peter Bruin

[pjbruin]

Changed reviewer from Peter Bruin to none

[pjbruin]

comment:10

The patchbot found one doctest failure, which is however completely unrelated to this ticket and is caused by the fact that the patchbot tests this ticket in a temporary directory.

[sagetrac-git]

Changed commit from f849274 to 608c103

[sagetrac-git]

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

37fc8e8	Upgrade to PARI-2.7.1
5db54b6	Trac 15767: reviewer patch
1d103da	Trac 15767: fix doctest in Ser()
62ca821	Trac 15767: explain application of Sturm's theorem
bf435f8	Merge tag '6.4.beta1' into ticket/15767
608c103	Merge branch 'ticket/15767-pari-2.7.1' into ticket/15486-roots_of_unity

[pjbruin]

Changed dependencies from #15898 to #15898, #15767

[sagetrac-git]

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

6b4dee6	Merge branch 'develop' into ticket/15486-roots_of_unity
0bbfc15	Merge branch 'develop' into ticket/15486-roots_of_unity

[sagetrac-git]

Changed commit from 608c103 to 0bbfc15

[fchapoton]

comment:16

As far as I can tell, this looks good. Disclaimer: I am not a number theorist.
All tests pass, the patchbot is happy, the NewForms test takes 3s.
I was worrying about some eventual regressions in timings.
But I have not been able to find any.
Let me put this in positive review.

[fchapoton]

Reviewer: Frédéric Chapoton

[vbraun]

Changed branch from u/pbruin/15486-roots_of_unity to 0bbfc15