Opened 4 years ago
Closed 3 years ago
#24300 closed defect (fixed)
Computation of modular form Hecke matrices is very inefficient
Reported by:  davidloeffler  Owned by:  

Priority:  major  Milestone:  sage8.2 
Component:  modular forms  Keywords:  
Cc:  Merged in:  
Authors:  David Loeffler  Reviewers:  Vincent Delecroix 
Report Upstream:  N/A  Work issues:  
Branch:  fe985bc (Commits, GitHub, GitLab)  Commit:  fe985bc15f32bc8d9e221219ae435d5b59e02046 
Dependencies:  Stopgaps: 
Description (last modified by )
In order to compute the matrix of T(p) on a modular forms space, we currently compute a qexpansion basis of the space (using modular symbols) up to high enough precision that T(p) can be read off from the qexpansions. If the space is at all large, then we will need huge numbers of qexpansion coefficients to do things this way: to compute T(p) on modular forms, this algorithm will trigger computation of T(r) on modular symbols for all primes r up to about p * (Sturm bound for the space), which is very, very slow. For instance, this computation takes a whole 21 seconds:
sage: C=CuspForms(105, 2) sage: time C.hecke_matrix(17) CPU times: user 21 s, sys: 327 ms, total: 21.3 s Wall time: 21.3 s [ 1/3 2/3 1/3 ...
If you run this with set_verbose(1)
, you see that along the way it computes Hecke matrices on C.ambient().modular_symbols(sign=1)
for all primes up to 457!
This is trivially fixable by being more intelligent about how we compute Hecke matrices. The following code computes T(2003) in only about half a second, and only needs modular symbol T(r) for r = 2003 and the primes r < Sturm bound:
sage: A = C.modular_symbols(sign=1) sage: time sage.modular.modform.cuspidal_submodule._convert_matrix_from_modsyms(A, A.hecke_matrix(2003))[0] CPU times: user 635 ms, sys: 16.5 ms, total: 652 ms Wall time: 632 ms [ 10/3 28 155/3 380/3 ...
Change History (18)
comment:1 Changed 4 years ago by
 Description modified (diff)
comment:2 Changed 4 years ago by
 Branch set to u/davidloeffler/speedup_hecke_matrix
comment:3 Changed 4 years ago by
 Commit set to 92dc71d18a66babd087d61e24257b2d4493a7d84
comment:4 Changed 4 years ago by
 Status changed from new to needs_review
comment:5 Changed 4 years ago by
 Commit changed from 92dc71d18a66babd087d61e24257b2d4493a7d84 to 595b315428bef777bacdcac224cfeb1b8e7acd94
Branch pushed to git repo; I updated commit sha1. New commits:
595b315  Trac 24300: fix deprecated ReST syntax

comment:6 Changed 4 years ago by
I just pushed a onebyte docstring formatting change, to keep the patchbot ReST syntax checker happy
comment:7 Changed 4 years ago by
 Commit changed from 595b315428bef777bacdcac224cfeb1b8e7acd94 to 8a18de4f85679a23d6fb6d864d88e5a9674e8a75
Branch pushed to git repo; I updated commit sha1. Last 10 new commits:
0d2ec9e  Merge branch 'u/chapoton/19169' in 8.1.b6

dc97ae9  Update upstream to 8.1.rc0

d893f92  Trac 19169: efficiency improvements, added cm_discriminant function

849c048  Fix tiny documentation glitches spotted by patchbot

08be2f4  Merge trac 19169 into 8.1.rc4

2441d5a  Trac 22780: hecke operators in level 1 use wrong basis

8bcd674  22780: handle 0dimensional spaces correctly

c68af72  Trac 22780: fix failing doctests in sage/modular/hecke

7c1b207  Merge trac 22780 into 8.1.rc4

8a18de4  Trac 24300: fix so it merges cleanly on top of #2330 and #22780

comment:8 Changed 4 years ago by
 Dependencies set to #2330, #19169, #22780
Unfortunately the branch I had previously uploaded had conflicts with other tickets that already have positive review. I've now handmerged those into the ticket branch.
comment:9 Changed 4 years ago by
 Branch changed from u/davidloeffler/speedup_hecke_matrix to u/davidloeffler/speedup_hecke_rebased
comment:10 Changed 4 years ago by
 Commit changed from 8a18de4f85679a23d6fb6d864d88e5a9674e8a75 to 9424b1f87ca8a72bc8988b20ffae60a222f20e0d
 Dependencies #2330, #19169, #22780 deleted
comment:11 Changed 4 years ago by
 Milestone changed from sage8.1 to sage8.2
comment:12 Changed 3 years ago by
For documentation and cross check purposes could you add
sage: ModularForms(17,4).hecke_matrix(2).charpoly() x^6  16*x^5 + 18*x^4 + 608*x^3  1371*x^2  4968*x + 7776
to the documentation of hecke_polynomial
?
comment:13 Changed 3 years ago by
and similarly in the cuspidal submodule?
comment:14 Changed 3 years ago by
 Commit changed from 9424b1f87ca8a72bc8988b20ffae60a222f20e0d to fe985bc15f32bc8d9e221219ae435d5b59e02046
Branch pushed to git repo; I updated commit sha1. New commits:
fe985bc  Trac 24300: extra doctests requested by reviewer

comment:15 Changed 3 years ago by
Et voilà.
comment:16 Changed 3 years ago by
 Reviewers set to Vincent Delecroix
 Status changed from needs_review to positive_review
comment:17 Changed 3 years ago by
Thanks for the review! Can you also mark #21546 as positive review, if you agree that this code fixes that bug as well?
comment:18 Changed 3 years ago by
 Branch changed from u/davidloeffler/speedup_hecke_rebased to fe985bc15f32bc8d9e221219ae435d5b59e02046
 Resolution set to fixed
 Status changed from positive_review to closed
I've uploaded a branch which fixes both this and #21546.
New commits:
Trac 24300: speed up computation of modular form Hecke matrices