Opened 6 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 )
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)
Change History (68)
comment:1 Changed 6 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:2 Changed 6 years ago by
- Status changed from needs_review to needs_work
comment:3 Changed 5 years ago by
- Keywords coxeter added
comment:4 Changed 5 years ago by
- Cc anne added
- Description modified (diff)
comment:5 follow-up: ↓ 6 Changed 5 years ago by
- Description modified (diff)
comment:6 in reply to: ↑ 5 ; follow-ups: ↓ 7 ↓ 8 Changed 5 years ago by
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
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
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
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
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: ↓ 12 Changed 5 years ago by
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
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
- 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
- Dependencies set to #8359
comment:15 Changed 5 years ago by
- Description modified (diff)
comment:16 follow-up: ↓ 17 Changed 5 years ago by
- Description modified (diff)
comment:17 in reply to: ↑ 16 ; follow-up: ↓ 18 Changed 5 years ago by
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
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
- 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: ↓ 22 Changed 5 years ago by
- 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
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.
comment:22 in reply to: ↑ 20 Changed 5 years ago by
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
- Status changed from needs_work to needs_review
comment:24 Changed 5 years ago by
- Keywords days45 added
comment:25 follow-up: ↓ 26 Changed 5 years ago by
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
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
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
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
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
- 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: ↓ 54 Changed 5 years ago by
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
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
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
- Description modified (diff)
- Work issues category setting deleted
comment:35 Changed 5 years ago by
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
Wait a minute; Brant found a typo ...
comment:37 Changed 5 years ago by
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
- Work issues set to coxeter_group.py in sage/libs ?
comment:39 Changed 5 years ago by
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
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
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.
comment:42 follow-up: ↓ 44 Changed 5 years ago by
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
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
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
- 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: ↓ 47 Changed 5 years ago by
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: ↓ 48 Changed 5 years ago by
The installation of the new spkg also works for me on MacOS 10.6.8.
comment:48 in reply to: ↑ 47 ; follow-up: ↓ 49 Changed 5 years ago by
Added reference for parabolic KL polynomials.
comment:49 in reply to: ↑ 48 Changed 5 years ago by
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
- Description modified (diff)
Fixed link to latest spkg by Jean-Pierre :-)
comment:51 Changed 5 years ago by
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
- 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
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
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: ↓ 56 Changed 5 years ago by
- 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
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: ↓ 58 Changed 5 years ago by
- Status changed from positive_review to needs_work
comment:58 in reply to: ↑ 57 Changed 5 years ago by
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
- Status changed from needs_work to positive_review
comment:60 Changed 5 years ago by
- 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
It looks like a few more tests need to be marked optional.
comment:62 Changed 5 years ago by
I am on it ...
Changed 5 years ago by
comment:63 Changed 5 years ago by
- Description modified (diff)
- Status changed from needs_work to needs_review
comment:64 Changed 5 years ago by
- Description modified (diff)
comment:65 Changed 5 years ago by
- Status changed from needs_review to positive_review
comment:66 Changed 5 years ago by
spkg is on its way to the servers!
comment:67 Changed 5 years ago by
- Merged in set to sage-5.8.beta1
- Resolution set to fixed
- Status changed from positive_review to closed
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.)