#4578: optimize modular symbols decomposition algorithm
------------------------------+---------------------------------------------
Reporter: was | Owner: craigcitro
Type: enhancement | Status: positive_review
Priority: major | Milestone: sage-4.7.2
Component: modular forms | Keywords:
Work_issues: | Upstream: N/A
Reviewer: David Loeffler | Author: Martin Raum
Merged: | Dependencies:
------------------------------+---------------------------------------------
Changes (by mraum):
* status: needs_work => positive_review
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.
>
> '''Depends on:'''
> 1. #10987
>
> '''Apply:'''
> 1. trac-4578-optimize_modular_symbols_decomposition.patch
> 2. trac-4578-optimize_modular_symbols_decomposition-doctest.patch
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.
'''Depends on:'''
1. #10987
'''Apply:'''
1. trac-4578-optimize_modular_symbols_decomposition-v2.patch
2. trac-4578-optimize_modular_symbols_decomposition-doctest.patch
--
Comment:
This was a very stupid typo. I have checked that it occurs with the old
patch and does not occur with the new one. The only thing that I changes
is two spaces, one added, one removed. So I set this back to positive
review; Sorry for the inconvenience, Jeroen!
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/4578#comment:10>
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.
