#12043: Hecke series for overconvergent modular forms
------------------------------+---------------------------------------------
Reporter: lauder | Owner: craigcitro
Type: enhancement | Status: needs_work
Priority: minor | Milestone: sage-5.0
Component: modular forms | Keywords:
Work_issues: | Upstream: N/A
Reviewer: David Loeffler | Author: Alan Lauder
Merged: | Dependencies:
------------------------------+---------------------------------------------
Comment(by davidloeffler):
OK, so I got to the bottom of this.
Something like 90% of the running time for {{{'hecke_series(p = 79, N = 1,
klist = 2, m = 3)'}}} is taken up by the following 3 lines of code, the
first part of Step 4 of the algorithm:
{{{
#!python
Ep1p = Ep1(q**p)
Ep1pinv = Ep1p**(-1)
G = Ep1*Ep1pinv
}}}
These are slowed down slightly by my changes, since my first reviewer
patch added an {{{O(q^x)}}} error placeholder onto the end of Ep1, which
slightly increases the time spent on this computation. But one can vastly
speed up these lines by:
* truncating Ep1, reducing its precision by a factor of p, before
substituting q^p^ in
* using the method "V" (Verschiebung?) of Sage power series objects, which
does the map {{{ f(q) |--> f(q^p) }}} much more quickly than the generic
power series composition code.
With the code above changed to
{{{
#!python
Ep1p = (Ep1.add_bigoh(ceil(Ep1.prec() / ZZ(p)))).V(p)
Ep1pinv = Ep1p**(-1)
G = Ep1*Ep1pinv
}}}
the execution time drops from 43.24 s to 2.68 s.
It's a bit of a mystery to me why the first version is quite so slow; I
guess it's calling some general-purpose routine for composition of power
series, not realizing that what we're substituting is so simple.
How does the new timing compare with Magma?
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12043#comment:15>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
