Interface to Fokko Ducloux's Coxeter 3 #12912

nthiery · 2012-05-06T15:42:55Z

Coxeter3 is a C implementation of Coxeter groups. Beside computing with elements (using the combinatorics of reduced words) it contains super fast code for bruhat order, Kazdhan-Lusztig polynomials and the like.

http://boxen.math.washington.edu/home/jpflori/coxeter3-1.1.spkg

Apply attachment: trac_12912-coxeter3-mh.patch

Add coxeter-3-1.1.spkg as optional package.

Depends on #8359

CC: @sagetrac-sage-combinat @anneschilling @jpflori

Component: packages: optional

Keywords: coxeter, days45

Author: Mike Hansen

Reviewer: Anne Schilling, Nicolas M. Thiéry, Jean-Pierre Flori

Merged: sage-5.8.beta1

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

kini · 2012-05-16T14:07:32Z

comment:2

Please set this ticket back to needs_review when there is a finished patch posted on the ticket! (I'm cleaning up needs_review tickets with no patches attached.)

fchapoton · 2012-11-19T17:00:40Z

Changed keywords from none to coxeter

anneschilling · 2013-01-30T21:47:37Z

comment:6

Nicolas figured out that the following triggers the seg fault in /libs/coxeter/coxeter.pyx

sage: from sage.libs.coxeter.co
sage.libs.coxeter.coxeter        sage.libs.coxeter.coxeter_group  
sage: from sage.libs.coxeter.coxeter import get_CoxGroup as CoxGroup
sage: W = CoxGroup(['A',1])
sage: W.bruhat_interval([],[])
[[]]
sage: W = CoxGroup(['A',2])

anneschilling · 2013-01-30T21:48:13Z

comment:7

The current patch does not handle the Coxeter group of type ['A',0] properly!

nthiery · 2013-01-30T23:17:45Z

comment:8

Replying to @anneschilling:

sage: from sage.libs.coxeter.co
sage.libs.coxeter.coxeter        sage.libs.coxeter.coxeter_group  
sage: from sage.libs.coxeter.coxeter import get_CoxGroup as CoxGroup
sage: W = CoxGroup(['A',1])
sage: W.bruhat_interval([],[])
[[]]
sage: W = CoxGroup(['A',2])

Investing further,
bruhat_interval explicitly destructs the C++ list which is defined
earlier in this method and passed to Coxeter3's interval function. Is
it really needed? If we comment it out, there is no more segfault. So
the destruction must somehow corrupt Coxeter3's internal state (though
it's strange that the segfault occurs upon constructing a new group)

Some evidence why it might not be needed:

It's a list, not a reference to a list; so c++ should destruct it at
the end of the function, right?
Assignment/copy operators seem to be appropriately defined in
Coxeter3 for CoxWord element to be put in a list and be destructed
properly.
The pointcare_polynomial does very similar things but does not call
this destructor at the end (so at least one of the two is wrong).

There does not seem to be a memory leak when one comments out the
destructor, at least not after the third call:

  sage: sage: from sage.libs.coxeter.coxeter import CoxGroup as CoxGroup
  sage: W = CoxGroup(['A',7])
  sage: w0 = WeylGroup(['A',7]).long_element().reduced_word()
  sage: sage.misc.getusage.get_memory_usage(t=None)
  sage: 911.23046875
  sage: len(W.bruhat_interval([], W(w0)))
  40320
  sage: sage: sage.misc.getusage.get_memory_usage(t=None)
  5972.0
  sage: len(W.bruhat_interval([], W(w0)))
  40320
  sage: sage.misc.getusage.get_memory_usage(t=None)
  5973.50390625
  sage: len(W.bruhat_interval([], W(w0)))
  40320
  sage: sage.misc.getusage.get_memory_usage(t=None)
  5973.50390625
  sage: len(W.bruhat_interval([], W(w0)))
  40320
  sage: sage.misc.getusage.get_memory_usage(t=None)
  5973.50390625

This is confirmed by looking at the processus memory usage.

Altogether, I guess I vote for commenting out the questionable
destructor call, and consider the issue as resolved for now. We will
see later if any issue arises once we put Coxeter 3 to heavy use.

Mike, what do you think?

Cheers,
Nicolas

mwhansen · 2013-01-30T23:29:22Z

comment:9

Nicolas -- thanks for looking into this. I've been busy with getting our housing situation taken care of (hopefully moving in on Friday). I think commenting out the destructor call is right for now. Do you want me to do it in the patch?

nthiery · 2013-01-30T23:40:20Z

comment:10

I am working on it right now, and doing a couple other cleanup's (like working around Coxeter 3 segfaulting for the trivial Coxeter group :-)).

I won't mind a double check on the result though!

nthiery · 2013-01-31T00:02:05Z

comment:11

Ok, done in the attached review patch. I am going to push it to the sage-combinat server too.

There remains a single issue: I replaced the loads/dumps tests by TestSuite call, and for all of them we dont get A == loads(dumps(A)). I am not sure how best to handle this? Shall we implement equality? Or, at least for the Coxeter groups themselves, fix the pickling to be done by construction so as to guarantee that unique representation is preserved?

Cheers,
Nicolas

anneschilling · 2013-02-05T05:27:11Z

comment:12

After discussions with Mike Hansen, we seemed to have fixed all remaining issues.

Apply: trac_12912-coxeter3-mh.patch

Nicolas, the patch is ready for its final review!

Anne

anneschilling · 2013-02-05T05:29:12Z

Reviewer: Anne Schilling, Nicolas M. Thiery

anneschilling · 2013-02-05T11:47:34Z

Dependencies: #8359

anneschilling · 2013-02-08T18:32:53Z

comment:17

Hi Jeroen,

Did get rid of the purple light by the patchbot, do you need to declare coxeter-3.0 as an optional package? I guess only you can do that, right?

Best,

Anne

anneschilling · 2013-02-09T19:46:42Z

comment:18

I folded Nicolas' review patch and uploaded the final version. Positive review (up to the review of the spkg).

Anne

nthiery · 2013-02-19T03:51:38Z

comment:53

Issue fixed in the updated patch, by having CoxGroup inherit from SageObject (since #13378, conversion can only be done from an object such that parent(x) is an instance of SageObject or a type.

The updated patch also improves the documentation for Kazhdan-Lusztig polynomials and renames the directory to sage.libs.coxeter3 for consistency with the package name. We cross-reviewed the changes with Anne.

Positive review!

nthiery · 2013-02-19T03:55:09Z

comment:54

Replying to @jpflori:

Once correctly installed it seems to work on Cygwin!

I'm not convinced the coxeter_group.py in sage/libs do really belong there.

I also wondered about it. At the end of the day, I find that it's really just a wrapper around the stuff implemented in coxeter.pyx, and is therefore best left there for code locality.

anneschilling · 2013-02-19T15:36:37Z

comment:56

Everything indeed looks good except for a few small changes Mark Shimozono and I want to make to parabolic KL polynomials. If this cannot be done quickly, we will separate those out as a separate patch.

Anne

anneschilling · 2013-02-19T20:49:01Z

comment:58

Mark Shimozono and I added some more documentation and tests for parabolic KLs. We also implemented various conventions of the KLs.

So back to positive review!

Anne

jdemeyer · 2013-02-20T11:04:36Z

comment:60

sage -t  -force_lib devel/sage/sage/libs/coxeter3/coxeter_group.py
**********************************************************************
File "/release/merger/sage-5.8.beta1/devel/sage-main/sage/libs/coxeter3/coxeter_group.py", line 304:
    sage: W = CoxeterGroup(['A',3],implementation='coxeter3')
Exception raised:
    Traceback (most recent call last):
      File "/release/merger/sage-5.8.beta1/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/release/merger/sage-5.8.beta1/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/release/merger/sage-5.8.beta1/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_18[2]>", line 1, in <module>
        W = CoxeterGroup(['A',Integer(3)],implementation='coxeter3')###line 304:
    sage: W = CoxeterGroup(['A',3],implementation='coxeter3')
      File "/release/merger/sage-5.8.beta1/local/lib/python/site-packages/sage/combinat/root_system/coxeter_group.py", line 85, in Coxeter
Group
        raise RuntimeError, "coxeter3 must be installed"
    RuntimeError: coxeter3 must be installed
**********************************************************************

and some more like this...

mwhansen · 2013-02-20T12:46:10Z

comment:61

It looks like a few more tests need to be marked optional.

nthiery · 2013-02-20T13:25:46Z

comment:62

I am on it ...

nthiery · 2013-02-20T15:52:25Z

comment:63

Attachment: trac_12912-coxeter3-mh.patch.gz

haraldschilly · 2013-02-22T13:35:40Z

comment:66

spkg is on its way to the servers!

jdemeyer · 2013-02-22T19:10:49Z

Merged: sage-5.8.beta1

nthiery added this to the sage-5.7 milestone May 6, 2012

nthiery added c: combinatorics labels May 6, 2012

nthiery assigned sagetrac-sage-combinat May 6, 2012

This comment has been minimized.

Sign in to view

nthiery added the s: needs review label May 6, 2012

kini added s: needs work and removed s: needs review labels May 16, 2012

This comment has been minimized.

Sign in to view

anneschilling added s: needs review and removed s: needs work labels Feb 5, 2013

This comment has been minimized.

Sign in to view

nthiery added the s: positive review label Feb 19, 2013

jdemeyer added c: packages: optional and removed c: combinatorics labels Feb 19, 2013

jdemeyer modified the milestones: sage-5.7, sage-5.8 Feb 19, 2013

anneschilling added s: needs work and removed s: positive review labels Feb 19, 2013

anneschilling added s: positive review and removed s: needs work labels Feb 19, 2013

jdemeyer added s: needs work and removed s: positive review labels Feb 20, 2013

This comment has been minimized.

Sign in to view

nthiery added s: needs review and removed s: needs work labels Feb 20, 2013

This comment has been minimized.

Sign in to view

anneschilling added s: positive review and removed s: needs review labels Feb 20, 2013

jdemeyer removed the s: positive review label Feb 22, 2013

jdemeyer closed this as completed Feb 22, 2013

nthiery mentioned this issue Feb 28, 2013

Remove coxeter matrix implementation for type H (the generic implementation is just as good) #14174

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Interface to Fokko Ducloux's Coxeter 3 #12912

Interface to Fokko Ducloux's Coxeter 3 #12912

nthiery commented May 6, 2012

This comment has been minimized.

kini commented May 16, 2012

fchapoton commented Nov 19, 2012

This comment has been minimized.

This comment has been minimized.

anneschilling commented Jan 30, 2013

anneschilling commented Jan 30, 2013

nthiery commented Jan 30, 2013

mwhansen commented Jan 30, 2013

nthiery commented Jan 30, 2013

nthiery commented Jan 31, 2013

anneschilling commented Feb 5, 2013

This comment has been minimized.

anneschilling commented Feb 5, 2013

anneschilling commented Feb 5, 2013

This comment has been minimized.

This comment has been minimized.

anneschilling commented Feb 8, 2013

anneschilling commented Feb 9, 2013

This comment has been minimized.

nthiery commented Feb 19, 2013

nthiery commented Feb 19, 2013

anneschilling commented Feb 19, 2013

anneschilling commented Feb 19, 2013

jdemeyer commented Feb 20, 2013

mwhansen commented Feb 20, 2013

nthiery commented Feb 20, 2013

nthiery commented Feb 20, 2013

This comment has been minimized.

This comment has been minimized.

haraldschilly commented Feb 22, 2013

jdemeyer commented Feb 22, 2013

Interface to Fokko Ducloux's Coxeter 3 #12912

Interface to Fokko Ducloux's Coxeter 3 #12912

Comments

nthiery commented May 6, 2012

This comment has been minimized.

kini commented May 16, 2012

fchapoton commented Nov 19, 2012

This comment has been minimized.

This comment has been minimized.

anneschilling commented Jan 30, 2013

anneschilling commented Jan 30, 2013

nthiery commented Jan 30, 2013

mwhansen commented Jan 30, 2013

nthiery commented Jan 30, 2013

nthiery commented Jan 31, 2013

anneschilling commented Feb 5, 2013

This comment has been minimized.

anneschilling commented Feb 5, 2013

anneschilling commented Feb 5, 2013

This comment has been minimized.

This comment has been minimized.

anneschilling commented Feb 8, 2013

anneschilling commented Feb 9, 2013

This comment has been minimized.

nthiery commented Feb 19, 2013

nthiery commented Feb 19, 2013

anneschilling commented Feb 19, 2013

anneschilling commented Feb 19, 2013

jdemeyer commented Feb 20, 2013

mwhansen commented Feb 20, 2013

nthiery commented Feb 20, 2013

nthiery commented Feb 20, 2013

This comment has been minimized.

This comment has been minimized.

haraldschilly commented Feb 22, 2013

jdemeyer commented Feb 22, 2013