Opened 2 years ago
Closed 2 years ago
#29893 closed enhancement (fixed)
Another speedup of hypergeometric trace formula
Reported by:  kedlaya  Owned by:  

Priority:  major  Milestone:  sage9.2 
Component:  modular forms  Keywords:  hypergeometric trace formula 
Cc:  roed, edgarcosta  Merged in:  
Authors:  Kiran Kedlaya  Reviewers:  Frédéric Chapoton 
Report Upstream:  N/A  Work issues:  
Branch:  ad2888b (Commits, GitHub, GitLab)  Commit:  ad2888b6047c8180a787e16832770315bfa11728 
Dependencies:  Stopgaps: 
Description
It seems that in earlier tickets meant to speed up the computation of the hypergeometric trace formula (especially #28902), the optimization of using symmetry in the trace formula for p**f
when f>1
did not get applied fully. Here we address this.
The status quo:
sage: from sage.modular.hypergeometric_motive import HypergeometricData as Hyp sage: H = Hyp(cyclotomic=([4,2,2],[3,3])) sage: time H.padic_H_value(next_prime(4096), 2, 1337) CPU times: user 47.9 s, sys: 456 ms, total: 48.4 s Wall time: 48.4 s 5526
This is already beating Magma (v2.249):
> H := HypergeometricData([4,2,2],[3,3]); > time HypergeometricTrace(H, 1/1337, 4099^2); 5526 Time: 84.140
But there is still room for improvement. (Restart Sage to suppress cacheing.)
sage: from sage.modular.hypergeometric_motive import HypergeometricData as Hyp sage: H = Hyp(cyclotomic=([4,2,2],[3,3])) sage: time H.padic_H_value(next_prime(4096), 2, 1337) CPU times: user 32.9 s, sys: 1.1 s, total: 34 s Wall time: 34 s 5526
Change History (16)
comment:1 Changed 2 years ago by
 Branch set to u/kedlaya/speed_up_hgm_coeffs
comment:2 Changed 2 years ago by
 Commit set to 3c99efe15890c7bd77ba5a8c7abb34ea007aef31
comment:3 Changed 2 years ago by
 Commit changed from 3c99efe15890c7bd77ba5a8c7abb34ea007aef31 to 8a048d20bb331a5051e4e93c3335b7b2ac607812
Branch pushed to git repo; I updated commit sha1. New commits:
8a048d2  Consolidate terms in hgm_coeffs

comment:4 Changed 2 years ago by
I thought of another improvement: since we only implement parameter values in Q, I can consolidate from q1
to p1
terms in hgm_coeffs
. This speeds things up some more:
sage: from sage.modular.hypergeometric_motive import HypergeometricData as Hyp sage: H = Hyp(cyclotomic=([4,2,2],[3,3])) sage: time H.padic_H_value(next_prime(4096), 2, 1337) CPU times: user 24 s, sys: 255 ms, total: 24.3 s Wall time: 24.3 s 5526
As a bonus, cacheing this result takes much less memory.
Let me sleep on this a bit before putting this up for review, to see if I'm missing another easy trick.
comment:5 Changed 2 years ago by
 Cc roed edgarcosta added
comment:6 Changed 2 years ago by
patchbot complains about a little code style detail :
+src/sage/modular/hypergeometric_motive.py:1101:28: E701 multiple statements on one line (colon) +src/sage/modular/hypergeometric_motive.py:1229:30: E701 multiple statements on one line (colon)
so please break those two lines to make it happier
comment:7 Changed 2 years ago by
 Commit changed from 8a048d20bb331a5051e4e93c3335b7b2ac607812 to 7a6acb2ce1b397fa836851954a598efc547ec9be
Branch pushed to git repo; I updated commit sha1. New commits:
7a6acb2  Fix deprecated inline ifs

comment:8 Changed 2 years ago by
needs review now ?
comment:9 Changed 2 years ago by
 Status changed from new to needs_review
Let's go ahead and advance this to the review stage. Apparently there is some room for improvement on the side of computing the padic Gamma function, but that can be a separate ticket later.
comment:10 Changed 2 years ago by
 Reviewers set to Frédéric Chapoton
 Status changed from needs_review to positive_review
ok, let it be
comment:12 Changed 2 years ago by
 Branch u/kedlaya/speed_up_hgm_coeffs deleted
 Commit 7a6acb2ce1b397fa836851954a598efc547ec9be deleted
My fault, I should have merged #29778 into this branch. Rebase coming up...
comment:13 Changed 2 years ago by
 Branch set to u/kedlaya/speed_up_hgm_coeffs_v2
comment:14 Changed 2 years ago by
 Commit set to ad2888b6047c8180a787e16832770315bfa11728
 Status changed from needs_work to needs_review
comment:15 Changed 2 years ago by
 Status changed from needs_review to positive_review
ok, green bot, and back to positive
comment:16 Changed 2 years ago by
 Branch changed from u/kedlaya/speed_up_hgm_coeffs_v2 to ad2888b6047c8180a787e16832770315bfa11728
 Resolution set to fixed
 Status changed from positive_review to closed
needs review ?
New commits:
Speed up hgm_coeffs using symmetry
Fix inline if
Implement keyboard interrupt in hgm_coeffs