Opened 11 years ago

Closed 10 years ago

Last modified 10 years ago

#8614 closed enhancement (fixed)

Optimize creation of modular symbols spaces by speeding up quotienting out by 2-term relations

Reported by: was Owned by: craigcitro
Priority: major Milestone: sage-4.7
Component: modular forms Keywords:
Cc: AlexGhitza Merged in: sage-4.7.alpha5
Authors: William Stein Reviewers: Alex Ghitza, David Loeffler, John Cremona
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by mraum)

  • The attached patch speeds up a creating ModularSymbols? spaces a bunch by removing a bottleneck -- quotienting by 2-term relations -- by moving it to Cython.
  • Also the coverage for the modular/modsym directory is improved to 100% by adding one trivial missing doctest.
  • Likewise, the coverage for the modular/modform directory is improved to 100% by adding another trivial doctest.

Depends on:

  1. #10709

Apply:

  1. trac-8614-optimize-modular-symbol-relations-rebase.patch

Attachments (2)

trac_8614.patch (15.9 KB) - added by was 11 years ago.
trac-8614-optimize-modular-symbol-relations-rebase.patch (8.7 KB) - added by mraum 10 years ago.

Download all attachments as: .zip

Change History (16)

comment:1 Changed 11 years ago by was

  • Description modified (diff)

Changed 11 years ago by was

comment:2 Changed 11 years ago by was

  • Status changed from new to needs_review

comment:3 Changed 11 years ago by davidloeffler

Which cases do you expect to be most speeded up by this patch? I ran some tests and it actually seems to make things marginally slower in the cases I tried:

Before:

sage: time ModularSymbols(2002, 2)
CPU times: user 1.52 s, sys: 0.41 s, total: 1.93 s
Wall time: 1.93 s
Modular Symbols space of dimension 673 for Gamma_0(2002) of weight 2 with sign 0 over Rational Field
sage: time ModularSymbols(302, 4)
CPU times: user 2.21 s, sys: 0.00 s, total: 2.21 s
Wall time: 2.21 s
Modular Symbols space of dimension 228 for Gamma_0(302) of weight 4 with sign 0 over Rational Field
sage: time ModularSymbols(Gamma1(33), 4)
CPU times: user 3.04 s, sys: 0.46 s, total: 3.49 s
Wall time: 3.49 s
Modular Symbols space of dimension 240 for Gamma_1(33) of weight 4 with sign 0 and over Rational Field
sage: time ModularSymbols(DirichletGroup(308).0, 5)
CPU times: user 5.94 s, sys: 0.65 s, total: 6.59 s
Wall time: 6.59 s
Modular Symbols space of dimension 384 and level 308, weight 5, character [-1, 1, 1], sign 0, over Rational Field

After:

sage: time ModularSymbols(2002, 2)
CPU times: user 1.52 s, sys: 0.67 s, total: 2.19 s
Wall time: 2.19 s
Modular Symbols space of dimension 673 for Gamma_0(2002) of weight 2 with sign 0 over Rational Field
sage: time ModularSymbols(302, 4)
CPU times: user 2.12 s, sys: 0.18 s, total: 2.30 s
Wall time: 2.30 s
Modular Symbols space of dimension 228 for Gamma_0(302) of weight 4 with sign 0 over Rational Field
sage: time ModularSymbols(Gamma1(33), 4)
CPU times: user 2.66 s, sys: 0.90 s, total: 3.57 s
Wall time: 3.57 s
Modular Symbols space of dimension 240 for Gamma_1(33) of weight 4 with sign 0 and over Rational Field
sage: time ModularSymbols(DirichletGroup(308).0, 5)
CPU times: user 5.97 s, sys: 0.71 s, total: 6.68 s
Wall time: 6.68 s
Modular Symbols space of dimension 384 and level 308, weight 5, character [-1, 1, 1], sign 0, over Rational Field

comment:4 Changed 11 years ago by AlexGhitza

  • Status changed from needs_review to needs_info

comment:5 Changed 10 years ago by AlexGhitza

  • Cc AlexGhitza added

comment:6 Changed 10 years ago by AlexGhitza

It appears to be significantly better for high weights:

On sage-4.6.1, before the patch:

sage: time M = ModularSymbols(1, 810, 0, GF(809))
CPU times: user 51.57 s, sys: 0.45 s, total: 52.02 s
Wall time: 52.03 s

After the patch:

sage: time M = ModularSymbols(1, 810, 0, GF(809))
CPU times: user 16.40 s, sys: 0.17 s, total: 16.57 s
Wall time: 16.58 s

This makes me *very* happy.

comment:7 follow-up: Changed 10 years ago by davidloeffler

