Opened 9 years ago
Closed 6 years ago
#12949 closed enhancement (fixed)
Better congruence testing for odd arithmetic subgroups
Reported by:  davidloeffler  Owned by:  craigcitro 

Priority:  major  Milestone:  sage6.7 
Component:  modular forms  Keywords:  
Cc:  vdelecroix  Merged in:  
Authors:  David Loeffler  Reviewers:  Vincent Delecroix 
Report Upstream:  N/A  Work issues:  
Branch:  27b7508 (Commits)  Commit:  27b7508b4c99f0116fd3d63dfd3b6dd242302049 
Dependencies:  Stopgaps: 
Description (last modified by )
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 bruteforce 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.
Attachments (4)
Change History (53)
comment:1 Changed 9 years ago by
 Status changed from new to needs_review
comment:2 Changed 9 years ago by
 Cc vdelecroix added
comment:3 Changed 8 years ago by
Hello,
Sorry to answer lately. This is quite nice that it works!
I am starting the review...
comment:4 Changed 8 years ago by
 Milestone changed from sage5.10 to sage5.11
 Reviewers set to Vincent Delecroix
 Status changed from needs_review to needs_work
 Work issues set to bring back old code + minor doc
I would prefer to keep both implementations (naive one vs checking relations with default to the latter one of course ;). Then you may add a dedicated test comparing the results in sage.modular.arithgroup.tests
. Otherwise the new implementation is well documented and everything works.
Is your result available to read ? A dissertation is a legitimate reference, but one may want to read it.
Why did you remove the reference of the article of Alexey G. Gorinov ? I do not claim that it is not a good idea but just that it was not the purpose of the ticket.
comment:5 followup: ↓ 6 Changed 8 years ago by
 Status changed from needs_work to needs_info
Dear Vincent,
Nice to hear from you; sorry it's taken me so long to look at this in turn...
 I didn't remove the reference to Gorinov. I just moved it a little higher in the list so the references were listed in alphabetical order.
 Hamilton's dissertation isn't available publicly anywhere, sadly; Warwick doesn't maintain an archive of MMath dissertations, although it does for MSc and PhD degrees. If you want to check the result, I have a copy I can send to you personally, if you like.
 I'm not quite sure what you're suggesting re keeping both algorithms. At the moment we have one (fast) algorithm for even subgroups only, and another (much slower) algorithm for odd subgroups. It seems silly to distinguish needlessly between even/odd  would you be happier with a setup where we have both algorithms available for both types of subgroups (with the fast one the default, of course)?
comment:6 in reply to: ↑ 5 Changed 8 years ago by
 Work issues changed from bring back old code + minor doc to ref issue + test
Hi,
Replying to davidloeffler:
 I didn't remove the reference to Gorinov. I just moved it a little higher in the list so the references were listed in alphabetical order.
My mistake.
 Hamilton's dissertation isn't available publicly anywhere, sadly; Warwick doesn't maintain an archive of MMath dissertations, although it does for MSc and PhD degrees. If you want to check the result, I have a copy I can send to you personally, if you like.
I would appreciate a copy but this is not the point. If you mention the Math dissertation as a reference for the algorithm it should be available for anyone. What about arXiv ?
 I'm not quite sure what you're suggesting re keeping both algorithms. At the moment we have one (fast) algorithm for even subgroups only, and another (much slower) algorithm for odd subgroups. It seems silly to distinguish needlessly between even/odd  would you be happier with a setup where we have both algorithms available for both types of subgroups (with the fast one the default, of course)?
You are right. It would be better to keep the fast algorithm only and to implement the naive test within the Test
class and check that the answers coincide.
Best Vincent
comment:7 Changed 8 years ago by
I'd need Hamilton's permission to put the work on the arxiv, I'll see if that can be got.
comment:8 Changed 8 years ago by
 Status changed from needs_info to needs_review
 Work issues ref issue + test deleted
