Ticket #10228 (closed enhancement: fixed)
optimize computation of Delta modulo an integer
|Reported by:||AlexGhitza||Owned by:||craigcitro|
|Component:||modular forms||Keywords:||delta finite field|
|Cc:||mraum, was||Work issues:|
|Report Upstream:||N/A||Reviewers:||Martin Raum|
|Authors:||Alex Ghitza||Merged in:||sage-4.6.1.alpha1|
At the moment, computing the q-expansion of Delta modulo an integer N is done by first computing the q-expansion over the integers and then reducing it modulo N. This is fine for getting a moderate number of coefficients, but wastes memory and becomes unnecessarily slow for large number of coefficients:
sage: time f = delta_qexp(10^6, K=GF(1009)) CPU times: user 12.01 s, sys: 0.49 s, total: 12.50 s Wall time: 12.50 s sage: time f = delta_qexp(10^7, K=GF(1009)) CPU times: user 473.93 s, sys: 4.56 s, total: 478.49 s Wall time: 478.59 s
The patch coming up implements the computation of delta_qexp directly modulo N:
sage: time f = delta_qexp(10^6, K=GF(1009)) CPU times: user 2.12 s, sys: 0.11 s, total: 2.23 s Wall time: 2.23 s sage: time f = delta_qexp(10^7, K=GF(1009)) CPU times: user 23.13 s, sys: 1.18 s, total: 24.31 s Wall time: 24.32 s
Computing things directly mod N seems to only pay off for more than about 150 coefficients, so for smaller precisions we use the old code.
The motivation for implementing this is of course #8282, and the ability to work with modular forms (mod p) in very high weights.
I don't see myself ever needing to work with Delta modulo non-primes, but I also don't see any reason to restrict to prime moduli.
- Cc mraum, was added
- Keywords delta finite field added
- Status changed from new to needs_review
- Authors set to Alex Ghitza
- Status changed from needs_review to positive_review
- Reviewers set to Martin Raum