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)

trac-4340.patch (8.4 KB) - added by craigcitro 11 years ago.
trac-4340-pt2.patch (716 bytes) - added by craigcitro 11 years ago.

Download all attachments as: .zip

Change History (13)

comment:1 Changed 11 years ago by craigcitro

  • 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

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

comment:2 Changed 11 years ago by robertwb

  • 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 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?

comment:4 Changed 11 years ago by robertwb

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

I'd actually change the name of F62.

Changed 11 years ago by craigcitro

comment:5 Changed 11 years ago by craigcitro

New patch with the name changed.

comment:6 Changed 11 years ago by robertwb

  • 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 mabshoff

  • 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 mabshoff

  • 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 craigcitro

comment:9 Changed 11 years ago by craigcitro

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 mabshoff

  • 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 mabshoff

  • Resolution set to fixed
  • Status changed from assigned to closed

Merged both patches in Sage 3.2.alpha2

Note: See TracTickets for help on using tickets.