Interface to Fokko Ducloux's Coxeter 3

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

[kini]

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

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

[aschilling]

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

[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

[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?

[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!

[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

[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

[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

[aschilling]

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

Anne

[nthiery]

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

[nthiery]

Oops, the category is not set properly:

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

Should be finite Coxeter groups.

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

[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

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

[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,

[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

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

[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?

[jpflori]

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.

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

[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

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

[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

[nthiery]

Wait a minute; Brant found a typo ...

[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!

[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!

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

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

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

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

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

[jpflori]

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.

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

[aschilling]

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

[aschilling]

Added reference for parabolic KL polynomials.

[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

[nthiery]

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

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

[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!

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

[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

[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

[jdemeyer]

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

[mhansen]

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

[nthiery]

I am on it ...

[schilly]

spkg is on its way to the servers!