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:

Status badges

Description (last modified by chapoton)

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

Change History (10)

comment:1 Changed 6 years ago by jlee

  • Branch set to u/jlee/speed_up_dimension_new_cusp_forms

comment:2 Changed 6 years ago by jlee

  • Authors set to Jonathan Lee
  • Commit set to 9fea76b93c304901090e2520e06fcadd5315b4ec
  • Milestone changed from sage-6.7 to sage-6.8

New commits:

​9fea76bImplemented Greg Martin's algorithm to compute dimensions of spaces of newforms

comment:3 Changed 6 years ago by git

  • Commit changed from 9fea76b93c304901090e2520e06fcadd5315b4ec to 9b47f7f294ca59b44fefccccec2c8afc256fc600

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

​9b47f7fAdded reference to algorithm; changed variable names; removed unnecessary import

comment:4 Changed 6 years ago by jlee

  • Status changed from new to needs_review

comment:5 Changed 6 years ago by jlee

  • Status changed from needs_review to needs_work

comment:6 Changed 4 years ago by chapoton

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

​cda9b13Merge branch 'u/jlee/speed_up_dimension_new_cusp_forms' in 8.0.b2

comment:7 Changed 4 years ago by chapoton

  • Milestone changed from sage-6.8 to sage-8.0

comment:8 Changed 4 years ago by chapoton

  • Description modified (diff)

comment:9 Changed 4 years ago by klui

  • 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 vbraun

  • Branch changed from public/18433 to cda9b136b4f545b1d64c7d23fe9d229ea91d66de
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.