Opened 9 years ago

Closed 8 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 rlm)

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

patch-10976.2.txt (2.8 KB) - added by swenson 8 years ago.
Patch for 10976
patch-10976.txt (2.8 KB) - added by swenson 8 years ago.
Patch for 10976
trac_10976.patch (2.8 KB) - added by was 8 years ago.
renamed to standard format for patch names
trac_10976.2.patch (3.5 KB) - added by swenson 8 years ago.
trac_10976.3.patch (3.8 KB) - added by swenson 8 years ago.
trac_10976.4.patch (3.8 KB) - added by swenson 8 years ago.
trac_10976.5.patch (3.8 KB) - added by swenson 8 years ago.
trac_10976.6.patch (4.1 KB) - added by swenson 8 years ago.
trac_10976.7.patch (5.1 KB) - added by swenson 8 years ago.
trac_10976.8.patch (4.2 KB) - added by was 8 years ago.
folded the two patches into one; added proper "Trac #10976" to commit message.

Download all attachments as: .zip

Change History (47)

comment:1 Changed 8 years ago by rlm

  • Description modified (diff)

comment:2 Changed 8 years ago by was

  • Keywords sd32 added

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

  • Status changed from new to needs_review

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

comment:5 Changed 8 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.

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

Google copyright is fine. What does "all rights reserved" mean exactly.

comment:8 Changed 8 years ago by swenson

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

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

comment:9 Changed 8 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:
...

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.

Changed 8 years ago by swenson

Patch for 10976

Changed 8 years ago by swenson

Patch for 10976

comment:10 Changed 8 years ago by swenson

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

Changed 8 years ago by was

renamed to standard format for patch names

comment:11 Changed 8 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 8 years ago by was

  • Status changed from needs_review to needs_work

Changed 8 years ago by swenson

comment:13 Changed 8 years ago by swenson

  • Status changed from needs_work to needs_review

I believe that I have addressed your concerns.

comment:14 Changed 8 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]
    

Changed 8 years ago by swenson

comment:15 follow-ups: Changed 8 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 8 years ago by was

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

Replying to swenson:

If we ever move to git, ...

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

-- William

comment:18 Changed 8 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.

Changed 8 years ago by swenson

comment:19 Changed 8 years ago by swenson

  • Status changed from needs_work to needs_review

Done.

comment:20 Changed 8 years ago by was

  • Status changed from needs_review to needs_work

Argh: "graoup"

Changed 8 years ago by swenson

comment:21 Changed 8 years ago by swenson

  • Status changed from needs_work to needs_review

My bad, must be an off day for me.

comment:22 Changed 8 years ago by was

  • Status changed from needs_review to positive_review

Thanks! Positive review.

comment:23 follow-up: Changed 8 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 8 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):

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

comment:25 in reply to: ↑ 23 Changed 8 years ago by novoselt

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

Changed 8 years ago by swenson

comment:29 Changed 8 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 8 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)" ?

Changed 8 years ago by swenson

comment:31 Changed 8 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 8 years ago by was

  • Status changed from needs_review to positive_review

comment:33 follow-up: Changed 8 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 8 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: Changed 8 years ago by was

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

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

  • Merged in set to sage-5.0.beta8
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.