Matrix term ordering

[kwankyu]

In Sage, I am trying to construct a polynomial ring with matrix
ordering.
....
AFAIK, it is not implemented, but I think that some people were
working on it.

It is in fact one of the things that I miss in Sage's polynomial rings
(the other thing are supercommutative rings), so that I need to use
the Singular interface rather than libsingular.
....
Anyway it will be great that the matrix ordering is included in Sage
natively.

CC: @novoselt

Component: basic arithmetic

Keywords: term order

Author: Kwankyu Lee

Reviewer: Martin Albrecht

Merged: sage-4.5.2.alpha0

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

[kwankyu]

comment:1

The patch introduces matrix term ordering, but it does not work yet unfortunately.

----------------------------------------------------------------------
| Sage Version 4.1.1, Release Date: 2009-08-14                       |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------
Loading Sage library. Current Mercurial branch is: local2
sage: R.<x,y>=PolynomialRing(QQ,order="matrix(1,3,1,0)")
sage: r=singular(R)
sage: r

//   characteristic : 0
//   number of vars : 2
//        block   1 : ordering M
//                  : names    x y 
//                  : weights  1 3 
//                  : weights  1 0 
//        block   2 : ordering C
sage: f=x^2+y
sage: f.lt()
x^2
sage: f=x^3+y
sage: f.lt()
x^3
sage: t=R.term_order()
sage: t
matrix(1,3,1,0) term order

Please someone who knows better check the patch, and make it work!

Simon says:

Better wait for a proper implementation in libsingular
(which is beyond my capabilities, I am afraid).

Cheers,
Simon

[malb]

comment:2

I don't think we should support the 'matrix()' syntax. The Singular syntax is 'M()' which we should support for compatibility and familiarity. However, adding another string expression does not seem to make sense, because we will be able to simply write order=A where A is an integer matrix which is much more python-ic.

[kwankyu]

comment:3

I agree partially. Should we follow the Singular syntax exactly? For short syntax, how about just "m(1,3,1,0)"? I personally think the Singular syntax for term ordering is somewhat cryptic.

I think it is better for Sage to support both the string description and TermOrder description. Thus for examples,

order='m(1,3,1,0)'+'deglex(2)'

order='m(1,3,1,0),deglex(3)'

for a square matrix m,

order=TermOrder(m)+TermOrder('deglex',3)

are all supported.

Marshall Hampton says:

I agree with John that Simon's example:

  sage: M = Matrix(2,2, [1,3,1,0])
  sage: R.<a,b,c,d,e,f> = PolynomialRing(QQ, order=TermOrder(M)
+TermOrder('deglex',3))

looks good and reasonably intuitive to me.

[kwankyu]

Changed author from Kwankyu Lee to none

[malb]

comment:4

Replying to @kwankyu:

I agree partially. Should we follow the Singular syntax exactly? For short syntax, how about just "m(1,3,1,0)"? I personally think the Singular syntax for term ordering is somewhat cryptic.

Sure, but it would be accepted anyway and passed through to Singular (in an ideal implementation) :)

I think it is better for Sage to support both the string description and TermOrder description. Thus for examples,

order='m(1,3,1,0)'+'deglex(2)'

order='m(1,3,1,0),deglex(3)'

This description is a mix of Singular syntax and Sage string syntax. I would like to avoid Sage string syntax as much as possible.

for a square matrix m,

order=TermOrder(m)+TermOrder('deglex',3)

are all supported.

I like this best.

Marshall Hampton says:

I agree with John that Simon's example:

  sage: M = Matrix(2,2, [1,3,1,0])
  sage: R.<a,b,c,d,e,f> = PolynomialRing(QQ, order=TermOrder(M)
+TermOrder('deglex',3))

looks good and reasonably intuitive to me.

Yep, that's what I would be aiming for.

[kwankyu]

comment:5

The replaced patch is still in beta stage, due to lack of docstrings. It adds matrix ordering to Sage term order suite, which works fine. It is based on Sage 4.4.2. The reason that I uploaded this premature patch is related with the ticket !#9003

[kwankyu]

comment:6

The replaced patch now works, though only with PolyDict engine.

[kwankyu]

Author: Kwankyu Lee

[malb]

comment:9

Replying to @kwankyu:

The replaced patch now works, though only with PolyDict engine.

Sorry for being a bit obnoxious about it, but shouldn't this be needs work until it works across the board? At least we should fall back to the PolyDict version automatically if a matrix term ordering is selected or something.

[kwankyu]

comment:10

Replying to @malb:

Sorry for being a bit obnoxious about it, but shouldn't this be needs work until it works across the board? At least we should fall back to the PolyDict version automatically if a matrix term ordering is selected or something.   

I am sorry that I cannot understand what you mean. Do you mean that matrix term order should work with Singular version before this patch is merged? Now, if a matrix term ordering is selected, then {{PolyDict}} version is used automatically because Singular version does not support matrix term ordering. If someone implements matrix term ordering with Singular version, then I would be happy. I have been waiting for this to be done. As it is not the case, I thought it's not bad to add matrix term ordering support only with {{PolyDict}} version--Singular version may be added later.

[malb]

comment:11

I am sorry that I cannot understand what you mean. Do you mean that matrix term
order should work with Singular version before this patch is merged? Now, if a
matrix term ordering is selected, then PolyDict version is used
automatically because Singular version does not support matrix term ordering.

Right, I forgot that I implemented to fall back this way :) Okay, my bad then.

If someone implements matrix term ordering with Singular version, then I would be
happy.

We all would be happy. All one needs to do btw. is to fix the constructor.

I have been waiting for this to be done.