According to the profiler, that difference seems to be coming almost entirely from the optimizations to binomial. The much larger chunk of new code in relation_matrix.pyx code only gets called when (among other conditions) the base ring is the rationals; and it doesn't seem to make much of an impact on the speed.

I suggest we split this into two tickets: one for the changes to binomial and the other miscellaneous fixes, which I would be happy to give a positive review to on the spot, and the other for the cythonization of the 2-term relations stuff, which seems a bit less clear-cut to me.

comment:8 in reply to: ↑ 7 Changed 10 years ago by AlexGhitza

  • Status changed from needs_info to needs_work

Replying to davidloeffler:

According to the profiler, that difference seems to be coming almost entirely from the optimizations to binomial. The much larger chunk of new code in relation_matrix.pyx code only gets called when (among other conditions) the base ring is the rationals; and it doesn't seem to make much of an impact on the speed.

I suggest we split this into two tickets: one for the changes to binomial and the other miscellaneous fixes, which I would be happy to give a positive review to on the spot, and the other for the cythonization of the 2-term relations stuff, which seems a bit less clear-cut to me.

I agree, and I had noticed the point about binomial myself. It's late (or really early) here, but I'll try to split off the easier bits tomorrow.

comment:9 Changed 10 years ago by AlexGhitza

OK, so I have split off the part not directly involved in the 2-term relations into two other tickets: #10709 for the binomial coefficients in the matrix actions on Manin symbols, and #10710 for the various docstring/doctest/comment fixes.

I will soon update the patch on this ticket by removing those parts.

comment:10 Changed 10 years ago by mraum

  • Description modified (diff)
  • Status changed from needs_work to needs_review

I rebased the patch to 4.7alpha2 (with #10709 applied). Its not true that the new code is slower. I ran the following small tests:

%time M = ModularSymbols(1000,2,sign=1).new_subspace().cuspidal_subspace()
%time t3 = M.hecke_matrix(3)
%time time d = t3.decomposition(algorithm='multimodular', height_guess=1)

%time ModularSymbols(2002, 2)
%time ModularSymbols(302, 4)
%time ModularSymbols(Gamma1(33), 4)
%time ModularSymbols(DirichletGroup(308).0, 5)
%time M = ModularSymbols(1, 810, 0, GF(809))

Without the patch:

Wall time: 2.92 s
Wall time: 0.19 s
Wall time: 0.09 s

Wall time: 1.34 s
Wall time: 4.08 s
Wall time: 2.20 s
Wall time: 10.97 s
Wall time: 16.23 s

With the patch applied:

Wall time: 2.77 s
Wall time: 0.13 s
Wall time: 0.09 s

Wall time: 1.22 s
Wall time: 4.38 s
Wall time: 2.10 s
Wall time: 11.12 s
Wall time: 15.33 s

None of the differences is significant in the sense that %timeit could reproduce it. A profile

%prun M = ModularSymbols(Gamma1(52), 4)

shows that indeed the new code is three times as fast as the old one. But since the relevant function only needs 0.1s and 0.03s, respectively, this can be hardly tracked.

Martin

comment:11 follow-up: Changed 10 years ago by cremona

The patch looks good to me (applied to 4.7.alpha2) and I am testing now, by testing whether ModularSymbols?(N) and CremonaModularSymbols?(N) have the same dimension for N up to 10^4. And some more.

comment:12 in reply to: ↑ 11 Changed 10 years ago by cremona

  • Authors set to William Stein
  • Reviewers set to Alex Ghitsa, David Loeffler, John Cremona
  • Status changed from needs_review to positive_review

Replying to cremona:

The patch looks good to me (applied to 4.7.alpha2) and I am testing now, by testing whether ModularSymbols?(N) and CremonaModularSymbols?(N) have the same dimension for N up to 10^4. And some more.

sage: time a=[CremonaModularSymbols(N).dimension() for N in [1000..2000]]
CPU times: user 31.12 s, sys: 0.52 s, total: 31.64 s
Wall time: 31.68 s
sage: time b=[ModularSymbols(N).dimension() for N in [1000..2000]]       
CPU times: user 636.90 s, sys: 0.14 s, total: 637.04 s
Wall time: 637.91 s
sage: a==b
True

This is enough to convince me that the implementation is ok. I tested the complete library too.

comment:13 Changed 10 years ago by jdemeyer

  • Merged in set to sage-4.7.alpha5
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:14 Changed 10 years ago by AlexGhitza

  • Reviewers changed from Alex Ghitsa, David Loeffler, John Cremona to Alex Ghitza, David Loeffler, John Cremona
Note: See TracTickets for help on using tickets.