Opened 9 years ago

Closed 6 years ago

# Full interface to letterplace from singular

Reported by: Owned by: burcin jdemeyer major sage-5.5 algebra singular, free algebra, letterplace PolyBoRi, saliola, malb, jhpalmieri, sage-combinat, OleksandrMotsak sage-5.5.beta2 Simon King, Michael Brickenstein, Burcin Erocal Alexander Dreyer None of the above - read trac for reasoning. #4539, #11268, #12461, #12749, #12988, #13237

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

Depends on #11068 #11268 #12641 #12749

### Changed 9 years ago by burcin

hack to create an MPolynomialRing as a parent for letterplace polynomials

### Changed 9 years ago by burcin

basic interface to compute groebner bases with letterplace

### comment:1 Changed 9 years ago by burcin

• Status changed from new to needs_review

### comment:2 Changed 9 years ago by burcin

• Description modified (diff)

### comment:3 Changed 8 years ago by malb

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.

### comment:4 Changed 8 years ago by malb

• Status changed from needs_review to needs_work

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.

### Changed 8 years ago by PolyBoRi

letter place singular interface

### comment:5 Changed 8 years ago by PolyBoRi

Hi!

I have corrected that using the new context interface.

Cheers, Michael

### comment:6 Changed 8 years ago by PolyBoRi

• Status changed from needs_work to needs_review

### comment:7 Changed 8 years ago by malb

• 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"?

### comment:8 Changed 8 years ago by malb

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.

### comment:9 Changed 8 years ago by PolyBoRi

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

### comment:10 Changed 8 years ago by PolyBoRi

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

### comment:11 follow-up: ↓ 12 Changed 8 years ago by PolyBoRi

the result seem to differ just in order.

### Changed 8 years ago by PolyBoRi

some improvements to plural interface, still not much working

### comment:12 in reply to: ↑ 11 Changed 8 years ago by malb

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

### comment:13 Changed 8 years ago by SimonKing

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

### comment:14 Changed 8 years ago by AlexanderDreyer

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

### comment:15 follow-up: ↓ 16 Changed 8 years ago by 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.

### comment:16 in reply to: ↑ 15 Changed 8 years ago by SimonKing

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.

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

### comment:17 Changed 8 years ago by SimonKing

• Status changed from needs_review to needs_work

I tried to apply the patches - apparently it is

Apply trac_7797-letterplace_ring_hack.patch trac_7797-letterplace.3.patch plural_functions.patch

Correct?

Unfortunately, plural_functions.patch fails. Can you rebase it, please?

### comment:18 Changed 8 years ago by SimonKing

• Work issues set to rebase, doctests

In addition, one doc test has a different result:

sage: from sage.libs.singular.letterplace import freegb
sage: F.<x,y,z> = FreeAlgebra(QQ, 3); F
Free Algebra on 3 generators (x, y, z) over Rational Field
sage: l=[2*x*z*x+y*x*y, 3*x*y+x*z]
sage: freegb(l, 10)
[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]

Which one is correct?

### comment:19 Changed 8 years ago by SimonKing

FYI: As I mentioned in an earlier post, just having a two-sided Gröbner basis is not enough for my envisioned applications. I also need a competitive arithmetic for free associative algebras, normal form computation, and, if possible, ideals in non-commutative rings, and ring quotients.

So, I implemented something from scratch, not based on the previous patches. I already got an implementation of free associative algebras based on letterplace (with a dynamic degree bound). For example, computing (x+y)**20 is 84 times faster than with the old implementation of free algebras.

I also have a base class for left, right and twosided ideals: If R is any ring and L a list of elements, then R*L is a left ideal, L*R a right ideal, and R*L*R a twosided ideal.

Using freegb for the computation of a two-sided Gröbner basis will be straight forward. In addition, Grischa Studzinski and Viktor Levandoskyy provided me with some code for computing normal forms in free algebras, that is supposed to be in a future Singular release. My plan is to back-port it.

And then there's documentation to write...

### comment:20 Changed 8 years ago by SimonKing

• Authors changed from Michael Brickenstein, Burcin Erocal to Simon King, Michael Brickenstein, Burcin Erocal
• Description modified (diff)
• Work issues rebase, doctests deleted

### comment:21 Changed 8 years ago by SimonKing

• Summary changed from basic interface to letterplace from singular to Full interface to letterplace from singular

I have attached a new patch that replaces all previous patches and provides a lot more functionality.

Since I learned much from the previous patches, I hesitate to remove Michael and Burcin from the author list. But perhaps you like to be referee? Then you should move your name into the reviewer field.

Technical Remarks

singular_function is very useful! However, it was impossible to simply call the freegb.lib library functions of Singular, since they rely on ring attributes -- but ring attributes have not been wrapped in libSingular.

Moreover, it is not a good idea to call the makeLetterplaceRing function from Singular and then transform the resulting RingWrap into a polynomial ring. It is possible -- but the result can not be pickled, since its variable names look like x(1),y(1),x(2),y(2) and are thus no valid identifiers.

But it is no problem to create another ring with more sober variable names, and apply the letterplace functions to it. One just needs to work around the attribute tests that these functions do. In fact, these functions do only one thing after the checking, namely a system call. So, I simply did this system calls as well.

In the current release, Singular does provide the Gröbner basis computations in free algebras, but it does not provide normal form computations. Grischa Studzinski has send me some code that is supposed to become part of freegb.lib -- again, I can not call it directly, but it was fairly straight forward to implement along the lines of Grischa's code.

New Features

Free Algebra constructor as UniqueFactory

Up to now, the FreeAlgebra constructor was based on an incomplete way of caching: When you pickle and unpickle a free algebra, you would not get the same object.

# old behaviour
sage: F.<a,b,c> = FreeAlgebra(QQ,3)
False

This is now resolved. Moreover, it is not needed to explicitly provide the number of generators, when it is obvious from the list of names:

sage: F.<x,y,z> = FreeAlgebra(QQ)
True

I did one change that may be subject to criticism, and I wouldn't oppose to revert it. A free algebra in one generator is a polynomial ring. So, I return a polynomial ring:

sage: FreeAlgebra(QQ,'x')
Univariate Polynomial Ring in x over Rational Field

The constructor can now also be asked for a different implementation, as in all examples below.

