Opened 11 years ago
Closed 11 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: |
Description (last modified by )
Stabilizer chains and other improvements.
Attachments (1)
Change History (37)
comment:1 Changed 11 years ago by
- Summary changed from Small improvements to partn_ref functions to Improvements to partn_ref functions, including stabilizer chains
comment:2 Changed 11 years ago by
- Status changed from new to needs_review
comment:3 Changed 11 years ago by
- Status changed from needs_review to needs_work
comment:4 Changed 11 years ago by
- Status changed from needs_work to needs_review
comment:5 Changed 11 years ago by
apply trac_10804.patch
comment:6 Changed 11 years ago by
- Status changed from needs_review to needs_work
Just updated patch to deal with conflict coming from #10712.
comment:7 Changed 11 years ago by
- Status changed from needs_work to needs_review
comment:8 Changed 11 years ago by
How do I get the buildbot to try again?
comment:9 Changed 11 years ago by
- 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 11 years ago by
Due to #10712 you need 4.6.2.rc1 or later.
comment:11 Changed 11 years ago by
I just successfully applied this patch to sage-4.7.alpha3.
comment:12 Changed 11 years ago by
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 11 years ago by
- Status changed from needs_info to needs_review
comment:14 Changed 11 years ago by
bah, that was pebcak, I was wrong to blame my poor computer. All tests pass, and this code looks really good!
comment:15 Changed 11 years ago by
- 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 11 years ago by
- Milestone changed from sage-4.7 to sage-4.7.1
- Reviewers set to Tom Boothby
comment:17 Changed 11 years ago by
- Status changed from positive_review to needs_work
This needs to be rebased to sage-4.7.alpha4 (because of #10886).
comment:18 Changed 11 years ago by
- 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 11 years ago by
- 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 11 years ago by
- Status changed from needs_work to positive_review
Sorry about that, please try again!
comment:21 Changed 11 years ago by
- Description modified (diff)
- Status changed from positive_review to needs_work
comment:22 Changed 11 years ago by
- 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 11 years ago by
- Description modified (diff)
- Status changed from needs_review to needs_info
comment:24 Changed 11 years ago by
- Status changed from needs_info to needs_review
comment:25 Changed 11 years ago by
- Status changed from needs_review to needs_work
comment:26 Changed 11 years ago by
- Status changed from needs_work to needs_review
comment:27 Changed 11 years ago by
- Status changed from needs_review to positive_review
Tested against 4.7.alpha5, all tests pass!
comment:28 Changed 11 years ago by
- Merged in set to sage-4.7.1.alpha0
- Resolution set to fixed
- Status changed from positive_review to closed
comment:29 Changed 11 years ago by
- 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 11 years ago by
- Status changed from new to needs_review
comment:31 Changed 11 years ago by
- Status changed from needs_review to needs_work
comment:32 Changed 11 years ago by
- Dependencies changed from #10886 to #10886, #10549
comment:33 Changed 11 years ago by
Hold on, wasn't this merged? #10549 wasn't merged yet, why was this marked needs_work
?
Changed 11 years ago by
comment:34 Changed 11 years ago by
- Status changed from needs_work to needs_review
I've rebased the patch here on #10549...
comment:35 Changed 11 years ago by
- Status changed from needs_review to positive_review
works for me.
comment:36 Changed 11 years ago by
- Merged in set to sage-4.7.1.alpha2
- Resolution set to fixed
- Status changed from positive_review to closed
buildbot applied the wrong patch... let's see if it works next time.