Another speedup of hypergeometric trace formula

[kedlaya]

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

[chapoton]

needs review ?

---

New commits:

​db56b9d	Speed up hgm_coeffs using symmetry
​abf212a	Fix inline if
​3c99efe	Implement keyboard interrupt in hgm_coeffs

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​8a048d2

Consolidate terms in hgm_coeffs

[kedlaya]

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.

[chapoton]

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

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​7a6acb2

Fix deprecated inline ifs

[chapoton]

needs review now ?

[kedlaya]

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.

[chapoton]

ok, let it be

[vbraun]

Merge conflict

[kedlaya]

My fault, I should have merged #29778 into this branch. Rebase coming up...

[kedlaya]

New commits:

​8a41546	Speed up hgm_coeffs using symmetry
​2ca6e99	Fix inline if
​a7565d2	Implement keyboard interrupt in hgm_coeffs
​fcbb2be	Consolidate terms in hgm_coeffs
​058dc4d	Fix deprecated inline ifs
​ad2888b	Update doctest in hgm_coeffs, simplify final loop

[chapoton]

ok, green bot, and back to positive