Opened 11 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 roed)

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)

powser-part1.patch (52.3 KB) - added by roed 11 years ago.
A patch of Craig that's applied before padicpoly.
padicpoly.patch (223.2 KB) - added by roed 11 years ago.
powser-part1.2.patch (52.3 KB) - added by roed 11 years ago.
A patch of Craig's needed for the rest to apply cleanly
trac_5075.patch (47.7 KB) - added by roed 11 years ago.
Fixes aimed at ticket 5075
padicpoly_outside.patch (23.3 KB) - added by roed 11 years ago.
Changes outside sage.rings.padics and sage.rings.polynomial.padics
padicpoly_ring_padic.patch (20.0 KB) - added by roed 11 years ago.
Changes in sage.rings.padics
padicpoly_new.patch (192.6 KB) - added by roed 11 years ago.
New files in sage.rings.polynomial.padics
padicpoly_update1.patch (193.5 KB) - added by roed 11 years ago.
Apply after other patches
6084_ALL.patch (422.9 KB) - added by roed 10 years ago.
Should apply against 4.3.2 and build; there are still doctest failures.
6084_1.patch (40.7 KB) - added by roed 9 years ago.
6084_2.patch (16.8 KB) - added by roed 9 years ago.
6084_3.patch (20.0 KB) - added by roed 9 years ago.
6084_4.patch (194.7 KB) - added by roed 9 years ago.
6084_5.patch (2.5 KB) - added by roed 9 years ago.
6084_6.patch (192.4 KB) - added by roed 9 years ago.
6084_7.patch (147.4 KB) - added by roed 9 years ago.
6084_8.patch (161.7 KB) - added by roed 9 years ago.
6084_9.patch (538 bytes) - added by roed 9 years ago.
6084_10.patch (21.0 KB) - added by roed 9 years ago.
6084_1.2.patch (41.2 KB) - added by roed 9 years ago.
Replaces 6084_1.patch
6084_2.2.patch (17.2 KB) - added by roed 9 years ago.
Replaces 6084_2.patch
6084_5.2.patch (2.8 KB) - added by roed 9 years ago.
Replaces 6084_5.patch
6084_6.2.patch (192.9 KB) - added by roed 9 years ago.
Replaces 6084_6.patch
6084_7.2.patch (148.0 KB) - added by roed 9 years ago.
Replaces 6084_7.patch
6084_8.2.patch (161.9 KB) - added by roed 9 years ago.
Replaces 6084_8.patch
6084_9.2.patch (756 bytes) - added by roed 9 years ago.
Replaces 6084_9.patch
6084_10.2.patch (21.3 KB) - added by roed 9 years ago.
Replaces 6084_10.patch
6084_ALL.2.patch (513.9 KB) - added by roed 9 years ago.
Collects all patches in the .2 revision. Only apply this patch

Change History (56)

comment:1 Changed 11 years ago by roed

  • 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 11 years ago by roed

A patch of Craig that's applied before padicpoly.

Changed 11 years ago by roed

Changed 11 years ago by roed

A patch of Craig's needed for the rest to apply cleanly

Changed 11 years ago by roed

Fixes aimed at ticket 5075

Changed 11 years ago by roed

Changes outside sage.rings.padics and sage.rings.polynomial.padics

Changed 11 years ago by roed

Changes in sage.rings.padics

Changed 11 years ago by roed

New files in sage.rings.polynomial.padics

comment:2 Changed 11 years ago by roed

  • Description modified (diff)

Changed 11 years ago by roed

Apply after other patches

comment:3 Changed 11 years ago by roed

  • Description modified (diff)

comment:4 Changed 10 years ago by AlexGhitza

David, is this ready for review now?

comment:5 Changed 10 years ago by mhansen

  • Report Upstream set to N/A

Ping. Any updates on this?

comment:6 Changed 10 years ago by roed

  • 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.

Changed 10 years ago by roed

Should apply against 4.3.2 and build; there are still doctest failures.

comment:7 Changed 9 years ago by wuthrich

Any news on this ? (Iam asking becasue of #8198 and #4656.)

comment:8 Changed 9 years ago by niles

  • Cc niles added

I eventually found this ticket after a bug hunt related to #9457. That patch changes power series comparison to use padded_list instead of list; I noticed that this patch (6084_ALL.patch) also makes changes to power series comparison, so maybe it makes sense to incorporate #9457 into this patch?

comment:9 Changed 9 years ago by wuthrich

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 9 years ago by roed

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: Changed 9 years ago by roed

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 9 years ago by niles

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 9 years ago by roed

Changed 9 years ago by roed

Changed 9 years ago by roed

Changed 9 years ago by roed

Changed 9 years ago by roed

Changed 9 years ago by roed

Changed 9 years ago by roed

Changed 9 years ago by roed

Changed 9 years ago by roed

Changed 9 years ago by roed

comment:13 follow-up: Changed 9 years ago by roed

  • 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 9 years ago by niles

  • Authors set to David Roe

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 9 years ago by niles

  • 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 9 years ago by roed

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:

  1. 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

(f0 + xn f1) (g0 + xn g1) = (f0 g0) + (f1 g1) x2n + ((f0 + f1)(g0 + g1) - f0 g0 - f1 g1)xn

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.

  1. 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.

Changed 9 years ago by roed

Replaces 6084_1.patch

Changed 9 years ago by roed

Replaces 6084_2.patch

Changed 9 years ago by roed

Replaces 6084_5.patch

Changed 9 years ago by roed

Replaces 6084_6.patch

Changed 9 years ago by roed

Replaces 6084_7.patch

Changed 9 years ago by roed

Replaces 6084_8.patch

Changed 9 years ago by roed

Replaces 6084_9.patch

Changed 9 years ago by roed

Replaces 6084_10.patch

Changed 9 years ago by roed

Collects all patches in the .2 revision. Only apply this patch

comment:17 Changed 9 years ago by roed

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 kedlaya

  • 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 saraedum

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 roed

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 saraedum

  • Summary changed from [needs work] Improved p-adic polynomials to Improved p-adic polynomials

comment:22 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:23 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:24 Changed 6 years ago by jpflori

  • Cc jpflori added

comment:25 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:26 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:27 Changed 4 years ago by saraedum

  • 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 vbraun

  • Resolution set to invalid
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.