TransitiveIdeal -> RecursivelyEnumeratedSet in the sage library #16352

seblabbe · 2014-05-13T20:02:35Z

TransitiveIdeal and TransitiveIealGraded are used in the code of sage/combinat, sage/categories and sage/groups at least. These should be replaced by RecursivelyEnumeratedSet for speed improvements and also to avoid issues explained in #6637.

This is a follow up of #6637 where TransitiveIdeal and TransitiveIealGraded have been deprecated.

More precisely, occurences of

TransitiveIdeal(succ, seeds)
TransitiveIdealGraded(succ, seeds, max_depth)

are replaced (respectively) by:

RecursivelyEnumeratedSet(seeds, succ, structure=None, enumeration='naive')
RecursivelyEnumeratedSet(seeds, succ, structure=None, enumeration='breadth', max_depth=max_depth)

Indeed, deprecated TransitiveIdealGraded class was not using the hypothesis of being graded in its code. This is why the structure is set to None for now. Of course, if people have really a graded structure, then the structure argument should be set to 'graded'... For now, I am keeping the behavior like it was before and I am assuming the structure is not graded.

CC: @anneschilling @tscrim

Component: combinatorics

Keywords: sd66

Author: Sébastien Labbé

Branch/Commit: 0beb042

Reviewer: Vincent Delecroix, Frédéric Chapoton

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

The text was updated successfully, but these errors were encountered:

seblabbe · 2015-04-03T14:22:30Z

Commit: 7956b77

seblabbe · 2015-04-03T14:22:30Z

Branch: u/slabbe/16352

seblabbe · 2015-04-03T14:22:30Z

New commits:

`7956b77`	`replacing TransitiveIdeal by RecursivelyEnumeratedSet in sage library`

seblabbe · 2015-04-03T14:28:25Z

Changed keywords from none to sd66

sagetrac-git · 2015-04-03T14:40:50Z

Changed commit from 7956b77 to 67e950d

sagetrac-git · 2015-04-03T14:40:50Z

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

`67e950d`	`replacing TransitiveIdeal by RecursivelyEnumeratedSet in sage library`

videlec · 2015-04-10T18:24:51Z

comment:9

Salut Sébastien,

Your branch is based on sage-6.5!! Would you mind rebasing on sage-6.6.rc2?

Your iterator for infinite conjugacy classes is wrong

sage: a = matrix(ZZ,2,[1,1,0,1])
sage: b = matrix(ZZ,2,[1,0,1,1])
sage: G = MatrixGroup([a,b])
sage: a = G(a)
sage: b = G(b)
sage: C = ConjugacyClass(G, a)
sage: m1 = b * a * ~b
sage: m2 = ~b * a * b
sage: any(x == m1 for x in C)
True
sage: any(x == m2 for x in C)
... can wait forever ...

I think that adding also inverses of generators would work. I.e. just replace self._parent.gens() with self._parent.semigroup_generators(). And please add the above test in the documentation.

Best,
Vincent

sagetrac-git · 2015-04-12T13:51:44Z

Changed commit from 67e950d to c272b7f

sagetrac-git · 2015-04-12T13:51:44Z

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

`7d7ce65`	`Merge branch 'u/slabbe/16352' on top of sage-6.6.rc2`
`c272b7f`	`Trac #16352: Fixed referee comment`

seblabbe · 2015-04-12T13:54:13Z

comment:11

I used monoid_generators instead of semigroup_generators since it does not contain the identity. It is good because when the group is finite, it just returns the gens without their inverses.

Needs review again!

videlec · 2015-04-12T15:11:24Z

comment:12

Shouldn't you remove the second todo in combinat/backtrack.py?

sagetrac-git · 2015-04-12T16:14:15Z

Changed commit from c272b7f to 0832bbc

sagetrac-git · 2015-04-12T16:14:15Z

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

`0832bbc`	`Trac #16352: removed a TODO in backtrac.py`

videlec · 2015-04-12T21:28:57Z

Author: Sébastien Labbé

videlec · 2015-04-12T21:28:57Z

Reviewer: Vincent Delecroix

