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:  sage8.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 Sage6.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 sage6.7 to sage6.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 sage6.8 to sage8.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