Opened 5 years ago

Closed 5 years ago

#12912 closed enhancement (fixed)

Interface to Fokko Ducloux's Coxeter 3

Reported by: nthiery Owned by: sage-combinat
Priority: major Milestone: sage-5.8
Component: packages: optional Keywords: coxeter, days45
Cc: sage-combinat, anne, jpflori Merged in: sage-5.8.beta1
Authors: Mike Hansen Reviewers: Anne Schilling, Nicolas M. Thiéry, Jean-Pierre Flori
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #8359 Stopgaps:

Description (last modified by nthiery)

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 trac_12912-coxeter3-mh.patch

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

Attachments (1)

trac_12912-coxeter3-mh.patch (100.2 KB) - added by nthiery 5 years ago.

Download all attachments as: .zip

Change History (68)

comment:1 Changed 5 years ago by nthiery

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

comment:2 Changed 5 years ago by kini

  • Status changed from needs_review to needs_work

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.)

comment:3 Changed 5 years ago by chapoton

  • Keywords coxeter added

comment:4 Changed 5 years ago by mhansen

  • Cc anne added
  • Description modified (diff)

comment:5 follow-up: Changed 5 years ago by tscrim

  • Description modified (diff)

comment:6 in reply to: ↑ 5 ; follow-ups: Changed 5 years ago by aschilling

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])

comment:7 in reply to: ↑ 6 Changed 5 years ago by aschilling

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

comment:8 in reply to: ↑ 6 Changed 5 years ago by nthiery

Replying to aschilling:

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

comment:9 Changed 5 years ago by mhansen

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?

comment:10 Changed 5 years ago by nthiery

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!

comment:11 follow-up: Changed 5 years ago by nthiery

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

comment:12 in reply to: ↑ 11 Changed 5 years ago by aschilling

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

comment:13 Changed 5 years ago by aschilling

  • Description modified (diff)
  • Reviewers set to Anne Schilling, Nicolas M. Thiery
  • Status changed from needs_work to needs_review

comment:14 Changed 5 years ago by aschilling

  • Dependencies set to #8359

comment:15 Changed 5 years ago by aschilling

  • Description modified (diff)

comment:16 follow-up: Changed 5 years ago by aschilling

  • Description modified (diff)

comment:17 in reply to: ↑ 16 ; follow-up: Changed 5 years ago by aschilling

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

comment:18 in reply to: ↑ 17 Changed 5 years ago by aschilling

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

Anne

comment:19 Changed 5 years ago by nthiery

  • Cc jpflori added
  • Description modified (diff)

I have just been through the spkg, and added a SPKG.txt and a minimal testsuite. If someone can double check them, this is good to go I guess.

Jean-Pierre: would you be so kind as to try the spkg under cygwin to see how it goes? Not that we really need it now, but that could catch other platform issues. A second eye on the SPKG won't hurt as well.

Thanks!

Nicolas

comment:20 follow-up: Changed 5 years ago by nthiery

  • Status changed from needs_review to needs_work
  • Work issues set to category setting

Oops, the category is not set properly:

sage: CoxeterGroup(["H",3], implementation="coxeter3").category()
Category of finite weyl groups

Should be finite Coxeter groups.

comment:21 Changed 5 years ago by bump

On Mac OS Lion (10.7.5) the Coxeter3 spkg fails with the following. It works on Anne's 10.6.8 Mac.

Note that g++ can't make sense of the -soname option. The question is why and is this needed.

If we remove the -soname option then it is broke on Anne's machine.

$ sage -f ~/patches/coxeter3-1.0.spkg
coxeter3-1.0
====================================================
Extracting package /Users/bump/patches/coxeter3-1.0.spkg
-rw-r--r--@ 1 bump  staff  5462933 Feb 13 09:53 /Users/bump/patches/coxeter3-1.0.spkg
Finished extraction
****************************************************
Host system:
Darwin tracer 11.4.2 Darwin Kernel Version 11.4.2: Thu Aug 23 16:25:48 PDT 2012; root:xnu-1699.32.7~1/RELEASE_X86_64 x86_64
****************************************************
C compiler: gcc
C compiler version:
Using built-in specs.
COLLECT_GCC=gcc

[snip]

