Opened 12 years ago
Closed 12 years ago
#10228 closed enhancement (fixed)
optimize computation of Delta modulo an integer
Reported by: | Alex Ghitza | Owned by: | Craig Citro |
---|---|---|---|
Priority: | major | Milestone: | sage-4.6.1 |
Component: | modular forms | Keywords: | delta finite field |
Cc: | Martin Raum, William Stein | Merged in: | sage-4.6.1.alpha1 |
Authors: | Alex Ghitza | Reviewers: | Martin Raum |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
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.
Attachments (2)
Change History (6)
Changed 12 years ago by
Attachment: | trac_10228.patch added |
---|
comment:1 Changed 12 years ago by
Authors: | → Alex Ghitza |
---|---|
Cc: | Martin Raum William Stein added |
Keywords: | delta finite field added |
Status: | new → needs_review |
I have attached the patch. I took the liberty to base it on top of the small patch at #10209, since that already has a positive review and is likely to be merged quickly.
However, I am happy to make it independent if that makes the review easier.
Cc-ing people who might be interested in this.
Changed 12 years ago by
Attachment: | trac_10228-review-optimize_delta.patch added |
---|
comment:2 Changed 12 years ago by
Everything passes fine. I only adapted the documentation (adding missing ') and I changed the exception to by Python 3 compatible. If your are fine with all these minor changes, give this a positive review.
comment:3 Changed 12 years ago by
Reviewers: | → Martin Raum |
---|---|
Status: | needs_review → positive_review |
Looks good to me.
Note to the release manager: apply only trac_10228-review-optimize_delta.patch
, after #10209 is merged.
comment:4 Changed 12 years ago by
Merged in: | → sage-4.6.1.alpha1 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
apply after ticket at #10209