Opened 8 years ago

Closed 5 years ago

#12949 closed enhancement (fixed)

Better congruence testing for odd arithmetic subgroups

Reported by: davidloeffler Owned by: craigcitro
Priority: major Milestone: sage-6.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 davidloeffler)

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.

Attachments (4)

trac_12949.patch (19.3 KB) - added by davidloeffler 6 years ago.
Rebased to 5.11.beta3
trac_12949-fixlink.patch (2.2 KB) - added by davidloeffler 6 years ago.
Apply over previous patch
trac_12949-rebased.patch (20.5 KB) - added by davidloeffler 6 years ago.
Rebased to apply cleanly over #12233
trac_12949-rebased-v2.patch (22.6 KB) - added by chapoton 6 years ago.
rebased again on 5.12.beta5

Download all attachments as: .zip

Change History (53)

comment:1 Changed 8 years ago by davidloeffler

  • Status changed from new to needs_review

comment:2 Changed 8 years ago by davidloeffler

  • Cc vdelecroix added

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)

comment:3 Changed 6 years ago by vdelecroix

Hello,

Sorry to answer lately. This is quite nice that it works!

I am starting the review...

comment:4 Changed 6 years ago by vdelecroix

  • Milestone changed from sage-5.10 to sage-5.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 follow-up: Changed 6 years ago by davidloeffler

  • 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 6 years ago by vdelecroix

  • 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 6 years ago by davidloeffler

I'd need Hamilton's permission to put the work on the arxiv, I'll see if that can be got.

comment:8 Changed 6 years ago by davidloeffler

  • 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 6 years ago by vdelecroix

patchbot is unhappy on 5.11.beta3. Is that normal?

Changed 6 years ago by davidloeffler

Rebased to 5.11.beta3

comment:10 Changed 6 years ago by davidloeffler

It conflicted with #14014. I've rebased it.

comment:11 Changed 6 years ago by vdelecroix

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 sage-devel thread)

... but this ticket has nothing to do with it ;-)

Best, Vincent

Last edited 6 years ago by vdelecroix (previous) (diff)

comment:12 Changed 6 years ago by vdelecroix

  • Status changed from needs_review to needs_work
  • Work issues set to test

Changed 6 years ago by davidloeffler

Apply over previous patch

comment:13 Changed 6 years ago by davidloeffler

  • 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 6 years ago by davidloeffler

  • Description modified (diff)

comment:15 Changed 6 years ago by davidloeffler

Apply trac_12949.patch trac_12949-fixlink.patch​

(for patchbot)

Last edited 6 years ago by davidloeffler (previous) (diff)

comment:16 Changed 6 years ago by davidloeffler

  • 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_12949-rebased.patch​

comment:17 Changed 6 years ago by davidloeffler

  • Dependencies changed from 12233 to #12233

Changed 6 years ago by davidloeffler

Rebased to apply cleanly over #12233

comment:18 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:19 Changed 6 years ago by chapoton

  • Description modified (diff)

for the patchbots

apply trac_12949-rebased-v2.patch

comment:20 Changed 6 years ago by vdelecroix

  • Status changed from needs_review to positive_review

Hi,

Good for me! Thanks.

Vincent

comment:21 Changed 6 years ago by jdemeyer

  • Status changed from positive_review to needs_work
dochtml.log:[arithgrou] /scratch/release/merger/sage-5.13.beta2/local/lib/python2.7/site-packages/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 6 years ago by chapoton

  • Status changed from needs_work to needs_review

New patch, where I have corrected the doc issue.

comment:23 Changed 6 years ago by chapoton

for the patchbots:

apply trac_12949-rebased-v2.patch

comment:24 Changed 6 years ago by davidloeffler

  • 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 6 years ago by jdemeyer

  • Status changed from positive_review to needs_work

Problem with the documentation:

dochtml.log:[arithgrou] /scratch/release/merger/sage-5.13.beta2/local/lib/python2.7/site-packages/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)?

Changed 6 years ago by chapoton

rebased again on 5.12.beta5

comment:26 Changed 6 years ago by chapoton

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 6 years ago by chapoton

apply trac_12949-rebased-v2.patch

comment:28 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:29 Changed 6 years ago by chapoton

  • 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 6 years ago by chapoton

  • Status changed from needs_work to needs_review

comment:31 Changed 6 years ago by git

  • Commit changed from 6091c3a468a76ffb25086c184fdd4446c79e291b to 389b3423203e1b5c7e363291c6d0d63473c5eb3a

Branch pushed to git repo; I updated commit sha1. New commits:

389b342trac #12949 minor details

comment:32 Changed 6 years ago by git

  • Commit changed from 389b3423203e1b5c7e363291c6d0d63473c5eb3a to 4820c61b038378aaa7640a8cb4675b52dfcfad57

Branch pushed to git repo; I updated commit sha1. New commits:

2789f49Merge branch 'u/chapoton/12949' of ssh://trac.sagemath.org:22/sage into 12949
4820c61trac #12949 details

comment:33 Changed 6 years ago by vdelecroix

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

337fc95Merge 6.2.rc1 into 12949-odd_subgroups

comment:34 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:35 Changed 6 years ago by vbraun

  • Branch changed from u/vdelecroix/12949 to 337fc958ba03cfcbc3bd9a1b7b465f3394b65cb3
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:36 Changed 6 years ago by vbraun

  • Commit 337fc958ba03cfcbc3bd9a1b7b465f3394b65cb3 deleted
  • Resolution fixed deleted
  • Status changed from closed to new

Does this ticket really need super-long 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 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:38 Changed 5 years ago by davidloeffler

  • Branch changed from 337fc958ba03cfcbc3bd9a1b7b465f3394b65cb3 to u/davidloeffler/337fc958ba03cfcbc3bd9a1b7b465f3394b65cb3

comment:39 Changed 5 years ago by davidloeffler

  • Branch changed from u/davidloeffler/337fc958ba03cfcbc3bd9a1b7b465f3394b65cb3 to u/davidloeffler/12949

comment:40 Changed 5 years ago by davidloeffler

  • Commit set to a2211519edd92e17203f3dcbd133dc467aecd548
  • Status changed from new to needs_review

I've uploaded a new version without the time-wasting 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 re-applying the changes by hand.)


New commits:

d8e4deaTrac 12949: better congruence testing
a221151Trac 12949: fixed ReST formatting errors

comment:41 Changed 5 years ago by davidloeffler

  • Description modified (diff)

comment:42 Changed 5 years ago by vdelecroix

  • 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 5 years ago by git

  • Commit changed from a2211519edd92e17203f3dcbd133dc467aecd548 to 27b7508b4c99f0116fd3d63dfd3b6dd242302049

Branch pushed to git repo; I updated commit sha1. New commits:

27b7508Trac 12949: changes suggested by reviewer

comment:44 Changed 5 years ago by davidloeffler

  • 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:45 Changed 5 years ago by vdelecroix

  • Status changed from needs_review to positive_review

Good!

comment:46 Changed 5 years ago by chapoton

  • Milestone changed from sage-6.4 to sage-6.6

comment:47 Changed 5 years ago by chapoton

  • Milestone changed from sage-6.6 to sage-6.7

comment:48 Changed 5 years ago by vbraun

  • Dependencies #12233 deleted

comment:49 Changed 5 years ago by vbraun

  • Branch changed from u/davidloeffler/12949 to 27b7508b4c99f0116fd3d63dfd3b6dd242302049
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.