Combinatorial implementation of the affine symmetric group

dec4a3e9-7377-4ea4-ae7b-b43807ab08bd commented 12 years ago

This is a combinatorial implementation of the affine symmetric group, providing a second implementation of the WeylGroup(['A',k,1]), but quite a bit faster. Also included are combinatorial implmenetations of affine types B,C,D and G. Extension to types E and F should be possible.

Apply:

attachment: trac_12940_affine_permutations-td.patch

Depends on #14673 Depends on #8392

CC: @nthiery @anneschilling @sagetrac-chrisjamesberg

Component: combinatorics

Keywords: affine, days38, days49

Author: Tom Denton

Reviewer: Chris Berg, Anne Schilling

Merged: sage-5.11.rc0

Issue created by migration from https://trac.sagemath.org/ticket/12940

dec4a3e9-7377-4ea4-ae7b-b43807ab08bd commented 12 years ago

Attachment: affine_permutations.pyx.gz

affine permutations class. (Attach this first, if testing.)

dec4a3e9-7377-4ea4-ae7b-b43807ab08bd commented 12 years ago

Attachment: affine_symmetric_group.py.gz

Affine symmetric group class file.

dec4a3e9-7377-4ea4-ae7b-b43807ab08bd commented 12 years ago

Attachment: affine_permutations.py.gz

dec4a3e9-7377-4ea4-ae7b-b43807ab08bd commented 12 years ago

comment:2

Removed the cython-ified version of the affine permutations class as it was creating issues, and wasn't really improving run times that much. Made numerous algorithm improvements, though; the patch is now int he sage-combinat queue as well.

anneschilling commented 12 years ago

comment:3

Hi Tom,

It looks like that Affine Permutations really need to be integrated into the sage file system. At the moment this seems to be a stand-alone patch!

Best,

Anne

dec4a3e9-7377-4ea4-ae7b-b43807ab08bd commented 12 years ago

comment:4

Ok, at long last, I've fixed up the sage combinat patch and exported; it's the attachment above. It should also patch the sage files that point out that the new directory and file exist!

anneschilling commented 12 years ago

comment:5

Hi Tom,

Could we entice you to add a to_core method? Also, some of your documentation using INPUT: etc is not standard and needs to be fixed. And ... please put your patch on the sage-combinat queue.

Cheers,

Anne

dec4a3e9-7377-4ea4-ae7b-b43807ab08bd commented 12 years ago

comment:6

Ok, changed the documentation, updated the patch in the combinat queue, and added some new functions.

There are two ways to pull a dominant element out of an affine permutation: one is to sort the Lehmer code, and the other is to write x=g*f, where g is dominant and f is finite type (0-parabolic). The to_dominant method does the sorting, and the grassmannian_quotient() method returns the pair (g,f). (Or (f,g) if you specify side='left'.) I also put in a to_core method, which uses the sorting approach. One can get the core for the quotient element by doing x.grassmannian_quotient()[0].to_core().

Best, -tom

anneschilling commented 12 years ago

comment:7

Hi Tom,

Without looking at the mathematics yet, here are some Sage specific requirements that your patch does not yet fulfill:

You need 100% coverage:

$affine_permutations anne$ sage -coverage affine_permutations.py 
----------------------------------------------------------------------
affine_permutations.py
ERROR: Please add a `TestSuite(s).run()` doctest.
SCORE affine_permutations.py: 95% (46 of 48)

Missing doctests:
     * __init__(self, parent, lst, check=True):
     * random_element(self, n):

