Changes between Version 21 and Version 22 of Ticket #10804


Ignore:
Timestamp:
04/15/11 17:29:04 (11 years ago)
Author:
rlm
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.

Legend:

Unmodified
Added
Removed
Modified
  • Ticket #10804

    • Property Status changed from needs_work to needs_review
  • Ticket #10804 – Description

    v21 v22  
    1 I'm glad I caught this in time...
    2 
    3 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.
     1Stabilizer chains and other improvements.