Opened 8 years ago

Closed 7 years ago

# Create a class for Coxeter matrices and types

Reported by: Owned by: Travis Scrimshaw Sage Combinat CC user major sage-6.10 group theory Coxeter groups, matrices, types, days64 Sage Combinat CC user, Darij Grinberg, Frédéric Chapoton, Jean-Philippe Labbé, Vivien Ripoll, Jean Michel, Nicolas M. Thiéry, Kevin Dilks Travis Scrimshaw, Jean-Philippe Labbé Jean-Philippe Labbé, Travis Scrimshaw N/A 5d188d4 #17990, #18152, #18743

This is a partial step towards #16126, but carries the necessary information to speed up #16630 when the input is given as a finite Cartan/Coxeter type.

It is possible to input numbers c<= -1 in the matrix to represent an infinite label, but with a different value in the bilinear form of the Tits representation.

The current implementation recognizes finite and affine types

Possible follow-up: -create an abstract class for Coxeter matrices and Cartan matrices? -Maybe change the name of CoxeterType?.py could to type_coxeter.py -Recognize more types

### comment:1 Changed 8 years ago by Travis Scrimshaw

Authors: → Travis Scrimshaw → public/combinat/coxeter_matrices-17798 → 5484c5d6077138d6ed79d5d19af38c1f1da120ea modified (diff) new → needs_review

Here's a working version that implements a class CoxeterMatrix and a generic CoxeterType coming from a CartanType. I also removed some deprecated code.

New commits:

 ​d31d286 Merge branch 'public/ticket/16630' of trac.sagemath.org:sage into public/combinat/coxeter_matrices-17798 ​1dddd20 Initial creation of the files. ​1aadfbe Merge branch 'develop' into public/combinat/coxeter_matrices-17798 ​f7fd3ac Merge branch 'develop' into public/combinat/coxeter_matrices-17798 ​5484c5d Making all doctests pass and removing some deprecated code.

### comment:2 Changed 8 years ago by Darij Grinberg

Some armchair reviewing (I am not sure if I am up to the actual job): You replaced the coxeter_matrix method on CartanType_abstract by a call to the CoxeterMatrix constructor, which is heavily ducktyped; you also removed the caching. Have you checked for speed regressions? I am also unhappy with the ducktyping since it is hard to debug. Does it makes sense to build a custom from_cartan_type constructor for CoxeterMatrix that bypasses most of the duckery?

### comment:3 Changed 8 years ago by Travis Scrimshaw

Actually, I will re-enable that caching; there was a time when I was considering the CoxeterMatrix to be a UniqueRepresentation, but it was easier to make it a usual class. However, for (better or) worse, pythonic code is ducktyped code since it is a weakly-typed language. Yet I tried to make case-by-case as much as possible (following what I did for CartanMatrix). There is some indirection done in CoxeterMatrix by converting the Cartan type to a Coxeter type, but I felt this was the best way to do things (at least with the current implementation). Yet this part isn't ducktyped. So what my long-winded reply is saying is I'm open to suggestions, but this is the local optimal code I'm at.

### comment:4 Changed 8 years ago by git

Commit: 5484c5d6077138d6ed79d5d19af38c1f1da120ea → 311eb184e6c37b7bfa0090468d79ca13509a63da

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

 ​311eb18 Fixing a pickling issue and some easy doctest failures.

### comment:5 Changed 8 years ago by git

Commit: 311eb184e6c37b7bfa0090468d79ca13509a63da → e61a4f3927c1d096f8ece1138ed33abbd928594d

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

 ​2ef21f0 Re-enable cache of coxeter_matrix() for CartanType_abstract. ​e61a4f3 Fixed import of numpy via UCF.

### comment:6 Changed 8 years ago by Darij Grinberg

I fear I cannot be of much help with this ticket, as I don't even know the difference between a Coxeter and a Cartan type... But please simplify that CoxeterMatrix.__init__. It is so complicated it is not pythonic in any good sense of this word. Python's the weak type system should not keep us from writing constructors (e.g., from_cartan_type) tailored to specific input data. I have no idea why catch-all constructors have become a standard in Sage, but this kind of programming gave us #17124 and probably some more ugliness I don't remember.

### comment:8 Changed 8 years ago by Jean-Philippe Labbé

In view of the tickets #15703, #16126, tt would be very good to include the possibility to have "generalized" Coxeter matrices.

The "generalized" means that for the infinite labels, we can put a real number <= -1 in the matrix.

