implementation of the cluster complex

[stumpc5]

The patch contains an implementation of the cluster complex for finite types.

sage: ClusterComplex(['A',3])
Cluster complex of type ['A', 3] with 9 vertices and 14 facets

The implementation depends on its realization as a subword complex.

[chapoton]

some comments :

there is a typo in "facet" at the beginning.

The examples are wrong, because they call "associahedron" which has nothing to do with the simplicial complex.

There is a "tba" in the examples section, that should be removed or replaced by a true example

You should include serious tests, like the computation of the homology of an example.

[chapoton]

Apply trac_10819-cluster_complex-cs.patch

[chapoton]

Hi,

1) here also, the header is not correct, you should add ticket number #10819.

2) this seems to be a real error, which appears several times :

AttributeError?: 'sage.matrix.matrix_integer_sparse.Matrix_integer_sparse' object has no attribute 'is_skew_symmetrizable'

[stumpc5]

Replying to chapoton:

1) here also, the header is not correct, you should add ticket number #10819.

I fixed it -- now I think I know what (not why) to do in order to pass the buildbot. Thanks!

2) this seems to be a real error, which appears several times :

There was one dependency missing, see #10298. This is like only knowing one linear extension of the ordering given by the dependencies -- so getting the dependencies is really try and error...

[chapoton]

Hello Christian. Here are two things that need to be corrected : 

1) type A_n is in n+3 sided polygon

2) formatting of doc is not correct in cartan_type

[stumpc5]

Replying to chapoton:

I really appreciate that you do some progress on these patches, thanks!

I think I will reimplement this patch using subword complexes rather than the cluster implementation. This will be much faster, and I don't expect that the cluster package will become part of main sage soon (see the dependency above). On the other hand, the subword complexes depend on my new implementation of finite reflection groups (#11187) which depends on the implementation of the universal cyclotomic field (#8327), so it will also be unlikely that it will get positively reviewed soon (and I see that all of them have rejects in the newest versions, so it will be an even longer way).

1) type A_n is in n+3 sided polygon 2) formatting of doc is not correct in cartan_type

I will update the patch fixing these issues.

Best, Christian

[stumpc5]

I fixed the two issues suggested by Frederic - what I do not like now is that the vertices are not positive roots anymore, but on the other hand the implementation is now valid for all finite Coxeter groups and also the multi-cluster complex can be constructed.

[davidloeffler]

Applying this and its dependencies to 5.0.beta11 results in a Sage install that won't start up, and hence fails every doctest in the library -- see patchbot logs.

[stumpc5]

Replying to davidloeffler:

Applying this and its dependencies to 5.0.beta11 results in a Sage install that won't start up, and hence fails every doctest in the library -- see patchbot logs.

Thanks for looking at it - for now, I would prefer if we postpone this patch, since I want to make some further improvements here.

Best, Christian

[chapoton]

Hello Christian,

I have made a git branch with one part of the patch, not touching the file cluster_seed.py in order to keep it as independent as possible.

I have also cleaned the code a little bit to make sur it passes the pyflakes and pep8 tests.

---

New commits:

​ffa07b5	#10819 Implementation of the cluster complex
​7a2d814	trac #10189 code clean-up (pyflakes, pep8, doc)

[chapoton]

New commits:

​fbd3246	Merge branch 'public/ticket/10189' into 6.10.beta2
​4f997a9	trac #10819 minor doc and code details

[git]

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

​3762d3e	Merge branch 'public/ticket/10819' into 7.1.b0
​615b67f	trac #10819 make it work by small changes

[chapoton]

This should be almost ready. Anybody available to have a look ?

[stumpc5]

Will do that.

[tscrim]

By almost ready, do you mean you will be making changes or that it just needs someone else to look it over?

[chapoton]

second thing: "it just needs someone else to look it over"

[tscrim]

Hey Christian and Frédéric, here are my comments:

• We should use the standard copyright template from ​​http://doc.sagemath.org/html/en/developer/coding_basics.html#headings-of-sage-library-code-files for all new files.
• The file should be added to the documentation.
• You should run the TestSuite on the cluster complex (often this is done in the __init__ tests).
• Error messages are typically not considered as sentences, so they should start with a lower case and not end with a period.
• Your __call__ does not appear to be idempotent, i.e., C(C((0,1))) should equal (or even better, be identical to) C((0,1)).
• You aren't properly using the category framework by not having ClusterComplexFacet as the Element attribute of ClusterComplex, and subsequently, you should use self.element_class in ClusterComplex.
• The methods of ClusterComplexFacet should at least have a one-line description of what the method does.

Some of these comments extend to the SubwordComplex, which might require a separate ticket to work on.

[git]

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

​ab38a11	Merge branch 'public/ticket/10819' of git://trac.sagemath.org/sage into u/stumpc5/10819
​b8b9e82	working on cleaning. Almost done with first round

[git]

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

​279a3da

removed one line in cluster seed that doesn't have anything to do with this ticket

[git]

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

​6d984c8

moved the file into the main combinat folder since the implementation does not have anything to do with cluster algebras anymore

[git]

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

​924a4d9	cleaning of the subword complex code
​c8e990c	Merge branch 't/20111/cleaning_of_subword_complex_code' into u/stumpc5/10819