fchapoton · 2015-04-21T19:17:16Z

comment:20

I think that it is necessary to keep the "graded" keyword whenever TransitiveIdealGraded was used.
Otherwise, you are losing information, that may never come back.

So I propose to try putting "graded" wherever it already was, and see what happens.

seblabbe · 2015-04-22T08:35:09Z

comment:21

Ok, I agree, let's have this discussion. I first tried to replace every occurences of TransitiveIdealGraded by RecursivelyEnumeratedSet(..., structure='graded'), but then I got infinite loops.

The reason is that if a structure is graded, the enumeration currently done in RecursivelyEnumeratedSet saves in memory only two grades (the current one and the precedent one). If the structure is not graded and we use the graded argument for RecursivelyEnumeratedSet, then we may get infinite loops and elements that are genereated twice or infinitely often.

I won't have access to my machine until Tuesday for redoing those tests and tell you exactly where were the infinite loops happening...

Meanwhile, I would like to know for each occurences of TransitiveIdealGraded in the sage library weather the structure was really graded. I recall that TransitiveIdealGraded was not using the graded hypothesis at all since it was saving all of the generated elements.

A) There were three files where TransitiveIdealGraded was used:

File src/sage/categories/crystals.py

class Crystals(Category_singleton):
    class ParentMethods:
        def __iter__(self, index_set=None, max_depth=float('inf')):
            from sage.combinat.backtrack import TransitiveIdealGraded
            from sage.combinat.backtrack import TransitiveIdeal
            # was using both ???

        def subcrystal(self, index_set=None, generators=None, max_depth=float("inf"),
            from sage.combinat.backtrack import TransitiveIdealGraded

File src/sage/categories/highest_weight_crystals.py

class HighestWeightCrystals(Category_singleton):
    class ParentMethods:
        def __iter__(self, index_set=None, max_depth = float("inf")):
            from sage.combinat.backtrack import TransitiveIdealGraded

File src/sage/combinat/root_system/root_lattice_realizations.py

from sage.combinat.backtrack import TransitiveIdeal, TransitiveIdealGraded
class RootLatticeRealizations(Category_over_base_ring):
    class ParentMethods:
        @cached_method
        def positive_roots(self, index_set=None):
            return TransitiveIdealGraded(attrcall('pred', index_set=index_set),
                                         [self.simple_root(i) for i in index_set])
        def positive_real_roots(self):
            if self.cartan_type().is_finite():
                return tuple(TransitiveIdealGraded(attrcall('pred'), self.simple_roots()))

        @cached_method
        def positive_roots_parabolic(self, index_set = None):
            return TransitiveIdealGraded(parabolic_covers, generators)

    class ElementMethods:
        def orbit(self):
            return [x for x in TransitiveIdealGraded(attrcall('simple_reflections'), [self])]

        def greater(self):
            return [x for x in TransitiveIdeal(attrcall('succ'), [self])]

        def smaller(self):
            return [x for x in TransitiveIdeal(attrcall('pred'), [self])]

B) For reference, below are the files where only TransitiveIdeal was used.

File src/sage/groups/conjugacy_classes.py

class ConjugacyClass(Parent):
    @cached_method
    def set(self):
        from sage.combinat.backtrack import TransitiveIdeal

File src/sage/combinat/rigged_configurations/kr_tableaux.py

class KirillovReshetikhinTableaux(CrystalOfWords):
    def __iter__(self):
        from sage.combinat.backtrack import TransitiveIdeal

File src/sage/combinat/rigged_configurations/rigged_configurations.py

class RiggedConfigurations(Parent, UniqueRepresentation):
    def __iter__(self):
        from sage.combinat.backtrack import TransitiveIdeal

File src/sage/combinat/rigged_configurations/tensor_product_kr_tableaux.py

class TensorProductOfKirillovReshetikhinTableaux(FullTensorProductOfRegularCrystals):
    def __iter__(self):
        from sage.combinat.backtrack import TransitiveIdeal

File src/sage/combinat/root_system/pieri_factors.py