Of course, this may be not so natural to have Coxeter matrices with such entries, but this will make life much much easier for the other tickets: being able to start with a matrix which encodes the "geometry" behind the matrix.

Ticket #16126 should be kind of parallel to this one.

If you think it is a good idea, I would try take the patch from here and make it possible to into such values.

### comment:10 Changed 8 years ago by Jean-Philippe Labbé

Dependencies: → #17990

### comment:11 Changed 8 years ago by Travis Scrimshaw

You can work around #17990 by explicitly specifying the base ring, but they only ring which has oo and the integers is the symbolic ring AFAIK. I think the best/long-term fix for allowing matrices with say ZZ[oo] is to construct a general parent for the ordered set R[oo] where R is any other ring (well ordered set where all things become less than infinity). Actually...you could probably use TropicalSemiring(ZZ) which does this (plus a bit more structure):

sage: T.zero()
+infinity
sage: T(2) < T.zero()
True
sage: T(2) > T.zero()
False


But the matrix space constructor requires a proper ring...which is where the real trouble probably is... I'm done rambling now.

### comment:12 Changed 8 years ago by git

Commit: e61a4f3927c1d096f8ece1138ed33abbd928594d → bdcd7a5dbfde7746a3e50a0d6e5d68fbbb05c2de

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

 ​bdcd7a5 Dirty version added possible entry <=-1 and affine types recognition

### comment:13 Changed 8 years ago by Jean-Philippe Labbé

Status: needs_review → needs_work

This is a dirty version so that you may have a look.

It includes now a classification of the affine types. I do not know exactly if this recognition algorithm was coded before. Anyways, I wrote it, it was a good exercise.

The code should be a cleaned and fully tested. Therefore I change the status to "needs_work".

If you have any suggestions, comments, I'm totally open!

### comment:14 Changed 8 years ago by git

Commit: bdcd7a5dbfde7746a3e50a0d6e5d68fbbb05c2de → 86b2d78d02683fee74b77742fee3ffd45ffb2e29

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

 ​86b2d78 Merge branch 'develop=6.6.b5' into t/17798/public/combinat/coxeter_matrices-17798

### comment:15 Changed 8 years ago by Jean-Philippe Labbé

Authors: Travis Scrimshaw → Travis Scrimshaw, Jean-Philippe Labbé Jean Michel added modified (diff) days64 added

### comment:16 Changed 8 years ago by git

Commit: 86b2d78d02683fee74b77742fee3ffd45ffb2e29 → f44e52fb40292424c439d90e29ddf0d3c0256b9f

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

 ​77189dd Corrected base ring of the Coxeter matrix ​f135c2e Corrected the bilinear form method ​f44e52f Now asks for a coercion map from base ring in bilinear form

### comment:17 Changed 8 years ago by Travis Scrimshaw

