Opened 10 years ago
Closed 9 years ago
#10976 closed enhancement (fixed)
computing order of a certain subgroup of a permutation group is double dog slow (compared to Magma)
Reported by: | was | Owned by: | swenson |
---|---|---|---|
Priority: | major | Milestone: | sage-5.0 |
Component: | group theory | Keywords: | sd32 |
Cc: | Merged in: | sage-5.0.beta8 | |
Authors: | Christopher Swenson | Reviewers: | William Stein |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
--- sage def foo(n): G = SymmetricGroup(n) H = G.stabilizer(n//2) return H.order() time n = foo(200) // approx 399 seconds --- magma n foo(n) G := Sym(n); H := Stabiliser(G,n div 2); return Order(H); end function; time n := foo(200); // approx 0.40 seconds
See also trac #10804 which is all about the underlying algorithms and ideas related to this problem.
Attachments (10)
Change History (47)
comment:1 Changed 10 years ago by
- Description modified (diff)
comment:2 Changed 10 years ago by
- Keywords sd32 added
comment:3 Changed 9 years ago by
- Owner changed from joyner to swenson
comment:4 Changed 9 years ago by
- Status changed from new to needs_review
Patch uploaded. Can I get someone to look it over?
comment:5 Changed 9 years ago by
The format of the patch is not standard (not made by Sage's Mercurial).
It is also the first time I see
Copyright 2012 Google Inc. All Rights Reserved.
and I am not sure if that's OK. Traditionally people who edit the file add themselves there, but "all rights reserved" is a bit scary.
comment:6 Changed 9 years ago by
My bad on the patch -- the new one should be in the correct format.
So, unfortunately, this is the copyright statement as required by my agreement with Google. The code is still licensed under GPL, but they require that exact wording in the copyright.
comment:7 Changed 9 years ago by
Google copyright is fine. What does "all rights reserved" mean exactly.
comment:8 Changed 9 years ago by
I think it makes lawyers feel better. Wikipedia says it means nothing.
comment:9 Changed 9 years ago by
Just out of curiosity, would it be allowed to do:
8 +- Christopher Swenson (2011): Added a special case to compute the order efficiently (This patch Copyright 2012 Google Inc. All Rights Reserved.) 9 + 10 REFERENCES: ...
instead of
8 +- Christopher Swenson (2011): Added a special case to compute the order efficiently. 9 + 10 REFERENCES: ... 17 +# Copyright 2012 Google Inc. All Rights Reserved.
Since it looks like Google is copyrighting the whole file otherwise.
comment:10 Changed 9 years ago by
Google said that was fine. I fixed the patch to reflect this.
comment:11 Changed 9 years ago by
I changed the name of the patch to our standard format. In particular, by ending in .patch instead of .txt, it now gets nicely syntax highlighted. Regarding the actual patch, can you:
- Indent four spaces instead of 2 (this is the Python.org standard, which we follow).
- Explain the mathematics behind the algorithm you are using. For example, if you look at http://trac.sagemath.org/sage_trac/attachment/ticket/11975/trac_11975-part4.patch you'll see that I explain the mathematics behind the algorithm that I've coded. Alternatively, if the algorithm you coded is very standard, you could give a reference (though I seem to recall you just came up with it from scratch).
comment:12 Changed 9 years ago by
- Status changed from needs_review to needs_work
Changed 9 years ago by
comment:13 Changed 9 years ago by
- Status changed from needs_work to needs_review
I believe that I have addressed your concerns.
comment:14 Changed 9 years ago by
- Status changed from needs_review to needs_work
I wish we had line-by-line commenting... Anyway:
- Change "that" to "for which" below?
1321 # Special case: certain subgroups of the symmetric group that Gap reports 1322 # generators of the form ((1, 2), (1, 3), ..., (1, m))
- Delete "the order of " below:
1330 "We then know that the order of this group is isomorphic to S_n" -- rewrite
- Is there confusion between "n" and "m" in the comments?
- It would be nice to have a doctest like this:
sage: [SymmetricGroup(n).stabilizer(1)._gap_().Size() for n in [2..10]] [1, 2, 6, 24, 120, 720, 5040, 40320, 362880] sage: [SymmetricGroup(n).stabilizer(1)._order() for n in [2..10]] [1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
Changed 9 years ago by
comment:15 follow-ups: ↓ 16 ↓ 17 Changed 9 years ago by
- Status changed from needs_work to needs_review
Done.
If we ever move to git, we could use gerrit. I don't know if there are good line-by-line commenting tools for hg.
comment:16 in reply to: ↑ 15 Changed 9 years ago by
Replying to swenson:
Done.
If we ever move to git, we could use gerrit. I don't know if there are good line-by-line commenting tools for hg.
I think it's more an issue of the code review tool we're using, e.g., trac. For example, http://code.google.com/ has line-by-line code review annotation, and fully supports Mercurial.
-- William
comment:17 in reply to: ↑ 15 Changed 9 years ago by
comment:18 Changed 9 years ago by
- Reviewers set to William Stein
- Status changed from needs_review to needs_work
I missed two small things:
- "This means that this graph is isomorphic" --> "This means that this group is isomorphic" (group, not graph).
- "Christopher Swenson (2011)" --> "Christopher Swenson (2012)"
Positive review once those two details are fixed.
Changed 9 years ago by
Changed 9 years ago by
comment:21 Changed 9 years ago by
- Status changed from needs_work to needs_review
My bad, must be an off day for me.
comment:22 Changed 9 years ago by
- Status changed from needs_review to positive_review
Thanks! Positive review.
comment:23 follow-up: ↓ 25 Changed 9 years ago by
Since I'm new here, I don't know what happens now. The developer's guide is a bit murky on what happens after you get a positive review, especially since I don't believe that I have commit privileges?
comment:24 Changed 9 years ago by
It's now the release manager's job (jdmeyer). Assuming we didn't forget anything obvious, and he trusts us, he'll apply your patch to one of the releases here (or soon to appear here):
Then the buildbot (or release manager) will run build tests all over the place (on dozens of computers). If any errors pop up, the ticket will get "needs work". If everything is fine, the patch stays in and will appear in the next Sage release (likely sage-5.0).
comment:25 in reply to: ↑ 23 Changed 9 years ago by
Replying to swenson:
Since I'm new here, I don't know what happens now. The developer's guide is a bit murky on what happens after you get a positive review, especially since I don't believe that I have commit privileges?
This probably means that there should be a ticket clarifying these steps in the developer's guide...
comment:26 Changed 9 years ago by
- Status changed from positive_review to needs_work
There are several doctest failures with sage-5.0.beta3:
The following tests failed: sage -t --long -force_lib devel/sage/doc/en/constructions/graph_theory.rst # 1 doctests failed sage -t --long -force_lib devel/sage/doc/en/thematic_tutorials/group_theory.rst # 1 doctests failed sage -t --long -force_lib devel/sage/sage/groups/perm_gps/partn_ref/data_structures_pyx.pxi # 3 doctests failed sage -t --long -force_lib devel/sage/sage/graphs/generic_graph.py # 1 doctests failed
(I'm assuming only the last patch needs to be applied)
comment:27 Changed 9 years ago by
Concerning creating patches: you should use "hg export tip", not "hg diff". This way, the uploaded patch contains meta-data about the username, the commit message...
If you use Mercurial queues, the commit message can be set using "hg qrefresh -e". If not, simply use "hg commit".
comment:28 Changed 9 years ago by
Wow, at least one of those doctest failures shows that there is a mistake in this algorithm:
sage: G = DihedralGroup(5).cayley_graph().automorphism_group() sage: sage: G.order() 6 sage: G._gap_().Order() 10 sage: len(list(G)) 10
I think that the author was perhaps assuming that the generators are all transpositions, but didn't test this:
sage: G.gens() [(1,8)(2,10)(3,4)(5,6)(7,9), (1,10)(2,3)(4,5)(6,7)(8,9)] sage: G.gens()[0].cycle_tuples() [(1, 8), (2, 10), (3, 4), (5, 6), (7, 9)]
But in the code in the patch we have
1357 a, b = g.cycle_tuples()[0]
Changed 9 years ago by
comment:29 Changed 9 years ago by
- Status changed from needs_work to needs_review
I believe I have fixed the errors.
I wasn't able to test against those files on my current box, as they seemed to be giving me a bunch of random, unrelated errors.
comment:30 Changed 9 years ago by
Looking at the code, I'm pretty confident this is right and will pass tests. Should the comment "* All generators have order 2 " be changed to "* All generators are transpositions (i.e., permutations that flip switch two elements and leave everything else fixed)" ?
Changed 9 years ago by
comment:31 Changed 9 years ago by
Sorry -- forgot that I still had to fix that comment.
Comment is now fixed in the latest patch set. Please take a look.
comment:32 Changed 9 years ago by
- Status changed from needs_review to positive_review
comment:33 follow-up: ↓ 34 Changed 9 years ago by
- Status changed from positive_review to needs_work
- Work issues set to rebase
trac_10976.7.patch doesn't apply to sage-5.0.beta7:
applying /mnt/usb1/scratch/jdemeyer/merger/patches/trac_10976.7.patch patching file sage/groups/perm_gps/permgroup.py Hunk #1 FAILED at 1330 1 out of 1 hunks FAILED -- saving rejects to file sage/groups/perm_gps/permgroup.py.rej abort: patch failed to apply
Changed 9 years ago by
folded the two patches into one; added proper "Trac #10976" to commit message.
comment:34 in reply to: ↑ 33 ; follow-up: ↓ 36 Changed 9 years ago by
- Status changed from needs_work to positive_review
Replying to jdemeyer:
trac_10976.7.patch doesn't apply to sage-5.0.beta7:
It does, sort of, but the .patch file actually had two separate HG commits in it, which "we don't do". I (the reviewer) have replaced it by a new patch with only one commit, and fixed the patch log description to start with "Trac #10976".
comment:35 Changed 9 years ago by
Thanks. I didn't know about the one-commit-per-patch thing. (In fact, I thought people were arguing against switching to gerrit because it enforces this...)
comment:36 in reply to: ↑ 34 Changed 9 years ago by
- Work issues rebase deleted
Replying to was:
It does, sort of, but the .patch file actually had two separate HG commits in it
There's nothing wrong with that as long as those two commits are in the correct order (which wasn't the case).
comment:37 Changed 9 years ago by
- Merged in set to sage-5.0.beta8
- Resolution set to fixed
- Status changed from positive_review to closed
I have a workaround I am testing for this (patch coming soon) that recognizes some subgroups of permutation groups (including stabilizer subgroups of the symmetric group), and can compute the order very quickly (~600 microseconds). The running time of foo(200) above is still about a second, because GAP takes that long to construct the stabilizer group and give us back the generators.
In the future, I can add some more cases, or try to develop a more general theory for quickly computing these group orders (the special case I added is based on a argument from graph theory).