Opened 10 years ago

Closed 9 years ago

#11847 closed enhancement (fixed)

unexpexted behavior of degree() with matrix ordering

Reported by: john_perry Owned by: malb
Priority: major Milestone: sage-4.8
Component: commutative algebra Keywords: degree, polynomial, singular
Cc: SimonKing, klee, mderickx Merged in: sage-4.8.alpha3
Authors: John Perry Reviewers: Martin Albrecht
Report Upstream: None of the above - read trac for reasoning. Work issues:
Branch: Commit:
Dependencies: sage 4.7.2 Stopgaps:

Status badges

Description

Singular assumes the standard grading when predefined orderings such as lex and degrevlex are given, but infers a grading of a ring from the first row of a specified matrix ordering. This can confuse users (and has confused some developers!) who expect to work in a standard grading, and will not expect this behavior:

sage: R.<x,y,z> = PolynomialRing(QQ,'x',3,order=TermOrder(matrix([3,0,1,1,1,0,1,0,0])))
sage: (x^2*y).degree()
6
sage: x.degree()
3
sage: x.degree(x)
1

This confusion is compounded by the fact that the term degree carries different meanings, depending on the context (degree wrt grading, degree wrt exponents, degree of a monomial, degree of a variable).

Sage has an exponents() command that behaves somewhat closer to what a user unfamiliar with graded rings might expect:

sage: (x^2*y).exponents()
[(2,1,0)]

The documentation should inform users of this behavior. It would also be nice to add a function that computes the total degree wrt the standard grading for the user.

Attachments (1)

trac11847_distinguish_ungraded_totaldegree.patch (3.9 KB) - added by john_perry 9 years ago.

Download all attachments as: .zip

Change History (20)

comment:1 Changed 10 years ago by john_perry

  • Authors set to john_perry
  • Cc malb removed
  • Dependencies set to sage 4.7.2
  • Status changed from new to needs_review

comment:2 Changed 10 years ago by john_perry

This patch adds a note and a test to degree() to inform the user of the behavior. It also adds a new function, total_degree_ungraded(), which returns the total degree without respect to a grading. Doctests pass for me on sage 4.7.2alpha2.

This patch and should perhaps include more, but I thought it best to see what others thought.