Since we are now wrapping a matrix, I think instead we should just make this either a list of lists or a dict of (i,j): val (where undefined entries are 2). That way we don't have to worry about the base ring or anything like that and we can (easily in the former case) pass that to the matrix constructor for those that want to do matrix operations. I'm actually leaning towards doing the dict method since most entires of a Coxeter matrix that people will use are 2 (at least, that's my current imagination). Thoughts?

### comment:18 Changed 8 years ago by Jean-Philippe Labbé

Probably a dictionary would be good. Though, we would have to write an appropriate string representation, this is not a big deal.

Adding a matrix method to Coxeter matrix may sound a bit absurd, but since the CoxeterMatrix? are more or less only to stock data, I believe it is ok. We may also make it cached...

### comment:19 Changed 8 years ago by Travis Scrimshaw

I doubt it's worth it to cache it...

Anyways, the string representation would probably be something like this (untested):

def _repr_(self):
w = max(len(str(v)) for row in self for v in row)
fstr = '{:>' + str(w) + '}' # should result in something like '{:>30}'
return '\n'.join('[' + ' '.join(fstr.format(v) for v in row) + ']' for row in self)


### comment:20 Changed 8 years ago by git

Commit: f44e52fb40292424c439d90e29ddf0d3c0256b9f → d0932c325ede70e04db1b659bcfbf86a7b691e06

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

 ​d0932c3 Removed inheritance from matrix, added methods and attributes

### comment:21 Changed 8 years ago by Jean-Philippe Labbé

Description: modified (diff) Coxeter, groups, matrices, types, days64 → Coxeter groups, matrices, types, days64

### comment:22 Changed 8 years ago by Jean-Philippe Labbé

Hi,

While having a look at the diff of the current patch, I saw that in CoxeterMatrixGroup? the method coxeter_graph is renamed by coxeter_diagram.

I would be tempted to have a clear distinction between dynkin diagram and coxeter graphs. Especially considering #16126 coming.

I guess eventually, there could be a common class on top of dynkin diagrams and coxeter graphs from which they inherit. But right now, it makes more sense to me to try to keep the convention coxeter graph vs dynkin diagram.

What do you think?

### comment:23 Changed 8 years ago by Travis Scrimshaw

There's some danger with calling it a Coxeter graph, as this was the first entry I got when Googling: http://en.wikipedia.org/wiki/Coxeter_graph. I don't believe this is what we want, and I believe the more common terminology is Coxeter diagram. This was my mistake in calling that method Coxeter graph, which I did without thinking/looking too much because it returns a Graph instance.

+1 for refactoring out common code between Coxeter and Dynkin diagrams, but IMO it doesn't need to be done here as we have #16126.

Last edited 8 years ago by Travis Scrimshaw (previous) (diff)

### comment:24 Changed 8 years ago by Jean-Philippe Labbé

Yes... It is a bummer that Coxeter does have a graph with its actual name tagged to it!

In the end, it is just a name, I guess we should try to be consistent in the naming convention since we are at it, and I'd like to know how to proceed...

As far as I know, Humphreys is careful not to give the graphs a name. On p.1 of Bjoerner&Brenti, they call it a "Coxeter graph (or Coxeter diagram)".

I would vote for Coxeter graph and Dynkin diagram since it emphasizes the difference between the two structures. About the confusion with the actual Coxeter graph, I believe it is not a so dreadful danger of confusion.

I think that the Coxeter graph is not so commonly used as to need it directly from the sage prompt, right?

Agreed with refactor common code later.

### comment:25 Changed 8 years ago by git

Commit: d0932c325ede70e04db1b659bcfbf86a7b691e06 → d3526392209128a21ee631666e406dd8fc74f631

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

 ​df3c69a Merge branch 6.7.beta3 into cox_matrices_trac ​764667e Corrected coding conventions ​f830a53 Made is_finite and is_affine attributes ​823c8f2 Added the rank as an attribute ​a5afb94 Subdivided the init (from matrix, graph, coxeter type) ​d352639 Added some tests

### comment:26 Changed 8 years ago by Jean-Philippe Labbé

Dependencies: #17990 → #17990, #18152 modified (diff)

Hi,

So I pushed some commits I did today.

There is still a lot to do, but it's progressing.

I tested the files and there were many tests that failed. I noticed that many of them fail because we removed the inheritance from matrices that was providing with equality tests.

I continue the coding... Don't hesitated if you have comments or suggestions!

### comment:27 follow-up:  28 Changed 8 years ago by Jean-Philippe Labbé

Hi,

Where should the function samples be placed?

If I put it in the abstract class CoxeterType?, it complains that it should be called on an instance.

JP

### comment:28 in reply to:  27 Changed 8 years ago by Nicolas M. Thiéry

Where should the function samples be placed?

If I put it in the abstract class CoxeterType?, it complains that it should be called on an instance.

It should be a staticmethod or classmethod..

### comment:29 Changed 8 years ago by git

Commit: d3526392209128a21ee631666e406dd8fc74f631 → fb77b786305566dff1200521cc8330cee7e6ec5b

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

 ​25a6f54 Added some values in the dictionnary of the matrix ​03b24b4 Edited the check coxeter type function ​532afda Added a samples method to CoxeterType ​d018e28 Added samples and made many tests pass ​fb77b78 PEP8 conventions

### comment:30 Changed 8 years ago by Jean-Philippe Labbé

Description: modified (diff)

Hi,

Now all test passes on the file coxeter_matrix, not on coxeter_type (3 failure caused by the old UCF implementation, I did not bother trying to correct them because of the new implementation in #18152). When it is going to be merged in a beta, I'll verify again.

The sample is supposed to contain all finite and affine coxeter types plus some more infinite types which are not affine.

I believe now the next step would be to go through the methods to double check that tests verify well the code.

About the renaming of the CoxeterType? file to type_coxeter, I believe it is better to keep it as it is now since it is similar to cartan_type.py

### comment:31 Changed 7 years ago by git

Commit: fb77b786305566dff1200521cc8330cee7e6ec5b → f2be73c3bdf6c76518e1899ee2753d8447ab58bf

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

 ​3262e43 Added tests ​a3c76fa Merge branch 'sage-6.8.beta2' into cox_matrices_trac ​f2be73c Made tests pass in coxeter_type

### comment:32 Changed 7 years ago by Jean-Philippe Labbé

Description: modified (diff) needs_work → needs_review

All tests pass on sage-6.8.beta2.

I would say that this version is ready for review.

### comment:33 Changed 7 years ago by Jean-Philippe Labbé

Status: needs_review → needs_work

Test fails in /sage/src/sage/groups/matrix_gps/coxeter_group.py

### comment:34 Changed 7 years ago by git

Commit: f2be73c3bdf6c76518e1899ee2753d8447ab58bf → 3d73c0b3e3cb85394ec21a3d24867072fc6b6e86

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

 ​3d73c0b Made tests pass in matrixcoxetergroup

### comment:35 Changed 7 years ago by Jean-Philippe Labbé

Status: needs_work → needs_review

There were some failing tests in the Coxeter groups as Matrix groups. They are solved now.

### comment:36 Changed 7 years ago by Frédéric Chapoton

Status: needs_review → needs_work

doc does not build

maybe because you need to use r""" when using latex command such as \infty or \ZZ

### comment:37 Changed 7 years ago by git

Commit: 3d73c0b3e3cb85394ec21a3d24867072fc6b6e86 → 19846a08c352ce041a3d5a8f2a6bf0757a91aae9

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

 ​19846a0 Fixed documentation

### comment:38 Changed 7 years ago by Jean-Philippe Labbé

Status: needs_work → needs_review

Should be fine now...

### comment:39 Changed 7 years ago by Jean-Philippe Labbé

There seems to be a test failing in the Coxeter group Category. I'll take care of that.

### comment:40 Changed 7 years ago by git

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

 ​32f2168 Made test pass in Category of Coxeter groups

### comment:41 Changed 7 years ago by git

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

 ​522f9a4 Added doctest coverage to __repr__

### comment:42 Changed 7 years ago by git

Commit: 522f9a4cc0c316553b1e9d34c74776223494d865 → df35a439d6b5b7f184f0d72647d1f5ae86e324aa

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

 ​9afb736 Merge branch 'public/combinat/coxeter_matrices-17798' of trac.sagemath.org:sage into public/combinat/coxeter_matrices-17798 ​df35a43 Implement a better API for pickling/classcall for Cartan/Coxeter matrices.

### comment:43 Changed 7 years ago by git

Commit: df35a439d6b5b7f184f0d72647d1f5ae86e324aa → eab7426aa7b98be3c11cce1bba68e035c9bf4b0c

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

 ​20bd15d Added support for _repr_option('ascii_art'). ​56307d7 Merge branch 'public/interfaces/repr_option_ascii_art-18743' into public/combinat/coxeter_matrices-17798 ​eab7426 Fixing doctest from #18743.

### comment:44 Changed 7 years ago by Travis Scrimshaw

Dependencies: #17990, #18152 → #17990, #18152, #18743 → Jean-Philippe Labbé, Travis Scrimshaw

I've made my round of changes. If your happy with my changes, then we can set a positive review (since we've done a cross-review, unless of course someone has any objections).

### comment:45 Changed 7 years ago by Jean-Philippe Labbé

Hi Travis,

Thanks for the recent changes! They look good to me.

The patchbot should check if everything is ok and then we could set it to positive review.

### comment:46 Changed 7 years ago by Jean-Philippe Labbé

Hi,

I have difficulty reading what the failure in "startup-module" really is.

What is wrong?

### comment:47 Changed 7 years ago by Travis Scrimshaw

So it is saying that we are importing 5 new modules at startup. I think we should lazily import the coxeter_matrix and coxeter_type. The other option is to change this to a lazy import: from sage.graphs.generators.basic import CycleGraph.

Also the test failures in src/sage/interfaces/psage.py are due to an old version of #18743, but we have to figure why the CoxeterGroup element doesn't work properly. It might be an issue with comparisons, but it might be with the pickling...

### comment:48 Changed 7 years ago by Travis Scrimshaw

Status: needs_review → needs_work

So the problem is that the type recognition does not support relabelings:

sage: M = CoxeterMatrix([[1,3,2],[3,1,6],[2,6,1]])
sage: M
[1 3 2]
[3 1 6]
[2 6 1]
sage: M.coxeter_type()
Coxeter type of ['G', 2, 1]
[1 2 3]
[2 1 6]
[3 6 1]


The type should be relabeled to (1, 2, 3) and does not necessarily correspond to (0, 1, 2).

### comment:49 Changed 7 years ago by git

Commit: eab7426aa7b98be3c11cce1bba68e035c9bf4b0c → c9125e118a46737c51400bbae469a6aa62b3014b

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

 ​f0ee04a Merge branch 'public/combinat/coxeter_matrices-17798' of trac.sagemath.org:sage into public/combinat/coxeter_matrices-17798 ​6285150 Merge branch 'public/interfaces/repr_option_ascii_art-18743' of trac.sagemath.org:sage into public/interfaces/repr_option_ascii_art-18743 ​7bc49f5 Adding _repr_option to the interface element to avoid __getattr__. ​27a2847 Merge branch 'public/interfaces/repr_option_ascii_art-18743' of trac.sagemath.org:sage into public/combinat/coxeter_matrices-17798 ​c9125e1 Implement better type recognition using (di)graph isomorphism testing.

### comment:50 Changed 7 years ago by Travis Scrimshaw

Milestone: sage-6.6 → sage-6.8 needs_work → needs_review

As per my discussion with Jean-Philippe at FPSAC, I've implemented type-checking using graph isomorphism testing, which fixes the relabeling issue (it feels more efficient). Just needs a quick check (and the remaining dependency should be a trivial review, but it needs a reviewer).

Last edited 7 years ago by Travis Scrimshaw (previous) (diff)

### comment:51 Changed 7 years ago by Jean-Philippe Labbé

It seems that there was an error when building sage.

I looked at the crash report and there is an ImportError?:

"ImportError?: No module named inherit_comparison"

Which seems to be the source of the problem.

Any idea?

### comment:52 Changed 7 years ago by Travis Scrimshaw

I don't get this error, and I have no idea what's going on with your build (the error occurs before startup, right?). You only get it with this patch? What is the output of git diff --name-status develop?

### comment:53 Changed 7 years ago by Jean-Philippe Labbé

I pulled the latest version of develop and it compiled fine. (make distclean && make). Then, I checked out the branch and pulled the latest changes and then built.

The output of git diff --name-status develop gives my a relatively long list of (python, rst, txt, etc.) files. Are you looking for something in particular? It may be difficult to track.

I'll just make distclean and compile again.

I'll report about the latest changes in the ticket then.

### comment:54 Changed 7 years ago by Travis Scrimshaw

git diff --name-status develop shows the files which are different compared to develop, so assuming you have merged in the latest develop to both branches, it should give a comprehensive list of changes.

However I'm not quite sure what you're saying. Did you already merge in the latest develop and tested this branch on top of that and it didn't work?

### comment:55 Changed 7 years ago by Jean-Philippe Labbé

I just went directly on the branch (without merging the very latest version of develop) and compiled. Now I get an error in building the doc, because some folder does not exist.

I will just do a merge with the latest develop and compile again. This seems to be a reasonable option now.

### comment:56 Changed 7 years ago by git

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

 ​cd7d946 Merge branch 'sage6.8.rc0' into cox_matrices_trac

### comment:57 Changed 7 years ago by Jean-Philippe Labbé

All test passed on sage6.8.rc0

If the bot is happy I would set the patch to positive review. I am satisfied with the changes in the type recognition algorithm.

### comment:58 Changed 7 years ago by Travis Scrimshaw

Thank you for your work on this. The bot seems to be down for the time being, but it did pass on the previous version. Do you think you could also give a quick review of the dependency too?

Let me know when the followups are ready for review.

### comment:59 Changed 7 years ago by Jean-Philippe Labbé

Milestone: sage-6.8 → sage-6.9

### comment:60 Changed 7 years ago by Kevin Dilks

Patchbot says this code now causes some sort of infinite recursion on crystals.

### comment:61 Changed 7 years ago by Jean-Philippe Labbé

Dear Kevin,

Could you give some minimal not-working example of the problem?

### comment:63 Changed 7 years ago by git

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

 ​86a3c73 Merge branch 'public/combinat/coxeter_matrices-17798' of trac.sagemath.org:sage into ticket17798 ​e2ad156 Made two tests pass

### comment:64 Changed 7 years ago by Travis Scrimshaw

Kevin and I tried it out and couldn't reproduce the patchbot results.

### comment:65 Changed 7 years ago by Jean-Philippe Labbé

All tests seem to pass on sage-6.9 on my computer right now...

There were two tests failing on 6.9 that I fixed in the last commit.

### comment:66 Changed 7 years ago by Kevin Dilks

Tests on the files you changed pass, but it's causing some sort of infinite recursion on crystals. It's also causing some doctests to fail in cluster_seed().

sage -t --long src/sage/combinat/rigged_configurations/kr_tableaux.py  # 5 doctests failed
sage -t --long src/sage/combinat/rigged_configurations/rigged_configurations.py  # 7 doctests failed
sage -t --long src/sage/combinat/crystals/littelmann_path.py  # 3 doctests failed
sage -t --long src/sage/combinat/crystals/kirillov_reshetikhin.py  # 34 doctests failed
sage -t --long src/sage/combinat/cluster_algebra_quiver/cluster_seed.py  # 3 doctests failed
sage -t --long src/sage/combinat/rigged_configurations/rigged_configuration_element.py  # 1 doctest failed
sage -t --long src/sage/combinat/crystals/kyoto_path_model.py  # 3 doctests failed
sage -t --long src/sage/combinat/crystals/tensor_product.py  # 6 doctests failed
sage -t --long src/doc/en/thematic_tutorials/lie/affine_finite_crystals.rst  # 9 doctests failed
sage -t --long src/sage/combinat/root_system/cartan_type.py  # 1 doctest failed
sage -t --long src/sage/combinat/root_system/dynkin_diagram.py  # 1 doctest failed
sage -t --long src/sage/combinat/crystals/subcrystal.py  # 2 doctests failed
sage -t --long src/sage/combinat/crystals/virtual_crystal.py  # 4 doctests failed


You can ignore two failing doctests in root system, since I believe you just fixed those.

### comment:67 Changed 7 years ago by Jean-Philippe Labbé

Excellent! On it...!

### comment:68 Changed 7 years ago by Kevin Dilks

Travis is working on the issue with crystals now.

The tests that are failing in cluster_seed.py are under universal_extension(), which mentions that it gets the almost positive co-roots in a non-elegant way and non-standard order, so it may have to be rewritten.

### comment:69 Changed 7 years ago by git

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

 ​e6971e7 Make sure that indexing sets are passed along by subtype.

### comment:70 Changed 7 years ago by git

Commit: e6971e72338766abeda78fbaecd3be863a4041e9 → 4ca434574be9cfc2412a90113cf98968ae347247

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

 ​4ca4345 Making KR crystals more robust against relabeling.

### comment:71 Changed 7 years ago by Travis Scrimshaw

Okay, so the issue which caused the crystals to infinitely recurse is that the type recognition via subtype() did not pass along the appropriate labels (I'm not 100% sure what was calling subtype()...). In particular, classical types got relabeled by [0, 1, ...], and KR crystals were sensitive to the labellings. I fixed this (which was indicated by the fact that we now had to add the relabel to the subtype test) and in a separate commit I made the KR crystals less sensitive to relabellings (but fixing them altogether is an entirely different issue and would deserve a separate ticket). What had changed from our previous version was that our type recognition system did not support relabelling, but now using Dynkin diagrams it does.

Unfortunately this did not fix the issue for cluster seeds.

### comment:72 Changed 7 years ago by git

Commit: 4ca434574be9cfc2412a90113cf98968ae347247 → 226f47a20a662f387b74b03941a55962db3c68e6

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

 ​226f47a Making KR crystals more robust against relabeling.

### comment:73 Changed 7 years ago by git

Commit: 226f47a20a662f387b74b03941a55962db3c68e6 → fe2e01fd1061c8675215050bcc120dd93dd83a5e

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

 ​fe2e01f Fixed cluster seed not expicitly specifying an indexing set.

### comment:74 follow-up:  77 Changed 7 years ago by Travis Scrimshaw

The fix was that the cluster seed code was assuming the indexing set of a Cartan matrix constructed from a matrix that was of finite type had the standard finite type indexing set of [1, 2, ..., n]. I fixed this by explicitly specifying this to be the index set of the Cartan matrix.

This brings up a point that might need a discussion: Should the index set of a matrix representing a finite type Cartan matrix be by default 1-based or 0-based? The argument for being 1-based is above, a natural assumption on index sets of finite type. Why we should have 0-based is consistency with the rest for default labellings and it agrees with the indexing set of the given matrix (and everything in python is 0-based). Thoughts?

### comment:75 Changed 7 years ago by git

Commit: fe2e01fd1061c8675215050bcc120dd93dd83a5e → e659186e20bbb4b4a942008dff32901659e42503

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

 ​e659186 Some pyflakes cleanup.

### comment:76 Changed 7 years ago by Travis Scrimshaw

This should at least get rid of the startup imports of the graph generators stuff.

Last edited 7 years ago by Travis Scrimshaw (previous) (diff)

### comment:77 in reply to:  74 ; follow-up:  78 Changed 7 years ago by Jean-Philippe Labbé

The fix was that the cluster seed code was assuming the indexing set of a Cartan matrix constructed from a matrix that was of finite type had the standard finite type indexing set of [1, 2, ..., n]. I fixed this by explicitly specifying this to be the index set of the Cartan matrix.

Is my last edition to make test pass consistent with this change?

This brings up a point that might need a discussion: Should the index set of a matrix representing a finite type Cartan matrix be by default 1-based or 0-based? The argument for being 1-based is above, a natural assumption on index sets of finite type. Why we should have 0-based is consistency with the rest for default labellings and it agrees with the indexing set of the given matrix (and everything in python is 0-based). Thoughts?

I would say 1-based for finite type since they probably have a labeling hardcoded when dealing with them through Cartan matrices and Coxeter Types.

I would say 0-based whenever there is no labels specified and it comes through a CoxeterMatrix? type, eventhough the type is finite.

But this probably causes trouble?

In a sense, having a "relabel" method somehow means that we have a canonical way of doing and then whenever it is not that one, it means that it was relabeled.

Does that make sense?

### comment:78 in reply to:  77 Changed 7 years ago by Travis Scrimshaw

Milestone: sage-6.9 → sage-6.10

The fix was that the cluster seed code was assuming the indexing set of a Cartan matrix constructed from a matrix that was of finite type had the standard finite type indexing set of [1, 2, ..., n]. I fixed this by explicitly specifying this to be the index set of the Cartan matrix.

Is my last edition to make test pass consistent with this change?

One of the trivial doctest failures because of subtype actually was the one indicating the problem, but that was because I wasn't passing the indexing set as I should have been. We should check for CoxeterMatrix and CoxeterType that labelings work as they should.

This brings up a point that might need a discussion: Should the index set of a matrix representing a finite type Cartan matrix be by default 1-based or 0-based? The argument for being 1-based is above, a natural assumption on index sets of finite type. Why we should have 0-based is consistency with the rest for default labellings and it agrees with the indexing set of the given matrix (and everything in python is 0-based). Thoughts?

I would say 1-based for finite type since they probably have a labeling hardcoded when dealing with them through Cartan matrices and Coxeter Types.

I would say 0-based whenever there is no labels specified and it comes through a CoxeterMatrix? type, eventhough the type is finite.

But this probably causes trouble?

I was talking about when no labels are given, and it sounds like we are in agreement. However there is some code that doesn't use the indexing set, but instead a range under the assumption that the indexing set is (1, 2, ..., n). I'm still partially debating whether or not to change the cluster seed code as well to help make it robust (although it is somewhat moot because we now specify the indexing set).

In short, it causes trouble for people's code that had made an assumption about the indexing set before.

In a sense, having a "relabel" method somehow means that we have a canonical way of doing and then whenever it is not that one, it means that it was relabeled.

Does that make sense?

Yes it makes sense. In a way, I agree with you. However, we must define a canonical way of labeling in order to implement the database of Cartan types. Also we can relabel relabeled types.

### comment:79 follow-up:  80 Changed 7 years ago by Nicolas M. Thiéry

For whatever it's worth, the strategy I followed in the root system code was to never make any assumption on the indexing set I.

For Cartan matrices, the situation is similar with that of matrices of module morphisms. Ideally they would be indexed by I; however we don't really have yet a good matrix class supporting arbitrary indexing (or do we? Panda's DataFrame? class [1] could be an interesting starting point!). That's in particular why I avoided using the Cartan matrix as much as possible in computations, preferring instead the Dynkin diagram.

Until we have a class for matrices with arbitrary indexing, I believe we should stick to what has been done so far: index the matrix by 0,...,|I|-1 with row/column i corresponding to the i-th element of the indexing set I (following Python's convention: i=0 gives the first element).

Cheers,

Nicolas

### comment:80 in reply to:  79 Changed 7 years ago by Travis Scrimshaw

Until we have a class for matrices with arbitrary indexing, I believe we should stick to what has been done so far: index the matrix by 0,...,|I|-1 with row/column i corresponding to the i-th element of the indexing set I (following Python's convention: i=0 gives the first element).

So my takeaway from what you're saying is that you also agree that the default indexing set for Cartan matrices should be 0, 1, ..., |I|-1. Is that correct? We aren't changing the actual __getitem__ in this ticket (which always uses 0, 1, ...., |I|-1). The failures in cluster seed was caused by the root system having the "wrong" indexing set.

### comment:81 follow-ups:  82  89 Changed 7 years ago by Jean-Philippe Labbé

All tests now pass on my sage-6.9 version (root_system, rigged_configuration, cluster_algebra_quiver, crystals folders)

Now, what is this startup module error in the patchbot??

### comment:82 in reply to:  81 Changed 7 years ago by Travis Scrimshaw

All tests now pass on my sage-6.9 version (root_system, rigged_configuration, cluster_algebra_quiver, crystals folders)

That's good.

Now, what is this startup module error in the patchbot??

It is because we have an extra module (the one for Coxeter matices) that gets imported when Sage starts. This is there as a very mild warning to try to not increase statup time, but it's somewhat of a necessary (very small) evil for us to do here.

### comment:83 Changed 7 years ago by Jean-Philippe Labbé

Status: needs_review → positive_review

As all tests are passed and the labeling issues were solved, I set the ticket to positive review.

### comment:84 Changed 7 years ago by Travis Scrimshaw

Thank you for your work on this.

### comment:85 Changed 7 years ago by Volker Braun

Status: positive_review → needs_work

PDF docs don't build

### comment:86 Changed 7 years ago by git

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

 ​6f8a932 Merge branch 'develop' into public/combinat/coxeter_matrices-17798 ​a44d071 Merge branch 'develop' into public/combinat/coxeter_matrices-17798 ​5d188d4 Fixing pdf build.

### comment:87 Changed 7 years ago by Travis Scrimshaw

Status: needs_work → positive_review

### comment:89 in reply to:  81 Changed 7 years ago by Sébastien Labbé

Now, what is this startup module error in the patchbot??

It is because the new imports in the sage namespaces done in the file # file /src/sage/combinat/root_system/all.py :

from coxeter_matrix import CoxeterMatrix
from coxeter_type import CoxeterType


which automatically loads all this from src/sage/combinat/root_system/coxeter_matrix.py file:

+from sage.misc.cachefunc import cached_method
+from sage.matrix.constructor import matrix
+from sage.matrix.matrix_space import MatrixSpace
+from sage.misc.classcall_metaclass import ClasscallMetaclass, typecall
+from sage.matrix.matrix_generic_dense import Matrix_generic_dense
+from sage.graphs.graph import Graph
+from sage.rings.all import ZZ, QQ, RR
+from sage.rings.infinity import infinity
+from sage.combinat.root_system.cartan_type import CartanType
+from sage.combinat.root_system.coxeter_type import CoxeterType


and this from src/sage/combinat/root_system/coxeter_type.py file:

+from sage.misc.abstract_method import abstract_method
+from sage.misc.cachefunc import cached_method
+from sage.misc.classcall_metaclass import ClasscallMetaclass
+from sage.combinat.root_system.cartan_type import CartanType
+from sage.matrix.all import MatrixSpace
+from sage.symbolic.ring import SR
+from sage.structure.unique_representation import UniqueRepresentation
+from sage.structure.sage_object import SageObject


which explains why the patchbot was saying that Sage now takes 6 seconds instead of 5 to start. You may think about the following questions:

• Do all of these imports really need to be done at the top level of those two modules?
• Do you really need to import CoxeterMatrix and CoxeterType in the Sage namespace? I mean, it is usefull for you, for me. But, maybe that 99% of people will not use those two things while using Sage. So I think you do not have to import them in the global Sage namespace.

Anyhow, since this ticket is closed, this discussion should be moved to another ticket if it is worthwhile to continue that discussion.

### comment:90 follow-up:  91 Changed 7 years ago by Travis Scrimshaw

You are not being fair. All of those are already imported, so they contribute so marginally to startup time that they are essentially non-existent. This can be seen by the startup time plugin which says there might have been a 1.6 millisecond increase in startup time out of 2.6 second average startup.

Also, how many things in the Sage namespace are really useful to most users of Sage? Most of the things that are there are not useful to 99% of the users. So let's advocate removing them from the global namespace, and then nothing except basic calculus will be easily discoverable.

I agree that we do need to be somewhat careful about startup time. However to do that, we need better resolution of lazy imports and large chunks of combinat to be changed to be lazily imported (see #15293). But let us keep this in perspective.

### comment:91 in reply to:  90 ; follow-up:  92 Changed 7 years ago by Sébastien Labbé

This can be seen by the startup time plugin which says there might have been a 1.6 millisecond increase in startup time out of 2.6 second average startup.

Sorry, I think the 5->6 seconds was only the time being spent by the plugin itself. Where do you read the "1.6 ms" information?

### comment:92 in reply to:  91 Changed 7 years ago by Travis Scrimshaw

See the plugins.startup_time link in the patchbot report.