Opened 12 years ago

Closed 11 years ago

#6922 closed enhancement (fixed)

Matrix term ordering

Reported by: klee Owned by: Somebody
Priority: minor Milestone: sage-4.5.2
Component: basic arithmetic Keywords: term order
Cc: novoselt Merged in: sage-4.5.2.alpha0
Authors: Kwankyu Lee Reviewers: Martin Albrecht
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

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.

Attachments (4)

trac#6922.patch (21.8 KB) - added by klee 11 years ago.
replaced
trac#6922.2.patch (26.1 KB) - added by klee 11 years ago.
with singular version support
trac_6922_referee.patch (1.6 KB) - added by malb 11 years ago.
apply after klee's patch
trac#6922_final.patch (26.4 KB) - added by klee 11 years ago.
combined with referee's patch

Download all attachments as: .zip

Change History (29)

comment:1 Changed 12 years ago by klee

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

comment:2 Changed 12 years ago by malb

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.

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

  • Authors Kwankyu Lee deleted

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.

comment:4 in reply to: ↑ 3 Changed 12 years ago by malb

Replying to klee:

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.

comment:5 Changed 12 years ago by klee

  • Report Upstream set to N/A
  • Status changed from new to needs_work

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

comment:6 follow-up: Changed 12 years ago by klee

  • Status changed from needs_work to needs_review

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

comment:7 Changed 12 years ago by klee

  • Authors set to Kwankyu Lee
  • Milestone changed from sage-feature to sage-4.4.3

comment:8 Changed 12 years ago by novoselt

  • Cc novoselt added

comment:9 in reply to: ↑ 6 ; follow-up: Changed 11 years ago by malb

Replying to klee:

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.

comment:10 in reply to: ↑ 9 ; follow-up: Changed 11 years ago by klee

  • Status changed from needs_review to needs_work

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. 

comment:11 in reply to: ↑ 10 Changed 11 years ago by malb

  • Status changed from needs_work to needs_review

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.

comment:12 Changed 11 years ago by malb

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.

comment:13 follow-up: Changed 11 years ago by 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.
  • 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.

comment:14 follow-up: Changed 11 years ago by malb

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.

comment:15 in reply to: ↑ 13 Changed 11 years ago by klee

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(...)' 

comment:16 in reply to: ↑ 14 Changed 11 years ago by klee

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.

Changed 11 years ago by klee

replaced

comment:17 follow-up: Changed 11 years ago by malb

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.

comment:18 in reply to: ↑ 17 ; follow-up: Changed 11 years ago by klee

  • Status changed from needs_review to needs_work

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.

 

Changed 11 years ago by klee

with singular version support

comment:19 Changed 11 years ago by klee

  • Status changed from needs_work to needs_review

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

comment:20 in reply to: ↑ 18 Changed 11 years ago by malb

Replying to klee:

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.

comment:21 Changed 11 years ago by malb

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.

Changed 11 years ago by malb

apply after klee's patch

Changed 11 years ago by klee

combined with referee's patch

comment:22 Changed 11 years ago by klee

  • Status changed from needs_review to positive_review

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

comment:23 Changed 11 years ago by davidloeffler

  • Reviewers set to Martin Albrecht

comment:24 Changed 11 years ago by mpatel

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

comment:25 Changed 11 years ago by mpatel

  • Merged in set to sage-4.5.2.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.