search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.44k stars 480 forks source link

Optimization for small permutation groups #28539

Open videlec opened 5 years ago

videlec commented 5 years ago

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 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.

Depends on #28544 Depends on #28652 Depends on #28653

CC: @tscrim @fchapoton @simonbrandhorst

Component: combinatorics

Author: Vincent Delecroix

Branch/Commit: u/vdelecroix/28539 @ 44bd863

Issue created by migration from https://trac.sagemath.org/ticket/28539

videlec commented 5 years ago

New commits:

f67ffccWIP: make small perm group faster
videlec commented 5 years ago

Commit: f67ffcc

videlec commented 5 years ago

Branch: u/vdelecroix/28539

videlec commented 5 years ago

Description changed:

--- 
+++ 
@@ -11,3 +11,5 @@
 - the `.subgroup` method of `PermutationGroupElement`
 - the product `p1 * p2` when `p1` is a symmetric group element and `p2` is a permutation group on the same domain
 - `__iter__` for `PermutationGroupElement` (that currently involves computing a strong generating scheme)
+
+Implementing these optimizations lower the `Hyperell(3)` computation mentioned above from 17.4 sec to 9 sec.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

096659c28539: rework constructor of PermutationGroupElement
2d23d9228539: faster multiplication and iteration
d00d37028539: fix some doctests
588824928539: mark not tested bug tracked in #28544
0dbcc3328539: reynolds operator and Galois conjugation
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from f67ffcc to 0dbcc33

videlec commented 5 years ago
comment:5

hmm some py2/py3 issue I guess.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

2c6290528539: rework constructor of PermutationGroupElement
55d3e8a28539: faster multiplication and iteration
b027f9128539: fix some doctests
5d77c2328539: mark not tested bug tracked in #28544
6ca383328539: reynolds operator and Galois conjugation
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from 0dbcc33 to 6ca3833

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

44bd86328539: fix more doctests (python2 and python3)
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 5 years ago

Changed commit from 6ca3833 to 44bd863

fchapoton commented 5 years ago
comment:9

Still failing. And proliferation of #py2 and # py3 does not seem to be a good solution.

tscrim commented 5 years ago
comment:10

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.

videlec commented 5 years ago
comment:11

Thanks for the feedback. I will cut the ticket and start by optimizing the constructor. Optimizing the iterator will be postponed to another one.

videlec commented 5 years ago

Dependencies: #28652

videlec commented 5 years ago

Description changed:

--- 
+++ 
@@ -7,7 +7,7 @@
 takes 13.5 sec on master but with MR 14 takes 17.4 sec.

 The profiling points to
-- the constructor `__init__` of `PermutationGroupElement`
+- the constructor `__init__` of `PermutationGroupElement`: see #28652
 - the `.subgroup` method of `PermutationGroupElement`
 - the product `p1 * p2` when `p1` is a symmetric group element and `p2` is a permutation group on the same domain
 - `__iter__` for `PermutationGroupElement` (that currently involves computing a strong generating scheme)
videlec commented 5 years ago

Description changed:

--- 
+++ 
@@ -9,7 +9,7 @@
 The profiling points to
 - the constructor `__init__` of `PermutationGroupElement`: see #28652
 - the `.subgroup` method of `PermutationGroupElement`
-- the product `p1 * p2` when `p1` is a symmetric group element and `p2` is a permutation group on the same domain
-- `__iter__` for `PermutationGroupElement` (that currently involves computing a strong generating scheme)
+- the product `p1 * p2` when `p1` is a symmetric group element and `p2` is a permutation group on the same domain: see #28652 (and also the bug #28544)
+- `__iter__` for `PermutationGroupElement` (that currently involves computing a strong generating scheme): see #28652 and #28653

 Implementing these optimizations lower the `Hyperell(3)` computation mentioned above from 17.4 sec to 9 sec.
videlec commented 5 years ago

Changed dependencies from #28652 to #28544, #28652, #28653

mwageringel commented 5 years ago
comment:14

See also #28674 which should eventually solve the consistency problems of RecursivelyEnumeratedSet.

videlec commented 5 years ago
comment:15

Replying to @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.

embray commented 4 years ago
comment:16

Ticket retargeted after milestone closed

mkoeppe commented 4 years ago
comment:17

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.

slel commented 4 years ago

Description changed:

--- 
+++ 
@@ -1,15 +1,32 @@
-This ticket stands for micro optimizations for small permutation groups. The rationale is to handle the situation where we have a billion of combinatorial objects and need to run through their automorphism groups most of which are trivial or let say, <= 100 elements. An even more concrete application is given by the [admcycles MR 14](https://gitlab.com/jo314schmitt/admcycles/merge_requests/14) where there is a tentative to use graph automorphisms from Sage instead of an handmade implementation. It turns out that this is slowing down a lot! For example
+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](https://gitlab.com/jo314schmitt/admcycles/merge_requests/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 sec on master but with MR 14 takes 17.4 sec.
+takes 13.5 s on master but with MR 14 takes 17.4 s.

 The profiling points to
-- the constructor `__init__` of `PermutationGroupElement`: see #28652
-- the `.subgroup` method of `PermutationGroupElement`
-- the product `p1 * p2` when `p1` is a symmetric group element and `p2` is a permutation group on the same domain: see #28652 (and also the bug #28544)
-- `__iter__` for `PermutationGroupElement` (that currently involves computing a strong generating scheme): see #28652 and #28653

-Implementing these optimizations lower the `Hyperell(3)` computation mentioned above from 17.4 sec to 9 sec.
+- the constructor `__init__` of `PermutationGroupElement`:
+  see #28652
+- the `subgroup` method of `PermutationGroupElement`
+- the product `p1 * p2` when `p1` is a symmetric group element
+  and `p2` is a permutation group on the same domain:
+  see #28652 (and also the bug #28544)
+- `__iter__` for `PermutationGroupElement` (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.
slel commented 4 years ago
comment:18

Supporting Python 2 is no longer needed now.

mkoeppe commented 3 years ago
comment:20

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

mkoeppe commented 3 years ago
comment:21

Setting a new milestone for this ticket based on a cursory review.