Enumerate integer vectors modulo the action of a Permutation Group

[sagetrac-nborie]

The goal of this ticket is to enumerate integer vectors up to the action of a Permutation Group.

This will produced a Parent : infinite enumerated set whose element are integer vectors (as list of integer)

Apply

• attachment: trac_6812_integer_vectors_mod_permgroup-final.patch
• attachment: trac_6812-reviewer.patch

CC: @sagetrac-sage-combinat

Component: combinatorics

Keywords: enumeration, integer, list, permutation, group

Author: Nicolas Borie, Simon King

Reviewer: Karl-Dieter Crisman, Simon King, Nicolas Borie

Merged: sage-5.1.beta4

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

[sagetrac-nborie]

comment:3

I fixed some language mistakes. I already tell reviewers that there are probably still some typos, misunderstood or mistakes. I am sorry for that... It's hard!

[sagetrac-nborie]

comment:5

Refactoring :
-> I move the code in sage/combinat/invariant_ring_perm_gps (advise form Nicolas Thiéry)
-> I implemented a new class InfiniteEnumeratedSet (with category)

There is no a shortcut in sage to IntegerVectorsUptoPermGroup which is a user friendly parent (with hope).
This code stay really strongly connected to the Invariant theory and connected with a the graded algebras of multivariate polynomial view as combination of orbit sum. This really why the code enter this new folder : sage/combinat/invariant_ring_perm_gps (other things have to come here....)

[aghitza]

Changed keywords from enumaration, integer, list, permutation, group to enumeration, integer, list, permutation, group

[simon-king-jena]

comment:10

Hi!

This is not a review yet, just some remarks.

Indeed it seems to me that the comments and the documentation should be proof read by a native speaker. I am not a native speaker, I'm afraid.

I also suggest to rename some methods. For example, the purpose of "generate_list_of_sum" is not clear from that name:

• "generate" suggests a process. Therefore, I expected that the method would return an iterator. But in fact, an actual list is returned. A similar statement applies to "get_orbit". Why not simply "orbit"?
• "list_of_sums" is not clear at all. I mean, there is the notion of "partition", so, there is no reason to describe it as "list of sums". Of course, not all partitions are returned, but representatives for each permutation class of partitions.

So, I think "partition_class_representatives" or slightly less precise "partition_classes" would be clearer.

And "generate_canonicals": The return value is the list of canonical representatives of all children of the input. So, why not "children_representatives" or "canonical_children"?

Best regards, Simon

[sagetrac-nborie]

comment:11

Hi Simon,

Thank for these advises, I start a new cleanup and will update a better version shortly!

[sagetrac-nborie]

comment:12

The patch use now the generic code from Search Forest (breadth_first_search....). So this patch now depends on #8288

[simon-king-jena]

comment:81

With the patch that I almost finished (not posted yet), I get

sage: TEST_generation_orbit_sum(TransitiveGroup(8,1), verbose=True)
For G be the transitive group number 1 of degree 8
Cardinality of G : 8
  
Cardinality of secondary invariants : 5040
Number of canonical monomials under staircase : 18297
Total time : 1.49698710442
 ------------------------------------- 
(1.4969871044158936, 18297, 8)
sage: TEST_generation_orbit_sum(TransitiveGroup(9,1), verbose=True)
For G be the transitive group number 1 of degree 9
Cardinality of G : 9
  
Cardinality of secondary invariants : 40320
Number of canonical monomials under staircase : 153974
Total time : 13.5961458683
 ------------------------------------- 
(13.596145868301392, 153974, 9)
sage: TEST_generation_orbit_sum(TransitiveGroup(10,1), verbose=True)
For G be the transitive group number 1 of degree 10
Cardinality of G : 10
  
Cardinality of secondary invariants : 362880
Number of canonical monomials under staircase : 1452325
Total time : 140.386005878
 ------------------------------------- 
(140.3860058784485, 1452325, 10)
sage: G = TransitiveGroup(15,28)
sage: S = IntegerVectorsModPermutationGroup(G, max_part=1)
sage: timeit('S._cardinality_from_iterator()')
5 loops, best of 3: 415 ms per loop

Without the patch, I get

sage: TEST_generation_orbit_sum(TransitiveGroup(8,1), verbose=True)
For G be the transitive group number 1 of degree 8
Cardinality of G : 8
  
Cardinality of secondary invariants : 5040
Number of canonical monomials under staircase : 18297
Total time : 1.58537387848
 ------------------------------------- 
(1.585373878479004, 18297, 8)
sage: TEST_generation_orbit_sum(TransitiveGroup(9,1), verbose=True)
For G be the transitive group number 1 of degree 9
Cardinality of G : 9
  
