Opened 7 years ago

Last modified 4 months ago

#8360 needs_work enhancement

Add an interface to Jean-Eric Pin's Semigroupe package

Reported by: nthiery Owned by: nthiery
Priority: major Milestone: sage-feature
Component: algebra Keywords: Semigroupes
Cc: sage-combinat, Jean-Eric.Pin@…, abmasse, tscrim Merged in:
Authors: Florent Hivert, Jean-Eric Pin, Nicolas M. Thiéry Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by nthiery)

Add an interface to Jean-Eric Pin's Semigroupe package

http://www.liafa.jussieu.fr/~jep/semigroupes.html

An experimental spkg is now on trac; here is the patch taken from the old Sage-Combinat patch server:

:attachment:trac_8360_semigroupe-interface-nt.patch

Status: advanced proof of concept, with interactions in both directions (building a semigroup in Semigroupe from Sage data). Main show stopper: one can only manipulate one semigroup at a time.

The following should hopefully get you started:

   sage -f http://trac.sagemath.org/sage_trac/raw-attachment/ticket/8360/semigroupe-2.0-2.spkg
   sage -combinat update
   sage -br

   sage: semigroupe?
   sage: semigroupe.tutorial?

Beware 'sage -f an_url' does not redownload the package if sage already has a copy of it. So you may have to first do:

        rm <SAGE_ROOT>/spkg/optional/semigroupe-2.0.spkg

Update 2016-12-05: James Mitchel is reimplementing Semigroupe in C++, which will lift the main limitation (a single semigroup at a time): https://james-d-mitchell.github.io/semigroupsplusplus/

This could be the occasion to revive this old code.

Attachments (4)

Semigroupe-2.0.spkg (1.7 MB) - added by nthiery 7 years ago.
semigroupe-2.0.spkg (905.5 KB) - added by nthiery 7 years ago.
Superceedes the previous spkg
semigroupe-2.0-2.spkg (891.3 KB) - added by nthiery 6 years ago.
Same as previous one, working on both 32bits and 64bits, but managing the patches on the semigroupe sources in a mercurial queue
trac_8360_semigroupe-interface-nt.patch (41.3 KB) - added by nthiery 4 months ago.

Change History (22)

Changed 7 years ago by nthiery

comment:1 Changed 7 years ago by nthiery

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

Changed 7 years ago by nthiery

Superceedes the previous spkg

comment:2 Changed 7 years ago by nthiery

  • Description modified (diff)

comment:3 Changed 7 years ago by nthiery

  • Description modified (diff)

comment:4 Changed 7 years ago by nthiery

  • Description modified (diff)

comment:5 follow-up: Changed 7 years ago by saliola

There seems to be a problem on a 64bit machine. After installing the spkg, the following commands will cause Sage to segfault:

sage: W = CoxeterGroup(["H",4])
sage: S = semigroupe.AutomaticSemigroup(W.semigroup_generators(), W.one(), category = FiniteCoxeterGroups())
sage: S.cardinality()
------------------------------------------------------------
Unhandled SIGSEGV: A segmentation fault occured in Sage.
...

The problem seems to be with compiling Semigroupe on a 64bit machine. After installing the package, the following segfaults:

karkwa: cd $SAGE_ROOT/local/bin
karkwa: Semigroupe
karkwa: ./Semigroupe
Segmentation fault
karkwa: ./SelfContainedTest 
Toto
a | 2  3  1 
b | 2  1  3 
c | 1  2  1 

Segmentation fault
karkwa: ./SemigroupeModuleTest 

a | 2  1 
b | 1  1 

Segmentation fault 

I think that the two test suites (I think they are test suites...) should be run by the spkg-check script.

comment:6 Changed 7 years ago by aschilling

On a 32-bit machine, I obtain the following error:

sage: S = semigroupe.AutomaticSemigroup?(W.semigroup_generators(), W.one(), category = FiniteCoxeterGroups?()) sage: S.cardinality() python(24860) malloc: * vm_allocate(size=262144) failed (error code=3) python(24860) malloc: * error: can't allocate region python(24860) malloc: * set a breakpoint in szone_error to debug memory allocation failed memory usage :

size : 2 used/allocated

0 310/312 1 21/22 2 109/109 3 73/73 4 49/50 5 5/6 6 9/9 7 3/3 8 1/1 9 1/1

10 1/2 11 0/1 12 0/0 13 0/1 14 1/1 15 25959/25959 16 0/0 17 0/0 18 0/0 19 0/0 20 0/0 21 0/0 22 0/0 23 0/0 24 0/0 25 0/0 26 0/0 27 0/0 28 0/0 29 0/0 30 0/0 31 0/0

