#12949: Better congruence testing for odd arithmetic subgroups
----------------------------------+----------------------------------
Reporter: davidloeffler | Owner: craigcitro
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-5.11
Component: modular forms | Resolution:
Keywords: | Merged in:
Authors: David Loeffler | Reviewers: Vincent Delecroix
Report Upstream: N/A | Work issues:
Branch: | Dependencies: 12233
Stopgaps: |
----------------------------------+----------------------------------
Changes (by davidloeffler):
* dependencies: => 12233
Old description:
> This patch relates to the {{{ is_congruence() }}} method of arithmetic
> subgroups of SL2Z (described in terms of permutations, cf. {{{
> sage.modular.arithgroup.arithgroup_perm}}}). For even subgroups
> (containing -1), there is a very fast algorithm due to Tim Hsu, but for
> odd subgroups we were using a much, much slower brute-force algorithm.
>
> My student Thomas Hamilton checked in his MMath thesis that Hsu's
> algorithm also works for odd subgroups with minor modifications. This
> patch implements this generalized Hsu algorithm, resulting in a speedup
> of about three orders of magnitude in all the examples I tried.
>
> Apply [attachment:trac_12949.patch],
> [attachment:trac_12949-fixlink.patch]
New description:
This patch relates to the {{{ is_congruence() }}} method of arithmetic
subgroups of SL2Z (described in terms of permutations, cf. {{{
sage.modular.arithgroup.arithgroup_perm}}}). For even subgroups
(containing -1), there is a very fast algorithm due to Tim Hsu, but for
odd subgroups we were using a much, much slower brute-force algorithm.
My student Thomas Hamilton checked in his MMath thesis that Hsu's
algorithm also works for odd subgroups with minor modifications. This
patch implements this generalized Hsu algorithm, resulting in a speedup of
about three orders of magnitude in all the examples I tried.
Apply [attachment:trac_12949-rebased.patch]
--
Comment:
This conflicts (in a very minor way) with #12233, which now has a positive
review, so I rebased it.
Apply trac_12949-rebased.patch
--
Ticket URL: <http://trac.sagemath.org/ticket/12949#comment:16>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
