Opened 5 years ago
Closed 4 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 4 years ago by
 Status changed from new to needs_review
comment:2 Changed 4 years ago by
comment:3 Changed 4 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 4 years ago by
 Branch set to u/davidloeffler/hecke_polynomial
comment:5 Changed 4 years ago by
 Commit set to fe985bc15f32bc8d9e221219ae435d5b59e02046
 Dependencies set to 24300
 Reviewers set to 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 4 years ago by
 Commit changed from fe985bc15f32bc8d9e221219ae435d5b59e02046 to 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:7 Changed 4 years ago by
Oops, forgot to commit before I pushed!
comment:8 Changed 4 years ago by
 Dependencies changed from 24300 to #24300
comment:9 Changed 4 years ago by
 Status changed from needs_review to positive_review
comment:10 Changed 4 years ago by
 Branch changed from u/davidloeffler/hecke_polynomial to 51d0cc8835b8f6d3b259662fd88d22ad97fd8659
 Resolution set to fixed
 Status changed from positive_review to 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.