Opened 16 months ago

Last modified 3 months ago

#28539 needs_work task

Optimization for small permutation groups

Reported by: vdelecroix Owned by:
Priority: major Milestone: sage-9.3
Component: combinatorics Keywords:
Cc: tscrim, chapoton, sbrandhorst Merged in:
Authors: Vincent Delecroix Reviewers:
Report Upstream: N/A Work issues:
Branch: u/vdelecroix/28539 (Commits) Commit: 44bd8638bebbed543ff6f3c13846893ebca17f8b
Dependencies: #28544, #28652, #28653 Stopgaps:

Description (last modified by slelievre)

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

Change History (19)

comment:1 Changed 16 months ago by vdelecroix

  • Branch set to u/vdelecroix/28539
  • Commit set to f67ffcc1bcfcd460a6364948e0c875573f31675c

New commits:

f67ffccWIP: make small perm group faster

comment:2 Changed 16 months ago by vdelecroix

  • Description modified (diff)

comment:3 Changed 16 months ago by git

  • Commit changed from f67ffcc1bcfcd460a6364948e0c875573f31675c to 0dbcc3383eac6497c1f7c0711e17b9e831cfeb14

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

comment:4 Changed 16 months ago by vdelecroix

  • Cc chapoton sbrandhorst added
  • Status changed from new to needs_review

comment:5 Changed 16 months ago by vdelecroix

  • Status changed from needs_review to needs_work

hmm some py2/py3 issue I guess.

comment:6 Changed 16 months ago by git

  • Commit changed from 0dbcc3383eac6497c1f7c0711e17b9e831cfeb14 to 6ca3833fff437f52136279a0c6273954f093a8b1

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

comment:7 Changed 16 months ago by git

  • Commit changed from 6ca3833fff437f52136279a0c6273954f093a8b1 to 44bd8638bebbed543ff6f3c13846893ebca17f8b

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

44bd86328539: fix more doctests (python2 and python3)

comment:8 Changed 16 months ago by vdelecroix

  • Status changed from needs_work to needs_review

comment:9 Changed 16 months ago by chapoton

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

comment:10 Changed 16 months ago by tscrim

  • Status changed from needs_review to 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 16 months ago by vdelecroix

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 15 months ago by vdelecroix

  • Dependencies set to #28652
  • Description modified (diff)
  • Type changed from enhancement to task

comment:13 Changed 15 months ago by vdelecroix

  • Dependencies changed from #28652 to #28544, #28652, #28653
  • Description modified (diff)

comment:14 follow-up: Changed 15 months ago by gh-mwageringel

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

comment:15 in reply to: ↑ 14 Changed 15 months ago by vdelecroix

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 13 months ago by embray

  • Milestone changed from sage-9.0 to sage-9.1

Ticket retargeted after milestone closed

comment:17 Changed 9 months ago by mkoeppe

  • Milestone changed from sage-9.1 to 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 5 months ago by slelievre

  • Description modified (diff)
  • Status changed from needs_info to needs_work

Supporting Python 2 is no longer needed now.

comment:19 Changed 3 months ago by mkoeppe

  • Milestone changed from sage-9.2 to sage-9.3
Note: See TracTickets for help on using tickets.