#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 mraum):
* status: needs_info => needs_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
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.patch
2. trac-4578-optimize_modular_symbols_decomposition-doctest.patch
--
Comment:
You're completely right. Thank you for catching this! I replaced the old
patch with the right one. Doing this it turned out, that I needed to
change one doctest. The change is justified as the element alpha - 1 and
1/2 alpha + 1/2 have the same minpolys. They are, thought, elements of
number fields defined with completely different polynomial (They are
isomorphic!). This happens because the number field is now generated by a
different piece of code in the linalg modules of Sage.
The old and new parent are for me
{{{
OLD:
Number Field in alpha with defining polynomial x^2 + 4*x + 1
NEW:
Number Field in alpha with defining polynomial x^2 - 2*x - 11
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/4578#comment:6>
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.
