Opened 10 years ago

Closed 10 years ago

#10804 closed enhancement (fixed)

Improvements to partn_ref functions, including stabilizer chains

Reported by: rlm Owned by: rlm
Priority: major Milestone: sage-4.7.1
Component: group theory Keywords:
Cc: boothby Merged in: sage-4.7.1.alpha2
Authors: Robert Miller Reviewers: Tom Boothby
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #10886, #10549 Stopgaps:

Status badges

Description (last modified by jdemeyer)

Stabilizer chains and other improvements.

Attachments (1)

trac_10804.patch (191.3 KB) - added by rlm 10 years ago.

Download all attachments as: .zip

Change History (37)

comment:1 Changed 10 years ago by rlm

  • Summary changed from Small improvements to partn_ref functions to Improvements to partn_ref functions, including stabilizer chains

comment:2 Changed 10 years ago by rlm

  • Status changed from new to needs_review

comment:3 Changed 10 years ago by boothby

  • Status changed from needs_review to needs_work

buildbot applied the wrong patch... let's see if it works next time.

comment:4 Changed 10 years ago by boothby

  • Status changed from needs_work to needs_review

comment:5 Changed 10 years ago by rlm

apply trac_10804.patch

comment:6 Changed 10 years ago by rlm

  • Status changed from needs_review to needs_work

Just updated patch to deal with conflict coming from #10712.

comment:7 Changed 10 years ago by rlm

  • Status changed from needs_work to needs_review

comment:8 Changed 10 years ago by rlm

How do I get the buildbot to try again?

comment:9 Changed 10 years ago by boothby

  • Status changed from needs_review to needs_info

I just tried to apply this to 4.6.2.rc0 and got loads of failed hunks. Am I missing something, or are you?

comment:10 Changed 10 years ago by rlm

Due to #10712 you need 4.6.2.rc1 or later.

comment:11 Changed 10 years ago by rlm

I just successfully applied this patch to sage-4.7.alpha3.

comment:12 Changed 10 years ago by boothby

Okay, this is a little weird. Applied fine to 4.6.2, but I get the following:

sage -t  ".6.2/devel/sage/sage/groups/perm_gps/permgroup_morphism.py"
         [8.1 s]
sage -t  ".6.2/devel/sage/sage/groups/generic.py"
         [13.3 s]
sage -t  ".6.2/devel/sage/sage/stats/__init__.py"
         [0.2 s]
sage -t  ".6.2/devel/sage/sage/stats/intlist.pyx"
         [7.0 s]
sage -t  ".6.2/devel/sage/sage/stats/all.py"
         [0.2 s]
sage -t  ".6.2/devel/sage/sage/stats/test.py"

            if coset_eq(p, r, gens):
                found = True
                break
        if not found:
            reps.append(p)
Exception raised:
    Traceback (most recent call last):
      File "/home/tboothby/sage-4.6.2/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/tboothby/sage-4.6.2/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/tboothby/sage-4.6.2/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_1[14]>", line 5, in <module>
        if coset_eq(p, r, gens):
    NameError: name 'coset_eq' is not defined
**********************************************************************
File "/cecm/home/tboothby/sage-4.6.2/devel/sage/sage/groups/perm_gps/partn_ref/double_coset.pyx", line 165:
    sage: len(reps)
Expected:
    8
Got:
    1
**********************************************************************
1 items had failures:
   8 of  16 in __main__.example_1
***Test Failed*** 8 failures.
For whitespace errors, see the file /home/tboothby/.sage//tmp/.doctest_double_coset.py
         [5.3 s]
sage -t  ".6.2/devel/sage/sage/groups/perm_gps/permgroup_element.pyx"
         [6.0 s]
sage -t  ".6.2/devel/sage/sage/groups/perm_gps/permgroup_morphism.py"
         [8.1 s]
sage -t  ".6.2/devel/sage/sage/groups/generic.py"
         [13.3 s]
sage -t  ".6.2/devel/sage/sage/stats/__init__.py"
         [0.2 s]
