#4578: optimize modular symbols decomposition algorithm
-----------------------------+----------------------------------------------
Reporter: was | Owner: craigcitro
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.7
Component: modular forms | Keywords:
Author: Martin Raum | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-----------------------------+----------------------------------------------
Changes (by newvalueoldvalue):
* status: new => needs_review
* author: => Martin Raum
Old description:
> In short, the decomposition function on spaces of modular symbols is
> mysteriously way slower than it should be. Why?
>
> Consider this:
> {{{
> sage: M =
> ModularSymbols(1000,2,sign=1).new_subspace().cuspidal_subspace()
> sage: time d = M.decomposition(3)
> CPU times: user 3.21 s, sys: 0.11 s, total: 3.33 s
> Wall time: 3.37 s
> sage: t3 = M.hecke_matrix(3)
> sage: time d = t3.decomposition()
> CPU times: user 0.11 s, sys: 0.00 s, total: 0.11 s
> Wall time: 0.11 s
> sage: time d = t3.decomposition(algorithm='multimodular', height_guess=1)
> CPU times: user 0.06 s, sys: 0.00 s, total: 0.06 s
> Wall time: 0.06 s
> }}}
>
> This huge timing discrepancy isn't due to caching:
> {{{
> ^bsd:matrix was$ sage
> ----------------------------------------------------------------------
> | Sage Version 3.2, Release Date: 2008-11-20 |
> | Type notebook() for the GUI, and license() for information. |
> ----------------------------------------------------------------------
>
> sage: M =
> ModularSymbols(1000,2,sign=1).new_subspace().cuspidal_subspace()
> sage: t3 = M.hecke_matrix(3)
> sage: time d = t3.decomposition(algorithm='multimodular', height_guess=1)
> CPU times: user 0.07 s, sys: 0.01 s, total: 0.08 s
> Wall time: 0.08 s
> }}}
>
> For comparison:
> {{{
> sage: magma.eval("M := ModularSymbols(1000,2,1);")
> ''
> sage: magma.eval("S := NewSubspace(CuspidalSubspace(M)); time D :=
> Decomposition(S, 3);")
> 'Time: 0.050'
> }}}
>
> So Sage is nearly the same as Magma at the decomposition part of the
> computation, but is getting totally killed by using the wrong algorithm
> or doing something really dumb that it shouldn't even bother doing.
> I.e., above 3.2 seconds is spent doing something probably unnecessary,
> and only 0.08 is spent doing what should be the dominant step.
>
> There are of course numerous other similar examples. For concreteness,
> I think to close this ticket one should just worry about making it so
> that the above example completes in < 0.2 seconds instead of 3.3 seconds.
New description:
In short, the decomposition function on spaces of modular symbols is
mysteriously way slower than it should be. Why?
Consider this:
{{{
sage: M = ModularSymbols(1000,2,sign=1).new_subspace().cuspidal_subspace()
sage: time d = M.decomposition(3)
CPU times: user 3.21 s, sys: 0.11 s, total: 3.33 s
Wall time: 3.37 s
sage: t3 = M.hecke_matrix(3)
sage: time d = t3.decomposition()
CPU times: user 0.11 s, sys: 0.00 s, total: 0.11 s
Wall time: 0.11 s
sage: time d = t3.decomposition(algorithm='multimodular', height_guess=1)
CPU times: user 0.06 s, sys: 0.00 s, total: 0.06 s
Wall time: 0.06 s
}}}
This huge timing discrepancy isn't due to caching:
{{{
^bsd:matrix was$ sage
----------------------------------------------------------------------
| Sage Version 3.2, Release Date: 2008-11-20 |
| Type notebook() for the GUI, and license() for information. |
----------------------------------------------------------------------
sage: M = ModularSymbols(1000,2,sign=1).new_subspace().cuspidal_subspace()
sage: t3 = M.hecke_matrix(3)
sage: time d = t3.decomposition(algorithm='multimodular', height_guess=1)
CPU times: user 0.07 s, sys: 0.01 s, total: 0.08 s
Wall time: 0.08 s
}}}
For comparison:
{{{
sage: magma.eval("M := ModularSymbols(1000,2,1);")
''
sage: magma.eval("S := NewSubspace(CuspidalSubspace(M)); time D :=
Decomposition(S, 3);")
'Time: 0.050'
}}}
So Sage is nearly the same as Magma at the decomposition part of the
computation, but is getting totally killed by using the wrong algorithm or
doing something really dumb that it shouldn't even bother doing. I.e.,
above 3.2 seconds is spent doing something probably unnecessary, and only
0.08 is spent doing what should be the dominant step.
There are of course numerous other similar examples. For concreteness, I
think to close this ticket one should just worry about making it so that
the above example completes in < 0.2 seconds instead of 3.3 seconds.
'''Apply:'''
1. trac-4578-optimize_modular_symbols_decomposition.patch
--
Comment:
There are two reasons why this is much slower than we expect it to be:
First, the restriction of subspaces, when decomposing them, is checked.
This is not necessary and already this increases the performance.
Second, sorting the resulting Hecke modules depends on computing several
Hecke matrices. This we cannot change without introducing major
incompatibilities. But I added an option, that sorts the modules by their
basis structure. This makes the function again much fast.
{{{
sage: M = ModularSymbols(1000,2,sign=1).new_subspace().cuspidal_subspace()
sage: %time d = M.decomposition(3)
CPU times: user 1.62 s, sys: 0.00 s, total: 1.63 s
Wall time: 1.92 s
}}}
and
{{{
sage: M = ModularSymbols(1000,2,sign=1).new_subspace().cuspidal_subspace()
sage: %time d = M.decomposition(3, sort_by_basis = True)
CPU times: user 0.94 s, sys: 0.00 s, total: 0.94 s
Wall time: 1.59 s
}}}
Note, that the bare decomposition given in the description is not
sufficient: We need at least compute two further decompositions, since two
of the resulting modules are not irreducible with respect to T(2).
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/4578#comment:3>
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.