total : 850645964/850657280 4-byte units used/allocated .../Applications/sage-4.4/devel/sage-combinat/sage/combinat/crystals$

Anne

comment:7 Changed 7 years ago by saliola

In case this helps track down the issue: things seem to be working correctly in a 32bit virtual machine. I created a 32bit VirtualBox? virtual machine, installed Ubuntu 10.04, then I installed the sage-4.4.1 binary, the gap3 spkg from #8906, and the semigroupe spkg here.

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

  • Authors changed from Florent Hivert, Jean-Eric Pin Nicolas M. Thiéry to Florent Hivert, Jean-Eric Pin, Nicolas M. Thiéry

I think that the two test suites (I think they are test suites...) should be run by the spkg-check script.

Those are little self contained test programs we had written with Florent to understand how semigroupe was working. Yes, they eventually should be turned into test suites, and run from spkg-check.

comment:9 Changed 7 years ago by nthiery

  • Description modified (diff)

Changed 6 years ago by nthiery

Same as previous one, working on both 32bits and 64bits, but managing the patches on the semigroupe sources in a mercurial queue

comment:10 Changed 6 years ago by abmasse

  • Cc abmasse added

comment:11 Changed 3 years ago by slabbe

Note that semigroupe is now part of the experimental packages:

http://www.sagemath.org/packages/experimental/

One can install it with the usual sage -i semigroupe-2.0-2.spkg.

next step is to make the code in sage-combinat go into sage...

comment:12 follow-up: Changed 3 years ago by nthiery

Great, thanks Sébastien for taking care of this!

The next step is actually just to make a branch out of the patch. I am not sure about actually getting this branch into Sage until Semigroupe will be fixed one way or the other to support several semigroups simultaneously.

Cheers,

Nicolas

comment:13 in reply to: ↑ 12 ; follow-up: Changed 3 years ago by slabbe

Replying to nthiery:

Great, thanks Sébastien for taking care of this!

The next step is actually just to make a branch out of the patch.

you mean a git branch?

which patch? is it finite_semigroup-nt.patch ?

I don't see how this patch uses semigroupe.

I am not sure about actually getting this branch into Sage until Semigroupe will be fixed one way or the other to support several semigroups simultaneously.

I think I don't agree. I think the goal of the actual ticket #8360 is to make the actual semigroup into sage as it is. semigroupe was written for something no? Let's first make this available!

Then I suggest to open a ticket showing with sage command line code illustrating how the bug for creating two semigroup simultaneously is obtained. The new ticket would ask for an upstream fix.

Sébastien

comment:14 in reply to: ↑ 13 Changed 3 years ago by nthiery

Replying to slabbe:

Replying to nthiery:

The next step is actually just to make a branch out of the patch.

you mean a git branch?

Yup.

which patch? is it finite_semigroup-nt.patch ? I don't see how this patch uses semigroupe.

trac_8360_semigroupe-interface-nt.patch

I am not sure about actually getting this branch into Sage until Semigroupe will be fixed one way or the other to support several semigroups simultaneously.

I think I don't agree. I think the goal of the actual ticket #8360 is to make the actual semigroup into sage as it is. semigroupe was written for something no? Let's first make this available!

Indeed, the interface was written for something. But in practice, even if I spent quite some time on it, I am actually seldom using it because that misfeature is making it relatively unusable (at least in my use-cases).

Then I suggest to open a ticket showing with sage command line code illustrating how the bug for creating two semigroup simultaneously is obtained. The new ticket would ask for an upstream fix.

That's an option. If you are convinced that:

  • At some point not to far in the future the bug will be fixed upstream (upstream meaning possibly us taking the time to do the fix).
  • The current code won't need serious interface change then.

Then let's go ahead. I'd love to have this code always under my fingertips. Otherwise I am a bit reluctant to put in Sage some code that we might need to remove (because unused) or change a lot later on.

At the end of the day, this would actually be best handled by putting the interface code in the spkg and not in the Sage library. I haven't checked how hard/easy it would be to handle.

Cheers,

Nicolas

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

Changed 4 months ago by nthiery

comment:15 Changed 4 months ago by nthiery

  • Description modified (diff)

comment:16 Changed 4 months ago by nthiery

  • Description modified (diff)

comment:17 Changed 4 months ago by nthiery

  • Description modified (diff)

comment:18 Changed 4 months ago by tscrim

  • Cc tscrim added
Note: See TracTickets for help on using tickets.