computing order of a certain subgroup of a permutation group is double dog slow (compared to Magma) #10976

williamstein · 2011-03-21T21:17:24Z

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

Component: group theory

Keywords: sd32

Author: Christopher Swenson

Reviewer: William Stein

Merged: sage-5.0.beta8

Issue created by migration from https://trac.sagemath.org/ticket/10976

The text was updated successfully, but these errors were encountered:

williamstein · 2011-08-24T23:41:38Z

Changed keywords from none to sd32

swenson · 2012-01-22T19:32:16Z

comment:3

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

sage: def foo(n):
....:     G = SymmetricGroup(n)
....:     H = G.stabilizer(n//2)
....:     return H.order()
....: 
sage: %timeit foo(200)
5 loops, best of 3: 935 ms per loop

swenson · 2012-02-07T00:20:29Z

comment:4

Patch uploaded. Can I get someone to look it over?

novoselt · 2012-02-07T03:05:16Z

comment:5

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.

swenson · 2012-02-07T03:28:31Z

comment:6

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.

williamstein · 2012-02-07T15:20:30Z

comment:7

swenson · 2012-02-07T15:33:56Z

comment:8

I think it makes lawyers feel better. Wikipedia says it means nothing.

http://en.wikipedia.org/wiki/All_rights_reserved

williamstein · 2012-02-07T16:51:08Z

comment:9

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.

swenson · 2012-02-07T17:48:18Z

Patch for 10976

swenson · 2012-02-07T17:48:39Z

Attachment: patch-10976.2.txt

Patch for 10976

swenson · 2012-02-07T17:49:25Z

comment:10

Attachment: patch-10976.txt

Google said that was fine. I fixed the patch to reflect this.

williamstein · 2012-02-07T17:52:15Z

renamed to standard format for patch names

williamstein · 2012-02-07T17:56:17Z

comment:11

Attachment: trac_10976.patch.gz

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 https://github.com/sagemath/sage-prod/files/10653953/trac_11975-part4.patch.gz 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).

swenson · 2012-02-08T16:26:45Z

Attachment: trac_10976.2.patch.gz

swenson · 2012-02-08T16:27:14Z

comment:13

I believe that I have addressed your concerns.

williamstein · 2012-02-08T17:21:29Z

comment:14

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]

swenson · 2012-02-08T20:02:43Z

comment:23

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?

williamstein · 2012-02-08T20:12:39Z

comment:24

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

http://sage.math.washington.edu/home/release/?C=M;O=D

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

novoselt · 2012-02-08T20:40:53Z

comment:25

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

jdemeyer · 2012-02-09T19:10:49Z

comment:26

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)

jdemeyer · 2012-02-09T19:13:13Z

comment:27

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

williamstein · 2012-02-09T23:20:38Z

comment:28

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]

swenson · 2012-02-12T03:06:16Z

comment:29

Attachment: trac_10976.6.patch.gz

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.

williamstein · 2012-02-13T14:48:32Z

comment:30

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)" ?

swenson · 2012-03-05T11:20:08Z

Attachment: trac_10976.7.patch.gz

swenson · 2012-03-05T11:20:46Z

comment:31

Sorry -- forgot that I still had to fix that comment.

Comment is now fixed in the latest patch set. Please take a look.

jdemeyer · 2012-03-08T08:00:50Z

comment:33

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

jdemeyer · 2012-03-08T08:00:50Z

Work Issues: rebase

williamstein · 2012-03-08T20:39:05Z

Attachment: trac_10976.8.patch.gz

folded the two patches into one; added proper "Trac #10976" to commit message.

williamstein · 2012-03-08T20:40:24Z

comment:34

Replying to @jdemeyer:

attachment: 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".

swenson · 2012-03-09T19:50:27Z

comment:35

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

jdemeyer · 2012-03-09T20:43:24Z

Changed work issues from rebase to none

jdemeyer · 2012-03-09T20:43:24Z

comment:36

Replying to @williamstein:

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

jdemeyer · 2012-03-13T08:22:32Z

Merged: sage-5.0.beta8

williamstein added this to the sage-5.0 milestone Mar 21, 2011

williamstein added c: group theory labels Mar 21, 2011

williamstein assigned wdjoyner Mar 21, 2011

This comment has been minimized.

Sign in to view

swenson assigned swenson and unassigned wdjoyner Jan 22, 2012

swenson added the s: needs review label Feb 7, 2012

williamstein added s: needs work and removed s: needs review labels Feb 7, 2012

swenson added s: needs review and removed s: needs work labels Feb 8, 2012

williamstein removed the s: needs review label Feb 8, 2012

jdemeyer added s: needs work and removed s: positive review labels Feb 9, 2012

swenson added s: needs review and removed s: needs work labels Feb 12, 2012

williamstein added s: positive review and removed s: needs review labels Mar 5, 2012

jdemeyer added s: needs work and removed s: positive review labels Mar 8, 2012

williamstein added s: positive review and removed s: needs work labels Mar 8, 2012

jdemeyer removed the s: positive review label Mar 13, 2012

jdemeyer closed this as completed Mar 13, 2012

computing order of a certain subgroup of a permutation group is double dog slow (compared to Magma) #10976

computing order of a certain subgroup of a permutation group is double dog slow (compared to Magma) #10976

Comments

williamstein commented Mar 21, 2011

This comment has been minimized.

williamstein commented Aug 24, 2011

swenson commented Jan 22, 2012

swenson commented Feb 7, 2012

novoselt commented Feb 7, 2012

swenson commented Feb 7, 2012

williamstein commented Feb 7, 2012

swenson commented Feb 7, 2012

williamstein commented Feb 7, 2012

swenson commented Feb 7, 2012

swenson commented Feb 7, 2012

swenson commented Feb 7, 2012

williamstein commented Feb 7, 2012

williamstein commented Feb 7, 2012

swenson commented Feb 8, 2012

swenson commented Feb 8, 2012

williamstein commented Feb 8, 2012

swenson commented Feb 8, 2012

williamstein commented Feb 8, 2012

novoselt commented Feb 8, 2012

jdemeyer commented Feb 9, 2012

jdemeyer commented Feb 9, 2012

williamstein commented Feb 9, 2012

swenson commented Feb 12, 2012

williamstein commented Feb 13, 2012

swenson commented Mar 5, 2012

swenson commented Mar 5, 2012

jdemeyer commented Mar 8, 2012

jdemeyer commented Mar 8, 2012

williamstein commented Mar 8, 2012

williamstein commented Mar 8, 2012

swenson commented Mar 9, 2012

jdemeyer commented Mar 9, 2012

jdemeyer commented Mar 9, 2012

jdemeyer commented Mar 13, 2012