Opened 12 years ago
Closed 10 years ago
#4578 closed enhancement (fixed)
optimize modular symbols decomposition algorithm
Reported by: | was | Owned by: | craigcitro |
---|---|---|---|
Priority: | major | Milestone: | sage-4.7.2 |
Component: | modular forms | Keywords: | |
Cc: | GeorgSWeber, AlexGhitza | Merged in: | sage-4.7.2.alpha2 |
Authors: | Martin Raum | Reviewers: | David Loeffler |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
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:
Apply:
- trac-4578-optimize_modular_symbols_decomposition-v2.patch
- trac-4578-optimize_modular_symbols_decomposition-doctest.patch
Attachments (2)
Change History (13)
comment:1 Changed 12 years ago by
- Cc GeorgSWeber added
comment:2 Changed 10 years ago by
- Cc AlexGhitza added
- Report Upstream set to N/A
comment:3 Changed 10 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:4 Changed 10 years ago by
- Description modified (diff)
comment:5 Changed 10 years ago by
- Status changed from needs_review to needs_info
Hang on. Surely this patch doesn't remotely match the ticket description? If called with the default arguments this patch is a complete no-op!
Did you perhaps want to call decomposition_of_subspace
with the argument "check_restrict=False"
? Because Sage's Hecke algebras are always commutative, this check is probably redundant. That would, I imagine, result in a substantial speedup.
Changed 10 years ago by
comment:6 Changed 10 years ago by
- Description modified (diff)
- Status changed from needs_info to needs_review
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
comment:7 Changed 10 years ago by
- Reviewers set to David Loeffler
- Status changed from needs_review to positive_review
I'm happy with that change. As Martin has pointed out, the timing comparison with Magma is misleading: Sage is computing much more information than Magma (decomposing a bunch more Hecke operators). So I advocate merging Martin's patch and closing this ticket.
comment:8 Changed 10 years ago by
- Milestone changed from sage-4.7.1 to sage-4.7.2
comment:9 Changed 10 years ago by
- Status changed from positive_review to needs_work
There is an issue with the documentation:
dochtml.log:/mnt/usb1/scratch/jdemeyer/merger/sage-4.7.2.alpha1/local/lib/python2.6/site-packages/sage/modular/hecke/module.py:docstring of sage.modular.hecke.module.HeckeModule_free_module.T:7: (WARNING/2) Bullet list ends without a blank line; unexpected unindent.
Changed 10 years ago by
comment:10 Changed 10 years ago by
- Description modified (diff)
- Status changed from needs_work to positive_review
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!
comment:11 Changed 10 years ago by
- Merged in set to sage-4.7.2.alpha2
- Resolution set to fixed
- Status changed from positive_review to closed
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.
and
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).