Opened 4 years ago

Closed 4 years ago

# Computation of modular form Hecke matrices is very inefficient

Reported by: Owned by: davidloeffler major sage-8.2 modular forms David Loeffler Vincent Delecroix N/A fe985bc fe985bc15f32bc8d9e221219ae435d5b59e02046

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

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

 ​92dc71d `Trac 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:

 ​595b315 `Trac 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:

 ​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 0-dimensional 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 davidloeffler

• 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 hand-merged those into the ticket branch.

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

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

 ​099ae38 `Trac 24300: speed up computation of modular form Hecke matrices` ​9424b1f `Trac 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
```
Version 0, edited 4 years ago by vdelecroix (next)

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

 ​fe985bc `Trac 24300: extra doctests requested by reviewer`

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.