Opened 6 years ago

Closed 5 years ago

#16352 closed enhancement (fixed)

TransitiveIdeal -> RecursivelyEnumeratedSet in the sage library

Reported by: slabbe Owned by:
Priority: major Milestone: sage-6.7
Component: combinatorics Keywords: sd66
Cc: aschilling, ​tscrim Merged in:
Authors: Sébastien Labbé Reviewers: Vincent Delecroix, Frédéric Chapoton
Report Upstream: N/A Work issues:
Branch: 0beb042 (Commits) Commit: 0beb0422ac4482d67e670340ce7c26b2a927d916
Dependencies: Stopgaps:

Description (last modified by slabbe)

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.

Change History (38)

comment:1 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:2 Changed 6 years ago by slabbe

  • Description modified (diff)

comment:3 Changed 6 years ago by slabbe

  • Description modified (diff)

comment:4 Changed 6 years ago by slabbe

  • Branch set to u/slabbe/16352
  • Commit set to 7956b77bd2eb0f3af9ab65450919d54c441e7f8f

New commits:

7956b77replacing TransitiveIdeal by RecursivelyEnumeratedSet in sage library

comment:5 Changed 6 years ago by slabbe

  • Keywords sd66 added

comment:6 Changed 6 years ago by git

  • Commit changed from 7956b77bd2eb0f3af9ab65450919d54c441e7f8f to 67e950df6d8ad3d35d3bac1113cba4091ef3fbf1

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

67e950dreplacing TransitiveIdeal by RecursivelyEnumeratedSet in sage library

comment:7 Changed 6 years ago by slabbe

  • Cc aschilling ​tscrim added
  • Status changed from new to needs_review

comment:8 Changed 6 years ago by slabbe

  • Description modified (diff)

comment:9 Changed 6 years ago by vdelecroix

  • Status changed from needs_review to needs_work

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

Last edited 6 years ago by vdelecroix (previous) (diff)

comment:10 Changed 6 years ago by git

  • Commit changed from 67e950df6d8ad3d35d3bac1113cba4091ef3fbf1 to c272b7f4300d1f6c6f61322e29fc6910d8b66a03

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

7d7ce65Merge branch 'u/slabbe/16352' on top of sage-6.6.rc2
c272b7fTrac #16352: Fixed referee comment

comment:11 Changed 6 years ago by slabbe

  • Status changed from needs_work to needs_review

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!

comment:12 Changed 6 years ago by vdelecroix

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

comment:13 Changed 6 years ago by git

  • Commit changed from c272b7f4300d1f6c6f61322e29fc6910d8b66a03 to 0832bbc90db342d49171de443e1de1bed839e02a

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

0832bbcTrac #16352: removed a TODO in backtrac.py

comment:14 Changed 6 years ago by vdelecroix

  • Authors set to Sébastien Labbé
  • Milestone changed from sage-6.4 to sage-6.6
  • Reviewers set to Vincent Delecroix
  • Status changed from needs_review to positive_review

comment:15 Changed 6 years ago by vbraun

  • Status changed from positive_review to needs_work

Merge conflict, try with 6.7.beta0 when its out

comment:16 Changed 6 years ago by git

  • Commit changed from 0832bbc90db342d49171de443e1de1bed839e02a to cecda3246fdbbf96cfb8461ee426dc9d079910ec

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

cecda32Trac #16352: solving conflicts with 6.7.beta0 in categories/finite_semigroups.py

comment:17 Changed 6 years ago by slabbe

  • Status changed from needs_work to needs_review

(the code using TransitiveIdeal in the file finite_semigroups.py was deleted in 6.7.beta0, that was the reason for the conflict)

Last edited 6 years ago by slabbe (previous) (diff)

comment:18 follow-up: Changed 6 years ago by vdelecroix

  • Status changed from needs_review to needs_work

got

sage -t --long src/sage/combinat/dyck_word.py
**********************************************************************
File "src/sage/combinat/dyck_word.py", line 3501, in sage.combinat.dyck_word.DyckWords_size.__init__
Failed example:
    TestSuite(DyckWords(4,2)).run()
Expected nothing
--
    The following tests failed: _test_enumerated_set_iter_cardinality
**********************************************************************

comment:19 in reply to: ↑ 18 Changed 6 years ago by vdelecroix

  • Status changed from needs_work to needs_review

Replying to vdelecroix:

got

sage -t --long src/sage/combinat/dyck_word.py
...

Sorry, seems to be a problem on my computer.

Vincent

comment:20 Changed 6 years ago by chapoton

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.

comment:21 Changed 6 years ago by slabbe

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())

comment:22 Changed 6 years ago by chapoton

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 ?

comment:23 Changed 6 years ago by chapoton

  • Branch changed from u/slabbe/16352 to public/ticket/16352
  • Commit changed from cecda3246fdbbf96cfb8461ee426dc9d079910ec to 1a1a6ccc6c1e731c2506cd527c7de6e331af4b0a

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:

73b4ec2Merge branch 'u/slabbe/16352' into 6.7.b2
1b831c1trac #16352 'graded' in src/sage/categories/highest_weight_crystals.py
1a1a6cctrac #16352 'graded' in root_lattice_realizations.py

comment:24 follow-ups: Changed 6 years ago by chapoton

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" ?

comment:25 Changed 6 years ago by chapoton

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.

comment:26 in reply to: ↑ 24 Changed 6 years ago by aschilling

Replying to chapoton:

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.

comment:27 follow-up: Changed 6 years ago by chapoton

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 ?

comment:28 in reply to: ↑ 27 ; follow-up: Changed 6 years ago by aschilling

Replying to chapoton:

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?

comment:29 in reply to: ↑ 28 Changed 6 years ago by chapoton

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.

comment:30 in reply to: ↑ 24 Changed 6 years ago by slabbe

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?

Last edited 6 years ago by slabbe (previous) (diff)

comment:31 Changed 6 years ago by git

  • Commit changed from 1a1a6ccc6c1e731c2506cd527c7de6e331af4b0a to 0beb0422ac4482d67e670340ce7c26b2a927d916

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

0beb042trac #16352 more 'graded' in root_lattice_realizations.py

comment:32 Changed 6 years ago by chapoton

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

comment:33 follow-ups: Changed 6 years ago by chapoton

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

comment:34 Changed 6 years ago by chapoton

  • Milestone changed from sage-6.6 to sage-6.7

comment:35 in reply to: ↑ 33 Changed 6 years ago by slabbe

Replying to chapoton:

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

Okay, I will take a look at this.

comment:36 in reply to: ↑ 33 Changed 5 years ago by slabbe

Replying to chapoton:

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!

comment:37 Changed 5 years ago by chapoton

  • Reviewers changed from Vincent Delecroix to Vincent Delecroix, Frédéric Chapoton
  • Status changed from needs_review to positive_review

ok, avanti !

comment:38 Changed 5 years ago by vbraun

  • Branch changed from public/ticket/16352 to 0beb0422ac4482d67e670340ce7c26b2a927d916
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.