Opened 10 years ago
Closed 4 years ago
#6084 closed enhancement (invalid)
Improved p-adic polynomials
Reported by: | roed | Owned by: | roed |
---|---|---|---|
Priority: | major | Milestone: | sage-duplicate/invalid/wontfix |
Component: | padics | Keywords: | |
Cc: | niles, kedlaya, jpflori | Merged in: | |
Authors: | David Roe | Reviewers: | |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
A reimplementation of p-adic polynomials in Cython with many different ways for handling precision. Needed for more generic p-adic rings and fields and factoring of p-adic polynomials
Should apply cleanly and build against sage-4.7.
Attachments (28)
Change History (56)
comment:1 Changed 10 years ago by
- Component changed from algebra to padics
- Milestone set to sage-4.0.2
- Owner changed from tbd to roed
- Type changed from defect to enhancement
Changed 10 years ago by
Changed 10 years ago by
comment:2 Changed 10 years ago by
- Description modified (diff)
comment:3 Changed 10 years ago by
- Description modified (diff)
comment:4 Changed 10 years ago by
David, is this ready for review now?
comment:6 Changed 10 years ago by
- Summary changed from Improved p-adic polynomials to [needs work] Improved p-adic polynomials
Yep. I started working on this again a week and a half ago. I'm currently fixing bugs and bringing it up to 100% doctests. I hope to have a version ready to review soon.
comment:7 Changed 9 years ago by
comment:8 Changed 9 years ago by
- Cc niles added
comment:9 Changed 8 years ago by
It is such a shame that this has frozen a year ago. There is a lot of good work here and I am sure it would solve quite a few problems in other tickets.
comment:10 Changed 8 years ago by
I know. I was just thinking the same thing after seeing the discussion at #10698. It's nice to know that p-adic polynomials are getting used, but also sad that this bug is causing so much problems.
Unfortunately, my thesis is due in a little over a month, so I cannot work on this right now. I know it's difficult to pick up someone else's work, but the code is mostly done; it mainly needs doctests and fixes to any problems that they reveal. If someone wants to take this on, let me know: I can make sure you have the latest patches and let you know what needs doing.
comment:11 follow-up: ↓ 12 Changed 8 years ago by
I'm getting started on this. Let me know if you want to help review it once I get it back in shape.
comment:12 in reply to: ↑ 11 Changed 8 years ago by
Replying to roed:
I'm getting started on this.
Great!
Let me know if you want to help review it once I get it back in shape.
Indeed, I'd be happy to help :)
Changed 8 years ago by
Changed 8 years ago by
Changed 8 years ago by
Changed 8 years ago by
Changed 8 years ago by
Changed 8 years ago by
Changed 8 years ago by
Changed 8 years ago by
Changed 8 years ago by
Changed 8 years ago by
comment:13 follow-up: ↓ 14 Changed 8 years ago by
- Description modified (diff)
Alright. Let's try this again.
Apply 6084_1.patch, 6084_2.patch, 6084_3.patch, 6084_4.patch, 6084_5.patch, 6084_6.patch, 6084_7.patch, 6084_8.patch, 6084_9.patch, 6084_10.patch. I'm happy to merge them, but I wanted them to be viewable on trac.
Not all doctests work yet, but I wanted to get this posted so that people could play with it and give me feedback. I'd like to succeed this time in getting it into Sage.
comment:14 in reply to: ↑ 13 Changed 8 years ago by
Replying to roed:
Great! The patches do all apply and build on 4.7, but there are errors when starting sage:
--------------------------------------------------------------------------- TypeError Traceback (most recent call last) /home/niles/sage/local/lib/python2.6/site-packages/IPython/ipmaker.pyc in force_import(modname) 64 reload(sys.modules[modname]) 65 else: ---> 66 __import__(modname) 67 68 ... /home/niles/sage/local/lib/python2.6/site-packages/sage/rings/polynomial/polynomial_element.so in sage.rings.polynomial.polynomial_element.Polynomial._repr_ (sage/rings/polynomial/polynomial_element.c:14010)() /home/niles/sage/local/lib/python2.6/site-packages/sage/rings/polynomial/polynomial_element.so in sage.rings.polynomial.polynomial_element.Polynomial._repr (sage/rings/polynomial/polynomial_element.c:13276)() /home/niles/sage/local/lib/python2.6/site-packages/sage/rings/polynomial/polynomial_element.so in sage.rings.polynomial.polynomial_element.Polynomial._top_nonzero_power (sage/rings/polynomial/polynomial_element.c:17586)() TypeError: degree() takes no arguments (1 given) Error importing ipy_profile_sage - perhaps you should run %upgrade? WARNING: Loading of ipy_profile_sage failed. sage:
Also, there are a number of failures on 4.7.1.alpha2 so this will have to be rebased.
comment:15 Changed 8 years ago by
- Status changed from new to needs_info
I think to get this reviewed, some additional organization will be useful -- here's what I would suggest:
- Give us an introductory description of what this patch accomplishes: What are the "many different ways of handling precision"? Why was this needed? What had to be done? What are the main ideas of your implementation?
- Presumably the patch has been broken into some conceptual pieces -- it would be useful if you could explain what these are, so that they can be reviewed somewhat independently if possible.
- I would suggest versioning each separate patch piece (since they will surely need to be updated), so a naming scheme like
6084_1.n.patch
.
- An always-up-to-date
6084_ALL.patch
will make for easy downloading and applying (but viewing the separate pieces on trac is very useful for me)
- Any other ways you can think to break the review down into distinct pieces will be much appreciated
comment:16 Changed 8 years ago by
I will build a copy of 4.7.1.alpha2 overnight and port the patches to there.
The key idea of this patch is that a polynomial over Zp should not be stored as a list of coefficients, but instead as an element of ZZ[x], together with some sort of precision object that records the precision to which each coefficient is known. There are two main benefits of this approach:
- One can use fast algorithms for things like polynomial multiplication, rather than being forced back on naive multiplication due to a desire to preserve precision. For example, Karatsuba multiplication uses the identity
(f_{0} + x^{n} f_{1}) (g_{0} + x^{n} g_{1}) = (f_{0} g_{0}) + (f_{1} g_{1}) x^{2n} + ((f_{0} + f_{1})(g_{0} + g_{1}) - f_{0} g_{0} - f_{1} g_{1})x^{n}
This can lose precision over the naive definition since there are more additions than needed. But if one computes an approximation over ZZ and then determines precision separately, one can use Karatsuba or FFT algorithms at will.
- If one wants to use different methods for tracking precision (see below), the separation makes the implementation more modular and thus easier to implement and maintain.
These patches implement two kinds of polynomials: an anchored polynomial type which stores an approximation (in ZZ[x] for example) and a precision object, and a floating polynomial type which stores a common power of p for all the coefficients together with an anchored polynomial (thus allowing polynomials over Qp).
There are three kinds of precision defined so far:
- Flat precision. The precision of every entry is just a constant value n. This is certainly the fastest option, and frequently is perfectly adequate.
- Jagged precision. Each coefficient has its own precision, subject only to the precision cap of the base ring. This is mainly for backward compatibility, but might also be useful in generating functions (maybe?).
- Newton precision. The Newton polygon of the polynomial and of the precision are stored. This is the default precision type, since it provides a compromise between the previous two types, and having precision above the Newton polygon is useless for evaluating the polynomial anyway.
I'll write more about the contents of the individual patches and some more of the contents tomorrow morning.
comment:17 Changed 8 years ago by
Should apply against 4.7.1.alpha4. One can apply only 6084_ALL.2.patch, with the rest existing so that one can view code on trac.
The breakdown into patches is not the best, but here's a description. Patch 1: Some changes to polynomials and power series to allow leading terms that are indistinguishable from 0. Patch 2: Original changes outside both sage.rings.padics and sage.rings.polynomial. Patch 3: Changes to sage.rings.padics Patch 4: The new code in sage.rings.polynomial Patch 5: A small change to polynomial_ring_constructor to allow arbitrary kwds to be passed on to polynomial ring init methods. Patch 6: First update, bugfixes Patch 7: Second update, bugfixes Patch 8: Third update, bugfixes Patch 9: Fourth update, bugfixes Patch 10: Removing an ill-advised attempt to use fmpz_montgomery types to speed up computations for polynomials over Zp with p odd.
If reviewers would like, I can split up the ALL patch into more reasonable chunks. Suggestions are welcome. Bugs still remain, which I will continue to hunt down.
comment:18 Changed 8 years ago by
- Cc kedlaya added
It would be even better to split the patch over several tickets, which could then be reviewed, merged, and closed separately (this may also help with bug tracking). For instance, Patch 1 could perhaps go in independently, and would probably resolve a number of other outstanding tickets which point back here (e.g., with polynomials over power series rings).
comment:19 Changed 7 years ago by
What is the status of these patches? The ticket still says "needs work" but it seems you split the patch up as requested. So should it be "needs review"?
Can this be made into several tickets somehow? It's quite frightening to see a patch that says "HTML preview not available, since the file size exceeds 262144 bytes." ;) Anyway, I could try to split it up, just give me some hints where to start.
Is this independent of #12555? Which one should be reviewed/merged first?
comment:20 Changed 7 years ago by
I've kinda given up on this ticket and am attempting to make the changes in smaller pieces elsewhere. Feel free to raid it for changes. #12555 is a much higher priority for me: help on that would be much appreciated! Once the templating code there gets in, I think the changes in this ticket will be easier to make.
comment:21 Changed 7 years ago by
- Summary changed from [needs work] Improved p-adic polynomials to Improved p-adic polynomials
comment:22 Changed 6 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:23 Changed 5 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:24 Changed 5 years ago by
- Cc jpflori added
comment:25 Changed 5 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:26 Changed 5 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:27 Changed 4 years ago by
- Milestone changed from sage-6.4 to sage-duplicate/invalid/wontfix
- Status changed from needs_info to positive_review
I believe this ticket can be closed. Some of the patches here are still useful but it is clear that this can never be merged as is.
comment:28 Changed 4 years ago by
- Resolution set to invalid
- Status changed from positive_review to closed
A patch of Craig that's applied before padicpoly.