g++ -c  -O2 -fPIC -g -DFAST -DALLTRUE sage.cpp
g++ -c  -O2 -fPIC -g -DFAST -DALLTRUE special.cpp
In file included from special.cpp:10:0:
directories.h:27:31: warning: deprecated conversion from string constant to 'char*' [-Wwrite-strings]
directories.h:28:28: warning: deprecated conversion from string constant to 'char*' [-Wwrite-strings]
directories.h:29:29: warning: deprecated conversion from string constant to 'char*' [-Wwrite-strings]
g++ -shared -Wl,-soname,libcoxeter3.so -o libcoxeter3.so affine.o automata.o bits.o cells.o commands.o constants.o coxgroup.o coxtypes.o error.o fcoxgroup.o files.o general.o graph.o help.o interactive.o interface.o invkl.o io.o kl.o klsupport.o main.o memory.o minroots.o posets.o sage.o schubert.o special.o transducer.o type.o typeA.o uneqkl.o wgraph.o -lc
ld: unknown option: -soname
collect2: ld returned 1 exit status
make: *** [coxeter] Error 1
cp: libcoxeter3.dylib: No such file or directory

real	0m9.362s
user	0m8.574s
sys	0m0.421s
Successfully installed coxeter3-1.0
Deleting temporary build directory
/Users/bump/src/sage-5.7.beta4/spkg/build/coxeter3-1.0
Finished installing coxeter3-1.0.spkg
Forcing sage-location, probably because a new package was installed.
Updating various hardcoded paths...
(Please wait at most a few minutes.)
DO NOT INTERRUPT THIS.
Done updating paths.

Last edited 5 years ago by bump (previous) (diff)

comment:22 in reply to: ↑ 20 Changed 5 years ago by aschilling

The updated patch fixes the WeylGroup? versus CoxeterGroup? issue that Nicolas mentioned. It also fixed a segfault caused by computing KL polynomial for elements that are not comparable in Bruhat order

sage: W = CoxeterGroup(['A', 3], implementation='coxeter3')
sage: W.kazhdan_lusztig_polynomial([1],[3,2])
------------------------------------------------------------------------
Unhandled SIGSEGV: A segmentation fault occurred in Sage.
This probably occurred because a *compiled* component of Sage has a bug
in it and is not properly wrapped with sig_on(), sig_off(). You might
want to run Sage under gdb with 'sage -gdb' to debug this.
Sage will now terminate.

The implementation of the parabolic KL polynomials is changed so that it works with infinite Coxeter groups.

Anne

comment:23 Changed 5 years ago by aschilling

  • Status changed from needs_work to needs_review

comment:24 Changed 5 years ago by aschilling

  • Keywords days45 added

comment:25 follow-up: Changed 5 years ago by mhansen

It seems like Dan's computer is not being picked up as a mac. What does he get when doing just running "uname" on his 10.7 box.

comment:26 in reply to: ↑ 25 Changed 5 years ago by nthiery

Replying to mhansen:

It seems like Dan's computer is not being picked up as a mac. What does he get when doing just running "uname" on his 10.7 box.

It is being picked up as a mac!

It's kind of the converse: the -soname option that is added by the Makefile under Darwin is not accepted by his compiler. My impression is that the compilation on Dan's machine (running Lion) is using Sage's own gcc (which like on Linux does not seem to need/want the soname option), whereas on Anne's machine one uses the system wide gcc by Apple (which seem to requires this option). I am wondering what's the standard way to handle this.

Cheers,

comment:27 Changed 5 years ago by jpflori

On Cygwin I get:

g++ -shared -Wl,-soname,libcoxeter3.so -o libcoxeter3.so special.o memory.o schubert.o help.o transducer.o type.o affine.o invkl.o klsupport.o uneqkl.o coxtypes.o interface.o cells.o posets.o commands.o graph.o wgraph.o main.o coxgroup.o io.o kl.o constants.o interactive.o error.o files.o fcoxgroup.o bits.o general.o automata.o typeA.o sage.o minroots.o -lc
memory.o: file not recognized: File format not recognized
collect2: error: ld returned 1 exit status

comment:28 Changed 5 years ago by jpflori

Some random remarks:

  • check youre actually in a Sage environment at the beginning of spkg-install
  • the way you patch is really strange, isn't it possible to use proper patches?
  • use $MAKE in spkg-install
  • check for errors in spkg-install

There are .o objects in the src dir, I guess that's why it fails on Cygwin and OS X, these are object files for Linux.

