Improved p-adic polynomials

[roed314]

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.

CC: @nilesjohnson @kedlaya @jpflori

Component: padics

Author: David Roe

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

[roed314]

A patch of Craig that's applied before padicpoly.

[roed314]

Attachment: powser-part1.patch.gz

Attachment: padicpoly.patch.gz

[roed314]

Attachment: powser-part1.2.patch.gz

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

[roed314]

Attachment: trac_5075.patch.gz

Fixes aimed at ticket 5075

[roed314]

Attachment: padicpoly_outside.patch.gz

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

[roed314]

Attachment: padicpoly_ring_padic.patch.gz

Changes in sage.rings.padics

[roed314]

Attachment: padicpoly_new.patch.gz

New files in sage.rings.polynomial.padics

[roed314]

Apply after other patches

[roed314]

comment:3

Attachment: padicpoly_update1.patch.gz

[aghitza]

comment:4

David, is this ready for review now?

[mwhansen]

comment:5

Ping. Any updates on this?

[roed314]

comment:6

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.

[roed314]

Attachment: 6084_ALL.patch.gz

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

[chriswuthrich]

comment:7

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

[nilesjohnson]

comment:8

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?

[chriswuthrich]

comment:9

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.

[roed314]

comment:10

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.

[roed314]

comment:11

I'm getting started on this. Let me know if you want to help review it once I get it back in shape.

[roed314]

comment:16

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

(f₀ + xⁿ f₁) (g₀ + xⁿ g₁) = (f₀ g₀) + (f₁ g₁) x²ⁿ + ((f₀ + f₁)(g₀ + g₁) - f₀ g₀ - f₁ g₁)xⁿ

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.

[roed314]

Attachment: 6084_1.2.patch.gz

Replaces 6084_1.patch

[roed314]

Attachment: 6084_2.2.patch.gz

Replaces 6084_2.patch

[roed314]

Replaces 6084_5.patch

[roed314]

Attachment: 6084_5.2.patch.gz

Replaces 6084_6.patch

[roed314]

Attachment: 6084_6.2.patch.gz

Attachment: 6084_7.2.patch.gz

Replaces 6084_7.patch

[roed314]

Attachment: 6084_8.2.patch.gz

Replaces 6084_8.patch

[roed314]

Replaces 6084_9.patch

[roed314]

Attachment: 6084_9.2.patch.gz

Replaces 6084_10.patch

[roed314]

Attachment: 6084_10.2.patch.gz

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

[roed314]

comment:17

Attachment: 6084_ALL.2.patch.gz

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.

[kedlaya]

comment:18

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

[saraedum]

comment:19

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?

[roed314]

comment:20

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.

[saraedum]

comment:27

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.