Implementation of finite reflection groups

[stumpc5]

This patch implements reflection groups to work with finite (crystallographic, real, complex) reflection groups. It is based on the GAP3 package chevie which is now an experimental package, see #20107.

sage: W = ReflectionGroup(['A',2],5,23); W
Reducible complex reflection group of rank 7 and type A2 x ST5 x H3
sage: W.irreducible_components()
[Irreducible real reflection group of rank 2 and type A2,
 Irreducible complex reflection group of rank 2 and type ST5,
 Irreducible real reflection group of rank 3 and type H3]

[stumpc5]

Apply only trac_11187-finite_reflection_groups-cs.patch

[stumpc5]

Apply only trac_11187-finite_reflection_groups-cs.patch

[stumpc5]

Apply only trac_11187-finite_reflection_groups-cs.patch

[stumpc5]

+    class SubcategoryMethods:
+
+        @cached_method
+        def Irreducible(self):
+            """
+            Returns the full subcategory of the irreducible objects of ``self``.
+
+            EXAMPLES::
+
+                sage: CoxeterGroups().Irreducible()
+                Category of irreducible coxeter groups
+
+            TESTS::
+
+                sage: AffineWeylGroups().Irreducible.__module__
+                'sage.categories.complex_reflection_groups'
+            """
+            return self._with_adjectives(('Irreducible',))
+
+    class Irreducible(AdjectiveCategory):
+        pass
+

[tscrim]

I've factored out the CartanMatrix class into #14137.

[tscrim]

I've rebased the patch and noticed that this will likely depend on #10963. I'll post a new version once I completely untangle what is going on with #10963.

[stumpc5]

Replying to tscrim:

I've rebased the patch and noticed that this will likely depend on #10963. I'll post a new version once I completely untangle what is going on with #10963.

I always made some minor changes on this patch locally - I would actually only start working on this patch after you guys are finished with #10963. If you want to actively work on this patch, ping me again, and we can discuss what is still needed to finilize this patch.

Cheers, Christian

[chapoton]

Hello Christian

Do you have a git branch for this ticket somewhere ? or should I try to resurrect the patch ?

[stumpc5]

Do you have a git branch for this ticket somewhere ? or should I try to resurrect the patch ?

No, I don't. But I have a local old version of Sage containing that code and quite a bit more, so I wonder if I should/will try to organize it a bit and put it up here.

Do you need any from that code in particular (in which case I am more tempted to work on that), or is that just a general question?

[chapoton]

Hello, no, no real need for this code, just asking a general question. Now that #10963 is over.

[tscrim]

Here's a git version of this patch with changes necessary to get Sage to start (I did not run any tests, so I am not saying things are working). There might be other changes to the files in question which need to be moved over too. Just as a general note from doing the rebasing, there are a bunch of methods missing doctests.

---

New commits:

​3489e1c	#11187 Implementation of finite reflection groups using the GAP3 package chevie
​1f3fe1e	Some other fixes from changes to Sage in order to get Sage to start.

[git]

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

​bc4e068	Merge branch 'public/groups/finite_reflection_groups-11187' of ssh://trac.sagemath.org:22/sage into 11187
​b60e61b	trac #11187 a few minor changes

[git]

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

​1de360f

trac #11187 crystallo takes 2 l

[git]

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

​deb13e3

trac #11187 trying to make doctest pass

[git]

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

​b6c1a62

trac #11187 a few more corrections

[git]

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

​becb1ca

trac #11187 a few more changes, removing duplicate functions

[git]

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

​da599f0	Merge branch 'public/groups/finite_reflection_groups-11187' of ssh://trac.sagemath.org:22/sage into 11187
​e97998c	trac #11187 more work, mostly minor

[git]

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

​03111c8

trac #11187 a little pyflakes cleanup

[git]

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

​6a0a3f3	Merge branch 'public/groups/finite_reflection_groups-11187' of ssh://trac.sagemath.org:22/sage into 11187
​4a37eac	trac #11187 very tiny changes

[git]

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

​527cb50

Merge branch 'public/groups/finite_reflection_groups-11187' into 6.6.b1

[git]

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

​f2fbe0a

merged in 6.8.beta2

[git]

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

​ba7b5f0

made Sage not crash on startup

[git]

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

​a2f0f31	first implementation of the iterator through magma elements
​6ca40fa	Merge branch 't/18584/iterator_through_magma_elements' into u/stumpc5/11187-new

[git]

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

​33f93c6

removed the magma iterator

[git]

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

​08a7821

fixed all doctests in src/sage/combinat/root_system/complex_reflection_group.py

[git]

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

​014fec2

got the doctests of complex reflection group category pass

[git]

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

​d3198f9

fixing a few bugs on coxeter number and fundamental invariants

[git]

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

​e2736f6	added another doctest
​8db1dee	first version of adding functionality to coxeter group categories

[git]

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

​425ca38

first version of coxeter groups from chevie with all tests passing!

[SimonKing]

The current code gives

sage: C = ComplexReflectionGroups()
sage: C.Irreducible()
Category of complex reflection groups
sage: C.Irreducible() is C
True

Is that what you intended? Perhaps the "irreducible" axiom should be defined on ComplexReflectionGroups().Finite(), not on ComplexReflectionGroups().

[SimonKing]

To summarise the discussion Christian and I just had: I believe WellGenerated should be an axiom. Christian said that the general notion of well-generated is a bit tricky for infinite groups. Hence, he actually only wants to take into account well-generatedness for finite complex reflection groups.

Hence, the aim would be to define WellGeneratedComplexReflectionGroups as application of an axiom to ComplexReflectionGroups.Finite. However, I believe that the name should contain the word "finite" if we really want to focus on finite well-generated groups. Alternatively, it should be implemented as a nested-nested class WellGenerated within the nested class ComplexReflectionGroups.Finite.

I also think that WellGeneratedComplexReflectionGroups should provide a parent method _test_well_generated that tests whether self is well-generated. Such method would automatically be executed when running the test suite.

[SimonKing]

We have discussed already that in order to fix the Irreducible axiom, it is needed (in addition to the nested class) to have a SubcategoryMethod called Irreducible.

Note that if we define WellGeneratedComplexReflectionGroups as a sub-category of ComplexReflectionGroups.Finite(), we should probably remove its subcategory-methods Finite and Irreducible, since both axioms have already been defined in the super-category.

[SimonKing]

The iterators currently cache the list of all elements of the group. Is that (always) a good idea?

[SimonKing]

After discussion with Christian, the iterator of a complex reflection group is a lot faster. What we did was to keep ._reduced_word as a list, and only transform it into an actual word when needed (i.e., in the .reduced_word() method).

Before:

sage: G = ComplexReflectionGroup([2,1,4])
sage: %timeit L = list(G); G._elements=None
The slowest run took 6.02 times longer than the fastest. This could mean that an intermediate result is being cached 
1 loops, best of 3: 66.4 ms per loop

After:

sage: G = ComplexReflectionGroup([2,1,4])
sage: %timeit L = list(G); G._elements=None
The slowest run took 66.44 times longer than the fastest. This could mean that an intermediate result is being cached 
1 loops, best of 3: 5.56 ms per loop

---

New commits:

​c0a036b

Avoid creation of _reduced_word during iteration

[chapoton]

New commits:

​405b26c	turned well-generated into an axiom
​0639665	fixed a but with Word(reduced_word) we worked on yesterday

[git]

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

​28f8abd

added a test for well generated

[SimonKing]

Hi Christian,

This is not how the tests work:

                def _test_well_generated(self, **options):
                    tester = self._tester(**options)
                    return self.is_well_generated()

Instead, do

                def _test_well_generated(self, **options):
                    tester = self._tester(**options)
                    tester.assert_(self.is_well_generated())

or something similar.

[chapoton]

see patchbot reports :

• some doctests should be marked with # optional - chevie or whatever
• doctest continuation is now ....: and not ...
• raise statements should use py3 syntax raise Error('message')

[git]

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

​3c79040	added rational catalan numbers
​697cd3f	replaced asserts by raises and a few other fixes

[stumpc5]

@Simon and Nicolas: The category for complex reflection groups (with axioms finite/irreducible/well-generated) is now sort of ready. I would now like to make ComplexReflectionGroups().Finite().WellGenerated() a super category of FiniteCoxeterGroups.

• Is that what I should do?
• If I simply add a method supercategories to FiniteCoxeterGroups, its string repr changes in a not desired way. How should I treat that?

