Opened 7 years ago

Closed 7 years ago

#18663 closed enhancement (fixed)

Speed up computation of twists of newforms

Reported by: David Loeffler Owned by:
Priority: major Milestone: sage-6.8
Component: modular forms Keywords:
Cc: Merged in:
Authors: David Loeffler Reviewers: Peter Bruin
Report Upstream: N/A Work issues:
Branch: a99880c (Commits, GitHub, GitLab) Commit: a99880cbde7ddefa6982e9c5b8ffb2565c5bc354
Dependencies: #18478 Stopgaps:

Status badges

Description

The current code for computing twists of newforms by Dirichlet characters is unnecessarily slow, because it computes a full decomposition of the target space into simple Hecke modules, and then throws all but one of the factors away. It is quicker just to directly pull out the appropriate factor using kernels of Hecke matrices.

Change History (12)

comment:1 Changed 7 years ago by David Loeffler

Branch: u/davidloeffler/better_twists

comment:2 Changed 7 years ago by David Loeffler

Commit: 480f9516ba7526b13ae34bd8b31dc224f1c62432
Dependencies: 18478

Here's a patch. I tested it doing sage: Newforms(11)[0].twist(DirichletGroup(5).0) and it went down from about 30 sec to about 3 sec on my machine. The doctest requires #18478 to pass.


New commits:

480f951Trac 18663: Speed up computation of twists of newforms

comment:3 Changed 7 years ago by David Loeffler

Status: newneeds_review

comment:4 Changed 7 years ago by Peter Bruin

Dependencies: 18478#18478
Status: needs_reviewneeds_work

I haven't looked at this in detail, but with both this ticket and #6018 applied, the example from comment:15:ticket:18086 only takes about a second. However, some long doctests fail even with #18478 merged:

sage -t --long --warn-long 49.1 src/sage/modular/modform/element.py
**********************************************************************
File "src/sage/modular/modform/element.py", line 1188, in sage.modular.modform.element.Newform.twist
Failed example:
    Delta.twist(chi, level=3)  # long time
Expected:
    Traceback (most recent call last):
    ...
    RuntimeError: twist of q - 24*q^2 + 252*q^3 - 1472*q^4 + 4830*q^5 + O(q^6) by Dirichlet character modulo 1 of conductor 1 is not a newform in Cuspidal subspace of dimension 3 of Modular Forms space of dimension 5 for Congruence Subgroup Gamma0(3) of weight 12 over Cyclotomic Field of order 1 and degree 1
Got:
    ...
         raise RuntimeError('twist of %s by %s is not a newform in %s' % (self, chi, S))
    UnboundLocalError: local variable 'S' referenced before assignment
**********************************************************************
File "src/sage/modular/modform/element.py", line 1192, in sage.modular.modform.element.Newform.twist
Failed example:
    Delta.twist(chi, level=3, check=False)  # long time
Exception raised:
    ...
         raise RuntimeError('twist of %s by %s is not a newform in %s' % (self, chi, S))
    UnboundLocalError: local variable 'S' referenced before assignment
**********************************************************************
1 item had failures:
   2 of  17 in sage.modular.modform.element.Newform.twist
    [305 tests, 2 failures, 45.85 s]
----------------------------------------------------------------------
sage -t --long --warn-long 49.1 src/sage/modular/modform/element.py  # 2 doctests failed
----------------------------------------------------------------------

comment:5 Changed 7 years ago by git

Commit: 480f9516ba7526b13ae34bd8b31dc224f1c6243291d4941180104d20e3633ff0002295725de56db9

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

91d4941Trac 18663: fix doctest failure

comment:6 Changed 7 years ago by David Loeffler

Status: needs_workneeds_review

Sorry, that was sloppy of me! Here's a fix.

comment:7 Changed 7 years ago by Peter Bruin

Status: needs_reviewneeds_work

One of the doctests still fails, this time because the effect of setting check=False is changed:

File "src/sage/modular/modform/element.py", line 1192, in sage.modular.modform.element.Newform.twist
Failed example:
    Delta.twist(chi, level=3, check=False)  # long time
Exception raised:
    ...
    RuntimeError: twist of q - 24*q^2 + 252*q^3 - 1472*q^4 + 4830*q^5 + O(q^6) by Dirichlet character modulo 1 of conductor 1 is not a newform in Cuspidal subspace of dimension 3 of Modular Forms space of dimension 5 for Congruence Subgroup Gamma0(3) of weight 12 over Cyclotomic Field of order 1 and degree 1

We should either just remove this doctest, or find a new example to document that check=False can lead to wrong results.

comment:8 Changed 7 years ago by David Loeffler

Branch: u/davidloeffler/better_twistsu/davidloeffler/better_twists_2

comment:9 Changed 7 years ago by David Loeffler

Commit: 91d4941180104d20e3633ff0002295725de56db9a99880cbde7ddefa6982e9c5b8ffb2565c5bc354

Here's a new version. I've made a subtle change which ensures that the code cannot return bogus results (even if check=False); it now either returns a correct answer, or fails with a ValueError if the form is not new at the specified level. The change is that the code starts by taking the new subspace of the modular symbols (which is pretty cheap to compute) and only then starts filtering down to kernels of Hecke operators.

I've also changed the error messages a bit so it returns a different error if the computed mod sym space is 0 than if it's too large (the latter could, theoretically, happen in valid examples if the level was gigantic, whereas the former can only occur if the input is bogus so it makes sense to return ValueError).


New commits:

a99880cTrac 18663: Speed up computation of twists of newforms

comment:10 Changed 7 years ago by David Loeffler

Authors: David Loeffler
Status: needs_workneeds_review

comment:11 Changed 7 years ago by Peter Bruin

Reviewers: Peter Bruin
Status: needs_reviewpositive_review

This looks good to me now.

comment:12 Changed 7 years ago by Volker Braun

Branch: u/davidloeffler/better_twists_2a99880cbde7ddefa6982e9c5b8ffb2565c5bc354
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.