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:

Status badges

Description (last modified by mraum)

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

Attachments (2)

Change History (13)

comment:1 Changed 12 years ago by GeorgSWeber

  • Cc GeorgSWeber added

comment:2 Changed 10 years ago by AlexGhitza

  • Cc AlexGhitza added
  • Report Upstream set to N/A

comment:3 Changed 10 years ago by mraum

  • Authors set to Martin Raum
  • Description modified (diff)
  • Status changed from new to needs_review

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).

comment:4 Changed 10 years ago by mraum

  • Description modified (diff)

comment:5 Changed 10 years ago by davidloeffler

  • 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.

comment:6 Changed 10 years ago by mraum

  • 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 davidloeffler

  • 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 jdemeyer

  • Milestone changed from sage-4.7.1 to sage-4.7.2

comment:9 Changed 10 years ago by jdemeyer

  • 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.

comment:10 Changed 10 years ago by mraum

  • 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 jdemeyer

  • Merged in set to sage-4.7.2.alpha2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.