Thanks, Christian

[git]

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

​92ab198

made the category of coxeter groups a subcategory of complex reflection groups

[tscrim]

Replying to stumpc5:

@Simon and Nicolas: The category for complex reflection groups (with axioms finite/irreducible/well-generated) is now sort of ready. I would now like to make ComplexReflectionGroups().Finite().WellGenerated() a super category of FiniteCoxeterGroups.

• Is that what I should do?
• If I simply add a method supercategories to FiniteCoxeterGroups, its string repr changes in a not desired way. How should I treat that?

It sounds more like you want to add ComplexReflectionGroups().WellGenerated() as a supercategory to CoxeterGroups, in particular to replace Groups().FinitelyGenerated() by ComplexReflectionGroups().WellGenerated(). I also think ComplexReflectionGroups() should be a subcategory of Groups().FinitelyGenerated() (otherwise the additional axiom should go on the supercategory for CoxeterGroups()). The finite part will take care of itself by the CategoryWithAxiom magic.

[git]

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

​ec94ae3	added a few more doctests for CoxeterGroupsChevie
​1878996	work in progress: new implementations are presumably correct, but existing bug discovered
​5716df5	Fixed according to Travis's suggestions
​4404133	Fixed according to Travis's suggestions, and now actually running I think
​8fe1bb8	Tab fixed
​a6dcb8b	merged with now-resolved conflicts
​c37a5ef	things appear to work in the sense that all tests have passed.
​1862325	removed trailing whitespace.
​1f29ae6	reordered documentation, as requested by chapoton
​abc690c	many doctests, and merged #18597

[chapoton]

Hello,

• once again: doctest continuation is now ....: and not ...

• could you please put a positive review on the duplicate #9288 ?

[git]

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

​742c0df

replaced '... ' by '....:'

[stumpc5]

Hi

• once again: doctest continuation is now ....: and not ...

done

• could you please put a positive review on the duplicate #9288 ?

done