comment:29 Changed 5 years ago by jpflori

And you will obviously not copy the right library file on Cygwin.

Could you create an install target in the makefile that would simplify installation?

comment:30 Changed 5 years ago by jpflori

  • Status changed from needs_review to needs_work

In fact you will copy the .so file, but I don't see why a .dylib file should be created when looking at the makefile... so you won't copy anything on mac os x.

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

comment:32 Changed 5 years ago by nthiery

Thanks much Jean-Pierre for your comments!

Cool that it works on cygwin!

Mike, Jean-Pierre: what's the best route from here?

One route is to fix the current manual handling of the different targets (macos, cygwin, ...). However that was written by Mike and I don't master the technical details, so I can't do it myself. The other option is to autoconfiscate the project, which I could do. What do you think?

Cheers,

Nicolas

comment:33 Changed 5 years ago by nthiery

Oops, I read a if wrong, so maybe Mike's analysis is actually right. And I screwed up the Coxeter3 sources. Let me fix that now, and let's see how it goes.

comment:34 Changed 5 years ago by nthiery

  • Description modified (diff)
  • Work issues category setting deleted

comment:35 Changed 5 years ago by nthiery

Hi Mike, Anne, Dan, Jean-Pierre,

Could you try the new spkg advertised above and let me know how it works on your platform? In principle I adressed the issues raised by Jean-Pierre, and unscrewed what I had screwed up. With some luck, the spkg will actually work on MacOS now.

Cheers,

Nicolas

comment:36 Changed 5 years ago by nthiery

Wait a minute; Brant found a typo ...

Last edited 5 years ago by nthiery (previous) (diff)

comment:37 Changed 5 years ago by nthiery

Just tested and passed smoothly on:

  • MacOS X.8 (installation)
  • MacOS X.7 (installation + optional tests in sage.libs.coxeter)
  • Ubuntu 11.10 (installation + optional tests in sage.libs.coxeter)

So I indeed was the one to screw up the installation on MacOS in the first place ...

Further test reports welcome!

comment:38 Changed 5 years ago by nthiery

  • Work issues set to coxeter_group.py in sage/libs ?

comment:39 Changed 5 years ago by jpflori

Last remarks for the moment:

  • could you redirect error message to stderr (>&2)
  • could you add a similar treatment for Cygwin ("$UNAME" = "CYGWIN") as for Darwin? You could then name the library cyg${module}.dll, put it in */bin (and potentially ask gcc to create an additional import library lib${module}.dll.a put in */lib, you can trigger its generation with -Wl,--out-implib=lib${module}.dll.a -Wl,--export-all-symbols, not sure the export all symbol thing is really necessary, i.e. if its default or not)
  • an exe extension for the executable would be nice as well on Cygwin!

comment:40 Changed 5 years ago by jpflori

Another one:

  • I see in the original makefile that cc is set to g++ and that cannot be overriden, maybe its worth changing that as well to use the default (and overridable) Sage C++ compiler.

comment:41 Changed 5 years ago by bump

Mike Hansen wrote:

It seems like Dan's computer is not being picked up as a mac. What does he get when doing just running "uname" on his 10.7 box.

$ uname -a
Darwin tracer 11.4.2 Darwin Kernel Version 11.4.2: Thu Aug 23 16:25:48 PDT
2012; root:xnu-1699.32.7~1/RELEASE_X86_64 x86_64

I'll try the revised spkg later tonight.

Last edited 5 years ago by bump (previous) (diff)

comment:42 follow-up: Changed 5 years ago by jpflori

I've put a further modified spkg at: http://boxen.math.washington.edu/home/jpflori/coxeter-3.1.1.spkg

Works on Linux, testing now on Cygwin.

comment:43 Changed 5 years ago by jpflori

And it does not work on Cygwin, some problem with UNAME, I guess it won't work on Darwin.

Some concerns not addressed but less important I guess:

  • no way for the user to use his C[|PP|XX]FLAGS,
  • no handling of SAGE_DEBUG.

comment:44 in reply to: ↑ 42 Changed 5 years ago by bump

Replying to jpflori:

I've put a further modified spkg at: http://boxen.math.washington.edu/home/jpflori/coxeter-3.1.1.spkg

Works on Linux, testing now on Cygwin.

