Opened 4 years ago

Closed 3 years ago

#24433 closed enhancement (fixed)

Speed up p-adic Gamma by caching Dwork expansion coefficients

Reported by: kedlaya Owned by:
Priority: major Milestone: sage-8.2
Component: padics Keywords: p-adic 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:

Status badges

Description

The computation of the p-adic 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/(p-1)).gamma(algorithm='pari') for a in range(p-1)]
CPU times: user 6min 17s, sys: 23.2 ms, total: 6min 17s
Wall time: 6min 17s
sage: time l2 = [F(a/(p-1)).gamma(algorithm='sage') for a in range(p-1)]
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(p-1))
True

Change History (12)

comment:1 Changed 4 years ago by kedlaya

  • Branch set to u/kedlaya/speed_up_p-adic_Gamma_by_caching_Dwork_expansion_coefficients

comment:2 Changed 4 years ago by git

  • Commit set to 81ed87ad291663b90a8a0b09782080c5166506fc

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

81ed87aCache Dwork expansion coefficients to speed up p-adic Gamma

comment:3 Changed 4 years ago by kedlaya

  • Authors set to Kiran Kedlaya
  • Cc roed added

comment:4 Changed 4 years ago by git

  • Commit changed from 81ed87ad291663b90a8a0b09782080c5166506fc to e890d67bd2a8f39ae50328e277ba7c463bc20792

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

e890d67Add algorithm flag to p-adic Gauss sums

comment:5 Changed 4 years ago by git

  • Commit changed from e890d67bd2a8f39ae50328e277ba7c463bc20792 to 8e5921baff1aa440cc279462648670eba1597c21

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

8e5921bEliminate extra O(p) step in use of the Dwork expansion

comment:6 Changed 4 years ago by kedlaya

The last commit introduces another change, this one even more significant.

In the previous implementation of p-adic 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/(p-1)).gamma(algorithm='sage') for a in range(p-1)]
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 git

  • Commit changed from 8e5921baff1aa440cc279462648670eba1597c21 to 3814d7d825af893130e71591c17935e5edb9acb7

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

fd55e45Optimizations for p-adic Gauss sums
edcbc8fOptimizations to p-adic Gamma
3814d7dOptimizations to hypergeometric trace formula

comment:8 Changed 4 years ago by kedlaya

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 p-adic Gamma involves the latter.

comment:9 follow-up: Changed 3 years ago by chapoton

  • Branch changed from u/kedlaya/speed_up_p-adic_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

I just made a few trivial changes. This can be set to positive if you want.


New commits:

9014637Merge branch 'u/kedlaya/speed_up_p-adic_Gamma_by_caching_Dwork_expansion_coefficients' in 8.2.rc2
a05daabtrac 24433 trivial details

comment:10 in reply to: ↑ 9 Changed 3 years ago by kedlaya

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 kedlaya

  • Status changed from needs_review to positive_review

comment:12 Changed 3 years ago by vbraun

  • Branch changed from public/24433 to a05daab31cc9f100d86c448c52321d51b964104b
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.