faster generator for noncrossing partitions

[fchapoton]

By not running over the full reflection group..

CC: @tscrim @stumpc5

Component: combinatorics

Author: Frédéric Chapoton, Christian Stump

Branch/Commit: 2dc91f5

Reviewer: Christian Stump, Frédéric Chapoton

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

[fchapoton]

New commits:

c4c7bb4

faster generation of noncrossing partitions

[fchapoton]

Branch: u/chapoton/27924

[fchapoton]

Commit: c4c7bb4

[stumpc5]

comment:2

I am a little uncertain whether or not to compute the reflection length in the unitary group or not.

Reflection length is the minimal number of reflections needed to write the element, in_unitary_group means the dimension of the move-space dim(w-1).

Both are equal for real groups and, in complex groups, for elements below Coxeter elements. It remains unclear to me whether or not we are allowed to use in_unitary_group here for the computation (which is in general much faster).

[fchapoton]

comment:3

I tried using in_unitary_group and the timings were similar.

By the way, I cannot test with gap3, as I am not able to install Chevie.

[stumpc5]

comment:4

Well, I only implemented all this with chevie in mind and at hand. Let me do some timings before proceeding. Also, I have to think about the theoretical question how to compute the noncrossing partitions.

[stumpc5]

comment:5

There is no difference for real groups, but there is for non-real complex groups:
Using reflection lengths, we get

sage: W = ReflectionGroup([3,1,4])
sage: %time len(list(W.elements_below_coxeter_element()))
CPU times: user 8.41 s, sys: 2.36 s, total: 10.8 s
Wall time: 2min 16s
70

while using move space dimensions, we get

sage: W = ReflectionGroup([3,1,4])
sage: %time len(list(W.elements_below_coxeter_element()))
CPU times: user 2.42 s, sys: 633 ms, total: 3.05 s
Wall time: 3.38 s
70

[stumpc5]

comment:6

I believe that I convinced myself at some point that we are allowed to use move space dimension here, so
if u.reflection_length(in_unitary_group=True) + 1 == w_len instead of if u.reflection_length() + 1 == w_len, but I cannot remember the argument at the moment.

[sagetrac-git]

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

98cdb0f

trac 27924 some details

[sagetrac-git]

Changed commit from c4c7bb4 to 98cdb0f

[fchapoton]

comment:8

ok, here it goes. Did you check if the new algo is a strong improvement over the old one ?

[stumpc5]

comment:9

Yes it is a good improvement:

sage: W = ReflectionGroup([3,1,4])
sage: %time len(list(W.elements_below_coxeter_element()))
CPU times: user 5.41 s, sys: 1.28 s, total: 6.69 s
Wall time: 7.03 s
70

[fchapoton]

comment:10

So, is this a positive review ? Patchbot is green.

[stumpc5]

Changed branch from u/chapoton/27924 to u/stumpc5/27924

[stumpc5]

comment:12

So, is this a positive review?

No, I am now clarifying the methods "elements_below_coxeter_element" and "noncrossing_partition_lattice". Have to leave now, will get back this afternoon. Let me know what you think in case you care!

---

New commits:

2c747ec

simplifying and stramlining noncrossing partition lattices

[stumpc5]

Changed commit from 98cdb0f to 2c747ec

[sagetrac-git]

Changed commit from 2c747ec to 39aec91

[sagetrac-git]

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

39aec91

polishing ncp and doctests

[stumpc5]

Changed author from Frédéric Chapoton to Frédéric Chapoton, Christian Stump

[stumpc5]

comment:14

okay, ready for review, I guess.

[stumpc5]

Reviewer: Christian Stump

[fchapoton]

comment:15

• doc of reflection_order_ideal must be refreshed (INPUT in particular)

• deprecation must be doctested

• commented lines should be removed

[sagetrac-git]

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

72103cf

updated doctests, removed commented code

[sagetrac-git]

Changed commit from 39aec91 to 72103cf

[sagetrac-git]

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

002a870

missed indention

[sagetrac-git]

Changed commit from 72103cf to 002a870

[stumpc5]

comment:18

okay, done

[fchapoton]

comment:19

I have made some small changes. If you agree with them, you can set to positive.

---

New commits:

2dc91f5

trac 27924 some details

[fchapoton]

Changed branch from u/stumpc5/27924 to public/ticket/27924

[fchapoton]

Changed commit from 002a870 to 2dc91f5

[stumpc5]

Changed reviewer from Christian Stump to Christian Stump, Frédéric Chapoton

[vbraun]

Changed branch from public/ticket/27924 to 2dc91f5