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: sage-7.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:

Status badges

Description

Reported by bober on sage-nt, see https://groups.google.com/forum/#!topic/sage-nt/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 davidloeffler

  • Status changed from new to needs_review

I fixed this at the same time as fixing #24300. Please review that ticket. Once it's reviewed and merged this can be closed.

comment:2 Changed 4 years ago by davidloeffler

  • Authors set to David Loeffler

comment:3 Changed 4 years ago by vdelecroix

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 davidloeffler

  • Branch set to u/davidloeffler/hecke_polynomial

comment:5 Changed 4 years ago by davidloeffler

  • 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:

099ae38Trac 24300: speed up computation of modular form Hecke matrices
9424b1fTrac 24300: fix deprecated ReST syntax
fe985bcTrac 24300: extra doctests requested by reviewer

comment:6 Changed 4 years ago by git

  • Commit changed from fe985bc15f32bc8d9e221219ae435d5b59e02046 to 51d0cc8835b8f6d3b259662fd88d22ad97fd8659

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

51d0cc8Trac 21546: add doctest (to show that problem is fixed by #24300)

comment:7 Changed 4 years ago by davidloeffler

Oops, forgot to commit before I pushed!

Last edited 4 years ago by davidloeffler (previous) (diff)

comment:8 Changed 4 years ago by davidloeffler

  • Dependencies changed from 24300 to #24300

comment:9 Changed 4 years ago by vdelecroix

  • Status changed from needs_review to positive_review

comment:10 Changed 4 years ago by vbraun

  • 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.