Opened 7 years ago
Closed 7 years ago
#14826 closed enhancement (fixed)
Newton polygons
Reported by: | caruso | Owned by: | roed |
---|---|---|---|
Priority: | major | Milestone: | sage-5.12 |
Component: | padics | Keywords: | Newton polygons |
Cc: | Merged in: | sage-5.12.beta3 | |
Authors: | Xavier Caruso | Reviewers: | Volker Braun |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #14987 | Stopgaps: |
Description (last modified by )
This patch implements basic functions on Newton polygons.
A small demo is available here: https://cethop.math.cnrs.fr:8443/home/pub/5/
Apply only trac_14826_newton_polygons.patch
Attachments (3)
Change History (32)
comment:1 Changed 7 years ago by
- Status changed from new to needs_review
comment:2 follow-up: ↓ 3 Changed 7 years ago by
comment:3 in reply to: ↑ 2 Changed 7 years ago by
Replying to vbraun:
There might be a better place that does not require another global name, maybe as method of local fields? At the very least the
NewtonPolygon
docstring should make an effort to disambiguate.
If there is some risk of confusion, the best is probably to remove the import of the constructor NewtonPolygon
. Indeed, as you say, these Newton polygons are mainly used for polynomials or series over padics (see tickets #14828 and #14830) and the user is definitely supposed to write f.newton_polygon()
if f
is such a polynomial or a series and not to construct a Newton polygon by himself.
A less scary way than
_normalize()
to compute the hull is to use some of Sage's existing polyhedral computation facilities:
I wonder if it makes sense to derive the class NewtonPolygon
(provided by this patch) from Polyhedron_QQ
.
There are obviously similarities (Newton polygons are polyhedrons in Q^{2}) but also differences (the sum of two Newton polygons are their convex hull, the product of two Newton polygons are their Minkowski sum).
What is your opinion?
Docstrings frequently need
INPUT
/OUTPUT
, see the sage developer manualPEP 8 spacing, e.g.
def __le__(self,other): # no def __le__(self, other): # yes
ParentNewtonPolygon.__repr__
should be_repr_
NewtonPolygon_lastslope._repr_
docstring has unused import
Thanks. I will fix it.
comment:4 Changed 7 years ago by
If your aim is to construct newton polygons from polynomials over local fields anyways then I would just make it a method there.
Inheriting from Polyhedron
would give you a lot of undesirable methods, so I would probably use composition over inheritance (than is, have a self._polyhedron
attribute instead of superclass). Though at the end of the day both ways would work.
comment:5 Changed 7 years ago by
Ok. Revised version posted...
comment:6 Changed 7 years ago by
- Status changed from needs_review to needs_work
I like this implementation much more than redoing everything from scratch (as is done in #6084).
- Not all functions have doctests or even documentation.
- There are doctest failures (click on the yellow blob at the top of this page to see them)
comment:8 Changed 7 years ago by
The function last_slope on lines 230 - 241 doesn't have input and output blocks, or an example block.
comment:10 Changed 7 years ago by
nice and useful code!
after testing a bit myself I only found one possible issue:
self._lastslope has not necessarily been set when it is used on line 602 resulting in bug in plot()
sage:NP=NewtonPolygon([(0,0),(1,0)],last_slope=2) sage:NP.plot()
there are also some unimportant typos like:
line 85: explicitly mentioned line 90: greater than or equal to line 272: is infinite line 351: are the union of those line 614: image of this
I hope this is useful, I'm currently at the SAGE days in Leiden and using this as practice
comment:11 follow-up: ↓ 12 Changed 7 years ago by
Try the @cached_method
decorator instead of caching manually.
The docstrings should start with a short (ideally one-line) description
def vertices(self, copy=True): """ Return the vertices of the Newton polytope. INPUT: ...
Are you going to add a method to polynomaials or is that going to be in a future ticket?
You should run the testsuite for parents and elements somewhere in your code (see http://www.sagemath.org/doc/reference/misc/sage/misc/sage_unittest.html#sage.misc.sage_unittest.TestSuite)
comment:12 in reply to: ↑ 11 Changed 7 years ago by
- Status changed from needs_review to needs_info
Replying to vbraun:
Are you going to add a method to polynomaials or is that going to be in a future ticket?
See ticket #14828
You should run the testsuite for parents and elements somewhere in your code
Hmm. In order to make this testsuite work, it seems that I need to put ParentNewtonPolygon?
in a category and I don't know which one is appropriate. Do you have a suggestion?
comment:13 follow-up: ↓ 14 Changed 7 years ago by
Is sage/categories/polyhedra.py
appropriate? If not, skip the categories test.
comment:14 in reply to: ↑ 13 Changed 7 years ago by
Replying to vbraun:
Is
sage/categories/polyhedra.py
appropriate?
I tried this. But the test fails because the elements (which are instances of NewtonPolygon_element
) are not instances of PolyhedralSets
and I do not really want to derive from this class.
If not, skip the categories test.
I can skip the category test, but it is also included in the elements tests. So, should I skip both?
comment:15 follow-up: ↓ 16 Changed 7 years ago by
Since you are deriving from RingElement your category should probably be Rings
. Does that work?
comment:16 in reply to: ↑ 15 Changed 7 years ago by
Replying to vbraun:
Since you are deriving from RingElement your category should probably be
Rings
. Does that work?
It should. Nevertheless, I just realized that the set of Newton polygons is not a ring but just a semiring (there is no additive inverse).
The category of semirings exists in sage (it seems that it is only used for the parent NN
) but there is apparently no generic class for elements in semirings. So, I don't know what I am supposed to do:
- should I implement a generic class for element in semirings (in
sage.structure.elements
) - can I derive my class from
RingElement
and raise an error in the_neg_
function? - something else...
comment:17 Changed 7 years ago by
There are two ways for your elements get an __add__
method: Either they inherit it from RingElement
or your category is (a refinement of) AdditiveMagmas
. If you don't want to have a ring (no __neg__
method) then you have to go the latter route. Just derive from Element
and initialize your category to
from sage.categories.all import Magmas, AdditiveMagmas category = (Magmas(), AdditiveMagmas()) super(...).__init__(..., category=category)
This is roughly how the polyhedra work, except they define a new category as the join.
comment:18 Changed 7 years ago by
Thanks!
I've tried to review my patch following your answer but I got a problem: it seems that the specials functions +
and *
are not catched correctly by the category framework (although it works for __add__
and __mul__
).
As far as I understand, the reason is that the method Element.__getattr__
is not called in these cases (and, as a consequence, the methods in category().element_class
are not examined).
I don't know if it is supposed to be a bug; if it is, I can open a new ticket about it.
In the attached patch, I've implemented a dirty hack (cf. lines 195-198) to get around this problem and make additions and multiplications of Newton polygons work correctly.
comment:19 Changed 7 years ago by
- Dependencies set to #14987
comment:20 Changed 7 years ago by
You must never use the bare element class (NewtonPolygon_class
in your case). Always use parent.element_class
sage: from sage.combinat.newton_polygon import * sage: NewtonPolygon_element <class 'sage.combinat.newton_polygon.NewtonPolygon_element'> sage: ParentNewtonPolygon().element_class <class 'sage.combinat.newton_polygon.ParentNewtonPolygon_with_category.element_class'>
My patch fixes that, and _add_
is now called the way it is supposed to.
Various docstrings need to be formatted according to http://www.sagemath.org/doc/developer/conventions.html#docstring-markup-with-rest-and-sphinx
Also, you need to get to 100% coverage:
$ sage -coverage sage/combinat/newton_polygon.py ------------------------------------------------------------------------ SCORE sage/combinat/newton_polygon.py: 82.6% (19 of 23) Missing documentation: * line 656: def _an_element_(self) Missing doctests: * line 488: def plot(self, **kwargs) * line 650: def _repr_(self) * line 659: def _element_constructor_(self, arg, sort_slopes=True, last_slope=Infinity) ------------------------------------------------------------------------
I would put the file in sage/geometry
instead of sage/combinat
.
comment:21 Changed 7 years ago by
- Description modified (diff)
- Status changed from needs_info to needs_review
Thanks a lot for your message (and your patience).
I fold the two patches (yours and mine), moved the file in sage/geometry
and completed doctests.
comment:22 Changed 7 years ago by
Can you double-check the docstrings? I see a couple that aren't typeset correctly. E.g.
- polyhedron -- a polyhedron defining the Newton polygon # no - ``polyhedron`` -- a polyhedron defining the Newton polygon # yes - repetition -- a boolean (default: True) # no - ``repetition`` -- a boolean (default: ``True``) # yes Returns ``self`` dilated by `exp` # no Returns ``self`` dilated by ``exp`` # yes
You can implement the comparison operators much easier via
def __cmp__(self, other): c = cmp(type(self), type(other)) if c != 0: return c return cmp(self._polyhedron, other._polyhedron)
though doing it the hard way is also acceptable.
comment:23 Changed 7 years ago by
- Description modified (diff)
comment:24 Changed 7 years ago by
I've posted a revised patch.
Concerning comparison, I'm not sure I can use the __cmp__
construction because the natural order on Newton polygons is not total (and I've read that - I don't remember where presently - that __cmp__
is only used to implement total order). Am I wrong?
For the bot: apply trac_14826_newton_polygons.patch
Changed 7 years ago by
comment:25 follow-up: ↓ 26 Changed 7 years ago by
Comparison deviates slightly in Sage vs. Python, especially for equality testing. If you don't have a total order then sort()
will have undefined behavior. But apart from that there is nothing wrong with it. The Element
base class already implements __cmp__
, so you can only override it but not get rid of it.
Did you upload the right patch? I get doctest failures in _test_prod
comment:26 in reply to: ↑ 25 Changed 7 years ago by
comment:27 Changed 7 years ago by
- Reviewers set to Volker Braun
Thanks, forgot about that. Patch looks good to me.
comment:28 Changed 7 years ago by
- Status changed from needs_review to positive_review
comment:29 Changed 7 years ago by
- Merged in set to sage-5.12.beta3
- Resolution set to fixed
- Status changed from positive_review to closed
That is of course not the same Newton polygon as
There might be a better place that does not require another global name, maybe as method of local fields? At the very least the
NewtonPolygon
docstring should make an effort to disambiguate.A less scary way than
_normalize()
to compute the hull is to use some of Sage's existing polyhedral computation facilities:Docstrings frequently need
INPUT
/OUTPUT
, see the sage developer manualPEP 8 spacing, e.g.
ParentNewtonPolygon.__repr__
should be_repr_
NewtonPolygon_lastslope._repr_
docstring has unused import