[with patch, positive review] Speed up Victor Miller basis code

[craigcitro]

The current Victor Miller basis code in Sage is painfully slow.

I've already written much faster code, which I'll submit shortly.

[craigcitro]

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 ...

[robertwb]

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?

[craigcitro]

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?

[robertwb]

OK, looks like #4359 got in, so that's good.

I'd actually change the name of F62.

[craigcitro]

New patch with the name changed.

[robertwb]

Positive review. Very nice work :).

[mabshoff]

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

[craigcitro]

Yep, I stupidly just ignored the cusp_only argument in the case where the space was one-dimensional. Attached patch fixes it.

[mabshoff]

The second patch fixes the doctest issue. Positive review, but I would be happy if an expert took another look.

Cheers,

Michael

[mabshoff]

Merged both patches in Sage 3.2.alpha2