Opened 8 years ago

Closed 7 years ago

Last modified 7 years ago

#17798 closed enhancement (fixed)

Create a class for Coxeter matrices and types

Reported by: Travis Scrimshaw Owned by: Sage Combinat CC user
Priority: major Milestone: sage-6.10
Component: group theory Keywords: Coxeter groups, matrices, types, days64
Cc: Sage Combinat CC user, Darij Grinberg, Frédéric Chapoton, Jean-Philippe Labbé, Vivien Ripoll, Jean Michel, Nicolas M. Thiéry, Kevin Dilks Merged in:
Authors: Travis Scrimshaw, Jean-Philippe Labbé Reviewers: Jean-Philippe Labbé, Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: 5d188d4 (Commits, GitHub, GitLab) Commit:
Dependencies: #17990, #18152, #18743 Stopgaps:

Status badges

Description (last modified by Jean-Philippe Labbé)

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

Change History (92)

comment:1 Changed 8 years ago by Travis Scrimshaw

Authors: Travis Scrimshaw
Branch: public/combinat/coxeter_matrices-17798
Commit: 5484c5d6077138d6ed79d5d19af38c1f1da120ea
Description: modified (diff)
Status: newneeds_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:

d31d286Merge branch 'public/ticket/16630' of trac.sagemath.org:sage into public/combinat/coxeter_matrices-17798
1dddd20Initial creation of the files.
1aadfbeMerge branch 'develop' into public/combinat/coxeter_matrices-17798
f7fd3acMerge branch 'develop' into public/combinat/coxeter_matrices-17798
5484c5dMaking 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: 5484c5d6077138d6ed79d5d19af38c1f1da120ea311eb184e6c37b7bfa0090468d79ca13509a63da

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

311eb18Fixing a pickling issue and some easy doctest failures.

comment:5 Changed 8 years ago by git

Commit: 311eb184e6c37b7bfa0090468d79ca13509a63dae61a4f3927c1d096f8ece1138ed33abbd928594d

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

2ef21f0Re-enable cache of coxeter_matrix() for CartanType_abstract.
e61a4f3Fixed 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:7 Changed 8 years ago by Jean-Philippe Labbé

Cc: Jean-Philippe Labbé added

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:9 Changed 8 years ago by Vivien Ripoll

Cc: Vivien Ripoll added

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: e61a4f3927c1d096f8ece1138ed33abbd928594dbdcd7a5dbfde7746a3e50a0d6e5d68fbbb05c2de

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

bdcd7a5Dirty version added possible entry <=-1 and affine types recognition

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

Status: needs_reviewneeds_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: bdcd7a5dbfde7746a3e50a0d6e5d68fbbb05c2de86b2d78d02683fee74b77742fee3ffd45ffb2e29

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

86b2d78Merge 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 ScrimshawTravis Scrimshaw, Jean-Philippe Labbé
Cc: Jean Michel added
Description: modified (diff)
Keywords: days64 added

comment:16 Changed 8 years ago by git

Commit: 86b2d78d02683fee74b77742fee3ffd45ffb2e29f44e52fb40292424c439d90e29ddf0d3c0256b9f

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

77189ddCorrected base ring of the Coxeter matrix
f135c2eCorrected the bilinear form method
f44e52fNow 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: f44e52fb40292424c439d90e29ddf0d3c0256b9fd0932c325ede70e04db1b659bcfbf86a7b691e06

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

d0932c3Removed inheritance from matrix, added methods and attributes

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

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

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

Cc: Nicolas M. Thiéry added

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'm having thoughts about this for a while.

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: d0932c325ede70e04db1b659bcfbf86a7b691e06d3526392209128a21ee631666e406dd8fc74f631

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

df3c69aMerge branch 6.7.beta3 into cox_matrices_trac
764667eCorrected coding conventions
f830a53Made is_finite and is_affine attributes
823c8f2Added the rank as an attribute
a5afb94Subdivided the init (from matrix, graph, coxeter type)
d352639Added some tests

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

Dependencies: #17990#17990, #18152
Description: 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 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

Replying to jipilab:

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: d3526392209128a21ee631666e406dd8fc74f631fb77b786305566dff1200521cc8330cee7e6ec5b

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

25a6f54Added some values in the dictionnary of the matrix
03b24b4Edited the check coxeter type function
532afdaAdded a samples method to CoxeterType
d018e28Added samples and made many tests pass
fb77b78PEP8 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: fb77b786305566dff1200521cc8330cee7e6ec5bf2be73c3bdf6c76518e1899ee2753d8447ab58bf

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

3262e43Added tests
a3c76faMerge branch 'sage-6.8.beta2' into cox_matrices_trac
f2be73cMade tests pass in coxeter_type

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

Description: modified (diff)
Status: needs_workneeds_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_reviewneeds_work

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

comment:34 Changed 7 years ago by git

Commit: f2be73c3bdf6c76518e1899ee2753d8447ab58bf3d73c0b3e3cb85394ec21a3d24867072fc6b6e86

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

3d73c0bMade tests pass in matrixcoxetergroup

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

Status: needs_workneeds_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_reviewneeds_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: 3d73c0b3e3cb85394ec21a3d24867072fc6b6e8619846a08c352ce041a3d5a8f2a6bf0757a91aae9

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

19846a0Fixed documentation

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

Status: needs_workneeds_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

Commit: 19846a08c352ce041a3d5a8f2a6bf0757a91aae932f216883758c1416d6f680b7dd3b571f8ad1a61

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

