Opened 14 years ago
Closed 14 years ago
#4340 closed defect (fixed)
[with patch, positive review] Speed up Victor Miller basis code
| Reported by: | Craig Citro | Owned by: | Craig Citro |
|---|---|---|---|
| Priority: | major | Milestone: | sage-3.2 |
| Component: | modular forms | Keywords: | |
| Cc: | Merged in: | ||
| Authors: | Reviewers: | ||
| Report Upstream: | N/A | Work issues: | |
| Branch: | Commit: | ||
| Dependencies: | Stopgaps: |
Status badges
Description
The current Victor Miller basis code in Sage is painfully slow.
I've already written much faster code, which I'll submit shortly.
Attachments (2)
Change History (13)
comment:1 Changed 14 years ago by
| Milestone: | sage-3.2.1 → sage-3.2 |
|---|---|
| Status: | new → assigned |
| Summary: | Speed up Victor Miller basis code → [with patch, needs review] Speed up Victor Miller basis code |
comment:2 Changed 14 years ago by
| Summary: | [with patch, needs review] Speed up Victor Miller basis code → [with patch, needs work] Speed up Victor Miller basis code |
|---|
Looks good to me--I had to add a "var" argument to modform/eis_series.py though, does this depend on a patch somewhere. But after that it seems to work fine (and fast).
Also, "F62" threw me for a bit, perhaps "F6sqare" or something like that would be better?
comment:3 Changed 14 years ago by
This extra argument to eisenstein_series_qexp was in #4359 ...
Yeah, I picked F62 because it was F_6^2 when I was writing it on paper ... should I add a comment in the code, or actually change the name?
comment:4 Changed 14 years ago by
OK, looks like #4359 got in, so that's good.
I'd actually change the name of F62.
Changed 14 years ago by
| Attachment: | trac-4340.patch added |
|---|
comment:6 Changed 14 years ago by
| Summary: | [with patch, needs work] Speed up Victor Miller basis code → [with patch, positive review] Speed up Victor Miller basis code |
|---|
Positive review. Very nice work :).
comment:7 Changed 14 years ago by
| Summary: | [with patch, positive review] Speed up Victor Miller basis code → [with patch, positive review, needs work] Speed up Victor Miller basis code |
|---|
Sorry, but
---------------------------------------------------------------------- | Sage Version 3.2.alpha1, Release Date: 2008-10-26 | | Type notebook() for the GUI, and license() for information. | ---------------------------------------------------------------------- sage: f = ModularForms(1,4).0 sage: time L = f.modform_lseries() WARNING: possible bug in q_expansion_basis for modular forms space Modular Forms space of dimension 1 for Congruence Subgroup Gamma0(1) of weight 4 over Rational Field WARNING: possible bug in q_expansion_basis for modular forms space Modular Forms space of dimension 1 for Congruence Subgroup Gamma0(1) of weight 4 over Rational Field WARNING: possible bug in q_expansion_basis for modular forms space Modular Forms space of dimension 1 for Congruence Subgroup Gamma0(1) of weight 4 over Rational Field WARNING: possible bug in q_expansion_basis for modular forms space Modular Forms space of dimension 1 for Congruence Subgroup Gamma0(1) of weight 4 over Rational Field WARNING: possible bug in q_expansion_basis for modular forms space Modular Forms space of dimension 1 for Congruence Subgroup Gamma0(1) of weight 4 over Rational Field WARNING: possible bug in q_expansion_basis for modular forms space Modular Forms space of dimension 1 for Congruence Subgroup Gamma0(1) of weight 4 over Rational Field <SNIP potentially infinite repetition - I killed the process after 20 minutes CPU time>
This is on sage.math with my 3.2.alph2 merge tree. Other than the above problem all doctests passed.
Cheers,
Michael
comment:8 Changed 14 years ago by
| Milestone: | sage-3.2 → sage-3.2.1 |
|---|---|
| Summary: | [with patch, positive review, needs work] Speed up Victor Miller basis code → [with patch, needs work] Speed up Victor Miller basis code |
Changed 14 years ago by
| Attachment: | trac-4340-pt2.patch added |
|---|
comment:9 Changed 14 years ago by
Yep, I stupidly just ignored the cusp_only argument in the case where the space was one-dimensional. Attached patch fixes it.
comment:10 Changed 14 years ago by
| Milestone: | sage-3.2.1 → sage-3.2 |
|---|---|
| Summary: | [with patch, needs work] Speed up Victor Miller basis code → [with patch, positive review] Speed up Victor Miller basis code |
The second patch fixes the doctest issue. Positive review, but I would be happy if an expert took another look.
Cheers,
Michael
comment:11 Changed 14 years ago by
| Resolution: | → fixed |
|---|---|
| Status: | assigned → closed |
Merged both patches in Sage 3.2.alpha2
This code is a massive speedup over the old code, and is still not as fast as I'm planning on making it. Even in examples as small as
victor_miller_basis(300,100), this gives a factor of 900 speedup. It's also now faster than Magma.I'm pretty sure I've got all the corner cases covered, too, but one can never be sure about these things ...