from sage.combinat.backtrack import TransitiveIdeal
class PieriFactors(UniqueRepresentation, Parent):
    @cached_method
    def elements(self):
        return TransitiveIdeal(attrcall('bruhat_lower_covers'), self.maximal_elements())

fchapoton · 2015-04-22T08:38:38Z

comment:22

I would say that crystal things are usually graded, but it would be better if crystal people can opt in and say their word about the matter. Travis ? Anne ?

fchapoton · 2015-04-22T14:37:35Z

Changed branch from u/slabbe/16352 to public/ticket/16352

fchapoton · 2015-04-22T14:37:35Z

comment:23

I have tried putting 'graded' in src/sage/categories/highest_weight_crystals.py
and it worked fine. I tested the file itself and the combinat/crystals folder.

I have tried putting 'graded' in src/sage/combinat/root_system/root_lattice_realizations.py and it worked fine. I tested the src/sage/combinat/root_system folder. Seems to be quicker by the way.

Let us see if the bot founds a problem with these two changes.

New commits:

`73b4ec2`	`Merge branch 'u/slabbe/16352' into 6.7.b2`
`1b831c1`	`trac #16352 'graded' in src/sage/categories/highest_weight_crystals.py`
`1a1a6cc`	`trac #16352 'graded' in root_lattice_realizations.py`

fchapoton · 2015-04-22T14:37:35Z

Changed commit from cecda32 to 1a1a6cc

fchapoton · 2015-04-22T16:05:02Z

comment:24

ok, no problem so far, the bot is happy.

There remains only the case of src/sage/categories/crystals.py

Anne, Travis ? What about affine crystals for example ? can we used "graded" ?

fchapoton · 2015-04-22T18:46:26Z

comment:25

I can now confirm that the each of the two remaining instances runs into infinite loops
when given the 'graded' argument.

Therefore this ticket is good to go.

If you agree, set this to positive review.

anneschilling · 2015-04-22T18:49:47Z

comment:26

Replying to @fchapoton:

ok, no problem so far, the bot is happy.

There remains only the case of src/sage/categories/crystals.py

Anne, Travis ? What about affine crystals for example ? can we used "graded" ?

Affine crystals are not necessarily graded. They can be cyclic.

fchapoton · 2015-04-22T19:55:34Z

comment:27

Thanks !

And are we safe with using 'graded' for highest weight crystals, as it seems ?

By the way, Anne, have you seen my Fulbright call on sage-combinat-devel ?

anneschilling · 2015-04-22T20:02:32Z

comment:28

Replying to @fchapoton:

Thanks !

And are we safe with using 'graded' for highest weight crystals, as it seems ?

Yes.

By the way, Anne, have you seen my Fulbright call on sage-combinat-devel ?

I am not sure. For postdocs with a permanent position?

fchapoton · 2015-04-22T20:05:24Z

comment:29

By the way, Anne, have you seen my Fulbright call on sage-combinat-devel ?

I am not sure. For postdocs with a permanent position?

Yes, hum. I am afraid that it is like looking for an element in the empty set. But maybe you could have somebody in mind.. Young, with a position, willing to spend time in Lyon, likes algebraic combinatorics. Not so easy to find, indeed.

seblabbe · 2015-04-22T20:48:10Z

comment:30

There remains only the case of src/sage/categories/crystals.py

There was four occurences of TransitiveIdealGraded in the file src/sage/combinat/root_system/root_lattice_realizations.py but you set structure='graded' in only one of them. Can you also check (mathematically + doctests) whether we can add the graded hypothesis for the three others also?

sagetrac-git · 2015-04-23T06:40:55Z

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

`0beb042`	`trac #16352 more 'graded' in root_lattice_realizations.py`

sagetrac-git · 2015-04-23T06:40:55Z

Changed commit from 1a1a6cc to 0beb042

fchapoton · 2015-04-23T06:42:26Z

comment:32

It seems to be ok for two of them, but not for the third one, which is an orbit.

But, damn, tests for this file are so long ...

fchapoton · 2015-04-23T11:44:00Z

comment:33

It seems that tests take slightly longer in root_lattice_realizations.py with this branch..

seblabbe · 2015-04-28T11:39:45Z

comment:35

Replying to @fchapoton:

