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:

Status badges

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)

trac_10228.patch (4.3 KB) - added by Alex Ghitza 12 years ago.
apply after ticket at #10209
trac_10228-review-optimize_delta.patch (4.3 KB) - added by Martin Raum 12 years ago.

Download all attachments as: .zip

Change History (6)

Changed 12 years ago by Alex Ghitza

Attachment: trac_10228.patch added

apply after ticket at #10209

comment:1 Changed 12 years ago by Alex Ghitza

Authors: Alex Ghitza
Cc: Martin Raum William Stein added
Keywords: delta finite field added
Status: newneeds_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 Martin Raum

comment:2 Changed 12 years ago by Martin Raum

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 Alex Ghitza

Reviewers: Martin Raum
Status: needs_reviewpositive_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 Jeroen Demeyer

Merged in: sage-4.6.1.alpha1
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.