Possibly wrong (function name doesn't occur in doctests):
     * _repr_(self):
     * check(self):
     * lower_covers(self,side="right"):
     * _element_constructor_(self, *args, **keywords):
     * _repr_(self):
     * is_crystallographic(self):
     * _an_element_(self):

The preamble of your patch needs to start with #12940: Title + then a summary of what this patch implements.
The indents of your tests are not right for many of your methods. You need

    EXAMPLES::

        sage: ....

Look at your documentation by building it via

sage -docbuild reference html

I can already see many places where you forgot for math display such as in\ZZ`.

So much for now,

Anne

dec4a3e9-7377-4ea4-ae7b-b43807ab08bd commented 12 years ago

comment:8

Ok, fixed up the docs. I hadn't seen the -coverage command before. The ones that are giving warnings now are methods (like _repr_) that are implicitly called within the doc test for that function.

I went through and fixed up latex parts by hand, and am still waiting on the documentation to build to really make a visual check...

Best, -tom

anneschilling commented 12 years ago

comment:9

Thanks, tom. You can put #indirect doctest in the line after your test to calm the

sage -coverage

command, if the test indeed indirectly tests the method.

Anne

anneschilling commented 12 years ago

comment:10

Hi tom,

Some more Sage comments:

Currently you have a directory in /sage/combinat called affine_permutations, but there is only one file in there, namely affine_permutations.py. Unless you forsee the addition of further file to break up the code, I would strongly suggest to get rid of the directory and just put affine_permutations.py in /sage/cominbat as is done for permutations, partitions etc..
For the documentation you need to put a link in /doc/en/reference/combinat

Best,

Anne

nthiery commented 12 years ago

comment:11

Hi Tom!

For the directory structure, you may want to follow that of permutation groups. Something like:

    sage/groups/affine_permutation_groups/affine_permutation.py
                                          affine_symmetric_group.py
                                          affine_permutation_group.py

Which just made me think: is there a way to generalize the algorithmic for permutation groups (see http://en.wikipedia.org/wiki/Strong_generating_set) to subgroups of the affine symmetric group? Hmm, if this hasn't been done yet, that could be a fun research project. Of course, the obvious first candidates to play with would be the affine coxeter groups realized as groups of permutations as we had discussed in Montreal.

Cheers, Nicolas

dec4a3e9-7377-4ea4-ae7b-b43807ab08bd commented 11 years ago

comment:12

Hello!

I've been trying to get this expanded and finished up. The following changes happened lately:

Changed the names of things to AffinePermutation and AffinePermutationGroup, because:
I added affine permutation groups of types ABCDG. (E and F are in Eriksson, but are ugly; I want to think about whether there's a cleaner way to go about these ones.)
Everything is just in the file affine_permutations.py, which sits directly in sage/combinat

I'm now getting a problem I can't figure out, though: Sage is refusing to import the AffinePermutationGroup name. It doesn't seem to be previously defined, and when I disable all of the import statements I still get an error (so it can't be an import loop; also, nothing calls my file...). I can manually attach the file just fine, too.

I've stared at this a good long time and haven't been able to figure out what's going wrong...

haraldschilly commented 11 years ago

comment:13

Replying to @sdenton4:

Hello!

I've been trying to get this expanded and finished up. The following changes happened lately:

Changed the names of things to AffinePermutation and AffinePermutationGroup, because:

I added affine permutation groups of types ABCDG. (E and F are in Eriksson, but are ugly; I want to think about whether there's a cleaner way to go about these ones.)

Everything is just in the file affine_permutations.py, which sits directly in sage/combinat

I'm now getting a problem I can't figure out, though: Sage is refusing to import the AffinePermutationGroup name. It doesn't seem to be previously defined, and when I disable all of the import statements I still get an error (so it can't be an import loop; also, nothing calls my file...). I can manually attach the file just fine, too.

I've stared at this a good long time and haven't been able to figure out what's going wrong...

Anne tries to write: Don't you mean non-twisted rather than non-exceptional? Type G is exceptional!

anneschilling commented 11 years ago

comment:14

Hi Tom,

I just answered your question on sage-combinat. In short, you need to remove some old files left over from your /combinat/affine_permutations/ directory by hand since it gets confused about the file and the directory.

Also, to be consistent with permutation.py, core.py, etc, shouldn't your file be called affine_permutation.py (without the s)?

In the documentation of AffinePermuation you says

    These are combinatorial implmentations of the affine Weyl groups of
    non-exceptional type as permutations of the set of all integers.
    the basic algorithms are derived from Bjorner and Brenti's `Combinatorics
    of Coxeter Groups.'

Don't you mean non-twisted rather than non-exceptional. Type G is exceptional!

Best,

Anne

dec4a3e9-7377-4ea4-ae7b-b43807ab08bd commented 11 years ago

Replying to @sdenton4:

This is a combinatorial implementation of the affine symmetric group, providing a second implementation of the WeylGroup(['A',k,1]), but quite a bit faster. The basic idea should be easily extensible to the combinatorial interpretations of the other affine types with window notations, and I've discussed a bit with N. Thiery about hacking together a kind of window notation for the other types.

dec4a3e9-7377-4ea4-ae7b-b43807ab08bd commented 11 years ago

Description changed:

--- 
+++ 
@@ -1 +1 @@
-This is a combinatorial implementation of the affine symmetric group, providing a second implementation of the WeylGroup(['A',k,1]), but quite a bit faster.  The basic idea should be easily extensible to the combinatorial interpretations of the other affine types with window notations, and I've discussed a bit with N. Thiery about hacking together a kind of window notation for the other types.
+This is a combinatorial implementation of the affine symmetric group, providing a second implementation of the WeylGroup(['A',k,1]), but quite a bit faster.  Also included are combinatorial implmenetations of affine types B,C,D and G.  Extension to types E and F should be possible.

dec4a3e9-7377-4ea4-ae7b-b43807ab08bd commented 11 years ago

comment:16

Recent changes:

Moved everything into a single file, as per reviewer request
Expanded to include types affine A,B,C,D,G
added TestSuite runs, for better coverage
fixed a bug with apply_simple_reflection_left in Type G

dec4a3e9-7377-4ea4-ae7b-b43807ab08bd commented 11 years ago

comment:17

Added is_fully_commutative to type A. Rebased to fix an issue with the new documentation system.

d561a5fa-51dc-41bc-86f5-988f7f02b59b commented 11 years ago

comment:19

Nicolas volunteered me to review the patch. =) I sent my comments directly to Tom. When he posts a new version, I can review that.