[stumpc5]

Once the issues raised by Travis are solved in #20111, I will start looking at the actual content of this ticket...

[git]

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

​8b74225	fixed the parent type problem for subwordcomplexfacet
​471fb5d	Merge branch 't/20111/cleaning_of_subword_complex_code' into u/stumpc5/10819
​102bba1	finished the moving of the file, fixed all issues raised by Travis

[stumpc5]

So, technically I think the ticket is ready. But the documentation is still lousy. I will work on this a bit, but it would also be good if someone else takes a look!

---

New commits:

​8b74225	fixed the parent type problem for subwordcomplexfacet
​471fb5d	Merge branch 't/20111/cleaning_of_subword_complex_code' into u/stumpc5/10819
​102bba1	finished the moving of the file, fixed all issues raised by Travis

[git]

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

​a34e61c	Merge branch 'develop' into u/stumpc5/10819
​81171d7	added doctest for classcall, removed __eq__ for subword complexes
​190e8d2	Merge branch 'u/stumpc5/cleaning_of_subword_complex_code' of trac.sagemath.org:sage into public/combinat/cleaning_subword_complex_code-20111
​e8ad2a9	Fixing doctest errors and some cython tweaks.
​51d99ce	Merge branch 't/20111/cleaning_of_subword_complex_code' into u/stumpc5/10819

[stumpc5]

A few methods here depend on the not-yet-available implementation of reflection groups. Is it appropriate to put them into comments for now?

---

New commits:

​a34e61c	Merge branch 'develop' into u/stumpc5/10819
​81171d7	added doctest for classcall, removed __eq__ for subword complexes
​190e8d2	Merge branch 'u/stumpc5/cleaning_of_subword_complex_code' of trac.sagemath.org:sage into public/combinat/cleaning_subword_complex_code-20111
​e8ad2a9	Fixing doctest errors and some cython tweaks.
​51d99ce	Merge branch 't/20111/cleaning_of_subword_complex_code' into u/stumpc5/10819

[git]

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

​8878fdc

added a few tests and docs, commented 2 methods that depend on #11187

[tscrim]

In a perfect world, I would just put it directly in a branch which depends on the branch which implements the reflection groups. However, I know that can be a hassle. So if it is just few lines, then I would say yes it is okay, but make sure to state clearly which ticket will change those lines. If they are entire methods, I'm more reluctant, but again, I'm not strictly opposed to it...

[stumpc5]

I already pushed that change, so have a look and tell me what you think concretely there...

[stumpc5]

It is the two methods

+    # the following methods only make sense for the implementation using #11187:
+
+    #def upper_cluster(self):
+    #def product_of_upper_cluster(self):

I might actually implement them in a much slower way now, so I guess that might be the way to go... (and then commenting out the possible speed improvement with #11187)

[git]

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

​9f6fe10

added naive implementations of upper cluster and its product

[stumpc5]

Okay, I now use a naive implementation. But I am missing

AttributeError: 'CoxeterMatrixGroup_with_category' object has no attribute 'root_to_reflection'

Is there chance to get this method ? Otherwise, I will just delete that method needing this for now. I can then get it back later, if desired.

---

New commits:

​9f6fe10

added naive implementations of upper cluster and its product

[tscrim]

I think this is the best way to do things (at least because their implementation was simple).

Coxeter groups don't necessarily have all of the methods that Weyl groups have (since they are not tied to a particular root lattice). You should be able to use W.reflections()[beta] from #20027, and it should work as well for Weyl groups now that the behavior is consistent.

[tscrim]

However, that's not to say we should not implement a method root_to_reflection for (finite) Coxeter groups.

[git]

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

​e1f49c3

added product of upper cluster

[stumpc5]

New commits:

​e1f49c3

added product of upper cluster

[git]

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

​90b278a	Reversing the family for reflections.
​8c9b809	Making CoxeterGroup.reflections return a Family and some touchups.
​2595826	Removing caching of CoxeterGroup.positive_roots().
​7ed4c2a	Merge 7.1.beta6.
​3c32075	Fixing doctest failures in the thematic tutorials.
​35eb71c	Fixing some documentation and adding note to WeylGroup.reflections.
​46565ec	Missed (hopefully the last) one instance of the flipped keys/values.
​a93c402	Merge branch 'u/stumpc5/20027' into u/stumpc5/10819
​e72d0a3	removed product of upper cluster for now
​f1d1dff	product is back again, though not clear why

[stumpc5]

(hey travis, are you in korea at the moment?)

[git]

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

​28ebb5b

Some reviewer changes.

[git]

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

​3c7d5ae

Missed a trailing whitespace.

[tscrim]

Indeed, greetings from Korea.

I pushed some changes:

• I moved the description of the cluster complex to the class-level doc (instead of the module-level doc) so it can be visible from ClusterComplex?.
• I updated the reference bibliographic info.
• I added more tests to __classcall__ to make sure it covers all of the code paths/input formats.
• I removed the verbose output from TestSuite as these can change as tests get added and it's annoying to make these trivial changes all over Sage (not that it happens that often).
• Other misc tweaks.

If you agree with my changes, then you can set a positive review.