32f2168Made test pass in Category of Coxeter groups

comment:41 Changed 7 years ago by git

Commit: 32f216883758c1416d6f680b7dd3b571f8ad1a61522f9a4cc0c316553b1e9d34c74776223494d865

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

522f9a4Added doctest coverage to __repr__

comment:42 Changed 7 years ago by git

Commit: 522f9a4cc0c316553b1e9d34c74776223494d865df35a439d6b5b7f184f0d72647d1f5ae86e324aa

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

9afb736Merge branch 'public/combinat/coxeter_matrices-17798' of trac.sagemath.org:sage into public/combinat/coxeter_matrices-17798
df35a43Implement a better API for pickling/classcall for Cartan/Coxeter matrices.

comment:43 Changed 7 years ago by git

Commit: df35a439d6b5b7f184f0d72647d1f5ae86e324aaeab7426aa7b98be3c11cce1bba68e035c9bf4b0c

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

20bd15dAdded support for _repr_option('ascii_art').
56307d7Merge branch 'public/interfaces/repr_option_ascii_art-18743' into public/combinat/coxeter_matrices-17798
eab7426Fixing doctest from #18743.

comment:44 Changed 7 years ago by Travis Scrimshaw

Dependencies: #17990, #18152#17990, #18152, #18743
Reviewers: 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_reviewneeds_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]
sage: loads(dumps(M))
[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: eab7426aa7b98be3c11cce1bba68e035c9bf4b0cc9125e118a46737c51400bbae469a6aa62b3014b

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

f0ee04aMerge branch 'public/combinat/coxeter_matrices-17798' of trac.sagemath.org:sage into public/combinat/coxeter_matrices-17798
6285150Merge branch 'public/interfaces/repr_option_ascii_art-18743' of trac.sagemath.org:sage into public/interfaces/repr_option_ascii_art-18743
7bc49f5Adding `_repr_option` to the interface element to avoid __getattr__.
27a2847Merge branch 'public/interfaces/repr_option_ascii_art-18743' of trac.sagemath.org:sage into public/combinat/coxeter_matrices-17798
c9125e1Implement better type recognition using (di)graph isomorphism testing.

comment:50 Changed 7 years ago by Travis Scrimshaw

Milestone: sage-6.6sage-6.8
Status: needs_workneeds_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

Commit: c9125e118a46737c51400bbae469a6aa62b3014bcd7d946d88e4345de062c2e7d1c8f700adb7f1a6

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

cd7d946Merge 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.8sage-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:62 Changed 7 years ago by Jean-Philippe Labbé

Cc: Kevin Dilks added

comment:63 Changed 7 years ago by git

Commit: cd7d946d88e4345de062c2e7d1c8f700adb7f1a6e2ad1561bd6d9ef31b53abaaac3681df99035745

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

86a3c73Merge branch 'public/combinat/coxeter_matrices-17798' of trac.sagemath.org:sage into ticket17798
e2ad156Made 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

Commit: e2ad1561bd6d9ef31b53abaaac3681df99035745e6971e72338766abeda78fbaecd3be863a4041e9

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

e6971e7Make sure that indexing sets are passed along by subtype.

comment:70 Changed 7 years ago by git

Commit: e6971e72338766abeda78fbaecd3be863a4041e94ca434574be9cfc2412a90113cf98968ae347247

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

4ca4345Making 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: 4ca434574be9cfc2412a90113cf98968ae347247226f47a20a662f387b74b03941a55962db3c68e6

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

226f47aMaking KR crystals more robust against relabeling.

comment:73 Changed 7 years ago by git

Commit: 226f47a20a662f387b74b03941a55962db3c68e6fe2e01fd1061c8675215050bcc120dd93dd83a5e

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

fe2e01fFixed cluster seed not expicitly specifying an indexing set.

comment:74 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: fe2e01fd1061c8675215050bcc120dd93dd83a5ee659186e20bbb4b4a942008dff32901659e42503

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

e659186Some 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 ; Changed 7 years ago by Jean-Philippe Labbé

Replying to tscrim:

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.9sage-6.10

Replying to jipilab:

Replying to tscrim:

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

[1] http://www.gregreda.com/2013/10/26/working-with-pandas-dataframes/

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

Replying to nthiery:

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

Replying to jipilab:

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_reviewpositive_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_reviewneeds_work

PDF docs don't build

comment:86 Changed 7 years ago by git

Commit: e659186e20bbb4b4a942008dff32901659e425035d188d4a0beb0022ad072068932222c6e23920ad

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

6f8a932Merge branch 'develop' into public/combinat/coxeter_matrices-17798
a44d071Merge branch 'develop' into public/combinat/coxeter_matrices-17798
5d188d4Fixing pdf build.

comment:87 Changed 7 years ago by Travis Scrimshaw

Status: needs_workpositive_review

comment:88 Changed 7 years ago by Volker Braun

Branch: public/combinat/coxeter_matrices-177985d188d4a0beb0022ad072068932222c6e23920ad
Resolution: fixed
Status: positive_reviewclosed

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

Commit: 5d188d4a0beb0022ad072068932222c6e23920ad

Replying to jipilab:

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 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 ; Changed 7 years ago by Sébastien Labbé

Replying to tscrim:

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

Replying to slabbe:

Replying to tscrim:

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?

See the plugins.startup_time link in the patchbot report.

Note: See TracTickets for help on using tickets.