Chris

d561a5fa-51dc-41bc-86f5-988f7f02b59b commented 11 years ago

Reviewer: Chris Berg

tscrim commented 11 years ago

Dependencies: #14673

tscrim commented 11 years ago

comment:20

This will need to have a minor rebase over #14673.

d561a5fa-51dc-41bc-86f5-988f7f02b59b commented 11 years ago

Changed keywords from affine, days38 to affine, days38, days49

anneschilling commented 11 years ago

comment:22

Hi Tom,

I think you need to rebase your patch on top of #8392. There is a conflict with the all.py file!

Also, would it be possible to explain the input of AffinePermutations in the header, since this is what the user will see if (s)he types AffinePermutations??.

Thank you!

Anne

anneschilling commented 11 years ago

comment:23

Hi Tom,

I put a rebased version of the patch on the sage-combinat queue. But please also add the input information for the AffinePermutations.

Anne

anneschilling commented 11 years ago

Changed reviewer from Chris Berg to Chris Berg, Anne Schilling

anneschilling commented 11 years ago

Changed dependencies from #14673 to #14673, #8392

anneschilling commented 11 years ago

comment:25

Hi Tom,

Here are some more comments about your patch:

is_i_grassmannian(i=0, side='right') needs a description of the input (like the i).
Please explain the input of to_weyl_group_element(W=None)
has_right_descent has a description of an option which is not there ('right' or 'left'). Same for has_left_descent.
Everywhere in the file you seem to use OPTIONS:. This should be replaced by or combined with INPUT. Also, as far as I know the syntax is

- ``variable`` -- description of what it does.

Tom, could you make the above changes? Also, I left a review patch called trac_12940-review-as.patch on the sage-combinat queue. Please fold it into the rebased patch on the sage-combinat queue.

Thanks!

Anne

anneschilling commented 11 years ago

comment:26

Hi Tom,

One more comment: please use

REFERENCE:

[XXX] blaba

for references and cite them via [XXX]_. See elsewhere in Sage how this is done!

Anne

dec4a3e9-7377-4ea4-ae7b-b43807ab08bd commented 11 years ago

Attachment: trac_12940_affine_permutations-td.2.patch.gz

anneschilling commented 11 years ago

Description changed:

--- 
+++ 
@@ -1 +1,5 @@
 This is a combinatorial implementation of the affine symmetric group, providing a second implementation of the WeylGroup(['A',k,1]), but quite a bit faster.  Also included are combinatorial implmenetations of affine types B,C,D and G.  Extension to types E and F should be possible.