Free Algebra via Letterplace

I provide a new implementation of free algebras. It can be constructed as follows:

sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace')
sage: F
Free Associative Unital Algebra on 3 generators ('x', 'y', 'z') over Rational Field

Due to some shortcomings of Singular's letterplace implementation, unfortunately we need to restrict to homogeneous elements:

sage: (x+2*y)^2
x*x + 2*x*y + 2*y*x + 4*y*y
sage: x+0
x
Traceback (most recent call last):
...
ArithmeticError: Can only add elements of the same degree

This is why the new implementation can not yet become the default.

However, the arithmetic in the new implementation is much faster than the old:

sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace')
sage: F_old.<a,b,c> = FreeAlgebra(QQ)
sage: timeit('t=(x+y)^15')
5 loops, best of 3: 27.7 ms per loop
sage: timeit('t=(a+b)^15')
sage: %time t=(a+b)^15
CPU times: user 4.51 s, sys: 0.09 s, total: 4.60 s
Wall time: 6.46 s
sage: 4510/27.7
162.815884476534
sage: timeit('t=(x+y)^15')
25 loops, best of 3: 19.7 ms per loop
sage: %time t=(a+b)^15
CPU times: user 2.70 s, sys: 0.02 s, total: 2.72 s
Wall time: 2.73 s
sage: 2700/19.7
137.055837563452

One- and Twosided Ideals of Noncommutative Rings

I implemented it in a fairly general way, ideals can be created for any ring:

sage: A = SteenrodAlgebra(2)
sage: IL = A*[A.1+A.2,A.1^2]; IL
Left Ideal (Sq(2) + Sq(4), Sq(1,1)) of mod 2 Steenrod algebra
sage: IR = [A.1+A.2,A.1^2]*A; IR
Right Ideal (Sq(2) + Sq(4), Sq(1,1)) of mod 2 Steenrod algebra
sage: IT = A*[A.1+A.2,A.1^2]*A; IT
Twosided Ideal (Sq(2) + Sq(4), Sq(1,1)) of mod 2 Steenrod algebra

Note some nastyness: The parent of an ideal still is the "monoid of ideals of a ring". But we actually have no multiplication in the non-commutative setting:

sage: IL*IR
Traceback (most recent call last):
...
NotImplementedError: Can not multiply non-commutative ideals.

Of course, in general, we have no way to solve the ideal containment problem. But in free algebras, we have letterplace:

sage: I.groebner_basis(degbound=3)
Twosided Ideal (y*y*y - y*y*z + y*z*y - y*z*z, y*y*x + y*y*z + y*z*x + y*z*z, x*y + y*z, x*x - y*x - y*y - y*z) of Free Associative Unital Algebra on 3 generators ('x', 'y', 'z') over Rational Field
sage: (x*y*z*y*x).normal_form(I)
y*z*z*y*z + y*z*z*z*x + y*z*z*z*z
sage: x*y*z*y*x - (x*y*z*y*x).normal_form(I) in I
True
sage: x*I.0-I.1*y+I.0*y in I
True
sage: 1 in I
False

Quotient Rings

Previously, quotient rings have only been available for rings that inherit from the base class of commutative rings. My patch makes them available for all rings, and actually it should work to some extent even for objects that belong to the category Rings() but do not inherit from sage.rings.ring.Ring.

The requirement is that we mod by an ideal I that is twosided and that has a method I.reduce(x) that returns a normal form of an element x with respect to I. That requirement holds for ideals of polynomial rings, and also for homogeneous ideals of free associative algebras. In particular:

sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace')
sage: I = F*[x*y+y*z,x^2+x*y-y*x-y^2]*F
sage: Q.<a,b,c> = F.quo(I); Q
Quotient of Free Associative Unital Algebra on 3 generators ('x', 'y', 'z') over Rational Field by the ideal (x*y + y*z, x*x + x*y - y*x - y*y)
sage: a*b
-b*c
sage: a^3
-b*c*a - b*c*b - b*c*c
sage: J = Q*[a^3-b^3]*Q
sage: R.<i,j,k> = Q.quo(J); R
Quotient of Free Associative Unital Algebra on 3 generators ('x', 'y', 'z') over Rational Field by the ideal (-y*y*z - y*z*x - 2*y*z*z, x*y + y*z, x*x + x*y - y*x - y*y)
sage: i^3
-j*k*i - j*k*j - j*k*k
sage: j^3
-j*k*i - j*k*j - j*k*k

One can also test if the quotient is commutative:

sage: Q.is_commutative()
False
sage: J = F*[x*y-y*x,x*z-z*x,y*z-z*y,x^3-y^3]*F
sage: R = F.quo(J)
sage: R.is_commutative()
True

Miscellaneous

I inserted the documentation of the new modules into the reference manual - I think it looks nice, but I guess a referee should double check.

Doc tests pass for me. Thus: Ready for review!!

### comment:22 Changed 8 years ago by SimonKing

• Status changed from needs_work to needs_review

### comment:23 Changed 8 years ago by SimonKing

I forgot one technical detail:

Not all rings inherit from the base class of rings. Examples are matrix algebras. In order to support non-commutative ideals for such rings, I provide the relevant methods as ParentMethods in the category of Rings(). Perhaps this duplication of code is considered a code smell.

At least, it enables the following:

sage: MS = MatrixSpace(QQ,2,2)
sage: MS*[MS.1,2]
Left Ideal
(
[0 1]
[0 0],

[2 0]
[0 2]
)
of Full MatrixSpace of 2 by 2 dense matrices over Rational Field

### comment:24 Changed 8 years ago by SimonKing

Apparently the patchbot does not read the ticket description.

Apply trac7797-full_letterplace_wrapper.patch

### comment:25 Changed 8 years ago by SimonKing

I realise that I made at least two copy-and-paste errors in the examples above: One of the "timeit" commands should be removed, and the ideals I always is the same, namely I = F*[x*y+y*z,x^2+x*y-y*x-y^2]*F.

Sorry, Simon

### comment:27 Changed 8 years ago by SimonKing

Anne Schilling reported a problem on sage-combinat-devel: The patch did apply, but "sage -br" did not work. I think I found the reason: The patch did not contain the empty __init__.py file in sage/algebras/letterplace/. Simply I forgot to add it.

