Opened 11 years ago

Closed 10 years ago

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

Reported by: Owned by: was swenson major sage-5.0 group theory sd32 sage-5.0.beta8 Christopher Swenson William Stein N/A

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

### comment:1 Changed 11 years ago by rlm

• Description modified (diff)

### comment:3 Changed 10 years ago by swenson

• Owner changed from joyner to swenson

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

### comment:4 Changed 10 years ago by swenson

• Status changed from new to needs_review

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

### comment:5 Changed 10 years ago by novoselt

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

### comment:6 Changed 10 years ago by swenson

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:8 Changed 10 years ago by swenson

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

### comment:9 Changed 10 years ago by was

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

```8	+- Christopher Swenson (2011): Added a special case to compute the order efficiently.
9	+
10	 REFERENCES:
...
```

Patch for 10976

Patch for 10976

### comment:10 Changed 10 years ago by swenson

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

### Changed 10 years ago by was

renamed to standard format for patch names

### comment:11 Changed 10 years ago by was

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:

1. Indent four spaces instead of 2 (this is the Python.org standard, which we follow).
1. 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 10 years ago by was

• Status changed from needs_review to needs_work

### comment:13 Changed 10 years ago by swenson

• Status changed from needs_work to needs_review

### comment:14 Changed 10 years ago by was

• 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]
```

### comment:15 follow-ups: ↓ 16 ↓ 17 Changed 10 years ago by swenson

• 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 10 years ago by was

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 10 years ago by was

If we ever move to git, ...

I think it is more a "when" than "if".

-- William

### comment:18 Changed 10 years ago by was

• Authors set to Christopher Swenson
• 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.

### comment:19 Changed 10 years ago by swenson

• Status changed from needs_work to needs_review

Done.

### comment:20 Changed 10 years ago by was

• Status changed from needs_review to needs_work

Argh: "graoup"

### comment:21 Changed 10 years ago by swenson

• Status changed from needs_work to needs_review

My bad, must be an off day for me.

### comment:22 Changed 10 years ago by was

• Status changed from needs_review to positive_review

Thanks! Positive review.

### comment:23 follow-up: ↓ 25 Changed 10 years ago by 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?

### comment:24 Changed 10 years ago by was

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 10 years ago by novoselt

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

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

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 10 years ago by was

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]
```

### comment:29 Changed 10 years ago by swenson

• 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 10 years ago by was

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

### comment:31 Changed 10 years ago by swenson

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 10 years ago by was

• Status changed from needs_review to positive_review

### comment:33 follow-up: ↓ 34 Changed 10 years ago by jdemeyer

• 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 10 years ago by was

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

### comment:34 in reply to: ↑ 33 ; follow-up: ↓ 36 Changed 10 years ago by was

• Status changed from needs_work to positive_review

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 10 years ago by swenson

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

• Work issues rebase deleted