+
+Apply:
+- [attachment: trac_12940_affine_permutations-td.patch](https://github.com/sagemath/sage-prod/files/10655486/trac_12940_affine_permutations-td.patch.gz)
+

jdemeyer commented 11 years ago

Changed author from tom denton to Tom Denton

jdemeyer commented 11 years ago

comment:29

The patch needs a proper commit message (use hg qrefresh -e to change the message).

anneschilling commented 11 years ago

Attachment: trac_12940_affine_permutations-td.3.patch.gz

anneschilling commented 11 years ago

Description changed:

--- 
+++ 
@@ -1,5 +1,5 @@
 This is a combinatorial implementation of the affine symmetric group, providing a second implementation of the WeylGroup(['A',k,1]), but quite a bit faster.  Also included are combinatorial implmenetations of affine types B,C,D and G.  Extension to types E and F should be possible.

 Apply:
-- [attachment: trac_12940_affine_permutations-td.patch](https://github.com/sagemath/sage-prod/files/10655486/trac_12940_affine_permutations-td.patch.gz)
+- [attachment: trac_12940_affine_permutations-td.3.patch](https://github.com/sagemath/sage-prod/files/10655485/trac_12940_affine_permutations-td.3.patch.gz)

d561a5fa-51dc-41bc-86f5-988f7f02b59b commented 11 years ago

comment:31

Apply: trac_12940_affine_permutations-td.3.patch

jdemeyer commented 11 years ago

comment:32

This patch badly abuses assert statements. Assertions should be used to check correctness of the code, not to validate user input. Any AssertionError caused by the use of public functions is by definition a bug.

jdemeyer commented 11 years ago

comment:33

Also, while you're at it, could you use the new style doctest continuations:

sage: for a in CP: 
....:     p.to_lehmer_code(a[0],a[1])

instead of

sage: for a in CP: 
...     p.to_lehmer_code(a[0],a[1])

dec4a3e9-7377-4ea4-ae7b-b43807ab08bd commented 11 years ago

comment:34

I'm confused, then; my understanding of the clonable array class was that it needs to have a check method which throws assertion errors if the 'checked' clonable array doesn't actually check out as a proper object. This checks simultaneously for user errors and for code errors.

Could you point me to a discussion or coding convention on proper ways to use assert statements or check for input correctness?

dec4a3e9-7377-4ea4-ae7b-b43807ab08bd commented 11 years ago

Description changed:

--- 
+++ 
@@ -1,5 +1,5 @@
 This is a combinatorial implementation of the affine symmetric group, providing a second implementation of the WeylGroup(['A',k,1]), but quite a bit faster.  Also included are combinatorial implmenetations of affine types B,C,D and G.  Extension to types E and F should be possible.

 Apply:
-- [attachment: trac_12940_affine_permutations-td.3.patch](https://github.com/sagemath/sage-prod/files/10655485/trac_12940_affine_permutations-td.3.patch.gz)
+- [attachment: trac_12940_affine_permutations-td.patch](https://github.com/sagemath/sage-prod/files/10655486/trac_12940_affine_permutations-td.patch.gz)

dec4a3e9-7377-4ea4-ae7b-b43807ab08bd commented 11 years ago

comment:36

Changed all assert statements outside of the 'check' and '_test.+' methods into ValueErrors. Others left as 'assert' according to conventions in: http://www.sagemath.org/doc/reference/structure/sage/structure/list_clone.html

jdemeyer commented 11 years ago

comment:37

Replying to @sdenton4:

Could you point me to a discussion or coding convention on proper ways to use assert statements or check for input correctness?

This has been discussed before, but I can't find the discussion anymore. There is some discussion at http://stackoverflow.com/questions/944592/best-practice-for-python-assert/945135#945135

Assertions (and this is not specific to Sage or Python) are internal checks for code correctness. Don't forget that assertions can be turned off (run Python with -O switch) and you don't want user code to depend on whether on not assertions are enabled.

I think of assertion failures as serious as a crash due to a Segmentation Fault: it is always a bug in the program if one occurs.

Most of the assertions in this ticket should be replaced by something of the form

if not some_condition:
    raise ValueError("some_condition failed")

or TypeError depending on the kind of error.

jdemeyer commented 11 years ago

comment:39

Replying to @sdenton4:

Changed all assert statements outside of the 'check' and '_test.+' methods into ValueErrors. Others left as 'assert' according to conventions in: http://www.sagemath.org/doc/reference/structure/sage/structure/list_clone.html

I think that IncreasingArray is doing things wrongly, so don't copy from that. It's not so bad though, since IncreasingArray is not meant to be used directly by users (it's a "small extension class for testing ClonableArray").

dec4a3e9-7377-4ea4-ae7b-b43807ab08bd commented 11 years ago

comment:40

I think that's the whole idea of the check methods: they aren't directly accessed by the user, but called to check the integrity of the object.

dec4a3e9-7377-4ea4-ae7b-b43807ab08bd commented 11 years ago

comment:41

Similarly, should one use asserts or exceptions in test suite methods?

jdemeyer commented 11 years ago

comment:42

Replying to @sdenton4:

Similarly, should one use asserts or exceptions in test suite methods?

In test suites, assertions are fine.

jdemeyer commented 11 years ago

comment:43

The following is still a bug. It's a clear example of bad user input leading to an AssertionError:

sage: AffinePermutationGroup(['A',8,1])([0])
---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
...
AssertionError: Length of list must be k+1=9.

jdemeyer commented 11 years ago

comment:44

Replying to @sdenton4:

I think that's the whole idea of the check methods: they aren't directly accessed by the user

It doesn't matter if they are directly or indirectly accessed by the user, what matters is that these "check" methods are used for validating user input.

sagemath / sage

Combinatorial implementation of the affine symmetric group #12940