I updated the patch, and now I hope it works. By the way, is the patchbot not working? I miss the coloured stamp on the ticket!

Apply trac7797-full_letterplace_wrapper.patch

### comment:28 Changed 8 years ago by SimonKing

Currently, the Letterplace Gröbner bases can only be computed if the ring of coefficients is a field. I don't know whether this condition can be lifted and whether the Singular team is working on it.

That restriction was mentioned in the doc, but not very clearly, and the error message was obscure (namely, it came from the failing call to a Singular system function). There is now additional documentation of that restriction, and the error message is nicer.

Apply trac7797-full_letterplace_wrapper.patch

### comment:30 follow-up: ↓ 31 Changed 8 years ago by nthiery

Version rebased on top of #10961 available from:

### comment:31 in reply to: ↑ 30 ; follow-up: ↓ 33 Changed 8 years ago by SimonKing

Version rebased on top of #10961 available from:

Thank you!

What is the procedure? Shall I replace my patch with the rebased one and state the dependency (to the patchbot), or shall the rebased version remain on the combinat patch server?

Best regards, Simon

### comment:32 follow-up: ↓ 35 Changed 8 years ago by aschilling

This patch provides an interface to Singular, which gives a faster implementation of free algebras and adds new features such as for example quotients of free algebras (for terms of homogeneous degree). I have tested the quotient algebra features extensively and they seem to work great!

I do not feel qualified to do a technical review, but I am happy to give a positive review for the new features added.

Anne

### comment:33 in reply to: ↑ 31 Changed 8 years ago by aschilling

Version rebased on top of #10961 available from:

Thank you!

What is the procedure? Shall I replace my patch with the rebased one and state the dependency (to the patchbot), or shall the rebased version remain on the combinat patch server?

Best regards, Simon

Since #10961 hopefully gets merged soon, you should probably upload the rebased version on trac and add Dependencies: #10961' to the description. Then patchbot should in principle know!

### comment:34 Changed 8 years ago by SimonKing

• Description modified (diff)

For the patchbot:

Apply trac7797-full_letterplace_wrapper.patch Depends on #10961

### comment:35 in reply to: ↑ 32 Changed 8 years ago by SimonKing

This patch provides an interface to Singular, which gives a faster implementation of free algebras and adds new features such as for example quotients of free algebras (for terms of homogeneous degree). I have tested the quotient algebra features extensively and they seem to work great!

Good! I'll give that feedback to the Singular team as well.

I do not feel qualified to do a technical review, but I am happy to give a positive review for the new features added.

Thank you! There is at least one point that should probably be raised on sage-algebra: Is it acceptable that (with my patch) the FreeAlgebra constructor returns a polynomial ring when asked for a free algebra with only one generator?

Mathematically it is correct, but I wonder if that is acceptable in a CAS.

Simon

### comment:36 Changed 8 years ago by SimonKing

• Description modified (diff)

The new patch differs from the old one only in the comments.

Again for the patchbot:

Apply trac7797-full_letterplace_wrapper.patch

Depends on #10961

### Changed 8 years ago by SimonKing

A full wrapper for Singular's letterplace functionality, plus non-commutative ideals and ring quotients; rebased on top of 10961

### comment:37 follow-up: ↓ 38 Changed 8 years ago by SimonKing

I added an __iter__ method for FreeAlgebraElement_letterplace, returning the list of pairs "exponent tuple, coefficient", and a method of FreeAlgebra_letterplace that returns an element, such that F(dict(p))==p for any element p of F. That has been requested by Nicolas.

For the patchbot:

Apply trac7797-full_letterplace_wrapper.patch

Depends on #10961

### comment:38 in reply to: ↑ 37 Changed 8 years ago by SimonKing

...such that F(dict(p))==p for any element p of F.

Sorry, I meant to write p == F._from_dict_(dict(p)).

### comment:39 Changed 8 years ago by SimonKing

• Reviewers set to split the ticket
• Status changed from needs_review to needs_work

It was suggested to split this ticket, and also it was suggested that the FreeAlgebra constructor always returns a free algebra, not a polynomial ring.

### comment:40 Changed 8 years ago by SimonKing

• Description modified (diff)
• Reviewers split the ticket deleted
• Work issues set to Unigenerated free algebra vs. univariate polynomial ring

I managed to split my patch. The part concerning "basic implementation of ideals in non-commutative rings" is now at #11068. The new patch is based on top of that.

TODO

Let the FreeAlgebra constructor always return a free algebra, not a polynomial ring.

New Feature

In addition to what was described in previous comments, my letterplace wrapper can compute complete twosided Gröbnerbases by an adaptive algorithm. The idea is simple: If the Gröbner basis is known out to degree 2*d-1, but the highest degree of its generators is d, then the Gröbner basis is complete.

Example:

sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace')
sage: I = F*[x*y-y*x,x*z-z*x,y*z-z*y,x^2*y-z^3,x*y^2+z*x^2]*F
sage: I.groebner_basis(Infinity)
Twosided Ideal (z*z*z*y*y + z*z*z*z*x, z*x*x*x + z*z*z*y, y*z - z*y, y*y*x + z*x*x, y*x*x - z*z*z, x*z - z*x, x*y - y*x) of Free Associative Unital Algebra on 3 generators ('x', 'y', 'z') over Rational Field

Since the commutators are contained in the ideal, we can verify that result with a commutative Gröbner basis, as follows:

sage: P.<c,b,a> = PolynomialRing(QQ,order='neglex')
sage: J = P*[a^2*b-c^3,a*b^2+c*a^2]
sage: J.groebner_basis()
[b*a^2 - c^3, b^2*a + c*a^2, c*a^3 + c^3*b, c^3*b^2 + c^4*a]

So, that's a good consistency test.

Apply trac7797-full_letterplace_wrapper_rel11068.patch

Depends on #11068

### comment:41 Changed 8 years ago by SimonKing

• Work issues changed from Unigenerated free algebra vs. univariate polynomial ring to Unigenerated free algebra vs. univariate polynomial ring; refactoring of nc-ideals

I don't know why, but even though mercurial claims that it tracks sage/algebras/letterplace/__init__.py, it kept forgetting to include it into the patch. So, I decided to fill __init__.py with some comment. Now it should work.

