#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: |
Description (last modified by )
- 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:
Apply:
Attachments (2)
Change History (16)
comment:1 Changed 11 years ago by
- Description modified (diff)
Changed 11 years ago by
comment:2 Changed 11 years ago by
- Status changed from new to needs_review
comment:3 Changed 11 years ago by
comment:4 Changed 11 years ago by
- Status changed from needs_review to needs_info
comment:5 Changed 10 years ago by
- Cc AlexGhitza added
comment:6 Changed 10 years ago by
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: ↓ 8 Changed 10 years ago by
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
- 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 inrelation_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
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.
Changed 10 years ago by
comment:10 Changed 10 years ago by
- 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: ↓ 12 Changed 10 years ago by
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
- 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
- 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
- Reviewers changed from Alex Ghitsa, David Loeffler, John Cremona to Alex Ghitza, David Loeffler, John Cremona
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:
After: