Full interface to letterplace from singular #7797

burcin · 2009-12-30T21:43:47Z

The new aim of this ticket is to add an interface to the letterplace component of Singular, that actually goes beyond what Singular offers.

The patch provides

A new implementation of free algebras with fast arithmetic, but restricted to weighted homogeneous elements, with positive integral degree weights.
Degree-wise Gröbner basis computation for twosided weighted homogeneous ideals of free algebras. If a finite complete Gröbner basis exists, it can be computed.
Normal form computation with respect to such ideals.
Quotient rings of such ideals

(Note that the original purpose was merely to compute Groebner bases up to a degree bound of two-sided ideals of free algebras, but without normal form computation etc.)

Examples are below, in the comments.

Apply

attachment: trac7797-full_letterplace_wrapper_combined.patch and attachment: trac_7797-ref.patch

Depends on #11068 #11268 #12641 #12749

Depends on #4539
Depends on #11268
Depends on #12461
Depends on #12749
Depends on #12988
Depends on #13237

Upstream: None of the above - read trac for reasoning.

CC: @sagetrac-PolyBoRi @saliola @malb @jhpalmieri @sagetrac-sage-combinat @sagetrac-OleksandrMotsak

Component: algebra

Keywords: singular, free algebra, letterplace

Author: Simon King, Michael Brickenstein, Burcin Erocal

Reviewer: Alexander Dreyer

Merged: sage-5.5.beta2

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

burcin · 2009-12-30T21:46:39Z

hack to create an MPolynomialRing as a parent for letterplace polynomials

burcin · 2009-12-30T21:47:33Z

Attachment: trac_7797-letterplace_ring_hack.patch.gz

basic interface to compute groebner bases with letterplace

burcin · 2009-12-30T21:47:50Z

comment:1

Attachment: trac_7797-letterplace.patch.gz

malb · 2010-06-03T22:21:04Z

comment:3

Doctest failure on sage.math:

File "/mnt/usb1/scratch/malb/sage-4.4/devel/sage-main/sage/libs/singular/letterplace.py", line 32:
    sage: freegb(l, 10)
Exception raised:
    Traceback (most recent call last):
      File "/mnt/usb1/scratch/malb/sage-4.4/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/mnt/usb1/scratch/malb/sage-4.4/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/mnt/usb1/scratch/malb/sage-4.4/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_1[5]>", line 1, in <module>
        freegb(l, Integer(10))###line 32:
    sage: freegb(l, 10)
      File "/mnt/usb1/scratch/malb/sage-4.4/local/lib/python/site-packages/sage/libs/singular/letterplace.py", line 70, in freegb
        libsingular_options(bck)
    TypeError: 'sage.libs.singular.option.LibSingularOptions' object is not callable

I think we used to allow calling libsingular option objects earlier, however load() replaces it.

malb · 2010-06-24T14:29:42Z

comment:4

Actually, this doesn't make sense to me:

bck = int(libsingular_options)  
#letter place needs these options
libsingular_options['redTail'] = True
libsingular_options['redSB'] = True
libsingular_options(bck)

First bck is stored and then options are changed. So far fine. However, then bck is loaded and thus overwrites the options just set.

sagetrac-PolyBoRi · 2010-06-30T09:06:53Z

letter place singular interface

sagetrac-PolyBoRi · 2010-06-30T09:07:40Z

comment:5

Attachment: trac_7797-letterplace.2.patch.gz

Hi!

I have corrected that using the new context interface.

Cheers,
Michael

sagetrac-PolyBoRi · 2010-06-30T09:10:23Z

Attachment: trac_7797-letterplace.3.patch.gz

malb · 2010-07-14T22:24:34Z

comment:7

While there are doctests, there is no documentation, no explanation what the functions are doing
- freegb should accept ideals (?)
- Why are you calling "singular_system"?

malb · 2010-07-14T22:41:41Z

comment:8

File "/mnt/usb1/scratch/malb/sage-4.4/devel/sage-main/sage/libs/singular/letterplace.py", line 32:

sage: freegb(l, 10)

Expected:

[3*y*x*z^7*y + y*x*z^8, 3*y*x*z^6*y + y*x*z^7, y*x*z^6*x*z + 314928*y^2*x*z^2*x^5, 3*y*x*z^5*y + y*x*z^6, y*x*z^5*x*z - 17496*y^2*x*z^2*x^4, 3*y*x*z^4*y + y*x*z^5, y*x*z^4*x*z + 972*y^2*x*z^2*x^3, 3*y*x*z^4*x^2*z*y + y*x*z^4*x^2*z^2, 3*y*x*z^3*y + y*x*z^4, y*x*z^3*x*z - 54*y^2*x*z^2*x^2, 3*y*x*z^3*x^2*z^2*y + y*x*z^3*x^2*z^3, 3*y*x*z^3*x^2*z*y + y*x*z^3*x^2*z^2, 3*y*x*z^3*x^3*z*y + y*x*z^3*x^3*z^2, 3*y*x*z^2*y + y*x*z^3, y*x*z^2*x*z + 3*y^2*x*z^2*x, 3*y*x*z^2*x^2*z^3*y + y*x*z^2*x^2*z^4, 3*y*x*z^2*x^2*z^2*y + y*x*z^2*x^2*z^3, y*x*z^2*x^2*z^2*x*z + 3*y^2*x*z^2*x^2*z^2*x, 3*y*x*z^2*x^2*z*y + y*x*z^2*x^2*z^2, 3*y*x*z^2*x^3*z^2*y + y*x*z^2*x^3*z^3, 3*y*x*z^2*x^3*z*y + y*x*z^2*x^3*z^2, 3*y*x*z^2*x^4*z*y + y*x*z^2*x^4*z^2, 3*y*x*z*y + y*x*z^2, x*z*y^6*x*z - 7776*y*x*z^2*x^6, x*z*y^5*x*z - 1296*y*x*z^2*x^5, x*z*y^4*x*z - 216*y*x*z^2*x^4, x*z*y^3*x*z - 36*y*x*z^2*x^3, x*z*y^2*x*z - 6*y*x*z^2*x^2, x*z*y*x*z - y*x*z^2*x, 6*x*z*x - y*x*z, 3*x*y + x*z]

Got
[3*x*y + x*z, 6*x*z*x - y*x*z, 3*y*x*z*y + y*x*z^2, 3*y*x*z^2*y + y*x*z^3, x*z*y*x*z - y*x*z^2*x, 3*y*x*z^3*y + y*x*z^4, y*x*z^2*x*z + 3*y^2*x*z^2*x, x*z*y^2*x*z - 6*y*x*z^2*x^2, 3*y*x*z^4*y + y*x*z^5, y*x*z^3*x*z - 54*y^2*x*z^2*x^2, x*z*y^3*x*z - 36*y*x*z^2*x^3, 3*y*x*z^5*y + y*x*z^6, y*x*z^4*x*z + 972*y^2*x*z^2*x^3, 3*y*x*z^2*x^2*z*y + y*x*z^2*x^2*z^2, x*z*y^4*x*z - 216*y*x*z^2*x^4, 3*y*x*z^6*y + y*x*z^7, y*x*z^5*x*z - 17496*y^2*x*z^2*x^4, 3*y*x*z^3*x^2*z*y + y*x*z^3*x^2*z^2, 3*y*x*z^2*x^2*z^2*y + y*x*z^2*x^2*z^3, 3*y*x*z^2*x^3*z*y + y*x*z^2*x^3*z^2, x*z*y^5*x*z - 1296*y*x*z^2*x^5, 3*y*x*z^7*y + y*x*z^8, y*x*z^6*x*z + 314928*y^2*x*z^2*x^5, 3*y*x*z^4*x^2*z*y + y*x*z^4*x^2*z^2, 3*y*x*z^3*x^2*z^2*y + y*x*z^3*x^2*z^3, 3*y*x*z^3*x^3*z*y + y*x*z^3*x^3*z^2, 3*y*x*z^2*x^2*z^3*y + y*x*z^2*x^2*z^4, y*x*z^2*x^2*z^2*x*z + 3*y^2*x*z^2*x^2*z^2*x, 3*y*x*z^2*x^3*z^2*y + y*x*z^2*x^3*z^3, 3*y*x*z^2*x^4*z*y + y*x*z^2*x^4*z^2, x*z*y^6*x*z - 7776*y*x*z^2*x^6]

This is with Singular 3-1-1-3 though.

sagetrac-PolyBoRi · 2010-07-15T08:22:48Z

comment:9

Aufruf von System ist offiziell, heißt aber nur, dass es nicht als extra Kommando eingebaut ist.

http://www.singular.uni-kl.de/Manual/latest/sing_433.htm

sagetrac-PolyBoRi · 2010-07-15T08:25:19Z

comment:10

sorry, for the language:
calling system is official. Using singular system was easier for the authors of freegb.

http://www.singular.uni-kl.de/Manual/latest/sing_433.htm

sagetrac-PolyBoRi · 2010-07-15T08:42:31Z

comment:11

the result seem to differ just in order.

What Ideal class is used for free algebras?

sagetrac-PolyBoRi · 2010-07-15T13:21:24Z

Attachment: plural_functions.patch.gz

some improvements to plural interface, still not much working

malb · 2010-07-15T15:27:33Z

comment:12

Replying to @sagetrac-PolyBoRi:

the result seem to differ just in order. What Ideal class is used for free algebras?

Apparently, we don't have one which works yet

sage: P.<a,b,c> = FreeAlgebra(QQ,3)
sage: P
Free Algebra on 3 generators (a, b, c) over Rational Field
sage: P.ideal([a*b+c,a+1])
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)

/home/malb/<ipython console> in <module>()

/usr/local/sage-4.3/local/lib/python2.6/site-packages/sage/rings/ring.so in sage.rings.ring.Ring.ideal (sage/rings/ring.c:3426)()

/usr/local/sage-4.3/local/lib/python2.6/site-packages/sage/rings/ideal.pyc in Ideal(*args, **kwds)
    187 
    188     if not commutative_ring.is_CommutativeRing(R):
--> 189         raise TypeError, "R must be a commutative ring"
    190 
    191     if len(gens) == 0:

TypeError: R must be a commutative ring

simon-king-jena · 2010-10-01T19:17:24Z

comment:13

Do I understand correctly that in this ticket it is not attempted to replace FreeAlgebra by a more efficient implementation based on Singular's Letterplace Algebra? This ticket is only about wrapping free Groebner bases, but not about wrapping the basic arithmetic?

What Sage currently does in free algebras is generic and slow. As pointed out on sage-devel, bot Singular and Gap are faster in basic arithmetic than the current implementation in Sage.

But this should be on a different ticket, right?

Best regards,
Simon

alexanderdreyer · 2010-10-01T20:19:41Z

comment:14

As I understand, this makes the Singular's letterplace functionality accessible to Sage (in addition to the Plural functionality of #4539).

burcin · 2010-10-01T20:28:46Z

comment:15

This ticket is only about exposing the Groebner basis computation. We didn't think arithmetic was usable since

there is a degree bound, and
it is a hack in Singular.

If you think the arithmetic should be wrapped as well, that should be on a different ticket. I don't know how much the Plural wrapper (#4539) will help with that.

simon-king-jena · 2010-10-02T07:41:50Z

comment:16

Replying to @alexanderdreyer:

As I understand, this makes the Singular's letterplace functionality accessible to Sage (in addition to the Plural functionality of #4539).

What is meant by "Letterplace functionality"? Is it "simply" computing Gröbner basis with degree bound in free associative algebras?

Something that irritates me (and I already asked in the Singular forum) is that I could not find a way to apply such Groebner basis, e.g., in order to compute a normal form of an element of the free associative algebra w.r.t. this Gröbner basis. Also I tend to call basic arithmetic a funtionality.

Replying to @burcin:

This ticket is only about exposing the Groebner basis computation. We didn't think arithmetic was usable since

there is a degree bound, and

it is a hack in Singular.

If you think the arithmetic should be wrapped as well, that should be on a different ticket. I don't know how much the Plural wrapper (#4539) will help with that.

OK. If I find the time, I'll finish the wrappers that I hacked together yesterday. The new ticket will then provide two alternative implementations of free (associative) algebras. One will be based on Gap, the other on Letterplace. The latter will be a hack as well: While doing arithmetic, the degree bound will be dynamically adapted. Currently I use Expect interfaces, but I guess using the Plural wrapper will improve things further.

Cheers,
Simon

jhpalmieri · 2012-10-24T15:01:33Z

comment:99

Tests pass on skynet machine mark.

jdemeyer · 2012-10-30T15:52:24Z

comment:101

I'm getting (in a trial sage-5.5.beta1, so it includes many other tickets)

sage -t  -force_lib devel/sage/sage/algebras/letterplace/free_algebra_letterplace.pyx
**********************************************************************
File "/release/merger/sage-5.5.beta1/devel/sage-main/sage/algebras/letterplace/free_algebra_letterplace.pyx", line 684:
    sage: G = F._reductor_(I.gens(),3); G
Expected:
    Ideal (x*y_1 + y*z_1, x_1*y_2 + y_1*z_2, x*x_1 + x*y_1 - y*x_1 - y*y_1, x_1*x_2 + x_1*y_2 - y_1*x_2 - y_1*y_2) of Multivariate Polynomial Ring in x, y, z, x_1, y_1, z_1, x_2, y_2, z_2, x_3, y_3, z_3... over Rational Field
Got:
    Ideal (x*y_1 + y*z_1, x_1*y_2 + y_1*z_2, x*x_1 + x*y_1 - y*x_1 - y*y_1, x_1*x_2 + x_1*y_2 - y_1*x_2 - y_1*y_2) of Multivariate Polynomial Ring in x, y, z, x_1, y_1, z_1, x_2, y_2, z_2 over Rational Field
**********************************************************************

simon-king-jena · 2012-10-30T16:00:41Z

comment:103

I think we have already discussed that the order of doctests may influence the size of the polynomial ring used to represent the letterplace elements.

So, the fix should be to have Multivariate Polynomial Ring in x, y, z, x_1, y_1, z_1, x_2, y_2, z_2... over Rational Field. I'll do so (hopefully) soonish.

jdemeyer · 2012-10-30T16:31:32Z

comment:104

Doctest error confirmed with (unreleased but essentially ready) sage-5.5.beta0, but not with sage-5.4.rc2.

simon-king-jena · 2012-11-09T10:16:51Z

A full wrapper for Singular's letterplace functionality, plus positive integral degree weights, plus complete Groebner bases of weighted homogeneous two-sided ideals, plus coercion. Rel #12988

simon-king-jena · 2012-11-09T10:20:36Z

comment:105

Attachment: trac7797-full_letterplace_wrapper_combined.patch.gz

I am sorry that I took so long to fix it.

I have changed the "big" patch. The diff of the two patch versions is:

--- trac7797-full_letterplace_wrapper_combined.patch    2012-11-09 11:15:19.355793326 +0100
+++ trac7797-full_letterplace_wrapper_combined.patch        2012-09-02 09:00:20.000000000 +0200
@@ -2176,7 +2176,7 @@
 +            sage: p.reduce(I)
 +            y*y*y - y*y*z + y*z*y - y*z*z
 +            sage: G = F._reductor_(I.gens(),3); G
-+            Ideal (x*y_1 + y*z_1, x_1*y_2 + y_1*z_2, x*x_1 + x*y_1 - y*x_1 - y*y_1, x_1*x_2 + x_1*y_2 - y_1*x_2 - y_1*y_2) of Multivariate Polynomial Ring in x, y, z, x_1, y_1, z_1, x_2, y_2, z_2... over Rational Field
++            Ideal (x*y_1 + y*z_1, x_1*y_2 + y_1*z_2, x*x_1 + x*y_1 - y*x_1 - y*y_1, x_1*x_2 + x_1*y_2 - y_1*x_2 - y_1*y_2) of Multivariate Polynomial Ring in x, y, z, x_1, y_1, z_1, x_2, y_2, z_2, x_3, y_3, z_3... over Rational Field
 +
 +        We do not use the usual reduction method for polynomials in
 +        Sage, since it does the reductions in a different order

I hope it is ok to restore the positive review, since I assume doctests will be run anyway before releasing.

Apply trac7797-full_letterplace_wrapper_combined.patch trac_7797-ref.patch

alexanderdreyer · 2012-11-09T11:49:57Z

comment:106

Just realized, that I'm the reviewer: I'm fine with reestablishing to positive review.

jdemeyer · 2012-11-16T21:25:01Z

Merged: sage-5.5.beta2

kcrisman · 2012-12-05T19:37:59Z

comment:108

See #13802 for a problem this causes on Cygwin, though it looks like the fix is easy. I'd appreciate knowing whether it's okay to add libraries=singular_libs or whether that would cause problems; I think I have to add SAGE_INC + 'factory'.

alexanderdreyer · 2012-12-05T21:51:21Z

comment:109

Replying to @kcrisman:

See #13802 for a problem this causes on Cygwin, though it looks like the fix is easy. I'd appreciate knowing whether it's okay to add libraries=singular_libs or whether that would cause problems; I think I have to add SAGE_INC + 'factory'.

Indeed, looking at the other singular-based modules it makes sense. I don't expect problems doing so.

kcrisman · 2012-12-05T22:08:26Z

comment:110

See #13802 for a problem this causes on Cygwin, though it looks like the fix is easy. I'd appreciate knowing whether it's okay to add libraries=singular_libs or whether that would cause problems; I think I have to add SAGE_INC + 'factory'.

Indeed, looking at the other singular-based modules it makes sense. I don't expect problems doing so.

Great, can you give some feedback on the patch at #13802 then? Thanks!

alexanderdreyer · 2012-12-06T08:38:18Z

comment:111

Replying to @kcrisman:

Great, can you give some feedback on the patch at #13802 then? Thanks!

Very well, I was able to positively review that patch.

kcrisman · 2012-12-06T15:15:02Z

comment:112

Great, can you give some feedback on the patch at #13802 then? Thanks!

Very well, I was able to positively review that patch.

Very helpful, thank you.

As discussed in sagemath#37390 (comment), we change how Sphinx role ``:issue:`` is rendered. For example, short ``` By Issue sagemath#7797, there is a different implementation ... ``` instead of current ``` By github issue sagemath#7797, there is a different implementation ... ``` Arguments for the short form are > Please don't do "Github issue". It is a lot of text with extremely little extra value. > In the trac era, it was "trac sagemath#7797".    ### 📝 Checklist     - [x] The title is concise, informative, and self-explanatory. - [x] The description explains in detail what this PR is about. - [x] I have linked a relevant issue or discussion. - [ ] I have created tests covering the changes. - [ ] I have updated the documentation accordingly. ### ⌛ Dependencies   URL: sagemath#37403 Reported by: Kwankyu Lee Reviewer(s): Travis Scrimshaw

burcin added this to the sage-4.7.1 milestone Dec 30, 2009

burcin added c: algebra labels Dec 30, 2009

burcin self-assigned this Dec 30, 2009

burcin added the s: needs review label Dec 30, 2009

This comment has been minimized.

Sign in to view

malb added s: needs work and removed s: needs review labels Jun 24, 2010

sagetrac-PolyBoRi mannequin added s: needs review and removed s: needs work labels Jun 30, 2010

jhpalmieri added s: positive review and removed s: needs review labels Oct 24, 2012

jdemeyer modified the milestones: sage-5.4, sage-5.5 Oct 29, 2012

jdemeyer added s: needs work and removed s: positive review labels Oct 30, 2012

simon-king-jena added s: positive review and removed s: needs work labels Nov 9, 2012

jdemeyer removed the s: positive review label Nov 16, 2012

jdemeyer closed this as completed Nov 16, 2012

burcin mentioned this issue Dec 30, 2009

plural wrapper #4539

Closed

This was referenced Aug 31, 2017

Basic implementation of one- and twosided ideals of non-commutative rings, and quotients by twosided ideals #11068

Closed

Cache groebner basis independend of degree bound #11667

Open

kcrisman mentioned this issue Dec 5, 2012

Extra includes needed for letterplace for Cygwin on XP #13802

Closed

This was referenced Feb 19, 2024

Replace all :trac: with :issue: in docstrings #37390

Merged

Use "Issue #" for github issue links #37403

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Full interface to letterplace from singular #7797

Full interface to letterplace from singular #7797

burcin commented Dec 30, 2009

burcin commented Dec 30, 2009

burcin commented Dec 30, 2009

burcin commented Dec 30, 2009

This comment has been minimized.

malb commented Jun 3, 2010

malb commented Jun 24, 2010

sagetrac-PolyBoRi mannequin commented Jun 30, 2010

sagetrac-PolyBoRi mannequin commented Jun 30, 2010

sagetrac-PolyBoRi mannequin commented Jun 30, 2010

malb commented Jul 14, 2010

malb commented Jul 14, 2010

sagetrac-PolyBoRi mannequin commented Jul 15, 2010

sagetrac-PolyBoRi mannequin commented Jul 15, 2010

sagetrac-PolyBoRi mannequin commented Jul 15, 2010

sagetrac-PolyBoRi mannequin commented Jul 15, 2010

malb commented Jul 15, 2010

simon-king-jena commented Oct 1, 2010

alexanderdreyer mannequin commented Oct 1, 2010

burcin commented Oct 1, 2010

simon-king-jena commented Oct 2, 2010

jhpalmieri commented Oct 24, 2012

jdemeyer commented Oct 30, 2012

simon-king-jena commented Oct 30, 2012

jdemeyer commented Oct 30, 2012

simon-king-jena commented Nov 9, 2012

simon-king-jena commented Nov 9, 2012

alexanderdreyer mannequin commented Nov 9, 2012

jdemeyer commented Nov 16, 2012

kcrisman commented Dec 5, 2012

alexanderdreyer mannequin commented Dec 5, 2012

kcrisman commented Dec 5, 2012

alexanderdreyer mannequin commented Dec 6, 2012

kcrisman commented Dec 6, 2012

Full interface to letterplace from singular #7797

Full interface to letterplace from singular #7797

Comments

burcin commented Dec 30, 2009

burcin commented Dec 30, 2009

burcin commented Dec 30, 2009

burcin commented Dec 30, 2009

This comment has been minimized.

malb commented Jun 3, 2010

malb commented Jun 24, 2010

sagetrac-PolyBoRi mannequin commented Jun 30, 2010

sagetrac-PolyBoRi mannequin commented Jun 30, 2010

sagetrac-PolyBoRi mannequin commented Jun 30, 2010

malb commented Jul 14, 2010

malb commented Jul 14, 2010

sagetrac-PolyBoRi mannequin commented Jul 15, 2010

sagetrac-PolyBoRi mannequin commented Jul 15, 2010

sagetrac-PolyBoRi mannequin commented Jul 15, 2010

sagetrac-PolyBoRi mannequin commented Jul 15, 2010

malb commented Jul 15, 2010

simon-king-jena commented Oct 1, 2010

alexanderdreyer mannequin commented Oct 1, 2010

burcin commented Oct 1, 2010

simon-king-jena commented Oct 2, 2010

jhpalmieri commented Oct 24, 2012

jdemeyer commented Oct 30, 2012

simon-king-jena commented Oct 30, 2012

jdemeyer commented Oct 30, 2012

simon-king-jena commented Nov 9, 2012

simon-king-jena commented Nov 9, 2012

alexanderdreyer mannequin commented Nov 9, 2012

jdemeyer commented Nov 16, 2012

kcrisman commented Dec 5, 2012

alexanderdreyer mannequin commented Dec 5, 2012

kcrisman commented Dec 5, 2012

alexanderdreyer mannequin commented Dec 6, 2012

kcrisman commented Dec 6, 2012