polynomial degree is broken for weighted block orders

[mwageringel]

sage: T = TermOrder('wdegrevlex', (1,2,3,4))
sage: R = PolynomialRing(QQ, 'x', 12, order=T+T+T)
sage: [x.degree() for x in R.gens()]    # wrong
[1, 2, 3, 4, 1, 1, 1, 1, 1, 1, 1, 1]

sage: from sage.libs.singular.function_factory import ff
sage: [ff.deg(x, ring=R) for x in R.gens()]    # correct
[1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4]

CC: @kwankyu @jpflori

Component: algebra

Keywords: singular

Author: Kwankyu Lee

Branch/Commit: 0100ac0

Reviewer: Markus Wageringel

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

[kwankyu]

comment:1

A related changed is

#21631 comment:23

At least I checked reverting to p_WTotaldegree solves the present problem. But there must have been some reason to have used p_WDegree.

[mwageringel]

comment:3

The reason for that change seems to be to fix the example in [#17254 comment:199] where a matrix ordering is used. Interestingly though, with current versions of Singular, the degree with a matrix ordering is not based on the first row of the matrix anymore:

sage: R.<x,y,z> = PolynomialRing(QQ, 3, order=TermOrder(matrix([3,0,1,1,1,0,1,0,0])))
sage: [a.degree() for a in R.gens()]
[3, 0, 1]
sage: [a._singular_().deg() for a in R.gens()]
[3, 0, 1]   # singular 3.1.7p1
[1, 1, 1]   # singular 4.1.1p2

Therefore, I think the degree function in Sage should be changed to return results consistent with Singular in case of matrix orderings. Based on this document, I replaced p_WDegree by p_FDeg, which fixes both examples here – though I am not completely certain this is the correct function to call.

I guess such a behavior change would need a deprecation period. How would one implement this in practice?

[mwageringel]

comment:4

Singular's deg function calls p_LDeg (source), so we should use that instead. This eliminates the need to explicitly loop over the monomials.

[kwankyu]

comment:5

I am quite certain that the best thing to do is to patch polynomial.pyx such that

cdef long singular_polynomial_deg(poly *p, poly *x, ring *r):
    ...
    if x == NULL:
        return p_WTotaldegree(p,r)

    cdef int i = 0
    ...

Note that the "loop" thing is not necessary. So this will speed up things.

But then we get

sage: R.<x,y,z> = PolynomialRing(QQ, 3, order=TermOrder(matrix([3,0,1,1,1,0,1,0,0])))
sage: [a.degree() for a in R.gens()]
[-3, 0, -1]
sage: [a._singular_().deg() for a in R.gens()]
[1, 1, 1]

I don't care the Singular degrees. They are p_Totaldegree (via p_FDeg via p_LDeg), as expected since Singular' deg function calls p_LDeg.

But the negative values above look strange. They are negative because the value OrdSgn is -1 for the ring. It means that the monomial ordering of R is not well-ordering. This is wrong! It is well-ordering since the first nonzero values of each column of the matrix is positive. So OrdSgn should be 1. I suspect that there is a bug somewhere in Sage or possibly in Singular. But I could not look deep into the Singular code to find the bug...

[kwankyu]

comment:6

Note that the "loop" thing is not necessary. So this will speed up things.

This is wrong. I forgot that the monomial ordering might be incompatible with degrees. Anyway, this part needs to be optimized as this would affect the overall performance of polynomial arithmetic of Sage...

[kwankyu]

comment:7

The bug in Singular about the wrong OrdSgn value was reported in

https://www.singular.uni-kl.de/forum/viewtopic.php?f=10&t=2899

[kwankyu]

Author: Kwankyu Lee

[kwankyu]

Branch: u/klee/28954

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Commit: b8f53f7

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

7ccd0d2

Use p_WTotalDegree for Sage degree

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from b8f53f7 to 7ccd0d2

[kwankyu]

comment:11

The branch modulo the fix in Singular part fixes the bug of this ticket.

I wish to remove the loop thing for the cases when the monomial ordering is compatible with the degrees, to speed up Sage polynomial arithmetic. But I don't know how to detect these cases, and this issue is for another ticket.

Perhaps we need to delay this ticket until the fix in Singular is available in Sage...

[kwankyu]

comment:12

@mwageringel:

I don't object to using p_LDeg if this is practically (that is, ignoring not-so-useful matrix orderings) consistent with the rest of Sage, as this has advantage in performance.

[mwageringel]

comment:13

Should we not add the upstream fix as a patch here? The regular upgrade of Singular might still take quite a while.

Replying to @kwankyu:

I don't object to using p_LDeg if this is practically (that is, ignoring not-so-useful matrix orderings) consistent with the rest of Sage, as this has advantage in performance.

This would be a practical thing to do, as it leaves it to Singular to provide an efficient implementation. Note that this only affects matrix orderings with zeros in the first row – if the entries in the first row are positive, these are returned as degrees as before.

(A potential downside of this is that it forces Singular's notion of degree upon Sage, whereas, if one ignores the Singular backend, Sage could have its own notion. In Macaulay2 for example, the notions of degree and weight are independent. For now, this seems fine though, as much of polynomial arithmetics in Sage is dictated by the Singular backend anyway.)

[kwankyu]

comment:14

Replying to @mwageringel:

Should we not add the upstream fix as a patch here? The regular upgrade of Singular might still take quite a while.

If we do not wait the regular upgrade of Singular, the upstream fix should go to the Singular package of Sage, as a patch (and be removed when the regular upgrade arrives). I guess this is not a good thing to do.

I don't object to using p_LDeg if this is practically (that is, ignoring not-so-useful matrix orderings) consistent with the rest of Sage, as this has advantage in performance.

This would be a practical thing to do, as it leaves it to Singular to provide an efficient implementation. Note that this only affects matrix orderings with zeros in the first row – if the entries in the first row are positive, these are returned as degrees as before.

After looking into the implementation of p_LDeg in Singular and some experiments, it seems that p_LDeg is not that faster than the loop thing with p_WTotaldegree as I expected initially.

Then I don't see any advantage of using p_LDeg while introducing a backward incompatible change in regard to matrix orderings.

I would prefer the present branch and bear with the bug until Singular gets the regular upgrade.

[kwankyu]

comment:15

After looking into the implementation of p_LDeg in Singular and some experiments, it seems that p_LDeg is not that faster than the loop thing with p_WTotaldegree as I expected initially.

This is wrong. I did more experiments.

sage: R.<x,y,z,w>=PolynomialRing(QQ,order=TermOrder('degrevlex'))
sage: [a.degree() for a in R.gens()]
[1, 1, 1, 1]
sage: f = (x - y*z - 2*z + w)^100
sage: f.degree()
200
sage: timeit('f.degree()')
125 loops, best of 3: 3.18 ms per loop

with p_WTotaldegree vs

sage: R.<x,y,z,w>=PolynomialRing(QQ,order=TermOrder('degrevlex'))
sage: [a.degree() for a in R.gens()]
[1, 1, 1, 1]
sage: f = (x - y*z - 2*z + w)^100
sage: f.degree()
200
sage: timeit('f.degree()')
125 loops, best of 3: 2.47 ms per loop

with p_LDeg

---

sage: R.<x,y,z,w>=PolynomialRing(QQ,order=TermOrder('lex'))
sage: [a.degree() for a in R.gens()]
[1, 1, 1, 1]
sage: f = (x - y*z - 2*z + w)^100
sage: f.degree()
200
sage: timeit('f.degree()')
125 loops, best of 3: 2.25 ms per loop

with p_WTotaldegree vs

sage: R.<x,y,z,w>=PolynomialRing(QQ,order=TermOrder('lex'))
sage: [a.degree() for a in R.gens()]
[1, 1, 1, 1]
sage: f = (x - y*z - 2*z + w)^100
sage: f.degree()
200
sage: timeit('f.degree()')
625 loops, best of 3: 777 μs per loop

with p_LDeg

---

sage: R.<x,y,z,w>=PolynomialRing(QQ,order=TermOrder('wdeglex',(1,2,3,4)))
sage: [a.degree() for a in R.gens()]
[1, 2, 3, 4]
sage: f = (x - y*z - 2*z + w)^100
sage: f.degree()
500
sage: timeit('f.degree()')
125 loops, best of 3: 3.88 ms per loop

with p_WTotaldegree vs

sage: R.<x,y,z,w>=PolynomialRing(QQ,order=TermOrder('wdeglex',(1,2,3,4)))
sage: [a.degree() for a in R.gens()]
[1, 2, 3, 4]
sage: f = (x - y*z - 2*z + w)^100
sage: f.degree()
500
sage: timeit('f.degree()')
125 loops, best of 3: 2.54 ms per loop

with p_LDeg

---

sage: R.<x,y,z,w>=PolynomialRing(QQ,order=TermOrder('deglex'))
sage: [a.degree() for a in R.gens()]
[1, 1, 1, 1]
sage: f = (x - y*z - 2*z + w)^100
sage: f.degree()
200
sage: timeit('f.degree()')
125 loops, best of 3: 3.81 ms per loop

with p_WTotaldegree vs

sage: R.<x,y,z,w>=PolynomialRing(QQ,order=TermOrder('deglex'))
sage: [a.degree() for a in R.gens()]
[1, 1, 1, 1]
sage: f = (x - y*z - 2*z + w)^100
sage: f.degree()
200
sage: timeit('f.degree()')
125 loops, best of 3: 2.75 ms per loop

with p_LDeg

---

sage: m = matrix(4,[4,3,2,1,1,0,0,0,0,1,0,0,0,0,1,0])
sage: m
[4 3 2 1]
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
sage: R.<x,y,z,w>=PolynomialRing(QQ,order=TermOrder(m))
sage: [a.degree() for a in R.gens()]
[4, 3, 2, 1]
sage: f = (x - y*z - 2*z + w)^100
sage: f.degree()
500
sage: timeit('f.degree()')
125 loops, best of 3: 2.84 ms per loop

with p_WTotaldegree vs

sage: m = matrix(4,[4,3,2,1,1,0,0,0,0,1,0,0,0,0,1,0])
sage: m
[4 3 2 1]
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
sage: R.<x,y,z,w>=PolynomialRing(QQ,order=TermOrder(m))
sage: [a.degree() for a in R.gens()]
[4, 3, 2, 1]
sage: f = (x - y*z - 2*z + w)^100
sage: f.degree()
500
sage: timeit('f.degree()')
125 loops, best of 3: 2.84 ms per loop

with p_LDeg

---

sage: m = matrix(2,[3,2,1,0])
sage: m
[3 2]
[1 0]
sage: R.<x,y,z,w>=PolynomialRing(QQ,order=TermOrder(m)+TermOrder(m))
sage: [a.degree() for a in R.gens()]
[3, 2, 3, 2]
sage: f = (x - y*z - 2*z + w)^100
sage: f.degree()
500
sage: timeit('f.degree()')
125 loops, best of 3: 3.17 ms per loop
sage: timeit('f.degree()')
125 loops, best of 3: 3.18 ms per loop

with p_WTotaldegree vs

sage: m = matrix(2,[3,2,1,0])
sage: m
[3 2]
[1 0]
sage: R.<x,y,z,w>=PolynomialRing(QQ,order=TermOrder(m)+TermOrder(m))
sage: [a.degree() for a in R.gens()]
[3, 2, 3, 2]
sage: f = (x - y*z - 2*z + w)^100
sage: f.degree()
500
sage: timeit('f.degree()')
125 loops, best of 3: 3.26 ms per loop
sage: timeit('f.degree()')
125 loops, best of 3: 3.28 ms per loop

with p_LDeg

---

sage: R.<x,y,z,w>=PolynomialRing(QQ,order=TermOrder('neglex'))
sage: [a.degree() for a in R.gens()]
[1, 1, 1, 1]
sage: f = (x - y*z - 2*z + w)^100
sage: f.degree()
200
sage: timeit('f.degree()')
125 loops, best of 3: 2.18 ms per loop

with p_WTotaldegree vs

sage: R.<x,y,z,w>=PolynomialRing(QQ,order=TermOrder('neglex'))
sage: [a.degree() for a in R.gens()]
[1, 1, 1, 1]
sage: f = (x - y*z - 2*z + w)^100
sage: f.degree()
200
sage: timeit('f.degree()')
625 loops, best of 3: 750 μs per loop

with p_LDeg

---

sage: m = matrix(4,[4,0,2,1,1,0,0,0,0,1,0,0,0,0,1,0])
sage: m
[4 0 2 1]
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
sage: R.<x,y,z,w>=PolynomialRing(QQ,order=TermOrder(m))
sage: [a.degree() for a in R.gens()]
[4, 0, 2, 1]
sage: f = (x - y*z - 2*z + w)^100
sage: f.degree()
400
sage: timeit('f.degree()')
125 loops, best of 3: 2.82 ms per loop
sage: timeit('f.degree()')
125 loops, best of 3: 2.78 ms per loop

with p_WTotaldegree vs

sage: m = matrix(4,[4,0,2,1,1,0,0,0,0,1,0,0,0,0,1,0])
sage: m
[4 0 2 1]
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
sage: R.<x,y,z,w>=PolynomialRing(QQ,order=TermOrder(m))
sage: [a.degree() for a in R.gens()]
[1, 1, 1, 1]
sage: f = (x - y*z - 2*z + w)^100
sage: f.degree()
200
sage: timeit('f.degree()')
625 loops, best of 3: 1.33 ms per loop
sage: timeit('f.degree()')
625 loops, best of 3: 1.37 ms per loop

with p_LDeg

---

sage: R.<x,y,z,w>=PolynomialRing(QQ,order=TermOrder('invlex'))
sage: [a.degree() for a in R.gens()]
[1, 1, 1, 1]
sage: f = (x - y*z - 2*z + w)^100
sage: f.degree()
200
sage: timeit('f.degree()')
125 loops, best of 3: 2.21 ms per loop

with p_WTotaldegree vs

sage: R.<x,y,z,w>=PolynomialRing(QQ,order=TermOrder('invlex'))
sage: [a.degree() for a in R.gens()]
[1, 1, 1, 1]
sage: f = (x - y*z - 2*z + w)^100
sage: f.degree()
200
sage: timeit('f.degree()')
625 loops, best of 3: 766 μs per loop

with p_LDeg

[kwankyu]

comment:16

I would prefer the present branch and bear with the bug until Singular gets the regular upgrade.

Now I prefer using `p_LDeg'!

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 7ccd0d2 to 896d628

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

896d628

Use p_LDeg for degree

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

06c2c54

Doctest fixes

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 896d628 to 06c2c54

[mwageringel]

comment:20

Replying to @kwankyu:

If we do not wait the regular upgrade of Singular, the upstream fix should go to the Singular package of Sage, as a patch (and be removed when the regular upgrade arrives). I guess this is not a good thing to do.

Ok, if we use p_LDeg, we do not actually need the upstream fix.

Could you add a doctest for the example in the ticket description, please? Also, I think we should keep one example of a matrix ordering with zeros in the first row, in order to document the fact that standard grading is now used in that case.

Finally, the imports p_Deg, p_Totaldegree, p_WTotaldegree, p_WDegree are not used anymore and could be removed.

Otherwise, this looks good to me. Thanks a lot for the comparisons and the fix.

[mwageringel]

Reviewer: Markus Wageringel

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

0100ac0

Fixes for reviewer comments

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 06c2c54 to 0100ac0

[kwankyu]

comment:22

Replying to @mwageringel:

Replying to @kwankyu:

If we do not wait the regular upgrade of Singular, the upstream fix should go to the Singular package of Sage, as a patch (and be removed when the regular upgrade arrives). I guess this is not a good thing to do.

Ok, if we use p_LDeg, we do not actually need the upstream fix.

Right.

Could you add a doctest for the example in the ticket description, please? Also, I think we should keep one example of a matrix ordering with zeros in the first row, in order to document the fact that standard grading is now used in that case.

Done.

Finally, the imports p_Deg, p_Totaldegree, p_WTotaldegree, p_WDegree are not used anymore and could be removed.

Done.

[mwageringel]

comment:23

Thank you.

[vbraun]

Changed branch from u/klee/28954 to 0100ac0