sage -t  ".6.2/devel/sage/sage/stats/intlist.pyx"
         [7.0 s]
sage -t  ".6.2/devel/sage/sage/stats/all.py"
         [0.2 s]
sage -t  ".6.2/devel/sage/sage/stats/test.py"

            if coset_eq(p, r, gens):
                found = True
                break
        if not found:
            reps.append(p)
Exception raised:
    Traceback (most recent call last):
      File "/home/tboothby/sage-4.6.2/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/tboothby/sage-4.6.2/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/tboothby/sage-4.6.2/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_1[14]>", line 5, in <module>
        if coset_eq(p, r, gens):
    NameError: name 'coset_eq' is not defined
**********************************************************************
File "/cecm/home/tboothby/sage-4.6.2/devel/sage/sage/groups/perm_gps/partn_ref/double_coset.pyx", line 165:
    sage: len(reps)
Expected:
    8
Got:
    1
**********************************************************************
1 items had failures:
   8 of  16 in __main__.example_1
***Test Failed*** 8 failures.
For whitespace errors, see the file /home/tboothby/.sage//tmp/.doctest_double_coset.py
         [5.3 s]
sage -t  ".6.2/devel/sage/sage/groups/perm_gps/permgroup_element.pyx"
         [6.0 s]
sage -t  ".6.2/devel/sage/sage/groups/perm_gps/permgroup_morphism.py"
         [8.1 s]
sage -t  ".6.2/devel/sage/sage/groups/generic.py"
         [13.3 s]
sage -t  ".6.2/devel/sage/sage/stats/__init__.py"
         [0.2 s]
sage -t  ".6.2/devel/sage/sage/stats/intlist.pyx"
         [7.0 s]
sage -t  ".6.2/devel/sage/sage/stats/all.py"
         [0.2 s]
sage -t  ".6.2/devel/sage/sage/stats/test.py"
         [4.8 s]
sage -t  ".6.2/devel/sage/sage/stats/basic_stats.py"        

                break
        if not found:
            reps.append(p)
Exception raised:
    Traceback (most recent call last):
      File "/home/tboothby/sage-4.6.2/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/tboothby/sage-4.6.2/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/tboothby/sage-4.6.2/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_1[14]>", line 5, in <module>
        if coset_eq(p, r, gens):
    NameError: name 'coset_eq' is not defined
**********************************************************************
File "/cecm/home/tboothby/sage-4.6.2/devel/sage/sage/groups/perm_gps/partn_ref/double_coset.pyx", line 165:
    sage: len(reps)
Expected:
    8
Got:
    1
**********************************************************************
1 items had failures:
   8 of  16 in __main__.example_1
***Test Failed*** 8 failures.
For whitespace errors, see the file /home/tboothby/.sage//tmp/.doctest_double_coset.py
         [5.3 s]
sage -t  ".6.2/devel/sage/sage/groups/perm_gps/permgroup_element.pyx"
         [6.0 s]
sage -t  ".6.2/devel/sage/sage/groups/perm_gps/permgroup_morphism.py"

... and it just keeps going. This machine is a little flaky, so maybe the problem is on my end. I'll try it on my laptop tonight.

comment:13 Changed 10 years ago by boothby

  • Status changed from needs_info to needs_review

comment:14 Changed 10 years ago by boothby

bah, that was pebcak, I was wrong to blame my poor computer. All tests pass, and this code looks really good!

comment:15 Changed 10 years ago by boothby

  • Status changed from needs_review to positive_review

... and, I forgot to change the status on that last comment. Does newbie behavior qualify me for a "first time review" in the changelog?

comment:16 Changed 10 years ago by jdemeyer

  • Milestone changed from sage-4.7 to sage-4.7.1
  • Reviewers set to Tom Boothby

comment:17 Changed 10 years ago by jdemeyer

  • Status changed from positive_review to needs_work

