Opened 4 years ago

Closed 4 years ago

#24300 closed defect (fixed)

Computation of modular form Hecke matrices is very inefficient

Reported by: davidloeffler Owned by:
Priority: major Milestone: sage-8.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:

Status badges

Description (last modified by davidloeffler)

In order to compute the matrix of T(p) on a modular forms space, we currently compute a q-expansion basis of the space (using modular symbols) up to high enough precision that T(p) can be read off from the q-expansions. If the space is at all large, then we will need huge numbers of q-expansion 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 davidloeffler

  • Description modified (diff)

comment:2 Changed 4 years ago by davidloeffler

  • Branch set to u/davidloeffler/speedup_hecke_matrix

comment:3 Changed 4 years ago by davidloeffler

  • Commit set to 92dc71d18a66babd087d61e24257b2d4493a7d84

I've uploaded a branch which fixes both this and #21546.


New commits:

92dc71dTrac 24300: speed up computation of modular form Hecke matrices

comment:4 Changed 4 years ago by davidloeffler

  • Authors set to David Loeffler
  • Status changed from new to needs_review

comment:5 Changed 4 years ago by git

  • Commit changed from 92dc71d18a66babd087d61e24257b2d4493a7d84 to 595b315428bef777bacdcac224cfeb1b8e7acd94

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

595b315Trac 24300: fix deprecated ReST syntax

comment:6 Changed 4 years ago by davidloeffler

I just pushed a one-byte docstring formatting change, to keep the patchbot ReST syntax checker happy

comment:7 Changed 4 years ago by git

  • Commit changed from 595b315428bef777bacdcac224cfeb1b8e7acd94 to 8a18de4f85679a23d6fb6d864d88e5a9674e8a75

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

0d2ec9eMerge branch 'u/chapoton/19169' in 8.1.b6
dc97ae9Update upstream to 8.1.rc0
d893f92Trac 19169: efficiency improvements, added cm_discriminant function
849c048Fix tiny documentation glitches spotted by patchbot
08be2f4Merge trac 19169 into 8.1.rc4
2441d5aTrac 22780: hecke operators in level 1 use wrong basis
8bcd67422780: handle 0-dimensional spaces correctly
c68af72Trac 22780: fix failing doctests in sage/modular/hecke
7c1b207Merge trac 22780 into 8.1.rc4
8a18de4Trac 24300: fix so it merges cleanly on top of #2330 and #22780

comment:8 Changed 4 years ago by davidloeffler

  • Dependencies set to #2330, #19169, #22780

Unfortunately this conflicts with other tickets that already have positive reviews, so I've merged those into the ticket branch.

Version 0, edited 4 years ago by davidloeffler (next)

comment:9 Changed 4 years ago by davidloeffler

  • Branch changed from u/davidloeffler/speedup_hecke_matrix to u/davidloeffler/speedup_hecke_rebased

comment:10 Changed 4 years ago by davidloeffler

  • Commit changed from 8a18de4f85679a23d6fb6d864d88e5a9674e8a75 to 9424b1f87ca8a72bc8988b20ffae60a222f20e0d
  • Dependencies #2330, #19169, #22780 deleted

Despite my best efforts, my branch still wouldn't merge with 8.2.beta0 so here is yet another new branch. No change to the actual code, still needs review.


New commits:

099ae38Trac 24300: speed up computation of modular form Hecke matrices
9424b1fTrac 24300: fix deprecated ReST syntax

comment:11 Changed 4 years ago by davidloeffler

  • Milestone changed from sage-8.1 to sage-8.2

comment:12 Changed 4 years ago by vdelecroix

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?

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

comment:13 Changed 4 years ago by vdelecroix

and similarly in the cuspidal submodule?

comment:14 Changed 4 years ago by git

  • Commit changed from 9424b1f87ca8a72bc8988b20ffae60a222f20e0d to fe985bc15f32bc8d9e221219ae435d5b59e02046

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

fe985bcTrac 24300: extra doctests requested by reviewer

comment:15 Changed 4 years ago by davidloeffler

Et voilà.

comment:16 Changed 4 years ago by vdelecroix

  • Reviewers set to Vincent Delecroix
  • Status changed from needs_review to positive_review

comment:17 Changed 4 years ago by davidloeffler

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 4 years ago by vbraun

  • Branch changed from u/davidloeffler/speedup_hecke_rebased to fe985bc15f32bc8d9e221219ae435d5b59e02046
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.