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:  sage6.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: 
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
Branch:  → u/davidloeffler/better_twists 

comment:2 Changed 7 years ago by
Commit:  → 480f9516ba7526b13ae34bd8b31dc224f1c62432 

Dependencies:  → 18478 
comment:3 Changed 7 years ago by
Status:  new → needs_review 

comment:4 Changed 7 years ago by
Dependencies:  18478 → #18478 

Status:  needs_review → needs_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 warnlong 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 warnlong 49.1 src/sage/modular/modform/element.py # 2 doctests failed 
comment:5 Changed 7 years ago by
Commit:  480f9516ba7526b13ae34bd8b31dc224f1c62432 → 91d4941180104d20e3633ff0002295725de56db9 

Branch pushed to git repo; I updated commit sha1. New commits:
91d4941  Trac 18663: fix doctest failure

comment:6 Changed 7 years ago by
Status:  needs_work → needs_review 

Sorry, that was sloppy of me! Here's a fix.
comment:7 Changed 7 years ago by
Status:  needs_review → needs_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
Branch:  u/davidloeffler/better_twists → u/davidloeffler/better_twists_2 

comment:9 Changed 7 years ago by
Commit:  91d4941180104d20e3633ff0002295725de56db9 → a99880cbde7ddefa6982e9c5b8ffb2565c5bc354 

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:
a99880c  Trac 18663: Speed up computation of twists of newforms

comment:10 Changed 7 years ago by
Authors:  → David Loeffler 

Status:  needs_work → needs_review 
comment:11 Changed 7 years ago by
Reviewers:  → Peter Bruin 

Status:  needs_review → positive_review 
This looks good to me now.
comment:12 Changed 7 years ago by
Branch:  u/davidloeffler/better_twists_2 → a99880cbde7ddefa6982e9c5b8ffb2565c5bc354 

Resolution:  → fixed 
Status:  positive_review → closed 
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:
Trac 18663: Speed up computation of twists of newforms