Opened 6 years ago

Closed 6 years ago

Last modified 6 years ago

#17798 closed enhancement (fixed)

Create a class for Coxeter matrices and types

Reported by: tscrim Owned by: sage-combinat
Priority: major Milestone: sage-6.10
Component: group theory Keywords: Coxeter groups, matrices, types, days64
Cc: sage-combinat, darij, chapoton, jipilab, vripoll, jmichel, nthiery, kdilks 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 jipilab)

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 6 years ago by tscrim

  • Authors set to Travis Scrimshaw
  • Branch set to public/combinat/coxeter_matrices-17798
  • Commit set to 5484c5d6077138d6ed79d5d19af38c1f1da120ea
  • Description modified (diff)
  • Status changed from new to 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:

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 6 years ago by darij

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 6 years ago by tscrim

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 6 years ago by git

  • Commit changed from 5484c5d6077138d6ed79d5d19af38c1f1da120ea to 311eb184e6c37b7bfa0090468d79ca13509a63da

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

311eb18Fixing a pickling issue and some easy doctest failures.

comment:5 Changed 6 years ago by git

  • Commit changed from 311eb184e6c37b7bfa0090468d79ca13509a63da to e61a4f3927c1d096f8ece1138ed33abbd928594d

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 6 years ago by darij

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 6 years ago by jipilab

  • Cc jipilab added

comment:8 Changed 6 years ago by jipilab

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 6 years ago by vripoll

  • Cc vripoll added

comment:10 Changed 6 years ago by jipilab

  • Dependencies set to #17990

comment:11 Changed 6 years ago by tscrim

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 6 years ago by git

  • Commit changed from e61a4f3927c1d096f8ece1138ed33abbd928594d to bdcd7a5dbfde7746a3e50a0d6e5d68fbbb05c2de

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

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

comment:13 Changed 6 years ago by jipilab

  • Status changed from needs_review to 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 6 years ago by git

  • Commit changed from bdcd7a5dbfde7746a3e50a0d6e5d68fbbb05c2de to 86b2d78d02683fee74b77742fee3ffd45ffb2e29

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 6 years ago by jipilab

  • Authors changed from Travis Scrimshaw to Travis Scrimshaw, Jean-Philippe Labbé
  • Cc jmichel added
  • Description modified (diff)
  • Keywords days64 added

comment:16 Changed 6 years ago by git

  • Commit changed from 86b2d78d02683fee74b77742fee3ffd45ffb2e29 to f44e52fb40292424c439d90e29ddf0d3c0256b9f

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 6 years ago by tscrim

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 6 years ago by jipilab

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 6 years ago by tscrim

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 6 years ago by git

  • Commit changed from f44e52fb40292424c439d90e29ddf0d3c0256b9f to d0932c325ede70e04db1b659bcfbf86a7b691e06

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

d0932c3Removed inheritance from matrix, added methods and attributes

comment:21 Changed 6 years ago by jipilab

  • Description modified (diff)
  • Keywords changed from Coxeter, groups, matrices, types, days64 to Coxeter groups, matrices, types, days64

comment:22 Changed 6 years ago by jipilab

  • Cc nthiery 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 6 years ago by tscrim

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 6 years ago by tscrim (previous) (diff)

comment:24 Changed 6 years ago by jipilab

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 6 years ago by git

  • Commit changed from d0932c325ede70e04db1b659bcfbf86a7b691e06 to d3526392209128a21ee631666e406dd8fc74f631

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 6 years ago by jipilab

  • Dependencies changed from #17990 to #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 follow-up: Changed 6 years ago by jipilab

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 6 years ago by nthiery

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 6 years ago by git

  • Commit changed from d3526392209128a21ee631666e406dd8fc74f631 to fb77b786305566dff1200521cc8330cee7e6ec5b

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 6 years ago by jipilab

  • 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 6 years ago by git

  • Commit changed from fb77b786305566dff1200521cc8330cee7e6ec5b to f2be73c3bdf6c76518e1899ee2753d8447ab58bf

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 6 years ago by jipilab

  • Description modified (diff)
  • Status changed from needs_work to needs_review

All tests pass on sage-6.8.beta2.

I would say that this version is ready for review.

comment:33 Changed 6 years ago by jipilab

  • Status changed from needs_review to needs_work

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

comment:34 Changed 6 years ago by git

  • Commit changed from f2be73c3bdf6c76518e1899ee2753d8447ab58bf to 3d73c0b3e3cb85394ec21a3d24867072fc6b6e86

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

3d73c0bMade tests pass in matrixcoxetergroup

comment:35 Changed 6 years ago by jipilab

  • Status changed from needs_work to needs_review

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

comment:36 Changed 6 years ago by chapoton

  • Status changed from needs_review to 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 6 years ago by git

  • Commit changed from 3d73c0b3e3cb85394ec21a3d24867072fc6b6e86 to 19846a08c352ce041a3d5a8f2a6bf0757a91aae9

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

19846a0Fixed documentation

comment:38 Changed 6 years ago by jipilab

  • Status changed from needs_work to needs_review

Should be fine now...

comment:39 Changed 6 years ago by jipilab

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

comment:40 Changed 6 years ago by git

  • Commit changed from 19846a08c352ce041a3d5a8f2a6bf0757a91aae9 to 32f216883758c1416d6f680b7dd3b571f8ad1a61

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

32f2168Made test pass in Category of Coxeter groups