Cardinality of secondary invariants : 40320
Number of canonical monomials under staircase : 153974
Total time : 15.0423038006
 ------------------------------------- 
(15.042303800582886, 153974, 9)
sage: TEST_generation_orbit_sum(TransitiveGroup(10,1), verbose=True)
For G be the transitive group number 1 of degree 10
Cardinality of G : 10
  
Cardinality of secondary invariants : 362880
Number of canonical monomials under staircase : 1452325
Total time : 162.007292032
 ------------------------------------- 
(162.00729203224182, 1452325, 10)
sage: G = TransitiveGroup(15,28)
sage: S = IntegerVectorsModPermutationGroup(G, max_part=1)
sage: timeit('S._cardinality_from_iterator()')
5 loops, best of 3: 933 ms per loop

So, it is roughly 10% to 50% improvement (even though I am currently still converting the set to sorted lists).

[sagetrac-nborie]

comment:82

Replying to @simon-king-jena:

There are two problems with the orbit() method:

        assert isinstance(v, (list, ClonableIntArray)), '%s shoud be a Python list or an element of %s'%(v, self)
        try:
            if v.parent() is self:
                return orbit(self._sgs, v)
        except:
            return orbit(self._sgs, self.element_class(self, v, check=False))

That means that None is returned if v happens to be a ClonableIntArray with a different parent. Shouldn't v be transformed into an element of self instead?

And is it really a good idea to convert v into an element of self without checking?

Yes, this piece of code is horribly ugly... The point is that the orbit method will work with any integer vector. v doesn't need to be canonical. I don't have a use case but I was thinking it would be more convenient to allow the user to use this method for any integer vector (canonical or not).

After for safety, I don't know the consequence of such a choice on the lung run.

Anyway, the test is_canonical should be very very much faster than the full expansion of an orbit and a user who want just an orbit can also compute his own function.

[simon-king-jena]

comment:83

Replying to @sagetrac-nborie:

Yes, this piece of code is horribly ugly... The point is that the orbit method will work with any integer vector. v doesn't need to be canonical. I don't have a use case but I was thinking it would be more convenient to allow the user to use this method for any integer vector (canonical or not).

Agreed. So, check=False should be fine.

But I do think that the orbit method should try to convert the input vector from a different parent into self, and should certainly not return "None".

Anyway, the test is_canonical should be very very much faster than the full expansion of an orbit

Of course. The algorithm for is_canonical looks almost the same as the full expansion of an orbit, but if it is in fact non-canonical then the function will return "False" before finishing the computation of the whole orbit.

By the way, I made some further tweaks and am now down to

sage: TEST_generation_orbit_sum(TransitiveGroup(8,1), verbose=True)
For G be the transitive group number 1 of degree 8
Cardinality of G : 8
  
Cardinality of secondary invariants : 5040
Number of canonical monomials under staircase : 18297
Total time : 1.43067121506
 ------------------------------------- 
(1.430671215057373, 18297, 8)
sage: TEST_generation_orbit_sum(TransitiveGroup(9,1), verbose=True)
For G be the transitive group number 1 of degree 9
Cardinality of G : 9
  
Cardinality of secondary invariants : 40320
Number of canonical monomials under staircase : 153974
Total time : 12.9384939671
 ------------------------------------- 
(12.938493967056274, 153974, 9)
sage: TEST_generation_orbit_sum(TransitiveGroup(10,1), verbose=True)
For G be the transitive group number 1 of degree 10
Cardinality of G : 10
  
Cardinality of secondary invariants : 362880
Number of canonical monomials under staircase : 1452325
Total time : 134.613152981
 ------------------------------------- 
(134.61315298080444, 1452325, 10)
sage: G = TransitiveGroup(15,28)
sage: S = IntegerVectorsModPermutationGroup(G, max_part=1)
sage: timeit('S._cardinality_from_iterator()')
5 loops, best of 3: 408 ms per loop

[sagetrac-nborie]

comment:84

Replying to @simon-king-jena:

But I do think that the orbit method should try to convert the input vector from a different parent into self, and should certainly not return "None".

Yes! None is not an option here. It must return a set or raise an error.

Of course. The algorithm for is_canonical looks almost the same as the full expansion of an orbit, but if it is in fact non-canonical then the function will return "False" before finishing the computation of the whole orbit.

And more than that, there is a king of gardener lemma inside the is_canonical method, the partial_lex comparison cut some branches of the orbit just by reading the first entries.

I also think the change from list to set produce more than x2 speedup, it is probably an exponential optimization, you should try before and after with graphs over 7 vertices :