Of course, you may play with the patch, but it still needs work. First of all, there is the issue that the free algebra constructor should never return a polynomial ring (in the univariate case). And then, my plan is to refactor things, such that there will also be dependencies with #9138 and #9944.

Depends on #11068

Apply trac7797-full_letterplace_wrapper_rel11068.patch

### comment:42 Changed 7 years ago by SimonKing

• Status changed from needs_work to needs_review
• Work issues Unigenerated free algebra vs. univariate polynomial ring; refactoring of nc-ideals deleted

I updated the patch.

Apply trac7797-full_letterplace_wrapper_rel11068.patch

Depends on #11068

Actually I am not sure about all dependencies. #11068 should be enough on top of sage-4.7.alpha5. However, here is a full account of the patches that I had applied to sage-4.7.alpha5 before creating the patch here: #10296, #9944, #9138, #9976, #11115, #11068.

In particular, I think the refactoring of rings, quotient rings and non-commutative ideals is successfully solved in #9138 and #11068. Concerning unigenerated free algebras, it seems better to stay in the world of free algebras, rather than returning a polynomial ring. So, we have

sage: F.<x> = FreeAlgebra(QQ)
sage: F
Free Algebra on 1 generators (x,) over Rational Field
sage: F.is_commutative()
True
sage: F.<x> = FreeAlgebra(QQ, implementation='letterplace')
sage: F
Free Associative Unital Algebra on 1 generators (x,) over Rational Field
sage: F.is_commutative()
True

In principle, it could be reviewed now. But the patch chain in front of it is rather large, and not everything has a positive review, yet.

My next plan: Allow positive integer degree weights on the generators, extending the scope of the letterplace wrapper from homogeneous to weighted homogeneous elements, and allow degree-wise computation of weighted homogeneous Gröbner bases. Note that this goes beyond what is currently implemented in Singular, but it should work using a little hack (slack variables).

### comment:43 Changed 7 years ago by SimonKing

Sorry, I needed to update the patch due to some outdated doc tests that I forgot to correct.

Apply trac7797-full_letterplace_wrapper_rel11068.patch

Depends on #11068

### comment:44 follow-up: ↓ 45 Changed 7 years ago by SimonKing

• Status changed from needs_review to needs_work