Dear Vincent,
Hamilton gave his permission for the work to be put on the Arxiv, so here's a new patch that references the Arxiv preprint. There is also a test in "tests.py" which compares is_congruence
against congruence_closure
, and a slight tweak to the congruence subgroup initialization code that makes the test run a little faster.
Best regards, David
comment:9 Changed 8 years ago by
patchbot is unhappy on 5.11.beta3. Is that normal?
comment:10 Changed 8 years ago by
It conflicted with #14014. I've rebased it.
comment:11 Changed 8 years ago by
Great! I am really happy that it was possible to put it on arxiv. Everything looks fine except for the tests: sage t
on sage.modular.arithgroup.tests was around 10sec and is now 576.57sec which is not reasonable. When testing the congruence try to set index_max to a much smaller value. You should also add some # long time
wherever appropriate.
I also notice that
 the Test class should be clean up (there is no reason to use
print
and there should be more occurences of tests inside the documentation)  there is a broken link in the documentation (see this sagedevel thread)
... but this ticket has nothing to do with it ;)
Best, Vincent
comment:12 Changed 8 years ago by
 Status changed from needs_review to needs_work
 Work issues set to test
comment:13 Changed 8 years ago by
 Status changed from needs_work to needs_review
 Work issues test deleted
Here's a new patch. The link now points to a copy Kurth's homepage as mirrored on an archive website. I kept the randomized test as it was, but flagged it with "long"; the problem is that if you reduce the index too far, then you only ever get one of a very small set of subgroups and so it's not really a worthwhile test.
I also corrected a tiny parity issue in the test routine (there are no odd subgroups of index 2 mod 4, and it was pure luck that the default parameters for the test routine don't provoke this error).
comment:14 Changed 8 years ago by
 Description modified (diff)
comment:15 Changed 8 years ago by
Apply trac_12949.patch trac_12949fixlink.patch
(for patchbot)
comment:16 Changed 8 years ago by
 Dependencies set to 12233
 Description modified (diff)
This conflicts (in a very minor way) with #12233, which now has a positive review, so I rebased it.
Apply trac_12949rebased.patch
comment:17 Changed 8 years ago by
 Dependencies changed from 12233 to #12233
comment:18 Changed 8 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:19 Changed 7 years ago by
 Description modified (diff)
for the patchbots
apply trac_12949rebasedv2.patch
comment:20 Changed 7 years ago by
 Status changed from needs_review to positive_review
Hi,
Good for me! Thanks.
Vincent
comment:21 Changed 7 years ago by
 Status changed from positive_review to needs_work
dochtml.log:[arithgrou] /scratch/release/merger/sage5.13.beta2/local/lib/python2.7/sitepackages/sage/modular/arithgroup/arithgroup_perm.py:docstring of sage.modular.arithgroup.arithgroup_perm:82: WARNING: Bullet list ends without a blank line; unexpected unindent.
comment:22 Changed 7 years ago by
 Status changed from needs_work to needs_review
New patch, where I have corrected the doc issue.
comment:23 Changed 7 years ago by
for the patchbots:
apply trac_12949rebasedv2.patch
comment:24 Changed 7 years ago by
 Status changed from needs_review to positive_review
I'm happy with the new patch, and doctests pass  I'll reinstate the positive review. Thanks, Frédéric!
comment:25 Changed 7 years ago by
 Status changed from positive_review to needs_work
Problem with the documentation:
dochtml.log:[arithgrou] /scratch/release/merger/sage5.13.beta2/local/lib/python2.7/sitepackages/sage/modular/arithgroup/arithgroup_perm.py:docstring of sage.modular.arithgroup.arithgroup_perm:82: WARNING: Bullet list ends without a blank line; unexpected unindent.
One more small remark: shouldn't the test methods (e.g. test_cong_closure
) be private (i.e. _test_cong_closure
)?
comment:26 Changed 7 years ago by
sorry. Now the doc should really be okay. I have not taken care of the test methods. Anyway, the file tests itself is not really for everybody..
comment:27 Changed 7 years ago by
apply trac_12949rebasedv2.patch
comment:28 Changed 7 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:29 Changed 7 years ago by
 Branch set to u/chapoton/12949
 Commit set to 6091c3a468a76ffb25086c184fdd4446c79e291b
Here is a git branch.
This ticket has once been positive reviewed..
New commits:
6091c3a  #12949: generalized Hsu congruence test for arithmetic subgroups

comment:30 Changed 7 years ago by
 Status changed from needs_work to needs_review
comment:31 Changed 7 years ago by
 Commit changed from 6091c3a468a76ffb25086c184fdd4446c79e291b to 389b3423203e1b5c7e363291c6d0d63473c5eb3a
