speed up dimension_new_cusp_forms

[williamstein]

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

http://www.math.ubc.ca/~gerg/papers/downloads/DSCFN.pdf

and slides

http://www.math.ubc.ca/~gerg/slides/Vancouver-13Sep12.pdf

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

CC: @kevinywlui

Component: modular forms

Author: Jonathan Lee

Branch/Commit: cda9b13

Reviewer: Kevin Lui

Issue created by migration from https://trac.sagemath.org/ticket/18433

[sagetrac-jlee]

Branch: u/jlee/speed_up_dimension_new_cusp_forms

[sagetrac-jlee]

New commits:

9fea76b

Implemented Greg Martin's algorithm to compute dimensions of spaces of newforms

[sagetrac-jlee]

Author: Jonathan Lee

[sagetrac-jlee]

Commit: 9fea76b

[sagetrac-git]

Changed commit from 9fea76b to 9b47f7f

[sagetrac-git]

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

9b47f7f

Added reference to algorithm; changed variable names; removed unnecessary import

[fchapoton]

comment:6

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

[fchapoton]

Changed commit from 9b47f7f to cda9b13

[fchapoton]

Changed branch from u/jlee/speed_up_dimension_new_cusp_forms to public/18433

[kevinywlui]

Reviewer: Kevin Lui

[kevinywlui]

comment:9

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

[vbraun]

Changed branch from public/18433 to cda9b13