Thanks for looking at this (and all the other tickets!

Christian

[git]

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

​ab914f5	first version of the subword complexes as of 2015
​cb3ca9c	improve the subword complex, in particular its documentation
​f105602	Merge branch 'u/stumpc5/11010' into u/stumpc5/11187-new
​8618845	playing, I hopefully can reorganize this again
​ab4999f	more intelligent fix a la stump
​df37b7e	Merge branch 't/18610/bug__circular_descent_check_in_weylgroups' into u/stumpc5/11187-new

[git]

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

​e180c31

Revert "improve the subword complex, in particular its documentation"

[git]

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

​450dadd

Revert "first version of the subword complexes as of 2015"

[stumpc5]

I took out the subword complex stuff which is handled in #11010, and which is depending on this one.

[git]

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

​e8e0d9a

added two doctests

[git]

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

​e6de158	added more doctests
​80b9a54	added more doctests, many more to come

[git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​a89a90f	removed trailing whitespace.
​ce30faf	reordered documentation, as requested by chapoton
​21abe06	replaced '... ' by '....:'
​4121914	improve the subword complex, in particular its documentation
​b2b7f68	more intelligent fix a la stump
​d662af6	Revert "improve the subword complex, in particular its documentation"
​1ef2de7	Revert "first version of the subword complexes as of 2015"
​03b60e2	added two doctests
​2a34bef	added more doctests
​d98ee4e	added more doctests, many more to come

[git]

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

​294d5f8

fixed a docstring

[git]

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

​2661ced	lazy import of ComplexReflectionGroups
​346532e	old style doc replaced
​894a671	fixed some doctests for ComplexReflectionGroups
​eddaef5	more doctest for ComplexReflectionGroups, almost done there

[git]

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

​fb852f5

added back the references to __init__

[git]

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

​3783ea2

added some stuff that got lost during rebasing

[git]

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

​c07e76e	moved from ComplexReflectionGroup/CoxeterGroupChevie to ReflectionGroup
​f845089	change in irreducible components
​bbe138f	Merge branch 't/18620/9a3e5cdacac40b505f7aad0a62b9e1bec76d8f3a' into u/stumpc5/11187-new
​43f1dce	reflection groups in the reference

[git]

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

​2f737ce

got the documentation run again as expected

[git]

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

​9df16f6

cleaned the documentation of the complex reflection group category

[git]

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

​bfd9aa6

added some references to ComplexReflectionGroups

[git]

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

​e3b047b

added some references to ComplexReflectionGroups

[git]

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

​7c8cc37	typo
​dd3d515	work on cartan and coxeter matrices
​d673668	removed a few patches that are not needed here

[git]

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

​ef3cbe7

fixed a docstring

[chapoton]

Hello Christian, thanks for your hard work on this ticket. I have only had a quick look, so trivial remarks:

• not yet 100% coverage, I think (I have seen a few methods without examples)
• TODO:: should be .. TODO::
• Could you please replace Returns by Return everywhere.
• Sometime the first line of the doc is made of two sentences. Please separate them as:

  Return something.
  
  Something is very very important.
  

• Please try to keep the lines 80 characters long.
• Bad alignement of EXAMPLES:: in distinguished_reflection, distinguished_reflections
• missing optional in sage: W = CoxeterGroup(["A",4], implementation="chevie")

And you should aim to have a green light from the patchbot. So far, this has never been the case.

[stumpc5]

Replying to chapoton:

Thanks for having a look at this ticket!

I have only had a quick look, so trivial remarks

I am aware of the stuff to do in the documentation, but before getting there (or, at least, in parallel, I'll fix your complaints now), I try to get the overall setting right (this includes the category framework, the interaction with other reflection group classes, and the dependence of chevie).

And you should aim to have a green light from the patchbot. So far, this has never been the case.

I'd like to get it green, but it has not run in 5 days, and I can only fix stuff the patchbot complaints about if I see its results regularly after uploading a new commit sequence (a patchbot that doesn't run soon after uploading doesn't really help during a coding sprint)...

Thanks again, Christian

[chapoton]

There are many patchbots, but only one that has added all your participants to its trust list (at my demand). This one is currently not active. You can try to contact some active patchbots owners to ask them to trust the participants (see ​http://wiki.sagemath.org/buildbot/owners and ​http://patchbot.sagemath.org/machines). Or run your own patchbot.

[stumpc5]

There are many patchbots, but only one that has added all your participants to its trust list (at my demand).

Oh, I didn't know that all participants must be on the trust list, I thought it was only the submitter of the branch - I gonna try to get a patchbot running...

[chapoton]

Yes, this comes from some difficulty to identify the true authors of the code..

For patchbot, please see the instructions there : ​http://wiki.sagemath.org/buildbot/details

[git]

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

​64fe437	copyright and stripped trailing whitespaces
​0a616e2	minor movings of code
​eee3af5	moved reduced_word for real groups
​40d22b2	fixed todos, bad alignments, returns

[kdilks]

I just started a patchbot recently, and I believe I now have it configured to trust all relevant participants and prioritize this ticket.

First run through wasn't very helpful, since I don't have Chevie installed. Though presumably everything should be marked with some kind of optional tag so that tests are skipped if Chevie isn't installed.

I'm in the process of trying to install Chevie, and if I succeed, I'll have it do another run.

[kdilks]

I have Gap3/Chevie installed now.

It's probably easier (and a lot faster) to run

./sage -t ./src/sage/combinat/root_system/reflection_group_complex.py ,

and if things are crashing and you need to see where, then do

./sage -t --verbose ./src/sage/combinat/root_system/reflection_group_complex.py .

Patchbots are good for finding merge conflicts with new betas and seeing if you unintentionally broke other parts of Sage, but at this point I think it's sufficient to only test the one file you're changing with this ticket.

After playing around for a bit, something seems to be broken with the iterator. The example W = ReflectionGroup((1,1,3)) (should be isomorphic to S3) included as a test works fine, but if I try W = ReflectionGroup((3,1,1)) (should be isomorphic to cyclic group of order 3) then it keeps printing out the three elements in a never-ending loop.

[jdemeyer]

Replace

# optional (require chevie)

by

# optional - chevie

[jdemeyer]

When adding new files, you should follow ​http://doc.sagemath.org/html/en/developer/coding_basics.html#headings-of-sage-library-code-files, in particular use the correct license statement.

[stumpc5]

Thanks for having a look here! I am currently working (since yesterday) on speeding the iteration through the group, I hope I have gotten somewhere later today...

I guess I must tag each and every test as

# optional - chevie

which means that these tests are not run on patchbots per default, or do they run if the patchbot has chevie installed?

[jdemeyer]

Replying to stumpc5:

I guess I must tag each and every test

Not literally every test, there are probably tests which do not require chevie.

do they run if the patchbot has chevie installed?

They would be run if the Sage optional package chevie is installed. However, such a package does not exist.

[stumpc5]

Replying to jdemeyer:

Not literally every test, there are probably tests which do not require chevie.

Every test (except for the creation of the category of complex reflection groups) handle with reflection groups (no surprise), and even initializing such a group requires chevie.

But within finite time, I will work on making some core functionalities work without having chevie installed.

They would be run if the Sage optional package chevie is installed. However, such a package does not exist.

Is that a problem? Should there be a possibility of installing chevie as an optional package? I update the description of this ticket to explain how to get chevie installed in a system. See #8906 for old stuff about that.

[jdemeyer]

Replying to stumpc5:

Is that a problem? Should there be a possibility of installing chevie as an optional package?

It's not a problem for me or for this ticket. I guess it is a problem if people want to use the code that you are writing here, since getting chevie to work within Sage is non-trivial.

[git]

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

​5a205a1	moved right coset representatives
​25139dd	removed the preloading of the ucf for reflection groups, and moved the new iterator into real reflection groups.
​7df41c2	new iterators through group
​83f9893	updated licence statements
​1c64c9b	added a todo for the iterator

[git]

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

​d0bfd81	fixed many doctests coming from new iteration order
​43f5056	reached 100% coverage and all tests passing

[stumpc5]

Okay, got 100% coverage and all tests passing! But I wouldn't know how to get the startup module green as I turned the ComplexReflectionGroups category into a super category of CoxeterGroups which is loaded on startup.

[kdilks]

I have a failing doctest for is_regular. There's not a problem with the is_regular method, but for W = ReflectionGroup(23), there are two elements where my computer returns a different reduced word than expected ( ​https://www.diffchecker.com/ewvevrda ). I consistently get the same different answer. Are you using the older/more stable gap-jm4, or the latest gap-jm5 ?

Unrelated, but I also can't get the long_element() method to work.

[stumpc5]

Replying to kdilks:

for W = ReflectionGroup(23), there are two elements where my computer returns a different reduced word than expected

This computation is currently done purely in my code, and it's not related to chevie. The iterator comes from _iterator_tracking_words so let's see what happens there.

Related here, and indeed also to your question on long_element, observe that currently

sage: W = ReflectionGroup(23); W
Irreducible complex reflection group of rank 3 and type H3
sage: W.category()
Join of Category of finite permutation groups and Category of irreducible finite coxeter groups
sage: W = ReflectionGroup(['H',3]); W
Irreducible real reflection group of rank 3 and type H3
sage: W.category()
Join of Category of finite permutation groups and Category of irreducible finite coxeter groups

Since the iter algorithm for coxeter groups is slightly smarter (it takes into account that the weak order is graded), the two iter functions are different.

But:

• both iter functions are supposed to return the same iteration through the group
• both iter functions should always return the elements in the very same order (in contrary to what we see on my vs on your machine)

I found a bug (having a set rather than a list in one spot), so let's see if this is fixed with my next push in a few minutes after all tests pass here.

Unrelated, but I also can't get the long_element() method to work.

The reason is, that you constructed the real group as a complex group, so the long element for ReflectionGroup(['H',3]) works while it currently doesn't work for ReflectionGroup(23). I do have to fix that and be more careful constructing the right class instance.

[git]

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

​e056f65	iteration is now stable among machines
​29a3fa3	reordered some doctests according to the new iteration order

[git]

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

​4a13365	trivialities
​556ab0e	changed the reduced word computation for real groups
​b123a81	hope the iteration order is now stable, also added a few optional chevie, but not many

[chapoton]

There are a few failing doctests, some easy, some less clear.

[chapoton]

now needs rebase, and care for the many failing doctests

[git]

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

​5f8f940	improved the reduced word for reflection groups
​711cf2c	8906: create file ``type`` declaring spkg optional
​f2777b8	8906: create package-version.txt file containing the version
​c5addcf	8906: generate checksums.ini
​af16d79	8906: create SPKG.txt file with package description, etc.
​ddbe1d5	8906: create spkg-install script, patches and increment patch level
​0defcc1	8906: add gap3 commandline option to sage startup script
​ab724b4	merged latest develop

[git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​1c64c9b	added a todo for the iterator
​d0bfd81	fixed many doctests coming from new iteration order
​43f5056	reached 100% coverage and all tests passing
​e056f65	iteration is now stable among machines
​29a3fa3	reordered some doctests according to the new iteration order
​4a13365	trivialities
​556ab0e	changed the reduced word computation for real groups
​b123a81	hope the iteration order is now stable, also added a few optional chevie, but not many
​5f8f940	improved the reduced word for reflection groups
​963397d	merged develop

[git]

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

​7fd11b5

Merge branch 'develop' into u/stumpc5/11187-new

[git]

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

​6443177

Merge branch 'develop' into u/stumpc5/11187-new

[git]

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

​218d6fa	Merge branch 'u/stumpc5/11187-new' into 11187-test
​00b9834	started replacing eval by sage_eval
​3f66a41	Merge branch '11187-test' into 11187-new

[git]

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

​61b0606	Merge branch 'public/interfaces/fix_gap3-19795' of git://trac.sagemath.org/sage into u/stumpc5/11187-new
​dd250eb	Merge branch 'u/stumpc5/11187-new' into temp

[git]

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

​a00d9c7

sage_eval to eval in one instance, needs to be checked at some point

[git]

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

​8c4204a

bug fix for the fundamental invariants

[git]

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

​3b24329	fixed small bug
​683a2f7	added doctest for the bug
​7bb0e6c	Merge branch 'u/stumpc5/19912' into u/stumpc5/11187-new

[git]

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

​20d254c	fixed the same bug in two more places
​fa40e5c	Merge branch 'u/stumpc5/19912' into u/stumpc5/11187-new
​1df9f53	working on a few glitches for CRGs
​66ec881	merged 7.1.beta0
​3957a56	Merge branch 'u/stumpc5/19912' into u/stumpc5/11187-new

[git]

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

​530a5c8

added two implementations of the invariant forms

[git]

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

​6d67ada	work on reflection hyperplanes
​8b39c85	added linear functional description of hyperplanes

[git]

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

​aa87d02

added matrix representation for non-well-generated types

[git]

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

​186d387

Merge branch 'u/stumpc5/11187-new' into test

[git]

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

​094c608

added some more todos for character theory

[dimpase]

are you aware of Geck's ​PyCox? ​http://www.mathematik.uni-stuttgart.de/~geckmf/chv1r6180.py

[stumpc5]

Replying to dimpase:

are you aware of Geck's ​PyCox? ​http://www.mathematik.uni-stuttgart.de/~geckmf/chv1r6180.py

Sure, but it is limited to finite _real_ reflection groups, while I certainly want to work with real and with complex reflection groups. E.g., the results in

• ​http://jlms.oxfordjournals.org/content/90/3/919.abstract (paywall)
• ​http://arxiv.org/abs/1211.2789 (free)

were only possible by using the code in this ticket to work in Sage with complex reflection groups from chevie through the gap3 interface.

[git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​cac3206	improved spkg-src
​181a352	undoing one thing in spkg-src
​ec01e30	moved to experimental package
​6e599cf	renamed optional package to experimental package in interfaces/gap3.py
​1583f99	replaced #20107 by :trac:20107
​38dbd60	replaced optional chevie by optional gap3 in combinat/root_system/coxeter_group.py
​d4f3a1d	updated the spkg-src to delete gap3 packages that need compilation
​7696a2c	added patch for init.g and fixed typo in patch for gap.sh
​3d123df	merged 20107 to the newest develop
​3da1ebb	Merge branch 'u/stumpc5/11187' into tmp

[stumpc5]

Concerning the iteration through elements without keeping them in memory, we have to benchmark agains

    gap> i:=0;;
    gap> W:=CoxeterGroup("E",7);;
    gap> ForEachElement(W,function(x)i:=i+1; 
    > if i mod 1000000=0 then Print("*\c");fi;
    > end);Print("\n");
    **

which takes about a second per million elements, see ​https://webusers.imj-prg.fr/~jean.michel/gap3/htm/chap075.htm.

[tscrim]

Continuing the discussion from #13580.

Replying to hivert:

Replying to tscrim:

Christian, Vivien, and I are working on trying to speed up the iteration of finite Coxeter groups by using (subgroups of) permutation groups and the iterator method of generic Coxeter groups, which uses a SearchForest (see #11187 and the CoxeterGroups category). Our goal is to try and match or beat GAP3 iteration time (which we are about ~30x slower).

I'll be both very happy and interested to have usecase for this code.

This will have the more serious use case I know of (the code in the generic Coxeter groups iterator, e.g., via CoxeterGroup, has not had any serious optimization attempts AFAIK).

We are in the process pushing our successor computation code to Cython and some of our other methods, but we would appreciate any insights you have.

Do you have a typical example relying on SearchForest of code on top of #11187 that I can profile ? Note that I included in the documentation of map_reduce.py a guide on how to profile the parallel code. I'd like to measure the proportion of time that is spend on Coxeter code one one hand and on the parallel infrastructure on the other.

Our current test cases are B₆ (~0.5s) and E₇ (~1m).

Now, concerning coxeter group, I'm quite sure that rewriting part of the code in C/C++ and using advanced parallel stuff (AVX instruction set + SIMD) you can get speedup a large as several hundreds and even thousand ! As a witness on ​https://github.com/hivert/IVMPG I wrote a code whose goal is to enumerate integer vector modulo permutation group. Compared to the code we have in Sage which has been Cythonized and optimized by Simon King I manage to get speedup a large as x2000 ! I need help on the build system to be able to distribute it. I'm pretty sure the code there is very similar to what you need in Coxeter groups.

One of the thoughts I'm bouncing around is doing a full C/C++ version using arrays, and then using Cython (mainly PermutationGroupElement) as a transfer layer to Sage/GAP. In which case it probably should be split off as a little specialized spkg.

That is quite an impressive speedup. I know a little bit about build systems (and its on my todo to learn more for fixing up coxeter3/LiE too), but, e.g., Jeroen or François are good people to ask. Although if you need GCC 5.x, then we will need to do some changes to Sage. Yet, I think moving to GCC 5.x is something that we want and are going to do soon...

---

New commits:

​e2f919f

New iterator for real reflection groups.

[hivert]

Replying to tscrim:

One of the thoughts I'm bouncing around is doing a full C/C++ version using arrays, and then using Cython (mainly PermutationGroupElement) as a transfer layer to Sage/GAP. In which case it probably should be split off as a little specialized spkg.

This is very similar to what I did. The idea is that if you want large performance, you need to completely control the way you use the memory. So what I did is to build in parallel a large linked list of arrays and then thanks to Cython I returns Sage an iterator which is a view on this list which wrap the element of the linked list into proper Sage Element.

[git]

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

​48835b7

Merge branch 'develop' into u/stumpc5/11187

[stumpc5]

For the record: as discussed last night, the first goal would be to separate the category stuff into its own ticket (@tscim is working on this), and then to get the present version well documented, tested, and finished. Only after this work is done, we will start improving stuff and add functionality.

To this end, we have to:

• get the category stuff right
• test properly that reducible groups work as desired
• test properly that the labelling system of simples/hyperplanes/reflections works properly
• test that the assumptions on how we obtain the data from chevie is correct (one example here is that the code tries to get n simple reflections, N* distinguished reflections, and then the remaining (N-N*) other reflections when listing all reflections. This has to be rechecked, but there are plenty of more similar examples.

---

New commits:

​e75f1a2	Updated TODO list
​1b798a7	Merge branch 'u/stumpc5/11187-new' of git://trac.sagemath.org/sage into t/11187/11187-new

[chapoton]

new branch, I have cleaned up the imports

---

New commits:

​0fc36ce

trac #11187 pyflakes cleanup

[git]

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

​220e0f0

trac #11187 changing next to python3 syntax

[git]

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

​3270a98

trac #11187 remove a method reflection to root in complex groups

[git]

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

​b947ea5

trac #11187 adding doc for reflecting hyperplane

[git]

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

​a697817

trac #11187 remove the invariant linear form in complex, for the moment

[git]

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

​9b73808

trac #11187 correct a doctest in coxeter_groups

[git]

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

​114b20b

trac #11187 adding a doctest for the invariant form

[git]

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

​71b77a1	Merge branch 'develop' into u/tscrim/11187
​b171922	Merge branch 'u/stumpc5/11187-new' of git://trac.sagemath.org/sage into u/tscrim/11187
​67e882a	Trying to get a bit more speed out and doing some code cleanup.
​c76dd9d	Merge branch 'u/tscrim/11187' of git://trac.sagemath.org/sage into u/stumpc5/11187
​ea14eb8	fixed some doctests, fixed a bug in hyperplanes, work on the iterator
​4e80c52	Merge branch 'u/chapoton/11187' of git://trac.sagemath.org/sage into u/stumpc5/11187

[git]

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

​d734321

trac #11187 a typo in doc in complex reflection groups

[git]

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

​7d88a6a

trac #11187 again a minor doc typo in complex refl group

[git]

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

​f42aba9

trac #11187 a typo in doc of real-refl-groups

[tscrim]

New commits:

​19af4e7	Merge branch 'u/chapoton/11187' of trac.sagemath.org:sage into u/tscrim/reflection_groups-11187
​b7f5ffe	Merge branch 'u/chapoton/11187' of trac.sagemath.org:sage into u/tscrim/reflection_groups-11187
​a384a06	Pulling changes from #11187 and making tests use colored permutations.
​e3b52f7	Merge branch 'public/categories/complex_reflection_groups-20397' of trac.sagemath.org:sage into u/tscrim/reflection_groups-11187

[git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​c76dd9d	Merge branch 'u/tscrim/11187' of git://trac.sagemath.org/sage into u/stumpc5/11187
​ea14eb8	fixed some doctests, fixed a bug in hyperplanes, work on the iterator
​4e80c52	Merge branch 'u/chapoton/11187' of git://trac.sagemath.org/sage into u/stumpc5/11187
​d734321	trac #11187 a typo in doc in complex reflection groups
​7d88a6a	trac #11187 again a minor doc typo in complex refl group
​f42aba9	trac #11187 a typo in doc of real-refl-groups
​b7f5ffe	Merge branch 'u/chapoton/11187' of trac.sagemath.org:sage into u/tscrim/reflection_groups-11187
​a384a06	Pulling changes from #11187 and making tests use colored permutations.
​e3b52f7	Merge branch 'public/categories/complex_reflection_groups-20397' of trac.sagemath.org:sage into u/tscrim/reflection_groups-11187
​2b01e8d	Merge branch 'u/tscrim/11187' of git://trac.sagemath.org/sage into t/11187/11187-new

[tscrim]

Everything should work now up to the printing of well-generated as part of the finite Coxeter group category.

---

Last 10 new commits:

​f77e89f	Getting the degrees correct.
​14d4c39	Merge branch 'public/20395' into public/categories/complex_reflection_groups-20397
​79bbb3f	Merge branch 'public/categories/complex_reflection_groups-20397' into u/tscrim/reflection_groups-11187
​a7c3db8	Fixing up the categories and doing some other cleanup.
​b9e0b0d	working on the iterator
​823ab4f	Merge branch 'u/chapoton/11187' of git://trac.sagemath.org/sage into u/stumpc5/11187
​80fe997	finished to encorporate the new iterator
​3538599	Merge branch 'u/vripoll/11187-new' of git://trac.sagemath.org/sage into u/stumpc5/11187
​90244d3	Merge branch 'u/stumpc5/11187-new' of git://trac.sagemath.org/sage into u/tscrim/reflection_groups-11187
​6daedef	Fixing everything else up except for well-generated being added to finite Coxeter groups.

[chapoton]

New commits:

​5f568f9

trac #11187 fixing shepard groups

[tscrim]

I was able to stop GeneralizedCoxeterGroup, ComplexReflectionGroup, and FiniteCoxeterGroup from being imported during startup.

---

New commits:

​a7976cb	removed ComplexReflectionGroups from global namespace
​d4775c7	Removing FiniteCoxeterGroups, ComplexReflectionGroups, and GeneralizedWeylGroups from startup import.

[git]

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

​beadf8a

Lazy imports must have absolute paths.

[git]

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

​f7a6dd1	Fixing global namespace issues.
​a53d8f1	added somes lines in doc + correction typo shephard
​4e71ef7	Some typos and corrections in the descriptions
​535d37e	removed spaces in example
​185be8f	Merge branch 'public/categories/complex_reflection_groups-20397' of trac.sagemath.org:sage into u/tscrim/reflection_groups-11187

[git]

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

​6dc2fdb	trac #11187 doc correction, and more doc
​b81dc42	Fixing simple_reflection_orders.

[chapoton]

some tiny fixes in doc, mainly

---

New commits:

​2b0c33a	trac #11187 replace exec by sage_eval, add more doc on reflection groups
​7271ead	trac #11187 fixing the doc (again)
​298cf98	trac #1118è adding one doc
​dffa31e	trac #11187 some more fine doc tuning
​2ec03b0	trac #11187 working on doc
​7324754	trac #11187 still working on doc
​2d70fab	trac #11187 more doc tuning

[stumpc5]

in the cython iterator, we should use sth like

tuple( W.simple_reflection(W._index_set_inverse[i]) for i in xrange(len(W._index_set)) )

[tscrim]

New commits:

​0bcce62	Making the iterator even faster.
​a04b9c8	Merge branch 'u/chapoton/11187' of trac.sagemath.org:sage into u/tscrim/reflection_groups-11187
​9c96d33	added ST type casting for real groups + documentation of crg's
​5b1f2b0	Merge branch 'u/stumpc5/11187' of trac.sagemath.org:sage into u/tscrim/reflection_groups-11187

[git]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

​aa07666	trac #11187 fixing catalog
​b2ba34c	Merge branch 'u/chapoton/11187' of trac.sagemath.org:sage into u/tscrim/reflection_groups-11187
​fa1b496	Changing the indexing sets and how they are handled.
​a1b61e6	moderate pep8 changes
​6da6f94	Merge branch 'u/chapoton/11187' of trac.sagemath.org:sage into u/tscrim/reflection_groups-11187
​85d0ce1	fixed a typo in the doc
​ab7afba	marked a missing doctest + fixed a bug to show type C2
​72082b1	fixed a bug in noncrossing partition lattice and reflection/absolute order
​844f450	Merge branch 'u/stumpc5/11187' of trac.sagemath.org:sage into u/tscrim/reflection_groups-11187
​d425669	Fixing failures and some other things.

[stumpc5]

New commits:

​87cd989	fixed one doctest in category complex reflection group
​05a8ab4	11187: fixed trivial doctest failures
​32bf1ae	11187: cleanup of the organization of the various axioms (WellGenerated, ...) for complex/generalized reflection groups + documentation improvements
​73276ca	Merge branch 'u/tscrim/11187' of trac.sagemath.org:sage into t/11187/11187
​e074050	merged

[git]

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

​b572c74

fixed a missing doctest

[stumpc5]

Only two trivial doctests failing + the missing doctest for _test_well_generated, though Nicolas thought he had added it.

[git]

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

​24191b0	11187: factored out common code from GeneralizedCoxeterGroups and ComplexReflectionGroups
​fced757	trac #11187 fixing import of QQbar and prod
​1daeaea	trac #11187 fixing degrees for finite Coxeter and Weyl
​2791d1e	Merge branch 'u/chapoton/11187' of trac.sagemath.org:sage into t/11187/11187
​4e4e65e	11187: finished the generic irreducible_components; fixed trivial doctest failures

[git]

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

​6d88d92

11187: oops, forgot to add one file

[git]

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

​9f72be3

Moving the iterator for complex reflection groups to the Cython file.

[git]

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

​833b550	trac #11187 better code for degrees
​ef835f6	Merge branch 'public/11187' into chapoton branch

[git]

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

​a45d823

fixed the allowed input types for reflection groups

[git]

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

​a9d858a	11187: documentation, crosslinks, full subcategories, uniformization of simple reflections/reflections/distinguished reflections
​211baa4	Merge branch 'public/11187' of trac.sagemath.org:sage into t/11187/11187
​a5e263d	Merge branch 'public/11187' of trac.sagemath.org:sage into t/11187/11187

[git]

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

​a95a5a9

11187: updated doctest + added comment for the next time

[git]

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

​e654c3e

11187: updated doctests: Coxeter groups don't define additional structure since they have now a supercategory doing so

[git]

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

​c3b5a32

fixed a bug in the degrees in coxeter groups category

[git]

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

​b5b8c3b

trac #11187 adding codegrees to finite Coxeter groups

[git]

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

​7eab06d

trac #11187 some typos in doc of categories/complex_reflection_group

[git]

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

​98f3c76	11187: fixed TODO statement, removed unused import
​d43a39f	11187: removed commented out link for some_elements
​e34c9a7	11187: refactor from_reduced_word and apply_*_reflection, cleanup
​8e08db2	Merge branch 'public/11187' of trac.sagemath.org:sage into t/11187/11187
​fae677f	11187: removed 3 spurious empty lines in the doc

[git]

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

​49f1897	trac #11187 implement coxeter_element and correct the degrees for symmetric gp
​f048ac3	Merge branch 'public/11187' into chapoton branch

[git]

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

​7880f30

trac #11187 one failing doctest in categories

[git]

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

​568d6c4	11187: Generalized methods from ComplexReflectionGroup, replace apply_simple_reflection_* by a definition of simple_reflection, documentation, TODOs
​9b7aba2	Merge branch 'public/11187' of trac.sagemath.org:sage into t/11187/11187

[git]

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

​fc5f667

removed several cached methods

[git]

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

​b55ecb0

moved the reduced_word_in_ref for real groups there, removed a few more cached methods, documented a few optional arguments

[git]

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

​2aa89b2

commenting on the todo list

[git]

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

​a7d65c6

fixed one failing doctest

[git]

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

​410d03d	11187: TODO + marked indirect doctest
​eb45b27	Merge branch 'public/11187' of trac.sagemath.org:sage into t/11187/11187

[git]

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

​f4801f2

trac 11187 making degrees be integers

[git]

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

​cb0a7a0

trac 11187 degrees in tuple

[git]

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

​883f3d6	sorted degrees in irred comps, sort also the fundamental invariants in the same way
​55104aa	Merge branch 'public/11187' of git://trac.sagemath.org/sage into u/stumpc5/11187

[git]

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

​5775f50	trac 11187 fixing doctest in degree, codegree, fundamental inv
​fbdabdc	trac 11187 codegrees in decreasing order

[git]

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

​8542562	11187: add _test_degrees (not yet finished)
​256edb7	Merge branch 'public/11187' of trac.sagemath.org:sage into t/11187/11187
​b29b702	11187: reflecting_hyperplanes -> reflection_hyperplanes
​ebbf9bf	11187: further work on _test_(co)_degrees; reflecting_hyperplanes -> reflection_hyperplanes
​249f619	Merge branch 'public/11187' of trac.sagemath.org:sage into t/11187/11187
​e22ee7e	11187: fixed typo in the code of number_of_irreducible_components

[git]

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

​0e0f7b3	11187: fixed degrees for non irreducible finite coxeter groups; removed the constraints that the (co)degrees shall be sorted
​722a767	11187: fixed degrees for more specific coxeter group implementations + doctest cleanup

[git]

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

​5294cf3

11187: fixed codegrees for colored permutations

[git]

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

​c7425f8

trac 11187 a typo in doc

[git]

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

​d411673	11187: fixed degrees and codegrees for Permutations to return tuple of Integers
​2def1e8	Merge branch 'public/11187' of trac.sagemath.org:sage into t/11187/11187

[git]

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

​241e660

11187: sum -> ZZ.sum for consistency when the list of degrees is empty

[git]

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

​82ff288

11187: rename 'reflecting hyperplane' to 'reflection hyperplane' in the docstrings

[git]

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

​c09cd4d

11187: Fixed heisenbug caused by temporarily breaking the implementation of (co)degrees for testing without restoring it after

[git]

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

​cf00014	trac #20396 adding the invariant linear form for complex refl groups
​75e8d69	trac #20396 first try at simpler implementation
​cdef4c3	trac #20396 not yet working
​8013693	Merge branch 'public/20396' of git://trac.sagemath.org/sage into u/stumpc5/20396
​e02cf02	still in trouble about the complex case
​07bd053	merged 11187
​bf2ea92	fixed the coroots + work on invariant form
​0becba3	Merge branch 'public/11187' of git://trac.sagemath.org/sage into u/stumpc5/20396

[git]

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

​8927ab9

matrix action is on the right!

[stumpc5]

Okay, all tests pass!

[stumpc5]

@trscim: For the record, the timings for iteration in E7 seem to be odd:

sage: W = ReflectionGroup(['E',7])                                              
sage: %time for w in W.iteration(algorithm="depth",tracking_words=False): pass  
CPU times: user 3.71 s, sys: 0 ns, total: 3.71 s
Wall time: 3.79 s
sage: %time for w in W.iteration(algorithm="breadth",tracking_words=False): pass
CPU times: user 8.72 s, sys: 4.84 ms, total: 8.73 s
Wall time: 8.72 s
sage: %time for w in W.iteration(algorithm="depth",tracking_words=True): pass   
CPU times: user 5.83 s, sys: 0 ns, total: 5.83 s
Wall time: 5.81 s
sage: %time for w in W.iteration(algorithm="breadth",tracking_words=True): pass 
CPU times: user 20.6 s, sys: 67.4 ms, total: 20.6 s
Wall time: 20.7 s

Also, I discussed with Nicolas yesterday, and (as what I said on the weekend), we are back at the situation that one can be much smarter concerning the ascents: Let i be an ascent of w and si and s_j commute. Then i is also an ascent of wsj. I will try to use that today, but it still seems that any test in this direction is much slower than doing the actual test for an ascent the way we already do it.

[git]

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

​eb2ea75	cleaned the reduced word code
​6fbba18	undo the change to repr methods
​8497f5d	first try to skip elements in the iteration, too slow
​def7015	reorganized the invariant form (still missing an improvement) + fixed two doctests

[stumpc5]

Travis, could you have a look at the diffset 8497f5d; I commented out that the change is actually used, see #for i in self.noncom[first], it seems to slow down the test even though much less is actually tested. Maybe you see how to get rid of the overhead the line for i in self.noncom[first] has compared to for i in range(first+1,self.n).

[stumpc5]

Travis: Also, you introduced _reduced_word to be a lazy attribute. This has a few drawbacks: not self._reduced_word is None in the length function in reflection_group_real.py is never triggered, and _reduced_word is now either a word in the index set (if the lazy attribute is triggered in the real case), or a word in range(n) if one has gotten it through the iterator. This way, the method reduced_word in the real case is always executed, even though the reduced word is already known.

Two solutions are:

• either set _reduced_word to a word in the indices in the iterator for the cost of list lookups for each letter in the word
• write the lazy attribute in the real case so that it gives a word in range(n)
• do neither and forget about the info gotten from the iterator in the real case.

[tscrim]

Replying to stumpc5:

Travis, could you have a look at the diffset 8497f5d; I commented out that the change is actually used, see #for i in self.noncom[first], it seems to slow down the test even though much less is actually tested. Maybe you see how to get rid of the overhead the line for i in self.noncom[first] has compared to for i in range(first+1,self.n).

My guess is because Cython is smart enough to translate

for i in range(n)

into

for(i=0; i<n; ++i)

whereas for the other, it is iterating over some object (which, a priori, may not even be iterable). In more detail, Cython doesn't even know that it is iterating over a list, just that self.noncom is. Try:

        nc = self.noncom[first]
        for i in nc:

or the variant

        nc = self.noncom[first]
        k = len(nc)
        for dummy in range(k):
            i = nc[dummy]

where you have cdef list nc and cdef int dummy, k (although I suspect the former of these is faster).

[tscrim]

Replying to stumpc5:

Travis: Also, you introduced _reduced_word to be a lazy attribute. This has a few drawbacks: not self._reduced_word is None in the length function in reflection_group_real.py is never triggered, and _reduced_word is now either a word in the index set (if the lazy attribute is triggered in the real case), or a word in range(n) if one has gotten it through the iterator. This way, the method reduced_word in the real case is always executed, even though the reduced word is already known.

Doing this simplified the code and probably got us a small speedup. Yet, this is a bug in my implementation. However, I'm not sure how much it is worth it to compute the length of an arbitrary element without computing its reduced word. If it becomes that time critical for someone, we can get them an algorithm option for length().

This way, the method reduced_word in the real case is always executed, even though the reduced word is already known.

This doesn't make sense. If anything reduced_word() will throw an error if _reduced_word was done by the lazy_attribute. The iterator overwrites (the lazy attribute) _reduced_word if the word comes from there, so it does not get computed twice. Otherwise it was a user created word and will never be identical (not just equals) to an element created from the iterator.

Two solutions are:

• write the lazy attribute in the real case so that it gives a word in range(n)

This is what I would do. Although we might be better off just doing our own implementation using a list (which we mutate) and starting with self.domain().

[git]

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

​7ce6850	playing with the iterator, nothing makes it faster currently...
​5a377c4	moved reduced word to cython + fixing doctests, added doctests for invariant form brute force

[stumpc5]

Done with "write the lazy attribute in the real case so that it gives a word in range(n)". This is now moved to cython (speed gain ~100 times faster).

[stumpc5]

One big issue that is still waiting for me to fix it is that it remains unclear if we want a left or right action. The implementation is a left action, but e.g. #20402 assumes a right action. I will get to this before the weekend and would then hope for the code to become stable and some final reviewing :-)

[tscrim]

Just FYI - you have reverted a python3 compatible change with this:

-                ....:     print('%s %s'%(w.reduced_word(), w.is_regular(W.coxeter_number())))
+                ....:     print w.reduced_word(), w.is_regular(h)

I think 2to3 can handle this, but I'm just stating a paranoia about it.

Although I would advocate for making doctests that avoid printing through an iteration altogether (really annoying failures when the iteration order changes), but this isn't really a big issue.

I will take a more detailed look at the recent changes before the weekend.

[nthiery]

Replying to stumpc5:

One big issue that is still waiting for me to fix it is that it remains unclear if we want a left or right action. The implementation is a left action, but e.g. #20402 assumes a right action. I will get to this before the weekend and would then hope for the code to become stable and some final reviewing :-)

How much additional code would it take to make it work on both sides, allowing the user to do ReflectionGroup(..., action="right")?

[stumpc5]

Just FYI - you have reverted a python3 compatible change with this

I am sure there are reasons for that python3 convention, but I do prefer simple to read code. Anyway, I can also do the other if you prefer.

How much additional code would it take to make it work on both sides,

I was afraid you'd ask that. in my eyes: too much. The elements are considered as permutations, words, and matrices at the same time (and there are even two types of words, in simples and in all reflections, and the simple words have wired properties in the non-real case), making options would pollute the code just soo much, I think, and would introduce so many possible mistakes. I prefer to have clean and fast code, that is hopefully getting better than chevie, eventually. Once that is achieved, I am getting in favour with adding another layer of user friendliness.

[nthiery]

Replying to stumpc5:

I was afraid you'd ask that.

:-)

in my eyes: too much. The elements are considered as permutations, words, and matrices at the same time (and there are even two types of words, in simples and in all reflections, and the simple words have wired properties in the non-real case), making options would pollute the code just soo much, I think, and would introduce so many possible mistakes. I prefer to have clean and fast code, that is hopefully getting better than chevie, eventually. Once that is achieved, I am getting in favour with adding another layer of user friendliness.

Fair enough: let's focus on getting things to work.

One thing though is that a lot of features are completely symmetric (e.g. the reverse of a word is a word). The only spot where things differ is when there is an explicit action. In my experience when implementing representations of semigroups, it was often possible to abstracted everything out by manipulating elements in the code as functions whenever there is an action involved (sorry, I know, this is a big vague).

Of course, a prerequisite for implementing this seamlessly is that permutation groups themselves would allow for both left and right actions.

Cheers,

Nicolas

[git]

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

​8862849

simple_roots, simple_coroots, and fundamental_weights are now index by the index set

[tscrim]

Replying to stumpc5:

Just FYI - you have reverted a python3 compatible change with this

I am sure there are reasons for that python3 convention, but I do prefer simple to read code. Anyway, I can also do the other if you prefer.

In python3, print becomes an actual function, so it needs the parentheses (which due to Python's handling of parentheses, print(foo) gets evaluated to print foo, but having a comma means (foo, bar) becomes a tuple). So to help make the doctests 2/3 compatible and to ease the eventual transition, I do prefer the way I had it or make it into a few examples and have a doctest which does check everything (without verbose).

[git]

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

​ef83323

clarified the fundamental weights, including an example

[stumpc5]

Replying to tscrim:

In python3, print becomes an actual function, so it needs the parentheses

I see, doesn't make it easier to read though...

[git]

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

​5ecc970

got the action on roots and the inversion set in its left- and right-flavor

[git]

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

​42d6b75

made matrix an alias for to_matrix, as matrix returns a huge permutation matrix of the roots

[git]

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

​8810c41

fixed one doctest + work on the invariant form

[git]

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

​2ba3740

fixed another doctest + a typo

[git]

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

​e28bbec

edited the length function to always use the reduced word

[git]

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

​a2ef2e4	added a few sentences to the doc
​dc01066	started to add 'optional - gap3'

[git]

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

​fd0c9cc

added optional gap3

[git]

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

​1537a79

added optional gap3

[git]

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

​a60cf31

added some missing optional gap3

[git]

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

​feebf97	finalized the invariant form
​4955d68	added the missing optional gap3 in the cython file

[git]

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

​c5c43bc

the next round of optional gap3 insertions

[git]

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

​244e6ff	Merge branch 'public/11187' of trac.sagemath.org:sage into public/reflection_groups-11187
​f541349	Some last little beautification.

[tscrim]

I've done a few little beautification things. If my changes are good, then we can set this to a positive review.

[stumpc5]

Thanks Travis, looking forward to have this to positive review and then merged!

[tscrim]

FYI - Patchbots seem happy with it.

[stumpc5]

FYI - Patchbots seem happy with it.

yes, but it didn't test the gap3 stuff again (I just asked Frederic how to get the patchbot to also test those), and also we still have two new startup modules (though the patchbot sees them without indicating it, see ​http://patchbot.sagemath.org/log/11187/Ubuntu/14.04/x86_64/3.13.0-85-generic/librae/2016-04-20%2010:00:02?plugin=plugins.startup_modules&diff=/log/0/Ubuntu/14.04/x86_64/3.13.0-85-generic/librae/2016-04-12%2018%3A16%3A59&ticket=11187&base=7.2.beta4)

[stumpc5]

To now run the doctests # optional - gap3, it seems I cannot use the patchbot anymore. Should I then do instead

sage-patchbot/sage -tp 4 --all --long --optional=gap3

myself?

[tscrim]

I think that will be best. I was going to try this afternoon to see if I can avoid importing those categories at startup, but I might not be successful at it.

[dimpase]

Replying to stumpc5:

To now run the doctests # optional - gap3, it seems I cannot use the patchbot anymore. Should I then do instead

sage-patchbot/sage -tp 4 --all --long --optional=gap3

myself?

I'd use --optional=gap3,sage

[stumpc5]

Replying to dimpase:

I'd use --optional=gap3,sage

wow, you are silently reading these hundreds of comments to now help out -- impressive, thanks!

[tscrim]

To remove generalized_coxeter_groups.py from the startup would either require making it a lazy import in coxeter_groups.py or making coxeter_groups.py not being imported at startup. I think the better strategy is to leave things how they are as an incentive to have coxeter_groups.py not be imported at startup. (Also it is only a net +1 imported at startup.)

[git]

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

​0db28d6

fixed doctests that have not been run last week!

[stumpc5]

I also copied the other optional from the patchbot:

./sage -tp 6 --all --long --optional=ccache,gap3,mpir,patchbot,python2,sage

@Frederic, is that what I should do? Would it be hard (desirable?) to tell the patchbot (maybe in config_file.json) which optional tests should in general be run?

[stumpc5]

there are still a few doctest failures that need to be fixed:

stumpc5@findstat:~/web-findstat/sage-patchbot$ ./sage -tp 6 --long --optional=ccache,gap3,mpir,patchbot,python2,sage src/sage/combinat/root_system/coxeter_group.py
too many failed tests, not using stored timings
Running doctests with ID 2016-04-21-13-13-55-f420497c.
Git branch: t/11187/public/11187
Using --optional=ccache,gap3,mpir,patchbot,python2,sage
Doctesting 1 file using 6 threads.
sage -t --long src/sage/combinat/root_system/coxeter_group.py
**********************************************************************
File "src/sage/combinat/root_system/coxeter_group.py", line 205, in sage.combinat.root_system.coxeter_group.CoxeterGroupAsPermutationGroup.__init__
Failed example:
    TestSuite(W).run()             # optional - gap3
Expected nothing
Got:
    Failure in _test_well_generated:
    Traceback (most recent call last):
      File "/srv/data/findstat.imp.fu-berlin.de/sage-patchbot/local/lib/python2.7/site-packages/sage/misc/sage_unittest.py", line 283, in run
        test_method(tester = tester)
      File "/srv/data/findstat.imp.fu-berlin.de/sage-patchbot/local/lib/python2.7/site-packages/sage/categories/finite_complex_reflection_groups.py", line 628, in _test_well_generated
        tester.assertEqual(self.number_of_simple_reflections(), self.rank())
      File "/srv/data/findstat.imp.fu-berlin.de/sage-patchbot/local/lib/python/unittest/case.py", line 515, in assertEqual
        assertion_func(first, second, msg=msg)
      File "/srv/data/findstat.imp.fu-berlin.de/sage-patchbot/local/lib/python/unittest/case.py", line 508, in _baseAssertEqual
        raise self.failureException(msg)
    AssertionError: 3 != 27
    ------------------------------------------------------------
    The following tests failed: _test_well_generated
**********************************************************************
File "src/sage/combinat/root_system/coxeter_group.py", line 231, in sage.combinat.root_system.coxeter_group.CoxeterGroupAsPermutationGroup._element_class
Failed example:
    W._element_class() is W.element_class                      # optional - gap3
Exception raised:
    Traceback (most recent call last):
      File "/srv/data/findstat.imp.fu-berlin.de/sage-patchbot/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/srv/data/findstat.imp.fu-berlin.de/sage-patchbot/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 858, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.combinat.root_system.coxeter_group.CoxeterGroupAsPermutationGroup._element_class[1]>", line 1, in <module>
        W._element_class() is W.element_class                      # optional - gap3
      File "sage/structure/parent.pyx", line 854, in sage.structure.parent.Parent.__getattr__ (/srv/data/findstat.imp.fu-berlin.de/sage-patchbot/src/build/cythonized/sage/structure/parent.c:8083)
        attr = getattr_from_other_class(self, self._category.parent_class, name)
      File "sage/structure/misc.pyx", line 253, in sage.structure.misc.getattr_from_other_class (/srv/data/findstat.imp.fu-berlin.de/sage-patchbot/src/build/cythonized/sage/structure/misc.c:1763)
        raise dummy_attribute_error
    AttributeError: 'CoxeterMatrixGroup_with_category' object has no attribute '_element_class'
**********************************************************************
2 items had failures:
   1 of   4 in sage.combinat.root_system.coxeter_group.CoxeterGroupAsPermutationGroup.__init__
   1 of   3 in sage.combinat.root_system.coxeter_group.CoxeterGroupAsPermutationGroup._element_class
    [54 tests, 2 failures, 10.25 s]
----------------------------------------------------------------------
sage -t --long src/sage/combinat/root_system/coxeter_group.py  # 2 doctests failed

[stumpc5]

And then, there are also a few in gap3.py, I am not sure if we have to treat them, but if anyone knows how to do it, please go ahead (this is also necessary to get the package to be optional rather than experimental...

stumpc5@findstat:~/web-findstat/sage-patchbot$ ./sage -tp 6 --long --optional=ccache,gap3,mpir,patchbot,python2,sage src/sage/interfaces/gap3.py
too many failed tests, not using stored timings
Running doctests with ID 2016-04-21-13-15-35-52e24ead.
Git branch: t/11187/public/11187
Using --optional=ccache,gap3,mpir,patchbot,python2,sage
Doctesting 1 file using 6 threads.
sage -t --long src/sage/interfaces/gap3.py
**********************************************************************
File "src/sage/interfaces/gap3.py", line 393, in sage.interfaces.gap3.Gap3._execute_line
Failed example:
    f([1,2,3])                                   #optional - gap3
Expected:
    Traceback (most recent call last):
    ...
    RuntimeError: Gap3 produced error output   
    Error, List Element: <position> must be a positive integer at
    return L[0] ... in
    ... called from
    main loop
    brk> quit;
    ...
Got:
    <BLANKLINE>
    Traceback (most recent call last):
      File "/srv/data/findstat.imp.fu-berlin.de/sage-patchbot/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/srv/data/findstat.imp.fu-berlin.de/sage-patchbot/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 858, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.interfaces.gap3.Gap3._execute_line[3]>", line 1, in <module>
        f([Integer(1),Integer(2),Integer(3)])                                   #optional - gap3
      File "/srv/data/findstat.imp.fu-berlin.de/sage-patchbot/local/lib/python2.7/site-packages/sage/interfaces/interface.py", line 805, in __call__
        return getattr(P, self.name())(*args)
      File "/srv/data/findstat.imp.fu-berlin.de/sage-patchbot/local/lib/python2.7/site-packages/sage/interfaces/interface.py", line 607, in __call__
        return self._parent.function_call(self._name, list(args), kwds)
      File "/srv/data/findstat.imp.fu-berlin.de/sage-patchbot/local/lib/python2.7/site-packages/sage/interfaces/gap.py", line 921, in function_call
        res = self.eval(marker+cmd)
      File "/srv/data/findstat.imp.fu-berlin.de/sage-patchbot/local/lib/python2.7/site-packages/sage/interfaces/gap.py", line 573, in eval
        result = Expect.eval(self, input_line, **kwds)
      File "/srv/data/findstat.imp.fu-berlin.de/sage-patchbot/local/lib/python2.7/site-packages/sage/interfaces/expect.py", line 1239, in eval
        for L in code.split('\n') if L != ''])
      File "/srv/data/findstat.imp.fu-berlin.de/sage-patchbot/local/lib/python2.7/site-packages/sage/interfaces/gap.py", line 771, in _eval_line
        raise RuntimeError(message)
    RuntimeError: Gap3 produced error output
    Error, Function: <function> must be a function
    <BLANKLINE>
       executing __SAGE_LAST__:="__SAGE_LAST__";;x(sage0);;
**********************************************************************
File "src/sage/interfaces/gap3.py", line 440, in sage.interfaces.gap3.Gap3.help
Failed example:
    m                                        #optional - gap3
Expected:
    [ [ 1, 2, 3 ], [ 4, 5, 6 ] ]
Got:
    <BLANKLINE>
**********************************************************************
File "src/sage/interfaces/gap3.py", line 442, in sage.interfaces.gap3.Gap3.help
Failed example:
    m.Print()                                #optional - gap3
Expected:
    [ [ 1, 2, 3 ], [ 4, 5, 6 ] ]
Got:
    "__SAGE_LAST__"
**********************************************************************
File "src/sage/interfaces/gap3.py", line 446, in sage.interfaces.gap3.Gap3.help
Failed example:
    m                                        #optional - gap3
Expected:
    [ [ 1, 2, 3 ], [ 4, 5, 6 ] ]
Got:
    <BLANKLINE>
**********************************************************************
File "src/sage/interfaces/gap3.py", line 448, in sage.interfaces.gap3.Gap3.help
Failed example:
    m.Print()                                #optional - gap3
Expected:
    [ [ 1, 2, 3 ], [ 4, 5, 6 ] ]
Got:
    "__SAGE_LAST__"
**********************************************************************
2 items had failures:
   1 of   5 in sage.interfaces.gap3.Gap3._execute_line
   4 of  10 in sage.interfaces.gap3.Gap3.help
    [108 tests, 5 failures, 7.01 s]
----------------------------------------------------------------------
sage -t --long src/sage/interfaces/gap3.py  # 5 doctests failed
----------------------------------------------------------------------
Total time for all tests: 15.7 seconds
    cpu time: 2.2 seconds
    cumulative wall time: 7.0 seconds

}}}

[git]

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

​7afc02c

Fixing doctests in combinat/root_system/coxeter_group.py.

[chapoton]

not a good idea in general to use a bare except:

except:

rather find what exception it is supposed to catch

[tscrim]

I fixed the errors in combinat/root_system/coxeter_group.py (to which, we should be able to do most (all) of that functionality without appealing to GAP3 and we should probably fold that into (Irreducible)RealReflectionGroup at some point). The latter errors are indicating issues with the interface, so I would just wait on those until we do #20393. Since gap3 is an experimental package, we are not strictly required to have all # optional - gap3 doctests pass.

[git]

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

​0269425

Blanket fix bare except block.

[tscrim]

Replying to chapoton:

not a good idea in general to use a bare except:

except:

rather find what exception it is supposed to catch

Right, good catch. I'm going to try and find the precise error that gets raised, but I've pushed a hack fix for now.

[git]

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

​9b0ef92

Making it an AttributeError.

[tscrim]

Replying to tscrim:

Replying to chapoton:

not a good idea in general to use a bare except:

except:

rather find what exception it is supposed to catch

Right, good catch. I'm going to try and find the precise error that gets raised, but I've pushed a hack fix for now.

It only throws an AttributeError, and I have changed it to catch only that.

[stumpc5]

Thanks for the fixes, I am doing another round of doctests now...

[stumpc5]

okay, the only remaining failures are

sage -t --long src/sage/tests/cmdline.py  # 1 doctest failed
sage -t --long src/sage/repl/interpreter.py  # 1 doctest failed
sage -t --long src/sage/parallel/map_reduce.py  # 1 doctest failed
sage -t --long src/sage/interfaces/gap3.py  # 5 doctests failed
sage -t --long src/sage/repl/interface_magic.py  # 1 doctest failed

of which we are only responsible for gap3.py. I'd thus suggest to set this to positive review...

[hivert]

Replying to stumpc5:

okay, the only remaining failures are

sage -t --long src/sage/tests/cmdline.py  # 1 doctest failed
sage -t --long src/sage/repl/interpreter.py  # 1 doctest failed
sage -t --long src/sage/parallel/map_reduce.py  # 1 doctest failed
sage -t --long src/sage/interfaces/gap3.py  # 5 doctests failed
sage -t --long src/sage/repl/interface_magic.py  # 1 doctest failed

of which we are only responsible for gap3.py. I'd thus suggest to set this to positive review...

Hi travis,

Can you send me the log of the map_reduce.py error ? On what kinds of machine was it ? Is it reproducible ?

Florent

[stumpc5]

Replying to hivert:

Replying to stumpc5:

okay, the only remaining failures are

sage -t --long src/sage/tests/cmdline.py  # 1 doctest failed
sage -t --long src/sage/repl/interpreter.py  # 1 doctest failed
sage -t --long src/sage/parallel/map_reduce.py  # 1 doctest failed
sage -t --long src/sage/interfaces/gap3.py  # 5 doctests failed
sage -t --long src/sage/repl/interface_magic.py  # 1 doctest failed

of which we are only responsible for gap3.py. I'd thus suggest to set this to positive review...

Hi travis,

...christian.

Can you send me the log of the map_reduce.py error ? On what kinds of machine was it ? Is it reproducible ?

I didn't log the test, but I can restart it now. If it stays, I will give you the details.

[stumpc5]

all tests pass this time, sorry for not being able to get you the error...

[hivert]

Replying to stumpc5:

all tests pass this time, sorry for not being able to get you the error...

Please let me know if it happen again.

[chapoton]

Replying to hivert:

Replying to stumpc5:

all tests pass this time, sorry for not being able to get you the error...

Please let me know if it happen again.

see there for one problem with map_reduce:

​http://patchbot.sagemath.org/log/11187/Ubuntu/14.04/x86_64/3.16.0-60-generic/irma-atlas/2016-04-19%2009:27:11?short

[git]

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

​8d76520

using a cached version self._number_of_reflections to avoid computing it again and again, expecially important in has_descent

[stumpc5]

Should I actually at all still push stuff into this ticket, or should we rather get it to positive review and do everything else in individual tickets? (I have redone the doctest for reflection_group_real.py after this last change.)

[chapoton]

Please stop touching anything here if you want this to be positive reviewed soon and not in 4 more years.

[stumpc5]

if you want this to be positive reviewed soon and not in 4 more years.

That's a little harsh for my taste. Anyway, I agree that I should stop doing anything here, the list of improvements is at #20394.

[chapoton]

sorry for that, I am not in a good mood..

[stumpc5]

I would rebase this to beta5, run the patchbot and do all doctests with the gap3 flag one more time.

[git]

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

​0b6d895

Merge branch 'develop' into public/11187

[chapoton]

ok, guys, I think it is time. I am setting to positive review in the name of all authors/reviewers.

[stumpc5]

Great -- thanks to all of you for participating!