I just found that the documentation (at least with #9976 applied) is not good. Some stuff is included that certainly does not belong there.

### comment:45 in reply to: ↑ 44 Changed 7 years ago by SimonKing

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

I just found that the documentation (at least with #9976 applied) is not good. Some stuff is included that certainly does not belong there.

Actually, on second thought, it belongs there: I am talking about the two singular_function instances included in the module. The main problem was that singular_function includes the documentation provided by Singular without taking care of formatting -- resulting in numerous errors (e.g., back ticks are misinterpreted as the beginning of Latex expressions, the indentation is handled differently, and so on).

In #11268, I suggest to take care if it by turning the Singular documentation into a verbose code block. With that change, the documentation looks a lot better. I therefore make it a new dependency.

Depends on #11068 #11268

### comment:46 Changed 7 years ago by SimonKing

• Dependencies set to #11068, #11268

### comment:47 Changed 7 years ago by SimonKing

• Description modified (diff)
• Keywords free algebra letterplace added

Meanwhile I implemented two other features:

Uniqueness of parents

sage: F.<x,y,z> = FreeAlgebra(QQ, 3)
False

I rewrote the FreeAlgebra constructor using UniqueFactory, so that the answer above becomes True.

Degree weights

The letterplace implementation in Singular is restricted to homogeneous ideals, and each generator can only have degree 1. With a little hack, I introduced positive integral degree weights for generators, so that we can now do:

sage: F.<x,y,z> = FreeAlgebra(QQ, implementation='letterplace', degrees=[1,2,3])
sage: I = F*[x*y+z-y*x,x*y*z-x^6+y^3]*F
sage: I.groebner_basis(Infinity)
Twosided Ideal (x*z*z - y*x*x*z - y*x*y*y + y*x*z*x + y*y*y*x + z*x*z + z*y*y - z*z*x, x*y - y*x + z, x*x*x*x*z*y*y + x*x*x*z*y*y*x - x*x*x*z*y*z - x*x*z*y*x*z + x*x*z*y*y*x*x + x*x*z*y*y*y - x*x*z*y*z*x - x*z*y*x*x*z - x*z*y*x*z*x + x*z*y*y*x*x*x + 2*x*z*y*y*y*x - 2*x*z*y*y*z - x*z*y*z*x*x - x*z*y*z*y + y*x*z*x*x*x*x*x - 4*y*x*z*x*x*z - 4*y*x*z*x*z*x + 4*y*x*z*y*x*x*x + 3*y*x*z*y*y*x - 4*y*x*z*y*z + y*y*x*x*x*x*z + y*y*x*x*x*z*x - 3*y*y*x*x*z*x*x - y*y*x*x*z*y + 5*y*y*x*z*x*x*x + 4*y*y*x*z*y*x - 4*y*y*y*x*x*z + 4*y*y*y*x*z*x + 3*y*y*y*y*z + 4*y*y*y*z*x*x + 6*y*y*y*z*y + y*y*z*x*x*x*x + y*y*z*x*z + 7*y*y*z*y*x*x + 7*y*y*z*y*y - 7*y*y*z*z*x - y*z*x*x*x*z - y*z*x*x*z*x + 3*y*z*x*z*x*x + y*z*x*z*y + y*z*y*x*x*x*x - 3*y*z*y*x*z + 7*y*z*y*y*x*x + 3*y*z*y*y*y - 3*y*z*y*z*x - 5*y*z*z*x*x*x - 4*y*z*z*y*x + 4*y*z*z*z - z*y*x*x*x*z - z*y*x*x*z*x - z*y*x*z*x*x - z*y*x*z*y + z*y*y*x*x*x*x - 3*z*y*y*x*z + 3*z*y*y*y*x*x + z*y*y*y*y - 3*z*y*y*z*x - z*y*z*x*x*x - 2*z*y*z*y*x + 2*z*y*z*z - z*z*x*x*x*x*x + 4*z*z*x*x*z + 4*z*z*x*z*x - 4*z*z*y*x*x*x - 3*z*z*y*y*x + 4*z*z*y*z + 4*z*z*z*x*x + 2*z*z*z*y, x*x*x*x*x*z + x*x*x*x*z*x + x*x*x*z*x*x + x*x*z*x*x*x + x*z*x*x*x*x + y*x*z*y - y*y*x*z + y*z*z + z*x*x*x*x*x - z*z*y, x*x*x*x*x*x - y*x*z - y*y*y + z*z) of Free Associative Unital Algebra on 3 generators (x, y, z) over Rational Field

This and the possibility to compute a complete Gröbner basis (provided a finite complete Gröbner basis exists) go beyond what is currently in Singular.

The underlying idea of the degree weights is: Introduce a homogenizing variable. By default, it is called x, but a different name is chosen if there is a name conflict. Here, it is renamed to x_. And then, we represent a generator z of degree d internally as z*x_^(d-1) (of course with non-commutative multiplication).

Hence, the underlying truncated letterplace ring becomes a bit bigger, and in the bigger ring all generators are of degree one. Of course, the additional variable is omitted in the string representation. We have for example

sage: z
z
sage: z.degree()
3
sage: z.letterplace_polynomial()
z*x__1*x__2

As much as I know, with that approach, Gröbner bases are correctly computed: If in all polynomials each occurrence of z is followed by x_^(d-1) then all S-polynomials and reductions (computed in the ring with additional generator x_ and with all generators in degree 1) will have the same property.

I know this is a hack, but I guess it may be useful. It certainly will be usefull for my current project, because I need degree weights.

Apply trac7797-full_letterplace_wrapper_rel11068.patch trac7797-letterplace_degree_weights.patch

Depends on #11068, #11268

### comment:48 Changed 7 years ago by SimonKing

• Description modified (diff)

I noticed that I forgot one detail: Latex!

With the latest patch, we also get

sage: K.<z> = GF(25)
sage: F.<a,b,c> = FreeAlgebra(K, implementation='letterplace', degrees=[1,2,3])
sage: -(a*b*(z+1)-c)^2
(2*z + 1)*a*b*a*b + (z + 1)*a*b*c + (z + 1)*c*a*b - c*c
sage: latex(-(a*b*(z+1)-c)^2)
\left(2 z + 1\right) a b a b + \left(z + 1\right) a b c + \left(z + 1\right) c a b - c c

Apply trac7797-full_letterplace_wrapper_rel11068.patch trac7797-letterplace_degree_weights.patch trac7797-latex_letterplace.patch

Depends on #11068, #11268

### comment:49 Changed 7 years ago by SimonKing

... or also

sage: F.<bla,alpha,z> = FreeAlgebra(QQ, implementation='letterplace', degrees=[1,2,3])
sage: latex(-3*alpha*bla-z)
-3 \alpha \mbox{bla} - z

### comment:50 Changed 7 years ago by SimonKing

Odd. The documentation for letterplace used to build fine. But now, it does not build at all! The output are three empty html pages (empty except for the title and the navigation) - the doc strings do not appear.

Any idea where that might come from?

### comment:51 Changed 7 years ago by SimonKing

• Milestone changed from sage-4.7.1 to sage-4.7

I don't know where it came from. But after deleting doc/output/html/en/reference and doc/output/doctrees/, building the documentation finally succeeded.

So, problem vanished.

### comment:52 Changed 7 years ago by SimonKing

• Milestone changed from sage-4.7 to sage-4.7.1

Apparently I had changed the milestone by accident...

### comment:53 Changed 7 years ago by SimonKing

• Description modified (diff)

In my application, I also need conversion from graded sub-algebras. Hence, I implemented it in the new patch.

To be precise: If we have free graded algebras A and B in letterplace implementation, then there is a coercion from A to B if and only if there is a coercion from the base ring of A to the base ring of B, and the set of generator names of A is a subset of the generator names of B, and the degrees of equally named generators of A and B are equal.

The coercion is always name and degree preserving.

Example:

sage: F.<t,y,z> = FreeAlgebra(ZZ, implementation='letterplace', degrees=[4,2,3])
sage: G = FreeAlgebra(GF(5), implementation='letterplace', names=['x','y','z','t'], degrees=[1,2,3,4])
sage: t*G.0       # indirect doctest
t*x
sage: (t*G.0 + G.1*G.2)*y
y*z*y + t*x*y

Apply trac7797-full_letterplace_wrapper_rel11068.patch trac7797-letterplace_degree_weights.patch trac7797-latex_letterplace.patch trac7797-letterplace_coercion.patch

### Changed 7 years ago by SimonKing

A full wrapper for Singular's letterplace functionality, plus complete Groebner bases; based on top of 11068

### Changed 7 years ago by SimonKing

Implement latex for letterplace polynomials and letterplace algebras

### Changed 7 years ago by SimonKing

Implementing coercion for letterplace algebras

### comment:54 Changed 7 years ago by SimonKing

I had to rebase three of the four patches. Still needing review...

Apply trac7797-full_letterplace_wrapper_rel11068.patch trac7797-letterplace_degree_weights.patch trac7797-latex_letterplace.patch trac7797-letterplace_coercion.patch

### comment:55 follow-up: ↓ 56 Changed 7 years ago by fbissey

• Status changed from needs_review to needs_work

In trac7797-full_letterplace_wrapper_rel11068.patch please do not use SAGE_ROOT + local/include in module_list.py use SAGE_INC instead. I spent sometime cleaning all that up for 4.7.1 and would like to see it stay clean for a little while longer.

### comment:56 in reply to: ↑ 55 Changed 7 years ago by SimonKing

In trac7797-full_letterplace_wrapper_rel11068.patch please do not use SAGE_ROOT + local/include in module_list.py use SAGE_INC instead.

I didn't know that SAGE_INC exists. It is certainly a good idea to use such variables whenever possible.

### comment:57 Changed 7 years ago by SimonKing

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

I'm now using SAGE_INC, and I used the occasion to create a combined patch. Apply trac7797-full_letterplace_wrapper_combined.patch

### comment:58 Changed 7 years ago by SimonKing

I had to rebase my patch: Some trivial changes in the doc tests were needed, since block orders are now displayed differently.

Apply trac7797-full_letterplace_wrapper_combined.patch

### comment:59 Changed 7 years ago by AlexanderDreyer

• Owner changed from burcin to (none)
• Reviewers set to Alexander Dreyer

sage-4.7.2alpha3-prerelease with the following patches applies:

trac11815_format_must_preserve_embedding.patch
trac11115-cached_cython.patch
trac11115_cached_function_pickling.patch
trac11068_nc_ideals_and_quotients.patch
trac11068_quotient_ring_without_names.patch
trac11068_lifting_map.patch
trac7797-full_letterplace_wrapper_combined.patch

compiles/installs and runs sage -testall successfully on a SuSE Enterprise 11.1. This is close to a positive review, but I'll check out another platform before and have a look at the patch.

### comment:60 Changed 7 years ago by AlexanderDreyer

• Owner changed from (none) to burcin

### comment:61 Changed 7 years ago by AlexanderDreyer

Also compiles/installs and runs sage -testall successfully on Mac OSX ppc (32bit). So I can give a positive review for the technical part. Somebody needs to look for the Maths.

### comment:62 Changed 7 years ago by SimonKing

• Dependencies changed from #11068, #11268 to #4539, #11268

I think it makes sense to use #4539 (which already has a positive review, but is pending because of #9138) as a dependency. I have updated the patch accordingly. The doc tests pass (at least on my machine).

### comment:63 Changed 7 years ago by SimonKing

I forgot to notify the patch bot:

Apply trac7797-full_letterplace_wrapper_combined.patch

### comment:64 Changed 7 years ago by davidloeffler

• Dependencies changed from #4539, #11268 to #4539, #11268, #12461
• Status changed from needs_review to needs_work

The patch fails to apply to 5.0.beta11 -- see patchbot logs. I suspect #12461 is the cause.

Last edited 7 years ago by davidloeffler (previous) (diff)

### comment:65 Changed 7 years ago by SimonKing

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

Yes, #12641 was to blame. The reason was that apparently #12641 did remove four blank spaces. So, the change is trivial.

By the way: At the recent annual meeting of the German Science Foundation Priority Programme on computer algebra, I was talking to Viktor Levandovskii, who is responsible for Letterplace in Singular. He confirmed that my hacks for implementing degree weights and for computing complete Gröbner bases are correct.

Apply trac7797-full_letterplace_wrapper_combined.patch

### comment:66 Changed 7 years ago by SimonKing

• Dependencies changed from #4539, #11268, #12461 to #4539, #11268, #12461, #12749
• Status changed from needs_review to needs_work
• Work issues set to rebase rel #12749

It needs to be rebased wrt. #12749: This ticket adds doctests, but one hunk for sage/algebras/free_algebra.py adds some doctest as well...

### comment:67 Changed 7 years ago by SimonKing

• Description modified (diff)
• Status changed from needs_work to needs_review
• Work issues rebase rel #12749 deleted

Apply trac7797-full_letterplace_wrapper_combined.patch

### comment:68 Changed 6 years ago by SimonKing

It is now 4 months ago that I last asked if someone could review the patch, so that we would have Gröbner bases of two-sided homogeneous ideals in free associative algebras. Which other CAS has those? So: BUMP!

### comment:69 Changed 6 years ago by SimonKing

• Dependencies changed from #4539, #11268, #12461, #12749 to #4539, #11268, #12461, #12749, #12988

I had to modify one doctest, due to a new test in the category of rings - see #12988.

Apply trac7797-full_letterplace_wrapper_combined.patch

### comment:70 follow-up: ↓ 71 Changed 6 years ago by AlexanderDreyer

The patch looks good to me, just use the :trac:7791 statement to refer to this ticket here. Provided, that the tests succeeds (I'm currently building a recent sage), I'd say, that we are close to positive.

### comment:71 in reply to: ↑ 70 Changed 6 years ago by SimonKing

• Status changed from needs_review to needs_work
• Work issues set to trailing whitespace, use :trac:

The patch looks good to me, just use the :trac:7791 statement to refer to this ticket here. Provided, that the tests succeeds (I'm currently building a recent sage), I'd say, that we are close to positive.

Yep, I think I wrote the patch before the :trac: directive has been introduced. The patchbot complains about trailing white space - so, I'll take care of that as well.

### comment:72 Changed 6 years ago by SimonKing

• Status changed from needs_work to needs_review
• Work issues trailing whitespace, use :trac: deleted

Now it should be fine, regarding whitespace and regarding :trac: directive.

Apply trac7797-full_letterplace_wrapper_combined.patch

### comment:73 Changed 6 years ago by AlexanderDreyer

The patch applies nicely to sage-5.3 beta1 and the rebuild of the sage library was successful. So let' s wait for make ptestlong to finish.

### comment:74 Changed 6 years ago by AlexanderDreyer

• Report Upstream changed from N/A to None of the above - read trac for reasoning.
• Status changed from needs_review to positive_review

Ok, ptestlong succeeded, so we ave a positive review!

### comment:75 Changed 6 years ago by jdemeyer

• Merged in set to sage-5.3.rc0
• Resolution set to fixed
• Status changed from positive_review to closed

### comment:76 Changed 6 years ago by jdemeyer

• Merged in sage-5.3.rc0 deleted
• Resolution fixed deleted
• Status changed from closed to new

This leads to lots of failures on Solaris SPARC:

sage -t  --long -force_lib devel/sage/sage/algebras/free_algebra.py # 3 doctests failed
sage -t  --long -force_lib devel/sage/sage/algebras/letterplace/free_algebra_element_letterplace.pyx # 13 doctests failed
sage -t  --long -force_lib devel/sage/sage/algebras/letterplace/free_algebra_letterplace.pyx # 6 doctests failed
sage -t  --long -force_lib devel/sage/sage/algebras/letterplace/letterplace_ideal.pyx # 14 doctests failed
sage -t  --long -force_lib devel/sage/sage/rings/quotient_ring.py # 11 doctests failed
sage -t  --long -force_lib devel/sage/sage/rings/quotient_ring_element.py # 1 doctests failed

### comment:77 Changed 6 years ago by jdemeyer

• Milestone changed from sage-5.3 to sage-5.4
• Status changed from new to needs_review

### comment:78 Changed 6 years ago by jdemeyer

• Status changed from needs_review to needs_work

### comment:79 follow-up: ↓ 80 Changed 6 years ago by SimonKing

I see that most (or all?) the errors reported in the log file occur while calling a singular_function. Is it perhaps the case that singular_function is generally problematic on Solaris SPARC?

Does Letterplace works on Solaris SPARC in Singular? I think I was told that Singular's system function could be a problem -- but Letterplace relies on it, both in Singular and here.

I.e., is the problem on the side of Singular, or of the wrapper?

### comment:80 in reply to: ↑ 79 ; follow-up: ↓ 81 Changed 6 years ago by jdemeyer

• Dependencies changed from #4539, #11268, #12461, #12749, #12988 to #4539, #11268, #12461, #12749, #12988, #13237

I.e., is the problem on the side of Singular, or of the wrapper?

How can I check? What commands should I run in Singular to check?

Also, I added #13237 (Upgrade to Singular-3-1-5) as dependency just in case it matters. My tests on Solaris SPARC were done with the new Singular from #13237.

### comment:81 in reply to: ↑ 80 ; follow-up: ↓ 82 Changed 6 years ago by SimonKing

I.e., is the problem on the side of Singular, or of the wrapper?

How can I check? What commands should I run in Singular to check?

Also, I added #13237 (Upgrade to Singular-3-1-5) as dependency just in case it matters. My tests on Solaris SPARC were done with the new Singular from #13237.

Hans Schönemann has tested it. He used Singular-3-1-5, or in more detail:

Singular for SunOS-5 version 3-1-5 (3150)  Aug 27 2012 19:23:52
with
factory(@(#) factoryVersion = 3.1.5),libfac(3.1.5,July 2012),
dynamic modules,dynamic p_Procs,OM_CHECK=0,OM_TRACK=0,random=1346170574
CC= gcc -m64 -mptr64 -mcpu=ultrasparc3 -O2 -w -fomit-frame-pointer -pipe -DNDEBUG -DOM_NDEBUG -DSunOS_5 -DHAVE_CONFIG_H,
CXX= g++ -m64 -mptr64 -mcpu=ultrasparc3 -O2 -w -fomit-frame-pointer -I.. -I/users/cip/alggeom/hannes/galois64 -pipe -DNDEBUG -DOM_NDEBUG -DSunOS_5 -DHAVE_CONFIG_H (3.3.2)

The example worked fine, which indicates that it is a problem with my wrapper. If you want to test it for yourself:

LIB "freegb.lib";
ring r = 0,(x,y,z),dp;
int d =4; // degree bound
def R = makeLetterplaceRing(d);
setring R;
ideal I = x(1)*y(2) + y(1)*z(2), x(1)*x(2) + x(1)*y(2) - y(1)*x(2) - y(1)*y(2);
option(redSB); option(redTail);
ideal J = letplaceGBasis(I);
J;

The expected result is

==> J[1]=x(1)*y(2)+y(1)*z(2)
==> J[2]=x(1)*x(2)-y(1)*x(2)-y(1)*y(2)-y(1)*z(2)
==> J[3]=y(1)*y(2)*y(3)-y(1)*y(2)*z(3)+y(1)*z(2)*y(3)-y(1)*z(2)*z(3)
==> J[4]=y(1)*y(2)*x(3)+y(1)*y(2)*z(3)+y(1)*z(2)*x(3)+y(1)*z(2)*z(3)
==> J[5]=y(1)*z(2)*y(3)*y(4)-y(1)*z(2)*y(3)*z(4)+y(1)*z(2)*z(3)*y(4)-y(1)*z(2\
)*z(3)*z(4)
==> J[6]=y(1)*z(2)*y(3)*x(4)+y(1)*z(2)*y(3)*z(4)+y(1)*z(2)*z(3)*x(4)+y(1)*z(2\
)*z(3)*z(4)
==> J[7]=y(1)*y(2)*z(3)*y(4)-y(1)*y(2)*z(3)*z(4)+y(1)*z(2)*z(3)*y(4)-y(1)*z(2\
)*z(3)*z(4)
==> J[8]=y(1)*y(2)*z(3)*x(4)+y(1)*y(2)*z(3)*z(4)+y(1)*z(2)*z(3)*x(4)+y(1)*z(2\
)*z(3)*z(4)

I will see whether letplaceGBasis does anything new - perhaps I can learn from it?

### comment:82 in reply to: ↑ 81 Changed 6 years ago by SimonKing

I will see whether letplaceGBasis does anything new - perhaps I can learn from it?

No, the essential part is the same. Namely:

ideal J = system("freegb",I,uptodeg,lV);

If I am not mistaken, it is the analogue of this command that fails in my code.

The question that I'd like to be answered is: Are calls to Singular's "system" function possible in Sage on Solaris SPARC? Could you please test the following in Sage on Solaris SPARC?

sage: from sage.libs.singular.function import singular_function
sage: sing_system = singular_function("system")
sage: R.<x,y> = QQ[]
sage: sing_system("uname", ring=R)
'x86_64-Linux'  # ok, the answer will be different on Solaris SPARC...
Last edited 6 years ago by SimonKing (previous) (diff)

### comment:83 Changed 6 years ago by jdemeyer

Solaris SPARC, Sage 5.2 (i.e. Singular-3-1-3-3):

----------------------------------------------------------------------
| Sage Version 5.2, Release Date: 2012-07-25                         |
| Type "notebook()" for the browser-based notebook interface.        |
| Type "help()" for help.                                            |
----------------------------------------------------------------------
sage: sage.libs.singular.function.singular_function("system")("uname", ring=PolynomialRing(QQ,2,'x'))
// ** s_internalDelete: cannot delete type sqrfree(493)
---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)

/home/jdemeyer/mark/sage-5.2/<ipython console> in <module>()

/home/jdemeyer/mark/sage-5.2/local/lib/python2.7/site-packages/sage/libs/singular/function.so in sage.libs.singular.function.SingularFunction.__call__ (sage/libs/singular/function.cpp:11875)()

/home/jdemeyer/mark/sage-5.2/local/lib/python2.7/site-packages/sage/libs/singular/function.so in sage.libs.singular.function.call_function (sage/libs/singular/function.cpp:13425)()

RuntimeError: Error in Singular function call 'system':
system(sqrfree`) failed

### comment:84 Changed 6 years ago by SimonKing

Thank you, Jeroen!

So, the bug is not in my wrapper, but in singular_function. And that error looks rather strange. I'll ask Hans, tomorrow.

Martin, do you have an idea where that error might come from?

### comment:85 follow-up: ↓ 86 Changed 6 years ago by SimonKing

Here is the code for system("uname") (to be found in Singular/extra.cc):

/*==================== uname ==================================*/
if(strcmp(sys_cmd,"uname")==0)
{
res->rtyp=STRING_CMD;
res->data = omStrDup(S_UNAME);
return FALSE;
}

About // ** s_internalDelete: cannot delete type sqrfree(493): According to Hans, 493 is the token for the command sqrfree, which is not a type but a command. Therefore deleting an object with 493's type is impossible. He doesn't understand how that happens here.

res->data is a C string, and STRING_CMD is the token 495, which stands for the type of a string (char *). Could Solares SPARC mistake 495 for 493??

### comment:86 in reply to: ↑ 85 Changed 6 years ago by AlexanderDreyer

res->data is a C string, and STRING_CMD is the token 495, which stands for the type of a string (char *). Could Solares SPARC mistake 495 for 493??

There probably an outdated Singular/tok.h around. Tokens like INTMOD_CMD were added recently, so this would explain the shift in the enum.

### comment:87 Changed 6 years ago by jdemeyer

• Owner changed from burcin to jdemeyer

Okay, with a build from scratch:

sage: sage.libs.singular.function.singular_function("system")("uname", ring=PolynomialRing(QQ,2,'x'))
'SunOS-5'

So I probably messed up something last time (e.g. forget sage -b).

### comment:88 follow-up: ↓ 89 Changed 6 years ago by jdemeyer

Strange. I applied the patch of this ticket again and get only one doctest failure now in sage/algebras:

sage -t  "devel/sage/sage/algebras/letterplace/free_algebra_letterplace.pyx"
**********************************************************************
File "/home/jdemeyer/mark/sage-5.4.beta0/devel/sage/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
**********************************************************************

This calls for some further investigation...

### comment:89 in reply to: ↑ 88 ; follow-up: ↓ 90 Changed 6 years ago by SimonKing

sage -t  "devel/sage/sage/algebras/letterplace/free_algebra_letterplace.pyx"
**********************************************************************
File "/home/jdemeyer/mark/sage-5.4.beta0/devel/sage/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
**********************************************************************

This calls for some further investigation...

That test is about an internally used method (note the underscores), and the output depends on a polynomial ring that is used to simulate computations in free associative algebras out to a certain degree. As you can see, the ideal we expect and the ideal we got are alike - only the polynomial rings differ.

The point is that the underlying polynomial ring can change during computations, and the free associative algebras are unique parents. Hence, if tests are executed in different order then it may very well be that the polynomial ring used behind the scenes is different. Only the final result (i.e., interpreted in the free associative algebra) is unique.

I suggest to modify that test (and perhaps others as well) as follows:

>     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... over Rational Field

The variables before the ... are guaranteed to occur, and we don't know (and don't care) whether more variables appear behind the scenes.

Would you accept that solution?

### comment:90 in reply to: ↑ 89 Changed 6 years ago by AlexanderDreyer

I suggest to modify that test (and perhaps others as well) as follows:

>     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... over Rational Field

The variables before the ... are guaranteed to occur, and we don't know (and don't care) whether more variables appear behind the scenes.

Would you accept that solution?

Sounds reasonable to me. So I'd reestablished the positive review, if Jeroen likes is, too.

Good for me.

### comment:92 in reply to: ↑ 91 Changed 6 years ago by SimonKing

Good for me.

OK, then I'll prepare a patch. Probably not before Sunday, though...

### comment:93 Changed 6 years ago by SimonKing

I have updated the patch, using an ellipse (...) in the failing test.

Apply trac7797-full_letterplace_wrapper_combined.patch

### comment:94 Changed 6 years ago by SimonKing

• Status changed from needs_work to needs_review

### comment:95 Changed 6 years ago by AlexanderDreyer

Hi, I can positively review for Linux. I don't get Sage 5.* compiled on Solaris. Are there any precompiled recent binaries around, maybe at *.washington.edu?

### comment:96 follow-up: ↓ 97 Changed 6 years ago by jhpalmieri

Passes tests for me (I just tested the modified files, not the whole Sage library) on Mac OS X 10.7 and OpenSolaris. I'm working on Solaris, but the only Solaris machines I have access to are really slow.

By the way, can you explain the role of the new line 821 in sage/structure/parent.pyx?

### comment:97 in reply to: ↑ 96 Changed 6 years ago by SimonKing

By the way, can you explain the role of the new line 821 in sage/structure/parent.pyx?

I guess the plan was to add a doc test, then I changed my mind and deleted the doctest incompletely. I guess that line can be removed (by a reviewer patch?).

### comment:98 Changed 6 years ago by jhpalmieri

• Description modified (diff)

### comment:99 Changed 6 years ago by jhpalmieri

• Status changed from needs_review to positive_review

Tests pass on skynet machine mark.

### comment:100 Changed 6 years ago by jdemeyer

• Milestone changed from sage-5.4 to sage-5.5

### comment:101 Changed 6 years ago by jdemeyer

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

### comment:102 Changed 6 years ago by jdemeyer

• Status changed from positive_review to needs_work

### comment:103 Changed 6 years ago by SimonKing

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.

### comment:104 Changed 6 years ago by jdemeyer

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

### Changed 6 years ago by SimonKing

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

### comment:105 Changed 6 years ago by SimonKing

• Status changed from needs_work to positive_review

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

 +            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

### comment:106 Changed 6 years ago by AlexanderDreyer

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

### comment:107 Changed 6 years ago by jdemeyer

• Merged in set to sage-5.5.beta2
• Resolution set to fixed
• Status changed from positive_review to closed

### comment:108 follow-up: ↓ 109 Changed 6 years ago by 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'.

### comment:109 in reply to: ↑ 108 ; follow-up: ↓ 110 Changed 6 years ago by AlexanderDreyer

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.

### comment:110 in reply to: ↑ 109 ; follow-up: ↓ 111 Changed 6 years ago by 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.

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

### comment:111 in reply to: ↑ 110 ; follow-up: ↓ 112 Changed 6 years ago by AlexanderDreyer

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

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

### comment:112 in reply to: ↑ 111 Changed 6 years ago by kcrisman

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

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