Why not give it a try yourself? I'd love to help but other commitments prevent me from doing so.

As it is not the case, I thought it's not bad to add matrix term ordering support
only with PolyDict version--Singular version may be added later. 

You are right, I stand corrected.

[malb]

comment:12

I stand corrected twice. YOU implemented it to fall back not me. I thought the automatic fallback would kick in, but from your patch it looks like it doesn't.

[malb]

comment:13

• NotImplementedError, "Singular engine in Sage cannot handle matrix ordering yet." should be replaced by NotImplementedError("Matrix term orderings are not supported by the libSingular interface yet." or something along those lines. I propose this change to make it clearer that Singular can indeed deal with Matrix term orderings and that it is us who cannot.
  • TypeError: Cannot use a matrix term order as a block. shouldn't that be a NotImplementedError?
  • I thought the agreement was not to allow 'matrix(0,1,2,3)' but to use Singular's convention instead? It seems you are allowing at and using it internally.

[malb]

comment:14

Oh, one more thing, isn't

TermOrder([0,1,2,3])

ambiguous since it could be interpreted as a list of weights? I'd vote to not to allow it for matrix term orders.

[kwankyu]

comment:15

Replying to @malb:

• NotImplementedError, "Singular engine in Sage cannot handle matrix ordering yet." should be replaced by NotImplementedError("Matrix term orderings are not supported by the libSingular interface yet." or something along those lines. I propose this change to make it clearer that Singular can indeed deal with Matrix term orderings and that it is us who cannot.

I agree.

• TypeError: Cannot use a matrix term order as a block. shouldn't that be a NotImplementedError?

I know Singular allow matrix term orderings in block order. But this feature is not one of the aims of the current patch. That could be included in a future patch that use Singular version.

• I thought the agreement was not to allow 'matrix(0,1,2,3)' but to use Singular's convention instead? It seems you are allowing at and using it internally.

I did not agree then. :-) Anyway, I will change it to 'm(...)'

[kwankyu]

comment:16

Replying to @malb:

Oh, one more thing, isn't #!python TermOrder([0,1,2,3]) ambiguous since it could be interpreted as a list of weights? I'd vote to not to allow it for matrix term orders.

Ok.

[kwankyu]

Attachment: trac#6922.patch.gz

replaced

[malb]

comment:17

The patch applies cleanly and doctests pass.

I'm still not happy with the interface:

sage: P.<a,b> = PolynomialRing(GF(32003),order=TermOrder(Matrix([1,2,0,3])))
sage: P.term_order()
m(1,2,0,3) term order

This uses the non-standard "m(...)" representation which I would avoid. I'd be happy with either "M()" (Singular notation) or "Matrix term ordering with matrix ..." or so.

Also, the "m()" notation is allowed but shouldn't.

sage: P.<a,b> = PolynomialRing(GF(32003),order='m(1,2,0,3)')

I understand that this is a typical paint-the-bike-shed scenario and in particular a question of choice. Still, I think we shouldn't invent more ad-hoc string notation when (a) there is an established notation and (b) we have a much nicer object oriented way of constructing term orderings.

However, since this isn't really that big of a deal, I am okay with being overruled by some other referee who disagrees.

PS: Apologies for taking so long to revisit this ticket.

[kwankyu]

comment:18

Replying to @malb:

I prefer "Matrix term ordering with matrix ...".

both "M(1,2,0,3)" and "m(1,2,0,3)" is allowed, which is not bad. The situation is the same with other orderings like "Lex", which is converted to lower case internally. I don't mind that "M(...)" should be the official string representation of matrix orderings.

I am working to make matrix ordering work with Singular version. I am not really confident whether the code is sound as it is based on a knowledge obtained by a reverse engineering of libSingular Sage interface.

I will upload a revised patch soon, perhaps within a couple of hours. Then I wish you again to review the patch.

[kwankyu]

with singular version support

[kwankyu]

comment:19

Attachment: trac#6922.2.patch.gz

The new patch supports also the Singular version. Now "M(...)" is the official string representation of matrix orderings.

[malb]

comment:20

Replying to @kwankyu:

The situation is the same with other orderings like "Lex", which is converted to
lower case internally.

Good point, I'm convinced.

I am working to make matrix ordering work with Singular version. I am not really
confident whether the code is sound as it is based on a knowledge obtained by a
reverse engineering of libSingular Sage interface.

Great, I'll take a look.

[malb]

comment:21

Patch looks good (small issue see below), applies cleanly, doctests pass.

So, this stuff now works, very cool:

sage: P = PolynomialRing(GF(127),2,'x',order=Matrix([1,2,0,3]))
sage: P.term_order()
Matrix term order with matrix
[1 2]
[0 3]
sage: magma(P)
Polynomial ring of rank 2 over GF(127)
Order: Weight [full]
Variables: x0, x1
sage: singular(P)
//   characteristic : 127
//   number of vars : 2
//        block   1 : ordering M
//                  : names    x0 x1
//                  : weights   1  2
//                  : weights   0  3
//        block   2 : ordering C

I've attached a small referee patch which Kwankyu or someone else has to sign of. Kwankyu's patch gets a positive review modulo the issue in the referee patch.

[malb]

Attachment: trac_6922_referee.patch.gz

apply after klee's patch

[kwankyu]

Attachment: trac#6922_final.patch.gz

combined with referee's patch

[kwankyu]

comment:22

Positive review for the referee's patch. Thank you!

[loefflerd]

Reviewer: Martin Albrecht

[qed777]

comment:24

I'm applying just trac#6922_final.patch to 4.5.2.alpha0. Just let me know if I'm wrong.

[qed777]

Merged: sage-4.5.2.alpha0