Opened 11 years ago
Closed 11 years ago
#4340 closed defect (fixed)
[with patch, positive review] Speed up Victor Miller basis code
Reported by: | craigcitro | Owned by: | craigcitro |
---|---|---|---|
Priority: | major | Milestone: | sage-3.2 |
Component: | modular forms | Keywords: | |
Cc: | Merged in: | ||
Authors: | Reviewers: | ||
Report Upstream: | Work issues: | ||
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
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 11 years ago by
- Milestone changed from sage-3.2.1 to sage-3.2
- Status changed from new to assigned
- Summary changed from Speed up Victor Miller basis code to [with patch, needs review] Speed up Victor Miller basis code
comment:2 Changed 11 years ago by
- Summary changed from [with patch, needs review] Speed up Victor Miller basis code to [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 11 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 11 years ago by
OK, looks like #4359 got in, so that's good.
I'd actually change the name of F62.
Changed 11 years ago by
comment:5 Changed 11 years ago by
New patch with the name changed.
comment:6 Changed 11 years ago by
- Summary changed from [with patch, needs work] Speed up Victor Miller basis code to [with patch, positive review] Speed up Victor Miller basis code
Positive review. Very nice work :).
comment:7 Changed 11 years ago by
- Summary changed from [with patch, positive review] Speed up Victor Miller basis code to [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 11 years ago by
- Milestone changed from sage-3.2 to sage-3.2.1
- Summary changed from [with patch, positive review, needs work] Speed up Victor Miller basis code to [with patch, needs work] Speed up Victor Miller basis code
Changed 11 years ago by
comment:9 Changed 11 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 11 years ago by
- Milestone changed from sage-3.2.1 to sage-3.2
- Summary changed from [with patch, needs work] Speed up Victor Miller basis code to [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 11 years ago by
- Resolution set to fixed
- Status changed from assigned to 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 ...