Opened 6 years ago
Closed 4 years ago
#18433 closed enhancement (fixed)
speed up dimension_new_cusp_forms
Reported by: | was | Owned by: | |
---|---|---|---|
Priority: | minor | Milestone: | sage-8.0 |
Component: | modular forms | Keywords: | |
Cc: | klui | Merged in: | |
Authors: | Jonathan Lee | Reviewers: | Kevin Lui |
Report Upstream: | N/A | Work issues: | |
Branch: | cda9b13 (Commits, GitHub, GitLab) | Commit: | cda9b136b4f545b1d64c7d23fe9d229ea91d66de |
Dependencies: | Stopgaps: |
Description (last modified by )
The code for computing this (and many similar things) in Sage-6.7 (and all previous versions):
Gamma0(11000).dimension_new_cusp_forms()
is just a "dumb" recurrence, which could be slow if the level is highly composite. I just noticed Greg Martin wrote a paper
and slides
that give a direct formula for computing the dimension of the new subspace for Gamma0(N). This may as well get coded up by somebody! And probably wouldn't be hard.
Before:
sage: G=Gamma0(factorial(12)) sage: %timeit dimension_new_cusp_forms(G) 1 loop, best of 3: 556 ms per loop
after:
sage: G=Gamma0(factorial(12)) sage: %timeit dimension_new_cusp_forms(G) The slowest run took 9.05 times longer than the fastest. This could mean that an intermediate result is being cached. 10000 loops, best of 3: 166 µs per loop
Change History (10)
comment:1 Changed 6 years ago by
- Branch set to u/jlee/speed_up_dimension_new_cusp_forms
comment:2 Changed 6 years ago by
- Commit set to 9fea76b93c304901090e2520e06fcadd5315b4ec
- Milestone changed from sage-6.7 to sage-6.8
comment:3 Changed 6 years ago by
- Commit changed from 9fea76b93c304901090e2520e06fcadd5315b4ec to 9b47f7f294ca59b44fefccccec2c8afc256fc600
Branch pushed to git repo; I updated commit sha1. New commits:
9b47f7f | Added reference to algorithm; changed variable names; removed unnecessary import
|
comment:4 Changed 6 years ago by
- Status changed from new to needs_review
comment:5 Changed 6 years ago by
- Status changed from needs_review to needs_work
comment:6 Changed 4 years ago by
- Branch changed from u/jlee/speed_up_dimension_new_cusp_forms to public/18433
- Cc klui added
- Commit changed from 9b47f7f294ca59b44fefccccec2c8afc256fc600 to cda9b136b4f545b1d64c7d23fe9d229ea91d66de
- Status changed from needs_work to needs_review
I checked the code by comparing to the article. It seems to be ok.
New commits:
cda9b13 | Merge branch 'u/jlee/speed_up_dimension_new_cusp_forms' in 8.0.b2
|
comment:7 Changed 4 years ago by
- Milestone changed from sage-6.8 to sage-8.0
comment:8 Changed 4 years ago by
- Description modified (diff)
comment:9 Changed 4 years ago by
- Reviewers set to Kevin Lui
- Status changed from needs_review to positive_review
I also checked it against the slides and they seem correct. Performance looks good as well.
old:
sage: G = Gamma0(prod(prime_range(20))) sage: %timeit G.dimension_new_cusp_forms() 10 loops, best of 3: 36.3 ms per loop sage: G = Gamma0(next_prime(10000)) sage: %timeit G.dimension_new_cusp_forms() 1000 loops, best of 3: 161 µs per loop sage: G = Gamma0(next_prime(1000000)) sage: %timeit G.dimension_new_cusp_forms() 10000 loops, best of 3: 163 µs per loop
new:
sage: G = Gamma0(prod(prime_range(20))) sage: %timeit G.dimension_new_cusp_forms() The slowest run took 4.19 times longer than the fastest. This could mean that an intermediate result is being cached. 10000 loops, best of 3: 89.8 µs per loop sage: G = Gamma0(next_prime(10000)) sage: %timeit G.dimension_new_cusp_forms() 10000 loops, best of 3: 60.4 µs per loop sage: G = Gamma0(next_prime(1000000)) sage: %timeit G.dimension_new_cusp_forms() The slowest run took 16.03 times longer than the fastest. This could mean that an intermediate result is being cached. 10000 loops, best of 3: 71 µs per loop
comment:10 Changed 4 years ago by
- Branch changed from public/18433 to cda9b136b4f545b1d64c7d23fe9d229ea91d66de
- Resolution set to fixed
- Status changed from positive_review to closed
New commits:
Implemented Greg Martin's algorithm to compute dimensions of spaces of newforms