Branch pushed to git repo; I updated commit sha1. New commits:
389b342  trac #12949 minor details

comment:32 Changed 7 years ago by
 Commit changed from 389b3423203e1b5c7e363291c6d0d63473c5eb3a to 4820c61b038378aaa7640a8cb4675b52dfcfad57
comment:33 Changed 7 years ago by
 Branch changed from u/chapoton/12949 to u/vdelecroix/12949
 Commit changed from 4820c61b038378aaa7640a8cb4675b52dfcfad57 to 337fc958ba03cfcbc3bd9a1b7b465f3394b65cb3
 Status changed from needs_review to positive_review
Hello,
I merged with 6.1.rc1 (trivial conflicts). All test pass and documentation builds. I set it back to positive review.
Vincent
New commits:
337fc95  Merge 6.2.rc1 into 12949odd_subgroups

comment:34 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:35 Changed 7 years ago by
 Branch changed from u/vdelecroix/12949 to 337fc958ba03cfcbc3bd9a1b7b465f3394b65cb3
 Resolution set to fixed
 Status changed from positive_review to closed
comment:36 Changed 7 years ago by
 Commit 337fc958ba03cfcbc3bd9a1b7b465f3394b65cb3 deleted
 Resolution fixed deleted
 Status changed from closed to new
Does this ticket really need superlong doctests to test things that absolutely cannot be tested by smaller parameters? Maximum time should be a few seconds, not minutes. There is no point in running huge computations if they don't test anyting that is already tested with smaller tests. Times out on slower buildbots.
comment:37 Changed 7 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:38 Changed 6 years ago by
 Branch changed from 337fc958ba03cfcbc3bd9a1b7b465f3394b65cb3 to u/davidloeffler/337fc958ba03cfcbc3bd9a1b7b465f3394b65cb3
comment:39 Changed 6 years ago by
 Branch changed from u/davidloeffler/337fc958ba03cfcbc3bd9a1b7b465f3394b65cb3 to u/davidloeffler/12949
comment:40 Changed 6 years ago by
 Commit set to a2211519edd92e17203f3dcbd133dc467aecd548
 Status changed from new to needs_review
I've uploaded a new version without the timewasting tests.
(For some reason, this ticket had been linked to a Git branch which "git trac" refused to read, so I just spent the entire morning reapplying the changes by hand.)
New commits:
d8e4dea  Trac 12949: better congruence testing

a221151  Trac 12949: fixed ReST formatting errors

comment:41 Changed 6 years ago by
 Description modified (diff)
comment:42 Changed 6 years ago by
 Status changed from needs_review to needs_work
Hello,
Replace ZZ(~Zmod(N)(2))
with ZZ(2).inverse_mod(N)
(several occurrences).
Do you know why L.order()
returns a Python int and not an Sage Integer? It looks like a bug to me as for example
sage: type(Zmod(5)(3).order()) <type 'sage.rings.integer.Integer'>
Vincent
comment:43 Changed 6 years ago by
 Commit changed from a2211519edd92e17203f3dcbd133dc467aecd548 to 27b7508b4c99f0116fd3d63dfd3b6dd242302049
Branch pushed to git repo; I updated commit sha1. New commits:
27b7508  Trac 12949: changes suggested by reviewer

comment:44 Changed 6 years ago by
 Status changed from needs_work to needs_review
I made the changes you suggested. I agree that the return type of "order" for perm group elements looks like a bug, so I changed that, although it has nothing really to do with this ticket.
comment:46 Changed 6 years ago by
 Milestone changed from sage6.4 to sage6.6
comment:47 Changed 6 years ago by
 Milestone changed from sage6.6 to sage6.7
comment:48 Changed 6 years ago by
 Dependencies #12233 deleted
comment:49 Changed 6 years ago by
 Branch changed from u/davidloeffler/12949 to 27b7508b4c99f0116fd3d63dfd3b6dd242302049
 Resolution set to fixed
 Status changed from positive_review to closed
Vincent: I'm ccing you on this ticket, since it was you who originally suggested that Hsu's algorithm should work for odd subgroups too (http://trac.sagemath.org/sage_trac/ticket/11598#comment:3)