comment:41 Changed 6 years ago by git

  • Commit changed from 32f216883758c1416d6f680b7dd3b571f8ad1a61 to 522f9a4cc0c316553b1e9d34c74776223494d865

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

522f9a4Added doctest coverage to __repr__

comment:42 Changed 6 years ago by git

  • Commit changed from 522f9a4cc0c316553b1e9d34c74776223494d865 to df35a439d6b5b7f184f0d72647d1f5ae86e324aa

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 6 years ago by git

  • Commit changed from df35a439d6b5b7f184f0d72647d1f5ae86e324aa to eab7426aa7b98be3c11cce1bba68e035c9bf4b0c

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 6 years ago by tscrim

  • Dependencies changed from #17990, #18152 to #17990, #18152, #18743
  • Reviewers set to 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 6 years ago by jipilab

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 6 years ago by jipilab

Hi,

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

What is wrong?

comment:47 Changed 6 years ago by tscrim

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 6 years ago by tscrim

  • Status changed from needs_review to 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]
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 6 years ago by git

  • Commit changed from eab7426aa7b98be3c11cce1bba68e035c9bf4b0c to c9125e118a46737c51400bbae469a6aa62b3014b

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 6 years ago by tscrim

  • Milestone changed from sage-6.6 to sage-6.8
  • Status changed from needs_work to 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 6 years ago by tscrim (previous) (diff)

comment:51 Changed 6 years ago by jipilab

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 6 years ago by tscrim

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 6 years ago by jipilab

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 6 years ago by tscrim

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 6 years ago by jipilab

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 6 years ago by git

  • Commit changed from c9125e118a46737c51400bbae469a6aa62b3014b to cd7d946d88e4345de062c2e7d1c8f700adb7f1a6

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

cd7d946Merge branch 'sage6.8.rc0' into cox_matrices_trac

comment:57 Changed 6 years ago by jipilab

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 6 years ago by tscrim

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 6 years ago by jipilab

  • Milestone changed from sage-6.8 to sage-6.9

comment:60 Changed 6 years ago by kdilks

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

comment:61 Changed 6 years ago by jipilab

Dear Kevin,

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

comment:62 Changed 6 years ago by jipilab

  • Cc kdilks added

comment:63 Changed 6 years ago by git

  • Commit changed from cd7d946d88e4345de062c2e7d1c8f700adb7f1a6 to e2ad1561bd6d9ef31b53abaaac3681df99035745

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 6 years ago by tscrim

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

comment:65 Changed 6 years ago by jipilab

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 6 years ago by kdilks

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 6 years ago by jipilab

Excellent! On it...!

comment:68 Changed 6 years ago by kdilks

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 6 years ago by git

  • Commit changed from e2ad1561bd6d9ef31b53abaaac3681df99035745 to e6971e72338766abeda78fbaecd3be863a4041e9

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

e6971e7Make sure that indexing sets are passed along by subtype.

comment:70 Changed 6 years ago by git

  • Commit changed from e6971e72338766abeda78fbaecd3be863a4041e9 to 4ca434574be9cfc2412a90113cf98968ae347247

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

4ca4345Making KR crystals more robust against relabeling.

comment:71 Changed 6 years ago by tscrim

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 6 years ago by git

  • Commit changed from 4ca434574be9cfc2412a90113cf98968ae347247 to 226f47a20a662f387b74b03941a55962db3c68e6

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 6 years ago by git

  • Commit changed from 226f47a20a662f387b74b03941a55962db3c68e6 to fe2e01fd1061c8675215050bcc120dd93dd83a5e

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

fe2e01fFixed cluster seed not expicitly specifying an indexing set.

comment:74 follow-up: Changed 6 years ago by 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.

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 6 years ago by git

  • Commit changed from fe2e01fd1061c8675215050bcc120dd93dd83a5e to e659186e20bbb4b4a942008dff32901659e42503

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

e659186Some pyflakes cleanup.

comment:76 Changed 6 years ago by tscrim

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

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

comment:77 in reply to: ↑ 74 ; follow-up: Changed 6 years ago by 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?

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 6 years ago by tscrim

  • Milestone changed from sage-6.9 to sage-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 follow-up: Changed 6 years ago by nthiery

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 6 years ago by tscrim

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 follow-ups: Changed 6 years ago by jipilab

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 6 years ago by tscrim

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 6 years ago by jipilab

  • Status changed from needs_review to positive_review

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

comment:84 Changed 6 years ago by tscrim

Thank you for your work on this.

comment:85 Changed 6 years ago by vbraun

  • Status changed from positive_review to needs_work

PDF docs don't build

comment:86 Changed 6 years ago by git

  • Commit changed from e659186e20bbb4b4a942008dff32901659e42503 to 5d188d4a0beb0022ad072068932222c6e23920ad

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 6 years ago by tscrim

  • Status changed from needs_work to positive_review

comment:88 Changed 6 years ago by vbraun

  • Branch changed from public/combinat/coxeter_matrices-17798 to 5d188d4a0beb0022ad072068932222c6e23920ad
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:89 in reply to: ↑ 81 Changed 6 years ago by slabbe

  • Commit 5d188d4a0beb0022ad072068932222c6e23920ad deleted

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 follow-up: Changed 6 years ago by tscrim

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: Changed 6 years ago by 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?

comment:92 in reply to: ↑ 91 Changed 6 years ago by tscrim

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.