Opened 4 years ago
Closed 3 years ago
#24433 closed enhancement (fixed)
Speed up padic Gamma by caching Dwork expansion coefficients
Reported by:  kedlaya  Owned by:  

Priority:  major  Milestone:  sage8.2 
Component:  padics  Keywords:  padic Gamma function 
Cc:  roed  Merged in:  
Authors:  Kiran Kedlaya  Reviewers:  Frédéric Chapoton 
Report Upstream:  N/A  Work issues:  
Branch:  a05daab (Commits, GitHub, GitLab)  Commit:  a05daab31cc9f100d86c448c52321d51b964104b 
Dependencies:  Stopgaps: 
Description
The computation of the padic Gamma function in both Pari and Sage uses a Mahler expansion in terms of the Dwork exponential series. The optional algorithm
flag defaults to pari
instead of sage
because the implementation there has been optimized better.
However, in use cases where one needs to repeatedly evaluate Gamma for the same prime p
, such as for the trace formula for hypergeometric motives (see #23952), it is better to cache the coefficients of the Dwork exponential rather than recomputing them. Sample output:
sage: p = next_prime(5000) sage: F = Qp(p) sage: time l1 = [F(a/(p1)).gamma(algorithm='pari') for a in range(p1)] CPU times: user 6min 17s, sys: 23.2 ms, total: 6min 17s Wall time: 6min 17s sage: time l2 = [F(a/(p1)).gamma(algorithm='sage') for a in range(p1)] CPU times: user 21.3 s, sys: 36 ms, total: 21.3 s Wall time: 21.3 s sage: all(l1[i] == l2[i] for i in range(p1)) True
Change History (12)
comment:1 Changed 4 years ago by
 Branch set to u/kedlaya/speed_up_padic_Gamma_by_caching_Dwork_expansion_coefficients
comment:2 Changed 4 years ago by
 Commit set to 81ed87ad291663b90a8a0b09782080c5166506fc
comment:3 Changed 4 years ago by
 Cc roed added
comment:4 Changed 4 years ago by
 Commit changed from 81ed87ad291663b90a8a0b09782080c5166506fc to e890d67bd2a8f39ae50328e277ba7c463bc20792
Branch pushed to git repo; I updated commit sha1. New commits:
e890d67  Add algorithm flag to padic Gauss sums

comment:5 Changed 4 years ago by
 Commit changed from e890d67bd2a8f39ae50328e277ba7c463bc20792 to 8e5921baff1aa440cc279462648670eba1597c21
Branch pushed to git repo; I updated commit sha1. New commits:
8e5921b  Eliminate extra O(p) step in use of the Dwork expansion

comment:6 Changed 4 years ago by
The last commit introduces another change, this one even more significant.
In the previous implementation of padic Gamma, there was a second O(p)
step which essentially used the functional equation of Gamma to reduce to considering arguments divisible by p
. However, it is far more efficient to directly apply Theorem 6.2 of FRV's book, which gives a similar formula for each residue class. Now at the cost of precomputing and storing O(pe)
terms, one gets an O(e)
algorithm for computing Gamma modulo p^e
.
This is what happened when I reran my original example with the new patch:
sage: p = next_prime(5000) sage: F = Qp(p) sage: time l2 = [F(a/(p1)).gamma(algorithm='sage') for a in range(p1)] CPU times: user 862 ms, sys: 23.9 ms, total: 886 ms Wall time: 875 ms
Maybe taking this back upstream would result in some additional improvement?
comment:7 Changed 4 years ago by
 Commit changed from 8e5921baff1aa440cc279462648670eba1597c21 to 3814d7d825af893130e71591c17935e5edb9acb7
comment:8 Changed 4 years ago by
A couple of minor modifications in the latest patch, gleaned by carefully reading profiler output. These also cover Gauss sums and hypergeometric motives, since my current interest in padic Gamma involves the latter.
comment:9 followup: ↓ 10 Changed 3 years ago by
 Branch changed from u/kedlaya/speed_up_padic_Gamma_by_caching_Dwork_expansion_coefficients to public/24433
 Commit changed from 3814d7d825af893130e71591c17935e5edb9acb7 to a05daab31cc9f100d86c448c52321d51b964104b
 Reviewers set to Frédéric Chapoton
 Status changed from new to needs_review
comment:10 in reply to: ↑ 9 Changed 3 years ago by
Replying to chapoton:
I just made a few trivial changes. This can be set to positive if you want.
Doing so. Patchbot seems happy (one successful run and one with only an irrelevant failure).
comment:11 Changed 3 years ago by
 Status changed from needs_review to positive_review
comment:12 Changed 3 years ago by
 Branch changed from public/24433 to a05daab31cc9f100d86c448c52321d51b964104b
 Resolution set to fixed
 Status changed from positive_review to closed
Branch pushed to git repo; I updated commit sha1. New commits:
Cache Dwork expansion coefficients to speed up padic Gamma