#10804: Improvements to partn_ref functions, including stabilizer chains
-----------------------------+----------------------------------------------
Reporter: rlm | Owner: rlm
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.7.1
Component: group theory | Keywords:
Author: Robert Miller | Upstream: N/A
Reviewer: Tom Boothby | Merged:
Work_issues: |
-----------------------------+----------------------------------------------
Changes (by rlm):
* status: needs_work => needs_review
Old description:
> I'm glad I caught this in time...
>
> The group output by the automorphism group function should be optional.
> Right now the stabilizer chain functions could seriously slow down some
> computations, such as automorphism groups of graphs of large degree. This
> is unnecessary and seriously bad. I'll update the patch and get it re-
> reviewed soon.
New description:
Stabilizer chains and other improvements.
--
Comment:
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.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10804#comment:22>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
