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)

trac_10709.patch (5.4 KB) - added by AlexGhitza 10 years ago.

Download all attachments as: .zip

Change History (11)

comment:1 Changed 10 years ago by AlexGhitza

  • Cc davidloeffler added
  • Status changed from new to needs_review

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

  • Status changed from needs_review to needs_work

I don't like the following:

sage: a = ZZ(10); b = (2*a).binomial(a, algorithm="spam")
sage: b is None
True

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.

comment:3 Changed 10 years ago by davidloeffler

s/instead/as well/.

comment:4 in reply to: ↑ 2 Changed 10 years ago by AlexGhitza

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

It 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: Changed 10 years ago by davidloeffler

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

comment:6 in reply to: ↑ 5 Changed 10 years ago by AlexGhitza

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

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

Looks fine now.

comment:8 Changed 10 years ago by AlexGhitza

  • Milestone changed from sage-4.7 to sage-4.6.2

comment:9 Changed 10 years ago by jdemeyer

  • Milestone changed from sage-4.6.2 to sage-4.7

comment:10 Changed 9 years ago by jdemeyer

  • Merged in set to sage-4.7.alpha2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.