Opened 10 years ago
Closed 9 years ago
#10709 closed enhancement (fixed)
speed up matrix actions on Manin symbols
Reported by: | AlexGhitza | Owned by: | craigcitro |
---|---|---|---|
Priority: | major | Milestone: | sage-4.7 |
Component: | modular forms | Keywords: | manin symbol binomial |
Cc: | davidloeffler | Merged in: | sage-4.7.alpha2 |
Authors: | William Stein, Alex Ghitza | Reviewers: | David Loeffler |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
The patch (basically written by William at #8614) speeds up these actions by changing the way the binomial coefficients are obtained.
Some timings (the weight seems to be the important parameter here):
BEFORE THE PATCH:
sage: from sage.modular.modsym.manin_symbols import ManinSymbolList_gamma0 sage: m = ManinSymbolList_gamma0(5, 8) sage: timeit("n = m.apply_T(4)") 625 loops, best of 3: 132 µs per loop sage: timeit("n = m.apply_TT(4)") 625 loops, best of 3: 26 µs per loop sage: m = ManinSymbolList_gamma0(5, 30) sage: timeit("n = m.apply_T(4)") 625 loops, best of 3: 541 µs per loop sage: timeit("n = m.apply_TT(4)") 625 loops, best of 3: 25.8 µs per loop sage: m = ManinSymbolList_gamma0(5, 100) sage: timeit("n = m.apply_T(4)") 125 loops, best of 3: 1.92 ms per loop sage: timeit("n = m.apply_TT(4)") 625 loops, best of 3: 25.8 µs per loop sage: eps = DirichletGroup(4).gen(0) sage: from sage.modular.modsym.manin_symbols import ManinSymbolList_character sage: m = ManinSymbolList_character(eps, 2) sage: timeit("n = m.apply_T(4)") 625 loops, best of 3: 141 µs per loop sage: timeit("n = m.apply_TT(4)") 625 loops, best of 3: 103 µs per loop sage: m = ManinSymbolList_character(eps, 30) sage: timeit("n = m.apply_T(4)") 125 loops, best of 3: 2.75 ms per loop sage: timeit("n = m.apply_TT(4)") 625 loops, best of 3: 105 µs per loop sage: m = ManinSymbolList_character(eps, 100) sage: timeit("n = m.apply_T(4)") 25 loops, best of 3: 9.35 ms per loop sage: timeit("n = m.apply_TT(4)") 625 loops, best of 3: 103 µs per loop
AFTER THE PATCH:
sage: from sage.modular.modsym.manin_symbols import ManinSymbolList_gamma0 sage: m = ManinSymbolList_gamma0(5, 8) sage: timeit("n = m.apply_T(4)") 625 loops, best of 3: 21.6 µs per loop sage: timeit("n = m.apply_TT(4)") 625 loops, best of 3: 13.8 µs per loop sage: m = ManinSymbolList_gamma0(5, 30) sage: timeit("n = m.apply_T(4)") 625 loops, best of 3: 74.4 µs per loop sage: timeit("n = m.apply_TT(4)") 625 loops, best of 3: 13.7 µs per loop sage: m = ManinSymbolList_gamma0(5, 100) sage: timeit("n = m.apply_T(4)") 625 loops, best of 3: 297 µs per loop sage: timeit("n = m.apply_TT(4)") 625 loops, best of 3: 13.8 µs per loop sage: eps = DirichletGroup(4).gen(0) sage: from sage.modular.modsym.manin_symbols import ManinSymbolList_character sage: m = ManinSymbolList_character(eps, 2) sage: timeit("n = m.apply_T(4)") 625 loops, best of 3: 126 µs per loop sage: timeit("n = m.apply_TT(4)") 625 loops, best of 3: 90.5 µs per loop sage: m = ManinSymbolList_character(eps, 30) sage: timeit("n = m.apply_T(4)") 125 loops, best of 3: 2.26 ms per loop sage: timeit("n = m.apply_TT(4)") 625 loops, best of 3: 91.3 µs per loop sage: m = ManinSymbolList_character(eps, 100) sage: timeit("n = m.apply_T(4)") 125 loops, best of 3: 7.7 ms per loop sage: timeit("n = m.apply_TT(4)") 625 loops, best of 3: 90.6 µs per loop
Attachments (1)
Change History (11)
comment:1 Changed 10 years ago by
- Cc davidloeffler added
- Status changed from new to needs_review
comment:2 follow-up: ↓ 4 Changed 10 years ago by
- Status changed from needs_review to needs_work
comment:3 Changed 10 years ago by
s/instead/as well/.
comment:4 in reply to: ↑ 2 Changed 10 years ago by
- Status changed from needs_work to needs_review
Replying to davidloeffler:
I don't like the following:
sage: a = ZZ(10); b = (2*a).binomial(a, algorithm="spam") sage: b is None TrueIt should probably raise an error if the algorithm is unrecognized, not just fall of the end of the function and return None.
Done.
Also, the "algorithm = mpir" option doesn't seem to allow the computation to be interrupted with Ctrl-C, so if you feed it a very large number by mistake you end up with no alternative but to kill your entire sage session. (The Pari implementation seems to handle interrupts better.)
Fixed.
Finally, I'd very much prefer it if the generic "binomial" function, called with an integer object, just called the binomial method of that object, and allowed the user to specify an algorithm there instead.
Done.
comment:5 follow-up: ↓ 6 Changed 10 years ago by
- Status changed from needs_review to needs_work
According to patchbot the new patch causes a doctest to fail in combinat (something to do with Catalan numbers).
Changed 10 years ago by
comment:6 in reply to: ↑ 5 Changed 10 years ago by
- Status changed from needs_work to needs_review
Replying to davidloeffler:
According to patchbot the new patch causes a doctest to fail in combinat (something to do with Catalan numbers).
Fixed and added a doctest to make sure I don't break it again.
comment:7 Changed 10 years ago by
- Reviewers set to David Loeffler
- Status changed from needs_review to positive_review
Looks fine now.
comment:8 Changed 10 years ago by
- Milestone changed from sage-4.7 to sage-4.6.2
comment:9 Changed 10 years ago by
- Milestone changed from sage-4.6.2 to sage-4.7
comment:10 Changed 9 years ago by
- Merged in set to sage-4.7.alpha2
- Resolution set to fixed
- Status changed from positive_review to closed
I don't like the following:
It should probably raise an error if the algorithm is unrecognized, not just fall of the end of the function and return None.
Also, the "algorithm = mpir" option doesn't seem to allow the computation to be interrupted with Ctrl-C, so if you feed it a very large number by mistake you end up with no alternative but to kill your entire sage session. (The Pari implementation seems to handle interrupts better.)
Finally, I'd very much prefer it if the generic "binomial" function, called with an integer object, just called the binomial method of that object, and allowed the user to specify an algorithm there instead.