PS: I removed malb from cc: after noticing that he was made the owner. So I suspect he is being notified anyway. I'm not real sure how notifications work, or who should be cc'd; I thought that everyone who commented on this topic in sage-devel should get some notification, and I knew Martin had worked on this code, too. Sorry if some of you are getting unwanted spam. :-(

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

Two cooments:

I don't see natural use cases for total_degree_ungraded() when one use non-default grading with a polynomial ring. If one need such a method for (I think) a very rare case, s/he can define it just for the case. The name is also confusing.

On the other hand, exponent(x) method, which Maarten suggested, would be useful and essential. Moreover you can make exponent() to return the sum of all exponents of the variables in the monomial, making total_degree_ungraded() redundant. Like degree() method, if exponent(x) or exponent() method is applied for a polynomial rather than a monomial, then the highest of the values for all monomials may be returned.

comment:4 in reply to: ↑ 3 Changed 10 years ago by john_perry

Replying to klee:

I don't see natural use cases for total_degree_ungraded() when one use non-default grading with a polynomial ring.

I discovered the problem when the grading changed while working with a matrix term ordering. It appears whenever one uses a matrix ordering, and total_degree() is not an uncommon tool.

The name is also confusing.

One goal was that the user find it easily when performing tab-completion, and would see that there are two different notions of total degree in play, prompting her or him to read the docstring. With that in mind, I aimed for a name that would be clear. It slipped from my mind that the ring is never ungraded, so I agree that this is a very, very bad name.

I had toyed with total_degree_exponents() as well. I could see exponent_total_degree(), but thought that harder for a user to find using tab-completion.

On the other hand, exponent(x) method, which Maarten suggested, would be useful and essential.

Actually, I suggested that name. :-) Maarten didn't suggest a particular name, but that there should be a different set of functions for ungraded degree. I originally set out to do as you suggest, but as I thought about it, several considerations presented themselves:

  1. The method degree(x) already exists, and does the same.
  2. It seems unwise to deprecate degree(x), which is probably used in a lot of code by a lot of people. (I've used it a lot, anyway.)
  3. The patch could leave degree(x) alone, and introduce exponent(x) (or whatever name) which merely replicates the behavior. I'm not opposed to that, but I wanted someone else's input first. I recall there was discussion of a similar duplication of methods in linear algebra some years ago (see e.g. eigenvectors_right and right_eigenvectors).
  4. I'd prefer to change degree() to behave as if the ring had the standard grading, and define degree_in_grading() (or something similar) to behave the way Singular defines it. Again, that could have an impact on how people have already been using degree() in code.

These thoughts prompted me to start with an incremental patch initially, which could be modified according to comments.

Moreover you can make exponent() to return the sum of all exponents of the variables in the monomial, making total_degree_ungraded() redundant.

That would be confusing to me; I've never seen total degree referred to as exponent. I would prefer a different name if we take that route, such as exponent_total_degree() or total_degree_exponents(). Or even something clearer.

comment:5 Changed 10 years ago by klee

I would never change the behavior of degree(),degrees(),total_degree(), which should return the standard things as Simon said, except of course bug fixes.

For exponent(), exponents(), total_exponents(), I would expect

sage: f=x^3+x*y+1
sage: f.exponent(x)
[3,1,1]
sage: f.exponents()
[(3,0),(1,1),(0,0)]
sage: f.total_exponent()
[3,2,0]
sage: f.exponent()
[3,2,0]
sage: g=x*y
sage: g.exponent(x) % convenient behavior for a monomial
1
sage: g.exponents()
(1,1)
sage: g.total_exponent()
2
sage: g.exponent()
2

Then even in a polynomial ring with the default grading, the two sets of methods will play different roles.

I would object names mixing "degree" and "exponent" in any way.

comment:6 follow-up: Changed 10 years ago by mderickx

We could also add a keyword "use_grading" to the degree methods.

Note that whathever we do, we should not do the combination of:

sage: f.exponent(x)
[3,1,1]
sage: g.exponent(x) % convenient behavior for a monomial
1

Such a function will be very hard to use since this behaviour will make you write ugly code like:

deg = f.exponent()
if f.is_monomial():
    do_something(f)
else:
    do_something_else(f)

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

Replying to mderickx:

We could also add a keyword "use_grading" to the degree methods.

Simon would think the "use_grading" keyword redundant because degree methods must always use grading. Perhaps keyword "use_default_grading" is more sensible. Anyway, using a long keyword is an overkill.

Note that whathever we do, we should not do the combination of:

sage: f.exponent(x)
[3,1,1]
sage: g.exponent(x) % convenient behavior for a monomial
1

Such a function will be very hard to use since this behaviour will make you write ugly code like:

deg = f.exponent()
if f.is_monomial():
    do_something(f)
else:
    do_something_else(f)

I think degee methods are for polynomials while exponent methods are for monomials. So it should be more convenient to use exponent methods with monomials. It would even be reasonable to raise an error if f is not a monomial in f.exponents(), though I admit the current behavior

sage: f=x^3+x*y
sage: f.exponents()
[(3,0),(1,1)]

is surely a convenient extension, if used carefully.

comment:8 in reply to: ↑ 7 ; follow-up: Changed 10 years ago by john_perry

Replying to klee:

Replying to mderickx:

We could also add a keyword "use_grading" to the degree methods.

Simon would think the "use_grading" keyword redundant because degree methods must always use grading. Perhaps keyword "use_default_grading" is more sensible. Anyway, using a long keyword is an overkill.

Using a keyword is a great idea. What about calling it standard_grading or (if that's too long) std_grading? For reasons of compatibility, the default would be False; when True, it uses the standard grading to compute degree() and total_degree().

OTOH I could see setting the default to True and raising a deprecation warning, since matrix orderings haven't been in Sage for very long. (Have they?) But that seems dicier.

I think degee methods are for polynomials while exponent methods are for monomials.

There's a strong case to be made for using monomials (efficiency, for example) but I also think that's a separate discussion, for a separate ticket. AFAIK Singular doesn't distinguish the two.

So it should be more convenient to use exponent methods with monomials. It would even be reasonable to raise an error if f is not a monomial in f.exponents()...

I would prefer not to deprecate old ways of doing things unless they were actually wrong or demonstrably dangerous. I don't think that's the case here, but maybe I'm wrong.

comment:9 in reply to: ↑ 8 Changed 10 years ago by john_perry

Replying to john_perry:

There's a strong case to be made for using monomials (efficiency, for example) but I also think that's a separate discussion, for a separate ticket.

I forgot to say: I also think monomials should be a separate class, not part of multi_polynomial_libsingular, in no small part because Singular doesn't distinguish the two.

comment:10 Changed 10 years ago by john_perry

I've attached a patch that implements this with a keyword (std_grading). The total_degree_exponents() method has disappeared, and degree() also accepts the keyword.

comment:11 Changed 10 years ago by john_perry

Whoops -- I had forgotten to refresh the mercurial queue... new patch in a second.

comment:12 Changed 9 years ago by john_perry

*bump* any chance of a review?

comment:13 Changed 9 years ago by malb

  • Status changed from needs_review to needs_work

I have trouble applying this patch to 4.8.alpha1:

Hunk #1 succeeded at 2414 with fuzz 2 (offset 191 lines).
Hunk #4 FAILED at 2260
Hunk #5 succeeded at 2466 with fuzz 2 (offset 191 lines).
Hunk #6 FAILED at 2306
2 out of 6 hunks FAILED -- saving rejects to file sage/rings/polynomial/multi_polynomial_libsingular.pyx.rej
patch failed, unable to continue (try -v)
patch failed, rejects left in working dir
errors during apply, please fix and refresh trac11847_distinguish_ungraded_totaldegree.patch

I think the implementation is fine (i.e., I read the patch) so for me all that is needed is to check the formalities (applies, tests pass, docs look okay, etc.)

Changed 9 years ago by john_perry

comment:14 Changed 9 years ago by john_perry

  • Status changed from needs_work to needs_review

I was unaware that 4.8.alpha1 was out... have to pay better attention to sage-devel.

New patch works on my installation of 4.8.alpha1. Thanks!

comment:15 Changed 9 years ago by malb

  • Authors changed from john_perry to John Perry
  • Reviewers set to Martin Albrecht
  • Status changed from needs_review to positive_review

applies cleanly && doctests pass && reads good.

comment:16 follow-up: Changed 9 years ago by jdemeyer

What is there to be reported upstream?

comment:17 in reply to: ↑ 16 ; follow-up: Changed 9 years ago by john_perry

  • Report Upstream changed from Not yet reported upstream; Will do shortly. to None of the above - read trac for reasoning.

Replying to jdemeyer:

What is there to be reported upstream?

IIRC, I checked that box only because Simon had mentioned that someone could discuss this behavior with the Singular developers at the then-upcoming Sage days; see the discussion at

http://groups.google.com/group/sage-devel/browse_thread/thread/fc6959dc18d6cda1/

I don't know if anyone actually talked about it with them, though -- Simon didn't seem perturbed. As far as I can tell, the bug (if any) was in our documentation, not theirs. Given that this assertion was controversial, I classified this as "an enhancement".

If you think it's okay, I'd prefer removing the "report upstream", and change it to "None of the above; see trac for reasoning". I've done that already, so change it back if you think that's inappropriate.

comment:18 in reply to: ↑ 17 Changed 9 years ago by SimonKing

Hi John and Jeroen,

Replying to john_perry:

Replying to jdemeyer:

What is there to be reported upstream?

IIRC, I checked that box only because Simon had mentioned that someone could discuss this behavior with the Singular developers at the then-upcoming Sage days;

Yes, and I did talk with people there. So, it is reported upstream. If I remember correctly, the Singular folks somehow agreed that it would be nice to have, but on the other hand it didn't seem easy to them to implement it, given their data structure.

So, I don't think that if it will soon be fixed/enhanced/whatever in upstream.

comment:19 Changed 9 years ago by jdemeyer

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