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: | sage-9.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.24-9):
> 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 q-1
to p-1
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 p-adic 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