Opened 3 years ago
Last modified 10 days ago
#28539 needs_work task
Optimization for small permutation groups
Reported by: | vdelecroix | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | |
Component: | combinatorics | Keywords: | |
Cc: | tscrim, chapoton, sbrandhorst | Merged in: | |
Authors: | Vincent Delecroix | Reviewers: | |
Report Upstream: | N/A | Work issues: | |
Branch: | u/vdelecroix/28539 (Commits, GitHub, GitLab) | Commit: | 44bd8638bebbed543ff6f3c13846893ebca17f8b |
Dependencies: | #28544, #28652, #28653 | Stopgaps: |
Description (last modified by )
This ticket proposes micro optimizations for small permutation groups. The rationale is to handle the situation where we have billions of combinatorial objects and need to run through their automorphism groups most of which are trivial or let's say have size at most 100. An even more concrete application is given by admcycles MR 14 where there is an attempt to use graph automorphisms from Sage instead of a handmade implementation. This turns out to result in a major slowdown! For example
sage: from admcycles.admcycles import Hyperell sage: %time H = Hyperell(3)
takes 13.5 s on master but with MR 14 takes 17.4 s.
The profiling points to
- the constructor
__init__
ofPermutationGroupElement
: see #28652 - the
subgroup
method ofPermutationGroupElement
- the product
p1 * p2
whenp1
is a symmetric group element andp2
is a permutation group on the same domain: see #28652 (and also the bug #28544) __iter__
forPermutationGroupElement
(that currently involves computing a strong generating scheme): see #28652 and #28653
The optimizations proposed in this ticket noticeably speed up
the Hyperell(3)
computation mentioned above: from 17.4 s with
the previous Sage implementation or 13.5 s with admcycle's
previous handmade implementation, the timing goes down to 9 s.
Change History (25)
comment:1 Changed 3 years ago by
Branch: | → u/vdelecroix/28539 |
---|---|
Commit: | → f67ffcc1bcfcd460a6364948e0c875573f31675c |
comment:2 Changed 3 years ago by
Description: | modified (diff) |
---|
comment:3 Changed 3 years ago by
Commit: | f67ffcc1bcfcd460a6364948e0c875573f31675c → 0dbcc3383eac6497c1f7c0711e17b9e831cfeb14 |
---|
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
096659c | 28539: rework constructor of PermutationGroupElement
|
2d23d92 | 28539: faster multiplication and iteration
|
d00d370 | 28539: fix some doctests
|
5888249 | 28539: mark not tested bug tracked in #28544
|
0dbcc33 | 28539: reynolds operator and Galois conjugation
|
comment:4 Changed 3 years ago by
Cc: | chapoton sbrandhorst added |
---|---|
Status: | new → needs_review |
comment:6 Changed 3 years ago by
Commit: | 0dbcc3383eac6497c1f7c0711e17b9e831cfeb14 → 6ca3833fff437f52136279a0c6273954f093a8b1 |
---|
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
2c62905 | 28539: rework constructor of PermutationGroupElement
|
55d3e8a | 28539: faster multiplication and iteration
|
b027f91 | 28539: fix some doctests
|
5d77c23 | 28539: mark not tested bug tracked in #28544
|
6ca3833 | 28539: reynolds operator and Galois conjugation
|
comment:7 Changed 3 years ago by
Commit: | 6ca3833fff437f52136279a0c6273954f093a8b1 → 44bd8638bebbed543ff6f3c13846893ebca17f8b |
---|
Branch pushed to git repo; I updated commit sha1. New commits:
44bd863 | 28539: fix more doctests (python2 and python3)
|
comment:8 Changed 3 years ago by
Status: | needs_work → needs_review |
---|
comment:9 Changed 3 years ago by
Still failing. And proliferation of #py2 and # py3 does not seem to be a good solution.
comment:10 Changed 3 years ago by
Status: | needs_review → needs_info |
---|
I agree with Frédéric that adding a whole bunch of # py2
and # py3
tags is not a good solution. I am assuming this comes from this change:
- return self.iteration(algorithm="SGS") + if len(self._gens) == 1: + return self._iteration_monogen() + elif self.cardinality() <= 100: + return self.iteration(algorithm="BFS") + else: + return self.iteration(algorithm="SGS")
and the BFS
option calls RecursivelyEnumeratedSet
, which has consistency problems on Python3 IIRC. So we have to solve that bigger problem first.
I have some other comments:
I don't see the point of going to cycles just to convert back here:
return grp.element_class(self.to_cycles(singletons=False), grp, check=False)
I know this was already done, but it seems useless as the PermutationGroupElement
stores things internally as a list in essentially the same way.
I would probably Cythonize from_cycles
.
Is there a reason why _set_identity
and _set_list_images
are cpdef
and not just cdef
(which is faster when being called by C code)? By being cpdef
, they also need doctests.
comment:11 Changed 3 years ago by
Thanks for the feedback. I will cut the ticket and start by optimizing the constructor. Optimizing the iterator will be postponed to another one.
comment:12 Changed 3 years ago by
Dependencies: | → #28652 |
---|---|
Description: | modified (diff) |
Type: | enhancement → task |
comment:13 Changed 3 years ago by
Dependencies: | #28652 → #28544, #28652, #28653 |
---|---|
Description: | modified (diff) |
comment:14 follow-up: 15 Changed 3 years ago by
See also #28674 which should eventually solve the consistency problems of RecursivelyEnumeratedSet
.
comment:15 Changed 3 years ago by
Replying to gh-mwageringel:
See also #28674 which should eventually solve the consistency problems of
RecursivelyEnumeratedSet
.
I don't think that the enumeration order is relevant here. This is convenient for doctests and only shows the weakness of them.
comment:16 Changed 3 years ago by
Milestone: | sage-9.0 → sage-9.1 |
---|
Ticket retargeted after milestone closed
comment:17 Changed 3 years ago by
Milestone: | sage-9.1 → sage-9.2 |
---|
Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.
comment:18 Changed 2 years ago by
Description: | modified (diff) |
---|---|
Status: | needs_info → needs_work |
Supporting Python 2 is no longer needed now.
comment:19 Changed 2 years ago by
Milestone: | sage-9.2 → sage-9.3 |
---|
comment:20 Changed 2 years ago by
Milestone: | sage-9.3 → sage-9.4 |
---|
Setting new milestone based on a cursory review of ticket status, priority, and last modification date.
comment:21 Changed 19 months ago by
Milestone: | sage-9.4 → sage-9.5 |
---|
Setting a new milestone for this ticket based on a cursory review.
comment:22 Changed 14 months ago by
Milestone: | sage-9.5 → sage-9.6 |
---|
comment:23 Changed 10 months ago by
Milestone: | sage-9.6 → sage-9.7 |
---|
comment:24 Changed 5 months ago by
Milestone: | sage-9.7 → sage-9.8 |
---|
comment:25 Changed 10 days ago by
Milestone: | sage-9.8 |
---|
New commits:
WIP: make small perm group faster