#4578: optimize modular symbols decomposition algorithm
---------------------------+------------------------------------------------
Reporter: was | Owner: craigcitro
Type: enhancement | Status: new
Priority: major | Milestone: sage-3.2.1
Component: modular forms | Keywords:
---------------------------+------------------------------------------------
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.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/4578>
Sage <http://sagemath.org/>
Sage - Open Source Mathematical Software: Building the Car Instead of
Reinventing the Wheel
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
