#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:

Status badges

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 13 months ago by kedlaya

  • Branch set to u/kedlaya/speed_up_hgm_coeffs

comment:2 Changed 13 months ago by chapoton

  • Commit set to 3c99efe15890c7bd77ba5a8c7abb34ea007aef31

needs review ?


New commits:

db56b9dSpeed up hgm_coeffs using symmetry
abf212aFix inline if
3c99efeImplement keyboard interrupt in hgm_coeffs

comment:3 Changed 13 months ago by git

  • Commit changed from 3c99efe15890c7bd77ba5a8c7abb34ea007aef31 to 8a048d20bb331a5051e4e93c3335b7b2ac607812

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

8a048d2Consolidate terms in hgm_coeffs

comment:4 Changed 13 months ago by 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.

comment:5 Changed 13 months ago by kedlaya

  • Authors set to Kiran Kedlaya
  • Cc roed edgarcosta added

comment:6 Changed 13 months ago by 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

comment:7 Changed 13 months ago by git

  • Commit changed from 8a048d20bb331a5051e4e93c3335b7b2ac607812 to 7a6acb2ce1b397fa836851954a598efc547ec9be

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

7a6acb2Fix deprecated inline ifs

comment:8 Changed 13 months ago by chapoton

needs review now ?

comment:9 Changed 13 months ago by kedlaya

  • 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 13 months ago by chapoton

  • Reviewers set to Frédéric Chapoton
  • Status changed from needs_review to positive_review

ok, let it be

comment:11 Changed 13 months ago by vbraun

  • Status changed from positive_review to needs_work

Merge conflict

comment:12 Changed 13 months ago by kedlaya

  • 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 13 months ago by kedlaya

  • Branch set to u/kedlaya/speed_up_hgm_coeffs_v2

comment:14 Changed 13 months ago by kedlaya

  • Commit set to ad2888b6047c8180a787e16832770315bfa11728
  • Status changed from needs_work to needs_review

New commits:

8a41546Speed up hgm_coeffs using symmetry
2ca6e99Fix inline if
a7565d2Implement keyboard interrupt in hgm_coeffs
fcbb2beConsolidate terms in hgm_coeffs
058dc4dFix deprecated inline ifs
ad2888bUpdate doctest in hgm_coeffs, simplify final loop

comment:15 Changed 13 months ago by chapoton

  • Status changed from needs_review to positive_review

ok, green bot, and back to positive

comment:16 Changed 13 months ago by vbraun

  • Branch changed from u/kedlaya/speed_up_hgm_coeffs_v2 to ad2888b6047c8180a787e16832770315bfa11728
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.