This needs to be rebased to sage-4.7.alpha4 (because of #10886).

comment:18 Changed 10 years ago by rlm

  • Status changed from needs_work to positive_review

A pretty trivial rebase, so I'm setting the status back to positive review.

comment:19 Changed 10 years ago by jdemeyer

  • Status changed from positive_review to needs_work
sage -t  -long -force_lib devel/sage/sage/groups/perm_gps/partn_ref/refinement_graphs.pyx
**********************************************************************
File "/mnt/usb1/scratch/jdemeyer/merger/sage-4.7.1.alpha0/devel/sage-main/sage/groups/perm_gps/partn_ref/refinement_graphs.pyx", line 764:
    sage: sage.groups.perm_gps.partn_ref.refinement_graphs.random_tests()  # long time (up to 25s on sage.math, 2011)
Expected:
    All passed: 640 random tests on 40 graphs.
Got:
    All passed: 200 random tests on 20 graphs.
**********************************************************************

comment:20 Changed 10 years ago by rlm

  • Status changed from needs_work to positive_review

Sorry about that, please try again!

comment:21 Changed 10 years ago by rlm

  • Description modified (diff)
  • Status changed from positive_review to needs_work

comment:22 Changed 10 years ago by rlm

  • Description modified (diff)
  • Status changed from needs_work to needs_review

I'm now convinced that the speed issues aren't a problem. The reason is that when we're computing an automorphism group we know that the stabilizer chain will be up to date below the current level, so we don't sift at all.

Just to make the argument convincing, I tested empty graphs (which have full symmetry group and would be most likely to show this problem if it were there):

sage: G = Graph(n)
sage: timeit('H = G.automorphism_group()')

The results, in milliseconds:

n:      |  10 |  20 |  30 |  40 |  50 |
--------|-----|-----|-----|-----|-----|
BEFORE: | 148 | 313 | 480 | 645 | 809 |
AFTER:  | 148 | 311 | 479 | 645 | 820 |

In other words, no change at all. For a more complicated graph of higher degree:

sage: G = graphs.HigmanSimsGraph()
sage: G.num_verts()
100
sage: G.num_edges()
1100

Before:

sage: timeit('H = G.automorphism_group()')
5 loops, best of 3: 274 ms per loop

After:

sage: timeit('H = G.automorphism_group()')
5 loops, best of 3: 267 ms per loop

So no significant changes. I'm going to ask Tom to re-review this patch, since it's been through a few changes since he gave it the thumbs up. Note that this patch applies cleanly to sage-4.7.alpha4.

comment:23 Changed 10 years ago by rlm

  • Description modified (diff)
  • Status changed from needs_review to needs_info

comment:24 Changed 10 years ago by rlm

  • Status changed from needs_info to needs_review

comment:25 Changed 10 years ago by rlm

  • Status changed from needs_review to needs_work

comment:26 Changed 10 years ago by rlm

  • Status changed from needs_work to needs_review

comment:27 Changed 10 years ago by boothby

  • Status changed from needs_review to positive_review

Tested against 4.7.alpha5, all tests pass!

comment:28 Changed 10 years ago by jdemeyer

  • Merged in set to sage-4.7.1.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:29 Changed 10 years ago by jdemeyer

  • Dependencies set to #10886
  • Description modified (diff)
  • Merged in sage-4.7.1.alpha0 deleted
  • Resolution fixed deleted
  • Status changed from closed to new

This patch conflicts with #10549.

comment:30 Changed 10 years ago by jdemeyer

  • Status changed from new to needs_review

comment:31 Changed 10 years ago by jdemeyer

  • Status changed from needs_review to needs_work

comment:32 Changed 10 years ago by rlm

  • Dependencies changed from #10886 to #10886, #10549

comment:33 Changed 10 years ago by boothby

Hold on, wasn't this merged? #10549 wasn't merged yet, why was this marked needs_work?

Changed 10 years ago by rlm

comment:34 Changed 10 years ago by rlm

  • Status changed from needs_work to needs_review

I've rebased the patch here on #10549...

comment:35 Changed 10 years ago by boothby

  • Status changed from needs_review to positive_review

works for me.

comment:36 Changed 10 years ago by jdemeyer

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