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:  sage6.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 )
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 5 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:2 Changed 5 years ago by
 Description modified (diff)
comment:3 Changed 5 years ago by
 Description modified (diff)
comment:4 Changed 5 years ago by
 Branch set to u/slabbe/16352
 Commit set to 7956b77bd2eb0f3af9ab65450919d54c441e7f8f
comment:5 Changed 5 years ago by
 Keywords sd66 added
comment:6 Changed 5 years ago by
 Commit changed from 7956b77bd2eb0f3af9ab65450919d54c441e7f8f to 67e950df6d8ad3d35d3bac1113cba4091ef3fbf1
Branch pushed to git repo; I updated commit sha1. New commits:
67e950d  replacing TransitiveIdeal by RecursivelyEnumeratedSet in sage library

comment:7 Changed 5 years ago by
 Cc aschilling tscrim added
 Status changed from new to needs_review
comment:8 Changed 5 years ago by
 Description modified (diff)
comment:9 Changed 5 years ago by
 Status changed from needs_review to needs_work
Salut Sébastien,
Your branch is based on sage6.5!! Would you mind rebasing on sage6.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
comment:10 Changed 5 years ago by
 Commit changed from 67e950df6d8ad3d35d3bac1113cba4091ef3fbf1 to c272b7f4300d1f6c6f61322e29fc6910d8b66a03
comment:11 Changed 5 years ago by
 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 5 years ago by
Shouldn't you remove the second todo
in combinat/backtrack.py
?
comment:13 Changed 5 years ago by
 Commit changed from c272b7f4300d1f6c6f61322e29fc6910d8b66a03 to 0832bbc90db342d49171de443e1de1bed839e02a
Branch pushed to git repo; I updated commit sha1. New commits:
0832bbc  Trac #16352: removed a TODO in backtrac.py

comment:14 Changed 5 years ago by
 Milestone changed from sage6.4 to sage6.6
 Reviewers set to Vincent Delecroix
 Status changed from needs_review to positive_review
comment:15 Changed 5 years ago by
 Status changed from positive_review to needs_work
Merge conflict, try with 6.7.beta0 when its out
comment:16 Changed 5 years ago by
 Commit changed from 0832bbc90db342d49171de443e1de1bed839e02a to cecda3246fdbbf96cfb8461ee426dc9d079910ec
Branch pushed to git repo; I updated commit sha1. New commits:
cecda32  Trac #16352: solving conflicts with 6.7.beta0 in categories/finite_semigroups.py

comment:17 Changed 5 years ago by
 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)
comment:18 followup: ↓ 19 Changed 5 years ago by
 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 5 years ago by
 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 5 years ago by
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 5 years ago by
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 5 years ago by
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 5 years ago by
 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:
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

comment:24 followups: ↓ 26 ↓ 30 Changed 5 years ago by
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 5 years ago by
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 5 years ago by
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 followup: ↓ 28 Changed 5 years ago by
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 sagecombinatdevel ?
comment:28 in reply to: ↑ 27 ; followup: ↓ 29 Changed 5 years ago by
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 sagecombinatdevel ?
I am not sure. For postdocs with a permanent position?
comment:29 in reply to: ↑ 28 Changed 5 years ago by
By the way, Anne, have you seen my Fulbright call on sagecombinatdevel ?
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 5 years ago by
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?
comment:31 Changed 5 years ago by
 Commit changed from 1a1a6ccc6c1e731c2506cd527c7de6e331af4b0a to 0beb0422ac4482d67e670340ce7c26b2a927d916
Branch pushed to git repo; I updated commit sha1. New commits:
0beb042  trac #16352 more 'graded' in root_lattice_realizations.py

comment:32 Changed 5 years ago by
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 followups: ↓ 35 ↓ 36 Changed 5 years ago by
It seems that tests take slightly longer in root_lattice_realizations.py
with this branch..
comment:34 Changed 5 years ago by
 Milestone changed from sage6.6 to sage6.7
comment:35 in reply to: ↑ 33 Changed 5 years ago by
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
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
 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
 Branch changed from public/ticket/16352 to 0beb0422ac4482d67e670340ce7c26b2a927d916
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
replacing TransitiveIdeal by RecursivelyEnumeratedSet in sage library