It seems that tests take slightly longer in root_lattice_realizations.py with this branch..

Okay, I will take a look at this.

seblabbe · 2015-04-29T15:03:39Z

comment:36

Replying to @fchapoton:

It seems that tests take slightly longer in root_lattice_realizations.py with this branch..

Running sage -t src/sage/combinat/root_system/root_lattice_realizations.py three times on 6.7.beta3, I get:

[575 tests, 10.62 s]
[575 tests, 10.62 s]
[575 tests, 10.70 s]

Running the same command three times on the same file with this branch, I get:

[575 tests, 10.62 s]
[575 tests, 10.59 s]
[575 tests, 10.59 s]

So I can't confirm that tests take any longer with this ticket. Needs review!

fchapoton · 2015-04-29T18:37:23Z

Changed reviewer from Vincent Delecroix to Vincent Delecroix, Frédéric Chapoton

fchapoton · 2015-04-29T18:37:23Z

comment:37

ok, avanti !

vbraun · 2015-05-01T18:46:02Z

Changed branch from public/ticket/16352 to 0beb042

seblabbe added this to the sage-6.3 milestone May 13, 2014

seblabbe added c: combinatorics labels May 13, 2014

sagetrac-vbraun-spam mannequin modified the milestones: sage-6.3, sage-6.4 Aug 10, 2014

This comment has been minimized.

Sign in to view

seblabbe added the s: needs review label Apr 3, 2015

This comment has been minimized.

Sign in to view

videlec added s: needs work and removed s: needs review labels Apr 10, 2015

seblabbe added s: needs review and removed s: needs work labels Apr 12, 2015

videlec removed the s: needs review label Apr 12, 2015

videlec added the s: needs review label Apr 17, 2015

fchapoton modified the milestones: sage-6.6, sage-6.7 Apr 23, 2015

fchapoton added s: positive review and removed s: needs review labels Apr 29, 2015

vbraun removed the s: positive review label May 1, 2015

vbraun closed this as completed in a686bc9 May 1, 2015

nthiery mentioned this issue May 13, 2014

standardize the interface to TransitiveIdeal and friends #6637

Closed

TransitiveIdeal -> RecursivelyEnumeratedSet in the sage library #16352

TransitiveIdeal -> RecursivelyEnumeratedSet in the sage library #16352

Comments

seblabbe commented May 13, 2014

This comment has been minimized.

This comment has been minimized.

seblabbe commented Apr 3, 2015

seblabbe commented Apr 3, 2015

seblabbe commented Apr 3, 2015

seblabbe commented Apr 3, 2015

sagetrac-git mannequin commented Apr 3, 2015

sagetrac-git mannequin commented Apr 3, 2015

This comment has been minimized.

videlec commented Apr 10, 2015

sagetrac-git mannequin commented Apr 12, 2015

sagetrac-git mannequin commented Apr 12, 2015

seblabbe commented Apr 12, 2015

videlec commented Apr 12, 2015

sagetrac-git mannequin commented Apr 12, 2015

sagetrac-git mannequin commented Apr 12, 2015

videlec commented Apr 12, 2015

videlec commented Apr 12, 2015

fchapoton commented Apr 21, 2015

seblabbe commented Apr 22, 2015

fchapoton commented Apr 22, 2015

fchapoton commented Apr 22, 2015

fchapoton commented Apr 22, 2015

fchapoton commented Apr 22, 2015

fchapoton commented Apr 22, 2015

fchapoton commented Apr 22, 2015

anneschilling commented Apr 22, 2015

fchapoton commented Apr 22, 2015

anneschilling commented Apr 22, 2015

fchapoton commented Apr 22, 2015

seblabbe commented Apr 22, 2015

sagetrac-git mannequin commented Apr 23, 2015

sagetrac-git mannequin commented Apr 23, 2015

fchapoton commented Apr 23, 2015

fchapoton commented Apr 23, 2015

seblabbe commented Apr 28, 2015

seblabbe commented Apr 29, 2015

fchapoton commented Apr 29, 2015

fchapoton commented Apr 29, 2015

vbraun commented May 1, 2015