Adding a weighted_degree function to Singular multivariate polynomials

[johanrosenkilde]

Multivariate polynomials over the Singular interface have several degree methods but not a weighted_degree function, often used in certain branches of discrete mathematics. This should be implemented.

CC: @novoselt

Component: algebraic geometry

Keywords: multivariate polynomials, degree, Singular

Author: Johan Sebastian Rosenkilde Nielsen, Luis Felipe Tabera Alonso

Branch: c48dab6

Reviewer: Marshall Hampton, John Perry

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

[johanrosenkilde]

comment:1

I have implemented the best I could easily do. I am sure that by utilising Singular, one can make a much faster implementation of weighted_degree; indeed, as far as I could gather, Singular has weighted degree functionality as part of the deg()-function, but I don't have the prerequisites for writing this code.

The patch I have uploaded uses Sage methods to iterate through all monomials of the polynomial, calculating each one's weighted degree, and selects the maximal of these.

[johanrosenkilde]

Straight-forward all-Sage implementation (not using Singular).

[johanrosenkilde]

comment:3

Attachment: trac_10716_adding_weighted_degree.patch.gz

I just uploaded a new patch which makes it possible not to specify the weights in a tuple. That was pretty silly with the old patch, where you would have to write something like

  Q.weighted_degree((1, 2))

Now you can omit the double-parenthesis, but also use the previous calls:

  Q.weighted_degree(1, 2)
  Q.weighted_degree((1, 2))
  Q.weighted_degree({x:1, y:2})

[5d2aaf09-c963-473a-bf79-1f742a72700f]

comment:4

In the docstring, instead of "INPUT::" it should be "INPUT:". The double colon indicates a literal block, which isn't what you want there. I changed this and one other instance of "INPUT::", which is in the attached cumulative patch. I think you (jsm) can give this a positive review if it looks OK.

[5d2aaf09-c963-473a-bf79-1f742a72700f]

Reviewer: Marshall Hampton

[5d2aaf09-c963-473a-bf79-1f742a72700f]

Cumulative patch with minor docstring fixes.

[5d2aaf09-c963-473a-bf79-1f742a72700f]

Description changed:

--- 
+++ 
@@ -1 +1,5 @@
 Multivariate polynomials over the Singular interface have several degree methods but not a weighted_degree function, often used in certain branches of discrete mathematics. This should be implemented.
+
+**Apply**
+1. [attachment: trac_10716_adding_weighted_degree_v2.patch](https://github.com/sagemath/sage-prod/files/10652000/trac_10716_adding_weighted_degree_v2.patch.gz)
+

[5d2aaf09-c963-473a-bf79-1f742a72700f]

comment:6

Attachment: trac_10716_adding_weighted_degree_v2.patch.gz

[malb]

comment:7

It seems the patchbot got confused by the apply command.

[malb]

Description changed:

--- 
+++ 
@@ -1,5 +1,4 @@
 Multivariate polynomials over the Singular interface have several degree methods but not a weighted_degree function, often used in certain branches of discrete mathematics. This should be implemented.

-**Apply**
-1. [attachment: trac_10716_adding_weighted_degree_v2.patch](https://github.com/sagemath/sage-prod/files/10652000/trac_10716_adding_weighted_degree_v2.patch.gz)
+**Apply** [attachment: trac_10716_adding_weighted_degree_v2.patch](https://github.com/sagemath/sage-prod/files/10652000/trac_10716_adding_weighted_degree_v2.patch.gz)

[johanrosenkilde]

comment:8

Replying to @sagetrac-mhampton:

In the docstring, instead of "INPUT::" it should be "INPUT:". The double colon indicates a literal block, which isn't what you want there. I changed this and one other instance of "INPUT::", which is in the attached cumulative patch. I think you (jsm) can give this a positive review if it looks OK.

Ah, ok, thanks. It looks fine. If the less-than-perfect performance can be tolerated until someone more Singular-savvy comes along, is the ticket then accepted? Related to that, sage-devel never agreed to a systematic way of marking TODOs (which could be used here), right?

[johnperry-math]

comment:9

Is there a reason you convert everything to vectors & use a dot_product? Seeing the concerns about performance -- is type conversion less expensive than calling prod() or something similar? I don't know about Cython, but my impression is that in some languages it would be more efficient to assume you have an iterable & just iterate.

FWIW, this functionality is available in Sage 4.7:

sage: R.<x,y,z> = GF(7)[]
sage: p = x^3 + y + x*z^2
sage: p.degree()
3
sage: P = PolynomialRing(GF(7),'x,y,z',
....: order=TermOrder(matrix([1,4,2,1,1,0,1,0,0])))
sage: q = P(p)
sage: q.degree()
4

The relevant code is in sage/libs/singular/polynomial.pyx, where singular_polynomial_deg manually changes the ring of p if it isn't equal to ring it has at first.

[11d1fc49-71a1-44e1-869f-76be013245a0]

comment:10

Apply trac_10716_adding_weighted_degree_v2.patch

(for the patchbot)

[lftabera]

comment:11

You should also add the same function to MPolynomial_polydict, so it is available to more general polynomial rings.

I will take a look to see if we can easily use libsingular here.

[lftabera]

Alternative patch

[lftabera]

comment:12

Attachment: trac_10716_adding_weighted_degree_alternative.patch.gz

I propose an alternative patch. It implements the weighted degree for all MPolynomial, not just Singular ones. It is also faster than the original patch. I think that, in general, it is better to use a polynomial ring with weighted degree if one is really interested so I have added a hint in the documentation.

[lftabera]

Description changed:

--- 
+++ 
@@ -1,4 +1,4 @@
 Multivariate polynomials over the Singular interface have several degree methods but not a weighted_degree function, often used in certain branches of discrete mathematics. This should be implemented.

-**Apply** [attachment: trac_10716_adding_weighted_degree_v2.patch](https://github.com/sagemath/sage-prod/files/10652000/trac_10716_adding_weighted_degree_v2.patch.gz)
+**Apply** [attachment: trac_10716_adding_weighted_degree_alternative.patch](https://github.com/sagemath/sage-prod/files/10652001/trac_10716_adding_weighted_degree_alternative.patch.gz)

[lftabera]

Changed author from Johan S. R. Nielsen to Johan S. R. Nielsen, Luis Felipe Tabera Alonso

[lftabera]

comment:14

Apply trac_10716_adding_weighted_degree_alternative.patch

[lftabera]

comment:18

Move my alternative patch to a git branch

---

New commits:

1036282

Adding a weighted_degree function to Singular multivariate polynomials

[lftabera]

Branch: u/lftabera/weighted_degree

[lftabera]

Description changed:

--- 
+++ 
@@ -1,4 +1,2 @@
 Multivariate polynomials over the Singular interface have several degree methods but not a weighted_degree function, often used in certain branches of discrete mathematics. This should be implemented.

-**Apply** [attachment: trac_10716_adding_weighted_degree_alternative.patch](https://github.com/sagemath/sage-prod/files/10652001/trac_10716_adding_weighted_degree_alternative.patch.gz)
-

[lftabera]

Commit: 1036282

[malb]

comment:19

if self.is_zero():
  #Corner case, note that the degree of zero is a python int
  return -1

Why not fix the bug?

weigths = map(int, weights)

Why int and not ZZ?

cdef int deg = -1
cdef int n = self.parent().ngens()
cdef int i, l

This is sets you up for integer overflows, why not avoid them by using ZZ? The function is going to be slow in any case.

Also, doesn't Singular have an internal function which would allow to calculate this?

[lftabera]

comment:20

I would not say that zero.degree() == -1 is a bug, but a feature.

The use of ints instead of ZZ is just for compatibility with the current degree method. In both MPolynomial_libsingular and MPolynomial_polydict polynomials the degree returns an int.

This method is intended for casual computations with weighted degree or with several weighted degrees at one. If the user is going to use heavy computations with the same weight on a Singular ring, it is better to set up a ring with the appropiated weighted degree as term order. This would use Singular internal method.

I should check, but if I recall correctly, to use Singular inner function one has the change the degree of the underlying ring, which is bad. Moreover, this patch also work for MPolynomial_polydict, not only rings mapped to Singular.

[malb]

comment:21

Replying to @lftabera:

I would not say that zero.degree() == -1 is a bug, but a feature.

I meant that it is returned as a Python int.

The use of ints instead of ZZ is just for compatibility with the current degree method. In both MPolynomial_libsingular and MPolynomial_polydict polynomials the degree returns an int.

MPolynomial_libsingular can only represent a total degree < INT_MAX, as far as I recall. Hence, using int there is fine. However, this function accepts a weights array which may contain arbitrary integers. Hence, this function can overflow, where MPolynomial_libsingular.total_degree() cannot (as far as I can tell).

[lftabera]

comment:22

I see your point. Should we allow negative or rational weights also?

[malb]

comment:23

If this question was directed at me, I never used weighted degrees, so I wouldn't know. Doesn't seem to cost much to add it, though (?)

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

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

a695d7d

Use Integer instead of int to avoid overflows

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

Changed commit from 1036282 to a695d7d

[johnperry-math]

comment:25

Replying to @sagetrac-git:

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

a695d7d

Use Integer instead of int to avoid overflows

Is "weights" supposed to be misspelled as "weigths"? Notice that this is a change from an earlier spelling.

Also, Singular doesn't accepted anything larger than 32-bit integers (confirmed w/Singular developer the other day). Will this change be practically useful?

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

Changed commit from a695d7d to 3155491

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

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

3155491

Corrected typo #10716

[lftabera]

comment:27

Thanks for catch the typo, I had a hard time finding it! Added a test that shows it was indeed a bug.

This patch is intended for arbitrary polynomials, I am not aware non-Singular degrees that admits such large exponents, bur someone might want to create one. Even if the degree of the polynomial is smaller than 32-bit the weighted degree might be.

I have not a strong opinion on this issue and taking an int would probably be safe for most users.

---

New commits:

3155491

Corrected typo #10716

[johnperry-math]

comment:28

Replying to @lftabera:

This patch is intended for arbitrary polynomials, I am not aware non-Singular degrees that admits such large exponents, bur someone might want to create one.

I do, actually. My current solution is to used marked polynomials instead.

Even if the degree of the polynomial is smaller than 32-bit the weighted degree might be.

That's true, but if I recall correctly, Singular won't work even then, because it assigns a weight to every monomial. You can have a sufficiently small weighted ordering, but with large exponents it will choke.

I have not a strong opinion on this issue and taking an int would probably be safe for most users.

My main concern is the performance penalty of converting from Integer to int. If it's just a one-time penalty (when creating a ring) then I wouldn't worry about it myself. But if it occurs with the creation of every polynomial, let alone every monomial, that could introduce a penalty for algorithms that create & manipulate polynomials. I think it's just the one-time penalty, but I don't actually know.

[lftabera]

comment:29

The conversion is the other way around, from int to Integer. You are right that there is a performance penalty. I do not have the numbers at hand right now but I will look at it and check if there is a more clever way.

The method is not cached in any way, the degree is computed any time that the method is called.

If the user want to use a ring that is mapped to singular as is worried about performance, because it will call the method a lot of times or over huge polynomials, the recommendation in the documentation is to create a ring with that term order and then just call degree inside that ring. It will be orders of magnitude faster. That is, this method is intended to use for a weighted degree different from the one in the base ring.

I have found further problems with the patch:

The patch is intended to work over every multivariate polynomial ring out there. But generic multivariate rings do not have an as_Etuple option in the exponents method. This means that the exponents are ETuples by default and I cannot use as_ETuple. This will impose a performance penalty greater than the int to Integer conversion.

The degree in generic multivariate rings do not return the weighted degree. This is a bug in my opinion. Because it makes sage non consistent. This is for another ticket.

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

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

811b796

Ticket: 10716

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

Changed commit from 3155491 to 811b796

[lftabera]

comment:31

I managed to use as_ETuples=False in any case. Concerning the performance, I have made some not serious test:

2 variables, 5 terms

• int: 2.38 µs
• Integer: 4.26 µs

5 variables, 20 terms

• int: 16 µs
• Integer: 25.8 µs

30 variables, ~80000 terms

• int: 208 ms
• Integer: 350 ms

I think it is reasonable for such a generic method.

[johnperry-math]

comment:32

Replying to @lftabera:

Concerning the performance, I have made some not serious test:

A penalty factor of ~1.7: what test did you perform?

[lftabera]

comment:33

I created another method substitutying the Integer with int. Then used the following code. To get an idea.

sage: K1=QQ['x,y']
sage: K2=PolynomialRing(QQ,'a',5)
sage: K3=PolynomialRing(QQ,'b',30)
sage: f=K1.random_element()
sage: g=K2.random_element(degree=10,terms=24)
sage: h=K3.random_element(degree=100,terms=10**5) #quite long time
sage: vf=random_vector(ZZ,2)
sage: vg=random_vector(ZZ,20)
sage: vh=random_vector(ZZ,30)
sage: %timeit f.weighted_degree(vf)
sage: %timeit f.weighted_degree_int(vf)
sage: %timeit g.weighted_degree(vg)
sage: %timeit g.weighted_degree_int(vg)
sage: %timeit h.weighted_degree(vh)
sage: %timeit h.weighted_degree(vh)

I do not have a strong opinion. Integer does not overflow, but int is faster (but also slow) and behaves like degree method (also returns int).

[johnperry-math]

comment:34

Replying to @lftabera:

I created another method substitutying the Integer with int. Then used the following code. To get an idea.

Can you test addition & multiplication of polynomials? That's the one that concerns me. It probably won't matter, but...

[lftabera]

comment:35

Do you mean comparing the cost of weighted_degree with addition/multiplication? That depends a lot on the underlying ring. Do you have a specific ring in mind?

This patch will have absolutely not impact on addition and mult. I expect that addition can be in fact faster that weighted degree for "nice" rings and multiplication will be much slower.

[johnperry-math]

comment:36

Replying to @lftabera:

Do you mean comparing the cost of weighted_degree with addition/multiplication?

I mean comparing the cost of, say, addition in a ring with Integer weighted orders vs. addition in a ring with int weighted orders. Use the same polynomials in the same base field. Then try with multiplication.

I have no particular ring in mind; I'm curious about all the "usual" rings: QQ[x], F_p[x], etc.

I expect that addition can be in fact faster that weighted degree for "nice" rings and multiplication will be much slower.

Why?

[lftabera]

comment:37

This patch will have no effect on that. There are no rings with int weighted order or Integer weighted order.

When you create a multivariate polynomial ring, you select a TermOrder, with degrevlex as default.

However, in some cases, a user may want to compute the degree of a polynomial with a weighted term order that is different from the term order of the underlying ring. In this, and only in this case the weighted_degree method will play a role. In QQ['x,y'] and GF(p)['x,y'] singular will be used, so for usual operations of addition and multiplication will use the singular implementation of term orders. This patch will not change that.

sage: K=PolynomialRing(QQ, 'a,b,c', order=TermOrder('wdeglex',(7,8,9)))
sage: a,b,c=K.gens()
sage: f = a+b**3+c**4
sage: f.degree() # uses the weights of K, it is singular who compute this.
36
sage: f.weighted_degree([7,8,9]) #My patch, not computed using singular.
36
sage: f.weighted_degree([1,3,-3]) #My patch, not computed using singular.
9
sage: #The term order of the underlying ring does not change.
sage: f.parent().term_order()
Weighted degree lexicographic term order with weights (7, 8, 9)

[johnperry-math]

comment:38

Replying to @lftabera:

However, in some cases, a user may want to compute the degree of a polynomial with a weighted term order that is different from the term order of the underlying ring.

Right. I get that. I didn't realize how weighted_degree was being used. I get that now.

I'll like to review this, but I haven't taken the time to work out the new development system. I'll try to figure out git & give this a careful review within the next few days. If nothing happens by next week, remind me.

[lftabera]

comment:39

Thanks!

[johnperry-math]

comment:41

Sorry it took so long; no one reminded me. ;-)

I've tested it, & everything seems to be in order. I just need to look over the source code.

So, now that we're on this new-fangled git system, How do I see the actual diff? The attachments don't show the most recent changes. When I click on the branch, it shows 1593 lines removed from src/sage/rings/polynomial/multi_polynomial.pyx, and 29 changes to src/sage/rings/polynomial/multi_polynomial_element.py. None of them involves weighted_degree(), & in fact the things removed from the first file look frightening. I'm guessing that branch has changed? But when I look at the source code in sage (f.weighted_degree()??) it looks fine.

[novoselt]

comment:42

If you click on commits, they look more sensible. Perhaps you need to merge this branch with the current devel to make things look better? Or, when everything else fails, you have to ask Volker ;-)

[johnperry-math]

comment:43

Replying to @novoselt:

If you click on commits, they look more sensible.

Not at first, but eventually :-) After that, the highlighted box is very appealing to click on, but doesn't give information. You have to click on completely plain text to get a diff.

But even that isn't right. The diff I get is a diff from previous work on this ticket, not from pre-ticket source. Is it possible to see the cumulative result of all the changes, just as we used to recommend on simpler tickets that someone combine all the tickets into one?

Perhaps you need to merge this branch with the current devel to make things look better?

I don't even know what that means. :-( I just did a sage -dev checkout --ticket 10716.