sage: G = TransitiveGroup(21,38)          
sage: S = IntegerVectorsModPermutationGroup(G, max_part=1)
sage: time S._cardinality_from_iterator()
1044
Time: CPU 128.64 s, Wall: 136.10 s

It become to be a large test for this last one. (1044 symmetric matrices of size 7)

A student of Florent Hivert had to master project to parallelize SearchForest. Imagine what such module can need by inheritance... (with possible adaptations according changes of SearchForest)

[simon-king-jena]

comment:85

Without patch

sage: G = TransitiveGroup(21,38)
sage: S = IntegerVectorsModPermutationGroup(G, max_part=1)
sage: %time S._cardinality_from_iterator()
CPU times: user 54.56 s, sys: 0.02 s, total: 54.58 s
Wall time: 54.64 s
1044

With patch

sage: G = TransitiveGroup(21,38)
sage: S = IntegerVectorsModPermutationGroup(G, max_part=1)
sage: %time S._cardinality_from_iterator()
CPU times: user 9.36 s, sys: 0.01 s, total: 9.37 s
Wall time: 9.38 s
1044

So, yes, it scales well...

[simon-king-jena]

Speed-ups and doc fixes

[simon-king-jena]

comment:86

Attachment: trac_6812_reviewer.patch.gz

My patch is posted.

I hesitate to directly give it a positive review, since I somehow think that my patch is not just a reviewer patch (in spite of its name), because it changes the code non-trivially. So, please have a closer look on it!

Apart from the code changes, I went through the doc strings and tried to fix some grammar. But I am not a native speaker - take my changes with a grain of salt...

Apply trac_6812_integer_vectors_mod_permgroup.patch trac_6812_reviewer.patch]

[simon-king-jena]

Changed author from Nicolas Borie to Nicolas Borie, Simon King

[simon-king-jena]

comment:87

It seems the patch bot didn't get it.

Apply trac_6812_integer_vectors_mod_permgroup.patch trac_6812_reviewer.patch

[simon-king-jena]

Fixing a corner case, adding a doc test

[simon-king-jena]

comment:88

Attachment: trac_6812_reviewer2.patch.gz

I posted an additional reviewer patch. Namely, in my first patch, I forgot to add a doctest (shame on me), and consequently the code contained a bug: Integer vectores [1,2,3,1] and [1,2,3] would have compared equal. That' fixed and tested with the second reviewer patch.

For the record: I give a positive review to Nicolas' patch. My first reviewer patch needs review, I believe. The second patch is trivial enough to be considered a "real" reviewer patch.

Apply trac_6812_integer_vectors_mod_permgroup.patch trac_6812_reviewer.patch trac_6812_reviewer2.patch

[sagetrac-nborie]

comment:89

I was just double checking everything... You really done a lot of work finally, really much as I expected. My first patch was not so much ready.

As you posted another reviewer patch, once I will test everything, I will perhaps merge the 3 patches into a final one for the release manager.

[sagetrac-nborie]

comment:90

Attachment: trac_6812_integer_vectors_mod_permgroup-final.patch.gz

I am completely agree with all corrections and improvements provided by the two reviewer patches from Simon. I just merge them into my first proposition.

The current implementation pass all my corner cases around invariant theory. All tests pass, the documentation seems good to me and the code looks ready to go. I give the patch a positive review.

This is a three years old wanted improvement (beginning of my PhD thesis) and Sage changed so much these last three years.... Thanks you Simon for the hours you spent on finalizing this and thanks you Karl for English suggestions/corrections (especially those sent by mail 6 month ago...)

apply trac_6812_integer_vectors_mod_permgroup-final.patch

[sagetrac-nborie]

Changed reviewer from Karl-Dieter Crisman, Simon King to Karl-Dieter Crisman, Simon King, Nicolas Borie

[kcrisman]

comment:91

I'm adding a very minor review patch for a few issues. This is an amazing contribution!

Also, can you fix this?

# User "sage-combinat script"

[kcrisman]

comment:92

Attachment: trac_6812-reviewer.patch.gz

Patchbot apply trac_6812_integer_vectors_mod_permgroup-final.patch and trac_6812-reviewer.patch.

[jdemeyer]

Changed work issues from long time tests, information about listing infinite sets to none

[sagetrac-nborie]

comment:94

Karl reasonably didn't change the status of the ticket. I definitely agree with his patch which fix a lot of typos. Thanks a lot for this reading and the associated patch which applied smoothly on the previous one.

If needed (or just for convenience), the release manager can ask me merging the two patch, if not

apply trac_6812_integer_vectors_mod_permgroup-final.patch trac_6812-reviewer.patch

[jdemeyer]

Merged: sage-5.1.beta4

[nthiery]

comment:97

Congratulations Nicolas!

And thanks you all for getting this great new feature into Sage.