Opened 6 years ago
Closed 5 years ago
#21546 closed defect (fixed)
Hecke polynomial of a cusp form space is needlessly slow
Reported by:  kedlaya  Owned by:  

Priority:  major  Milestone:  sage7.4 
Component:  modular forms  Keywords:  cusp forms, Hecke polynomials 
Cc:  Merged in:  
Authors:  David Loeffler  Reviewers:  Vincent Delecroix 
Report Upstream:  N/A  Work issues:  
Branch:  51d0cc8 (Commits, GitHub, GitLab)  Commit:  51d0cc8835b8f6d3b259662fd88d22ad97fd8659 
Dependencies:  #24300  Stopgaps: 
Description
Reported by bober on sagent, see https://groups.google.com/forum/#!topic/sagent/AbtJF3Z5_fM.
sage: S = CuspForms(1728, 2) sage: %time f = S.hecke_polynomial(2) CPU times: user 17276.68 s, sys: 13.46 s, total: 17290.14 s Wall time: 17293.59 s sage: f x^253 + x^251  2*x^249
Meanwhile, in a separate Sage session...
sage: %time M = ModularSymbols(1728, 2, 1) CPU times: user 0.47 s, sys: 0.03 s, total: 0.50 s Wall time: 0.54 s sage: %time S = M.cuspidal_subspace() CPU times: user 1.57 s, sys: 0.00 s, total: 1.57 s Wall time: 1.54 s sage: %time f = S.hecke_polynomial(2) CPU times: user 19.09 s, sys: 0.00 s, total: 19.09 s Wall time: 19.07 s sage: f x^253 + x^251  2*x^249
Change History (10)
comment:1 Changed 5 years ago by
Status:  new → needs_review 

comment:2 Changed 5 years ago by
Authors:  → David Loeffler 

comment:3 Changed 5 years ago by
Would be cool to have a doctest. That is a test that would take hours before but take reasonable amount after #24300.
comment:4 Changed 5 years ago by
Branch:  → u/davidloeffler/hecke_polynomial 

comment:5 Changed 5 years ago by
Commit:  → fe985bc15f32bc8d9e221219ae435d5b59e02046 

Dependencies:  → 24300 
Reviewers:  → Vincent Delecroix 
OK, I've put the example from the bug report as a doctest. The new code gets it down from 4.5 hours to 20 seconds, but it's still on the long side for a doctest so I've flagged it with # long time
.
New commits:
099ae38  Trac 24300: speed up computation of modular form Hecke matrices

9424b1f  Trac 24300: fix deprecated ReST syntax

fe985bc  Trac 24300: extra doctests requested by reviewer

comment:6 Changed 5 years ago by
Commit:  fe985bc15f32bc8d9e221219ae435d5b59e02046 → 51d0cc8835b8f6d3b259662fd88d22ad97fd8659 

Branch pushed to git repo; I updated commit sha1. New commits:
51d0cc8  Trac 21546: add doctest (to show that problem is fixed by #24300)

comment:8 Changed 5 years ago by
Dependencies:  24300 → #24300 

comment:9 Changed 5 years ago by
Status:  needs_review → positive_review 

comment:10 Changed 5 years ago by
Branch:  u/davidloeffler/hecke_polynomial → 51d0cc8835b8f6d3b259662fd88d22ad97fd8659 

Resolution:  → fixed 
Status:  positive_review → closed 
Note: See
TracTickets for help on using
tickets.
I fixed this at the same time as fixing #24300. Please review that ticket. Once it's reviewed and merged this can be closed.