The link is broke. The file exists in your directory but the spelling differs at the hyphen.

comment:45 Changed 5 years ago by jpflori

  • Description modified (diff)

I've just reupped an spkg, at: http://boxen.math.washington.edu/home/jpflori/coxeter3-1.1.spkg then. It now works on cygwin. The test I used was over quoted... And it needs $(CXX) to link on Cygwin, not sure why it works elsewher, surely because undefined symbols are allowed.

comment:46 follow-up: Changed 5 years ago by bump

With coxeter3-1.1.spkg and the posted patch, things now seem OK on my computer. (I haven't investigated the parabolic KL polynomials.)

comment:47 in reply to: ↑ 46 ; follow-up: Changed 5 years ago by aschilling

The installation of the new spkg also works for me on MacOS 10.6.8.

comment:48 in reply to: ↑ 47 ; follow-up: Changed 5 years ago by aschilling

Added reference for parabolic KL polynomials.

comment:49 in reply to: ↑ 48 Changed 5 years ago by aschilling

The index set was computed incorrectly (for affine types). I fixed that.

Unfortunately, going from sage-5.6 to sage-5.7.beta4 the following now fails:

sage: C = CoxeterGroup(['A',3,1],implementation='coxeter3')
sage: s = C.gens()
sage: s[0]*s[1]
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-3-059a6d605fdd> in <module>()
----> 1 s[Integer(0)]*s[Integer(1)]

/Applications/sage-5.7.beta4/local/lib/python2.7/site-packages/sage/categories/magmas.pyc in __mul__(self, right)
    307             """
    308             if have_same_parent(self, right) and hasattr(self, "_mul_"):
--> 309                 return self._mul_(right)
    310             from sage.structure.element import get_coercion_model
    311             import operator

/Applications/sage-5.7.beta4/local/lib/python2.7/site-packages/sage/libs/coxeter/coxeter_group.pyc in _mul_(self, y)
    450             """
    451             result = self.value * y.value
--> 452             return self.parent()(result)
    453 
    454         def __eq__(self, y):

/Applications/sage-5.7.beta4/local/lib/python2.7/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.__call__ (sage/structure/parent.c:7474)()

TypeError: No conversion defined from Coxeter group of type a and rank 4 to Coxeter group of type ['A', 3, 1] implemented by Coxeter3

Anne

comment:50 Changed 5 years ago by nthiery

  • Description modified (diff)

Fixed link to latest spkg by Jean-Pierre :-)

comment:51 Changed 5 years ago by nthiery

Hi Jean-Pierre

I just went through your changes to the spkg and they look good. Thanks much!

So this is a positive review on that aspect. I am now going to look at the above issues with beta4.

comment:52 Changed 5 years ago by nthiery

  • Reviewers changed from Anne Schilling, Nicolas M. Thiery to Anne Schilling, Nicolas M. Thiéry, Jean-Pierre Flori
  • Status changed from needs_work to positive_review
  • Work issues coxeter_group.py in sage/libs ? deleted

comment:53 Changed 5 years ago by nthiery

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!

comment:54 in reply to: ↑ 31 Changed 5 years ago by nthiery

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.

comment:55 follow-up: Changed 5 years ago by jdemeyer

  • Component changed from combinatorics to optional packages
  • Milestone changed from sage-5.7 to sage-5.8

comment:56 in reply to: ↑ 55 Changed 5 years ago by aschilling

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

comment:57 follow-up: Changed 5 years ago by aschilling

  • Status changed from positive_review to needs_work

comment:58 in reply to: ↑ 57 Changed 5 years ago by aschilling

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

comment:59 Changed 5 years ago by aschilling

  • Status changed from needs_work to positive_review

comment:60 Changed 5 years ago by jdemeyer

  • Status changed from positive_review to needs_work
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...

comment:61 Changed 5 years ago by mhansen

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

comment:62 Changed 5 years ago by nthiery

I am on it ...

Changed 5 years ago by nthiery

comment:63 Changed 5 years ago by nthiery

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

comment:64 Changed 5 years ago by nthiery

  • Description modified (diff)

comment:65 Changed 5 years ago by aschilling

  • Status changed from needs_review to positive_review

comment:66 Changed 5 years ago by schilly

spkg is on its way to the servers!

comment:67 Changed 5 years ago by jdemeyer

  • Merged in set to sage-5.8.beta1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.