Factoring padic polynomials

2190d0ee-e4da-4602-8835-8ea53fc1c317 commented 12 years ago

OM Tree construction and a native sage implementation of padic polynomial factoring using it. This factorization works for polynomials over Zp as well as over unramified and totally ramified extensions of Zp.

Depends on #15190 Depends on #14825 Depends on #20310

CC: @roed314 @pjbruin

Component: padics

Keywords: sd86.5, sd87, padicIMA

Work Issues: add to reference manual, improve arithmetic of FrameElt, FrameEltTerm (i.e., give them a parent)

Author: Brian Sinclair, Sebastian Pauli

Branch/Commit: u/roed/ticket/12561 @ 0e7f566

Reviewer: Julian Rüth

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

2190d0ee-e4da-4602-8835-8ea53fc1c317 commented 12 years ago

Attachment: 12561.patch.gz

saraedum commented 11 years ago

comment:1

On the wiki page about padic factoring it says that the implementation doesn't work correctly for some examples. Is there only a problem with some specific cases? I just tried a few products of low degree polynomials and the factorizations seemed ok.

I want to try to debug the code, so if you know of any simple examples for which it doesn't work, that would be helpful.

2190d0ee-e4da-4602-8835-8ea53fc1c317 commented 11 years ago

comment:2

Other than the poor state of documentation and polish, I cannot find any faults. I have run the code through all of the previously failed examples with no issue outside of occasionally having insufficient precision. The newton polygon code does not elegantly handle the infinite slope case (the case where the current phi actually divides Phi), but it doesn't have to for factoring since it can be (and is) caught earlier in the loop.

b97aefb0-77e6-484d-b5c5-96db38f6e875 commented 11 years ago

comment:3

Patch applies correctly on 7.5 and all doctests written so far pass. However:

In the doctest from pfactortree():

sage: from sage.rings.polynomial.padics.factor.factoring import jorder4,pfactortree 
sage: f = ZpFM(2,24,'terse')['x']( (x^32+16)*(x^32+16+2^16*x^2)+2^34 ) 
sage: pfactortree(f) # long (3.8s) 
[(1 + O(2^24))*x^64 + (65536 + O(2^24))*x^34 + (32 + O(2^24))*x^32 + (1048576 + O(2^24))*x^2 + (256 + O(2^24))]

This is just returning the polynomial unfactored, so demonstrably the factoring isn't working here. We should get:

sage: f = ZpFM(2,24,'terse')['x']( (x^32+16)*(x^32+16+2^16*x^2)+2^34 )
sage: f.factor()
((1 + O(2^24))*x^32 + (65536 + O(2^24))*x^2 + (16 + O(2^24))) * ((1 + O(2^24))*x^32 + (16 + O(2^24)))

Also, we should rework this code so that a sage Factorization object is returned, and that pfactortree is called by the .factor() method attached to p-adic polynomials.

roed314 commented 11 years ago

comment:4

Replying to @haikona:

Patch applies correctly on 7.5 and all doctests written so far pass. However:

In the doctest from pfactortree():
sage: from sage.rings.polynomial.padics.factor.factoring import jorder4,pfactortree 
sage: f = ZpFM(2,24,'terse')['x']( (x^32+16)*(x^32+16+2^16*x^2)+2^34 ) 
sage: pfactortree(f) # long (3.8s) 
[(1 + O(2^24))*x^64 + (65536 + O(2^24))*x^34 + (32 + O(2^24))*x^32 + (1048576 + O(2^24))*x^2 + (256 + O(2^24))] 
This is just returning the polynomial unfactored, so demonstrably the factoring isn't working here. We should get:
sage: f = ZpFM(2,24,'terse')['x']( (x^32+16)*(x^32+16+2^16*x^2)+2^34 )
sage: f.factor()
((1 + O(2^24))*x^32 + (65536 + O(2^24))*x^2 + (16 + O(2^24))) * ((1 + O(2^24))*x^32 + (16 + O(2^24)))
Also, we should rework this code so that a sage Factorization object is returned, and that pfactortree is called by the .factor() method attached to p-adic polynomials.

Note that increasing the precision yields a factorization:

sage: f = ZpFM(2,44,'terse')['x']( (x^32+16)*(x^32+16+2^16*x^2) + 2^34)
sage: pfactortree(f)
[(1 + O(2^44))*x^32 + (7242791239680 + O(2^44))*x^30 + (13194407968768 + O(2^44))*x^28 + (7902202888192 + O(2^44))*x^26 + (2147483648 + O(2^44))*x^24 + (442381107200 + O(2^44))*x^22 + (21474836480 + O(2^44))*x^20 + (6193337597952 + O(2^44))*x^18 + (240518168576 + O(2^44))*x^16 + (2405122965504 + O(2^44))*x^14 + (2886218022912 + O(2^44))*x^12 + (16766847680512 + O(2^44))*x^10 + (1099511627776 + O(2^44))*x^8 + (2190164885504 + O(2^44))*x^6 + (14293651161088 + O(2^44))*x^4 + (14178492350464 + O(2^44))*x^2 + (8796093022224 + O(2^44)),
 (1 + O(2^44))*x^32 + (10349394804736 + O(2^44))*x^30 + (8796093022208 + O(2^44))*x^28 + (5291936645120 + O(2^44))*x^26 + (17149804937216 + O(2^44))*x^22 + (11398848446464 + O(2^44))*x^18 + (15187063078912 + O(2^44))*x^14 + (825338363904 + O(2^44))*x^10 + (15402021158912 + O(2^44))*x^6 + (3413693759488 + O(2^44))*x^2 + (8797166764048 + O(2^44))]

In the case Simon pointed out, adding 2^34 doesn't do anything since the precision cap of the base ring is 24, so we have an actual example of a reducible polynomial being claimed to be irreducible.

saraedum commented 11 years ago

comment:5

The algorithm used in pfactortree only works for square-free polynomials, so I don't think this is a bug. Square-free decomposition doesn't work currently though, see #13439.

saraedum commented 11 years ago

comment:6

Oh wait. I looked at the wrong numbers sorry.

2190d0ee-e4da-4602-8835-8ea53fc1c317 commented 11 years ago

comment:8

Attachment: 12561.2.patch.gz

This new patch replaces the first and has a great deal of improvements, bug-fixes, and documentation. The examples should be more sensible now.

It should successfully factor monic, square-free, fixed-mod padic polynomials without fail.

I am running more tests to ensure its validity as well as implementing the transformations needed to handle non-monic cases, which would leave it only dependant on square-free decomposition.

saraedum commented 11 years ago

comment:9

Nice. I volunteer to review this once it is ready. On a first look, several methods still don't have docstrings (but you are probably aware of this).

jdemeyer commented 11 years ago

comment:10

Please be aware of #15422 (which fixes some bugs in Sage's factoring of non-squarefree p-adic polynomials).

roed314 commented 10 years ago

Dependencies: #15190

roed314 commented 10 years ago

Commit: f40ee7c

roed314 commented 10 years ago

Branch: u/roed/ticket/12561

2190d0ee-e4da-4602-8835-8ea53fc1c317 commented 10 years ago

Changed branch from u/roed/ticket/12561 to u/bsinclai/ticket/12561

roed314 commented 10 years ago

Changed branch from u/bsinclai/ticket/12561 to u/roed/ticket/12561

2190d0ee-e4da-4602-8835-8ea53fc1c317 commented 10 years ago

Changed branch from u/roed/ticket/12561 to u/bsinclai/ticket/12561

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from f40ee7c to e97aa08

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

e97aa08 Added check at FrameElt.polynomial to not allow negative exponents. Added example to FrameElt.residue.

roed314 commented 10 years ago

Changed branch from u/bsinclai/ticket/12561 to u/roed/ticket/12561

2190d0ee-e4da-4602-8835-8ea53fc1c317 commented 10 years ago

Changed branch from u/roed/ticket/12561 to u/bsinclai/ticket/12561

roed314 commented 10 years ago

Changed branch from u/bsinclai/ticket/12561 to u/roed/ticket/12561

2190d0ee-e4da-4602-8835-8ea53fc1c317 commented 10 years ago

Changed branch from u/roed/ticket/12561 to u/bsinclai/ticket/12561

2190d0ee-e4da-4602-8835-8ea53fc1c317 commented 10 years ago

New commits:

`f2e4f41`	`Adding a bit more documentation`
`2bf9723`	`Merge branch 'u/bsinclai/ticket/12561' of git://trac.sagemath.org/sage into ticket/12561`
`61d57ef`	`Adding more doctests, fixing trailing whitespace`
`60f5d9b`	`Miscellaneous style improvements, rewrite of _newton_polygon using monotone chain algorithm`
`6432e20`	`Changes to make sure types of slope, _exponent, Eplus, etc are consistent - int, Integer or Rational.`
`1d3f6c6`	`A few more changes related to variable types`
`0ec528d`	`Fix ignoring non-monics with all coefficients divisible by uniformizer. Fixes in FrameElt.`
`ab1540d`	`Merge branch 'u/bsinclai/ticket/12561' of git://trac.sagemath.org/sage into ticket/12561`
`e1bb657`	`Remove unneeded if-else statements in Frame.seed and Frame.find_psi. Fixed example in FrameElt.reduce.`

2190d0ee-e4da-4602-8835-8ea53fc1c317 commented 10 years ago

Changed commit from e97aa08 to e1bb657

jdemeyer commented 10 years ago

comment:21

Some comments (not planning to actually review this):

I would hope that this code works for all kinds of p-adic polynomials (over Zp, over Qp, over field extensions, all with different kinds of precision). Still, (almost) all examples in the doctests use ZpFM.
The factor() method doesn't actually use this code. What's the point then?
It would be good if this code would also support the factor_padic() method for polynomials over ZZ and QQ.
What happens if the assumption the the polynomial is squarefree doesn't hold?
Units in the Factorization should be put in the "unit" part, this is wrong:

sage: x = polygen(ZpFM(2,10))
sage: pfactor(3*x)[1]
(1 + 2 + O(2^10), 1)

Similarly, the primes should actually be primes, this should have a factor 2 with multiplicity 2:

sage: x = polygen(ZpFM(2,10))
sage: pfactor(4*x)[1]
(2^2 + O(2^10), 1)

jdemeyer commented 10 years ago

comment:22

The new code also seems slower than the factor() which is already in Sage (at least when #15654 is applied).

sage: x = polygen(ZpFM(3,50))
sage: pol = (x-1)^100 + x
sage: %time F1=factor(pol)
CPU times: user 0.68 s, sys: 0.00 s, total: 0.68 s
Wall time: 0.68 s
sage: %time F2=pfactor(pol)
CPU times: user 2.17 s, sys: 0.01 s, total: 2.18 s
Wall time: 2.16 s

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from e1bb657 to 7f250da

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

7f250da Fix unit part of factorization and factoring polynomials divisible by x.

roed314 commented 10 years ago

comment:25

Replying to @jdemeyer:

The new code also seems slower than the factor() which is already in Sage (at least when #15654 is applied).

It hasn't been optimized, so I'm hoping that these timings will improve (currently, a lot of time is spent in initialization of various objects that can be reduced).

roed314 commented 7 years ago

Changed branch from u/bsinclai/ticket/12561 to u/roed/ticket/12561

saraedum commented 7 years ago

Changed keywords from none to sd86.5

saraedum commented 7 years ago

Changed commit from 7f250da to 001088d

saraedum commented 7 years ago

New commits:

001088d Merge branch 'develop' into t/12561/ticket/12561

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from 001088d to 6fdd537

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

6fdd537 Fix broken import

roed314 commented 7 years ago

Changed keywords from sd86.5 to sd86.5, sd87

2190d0ee-e4da-4602-8835-8ea53fc1c317 commented 7 years ago

Changed dependencies from #15190 to #15190, #14825, #20310

2190d0ee-e4da-4602-8835-8ea53fc1c317 commented 7 years ago

Changed commit from 6fdd537 to 4df99a1

2190d0ee-e4da-4602-8835-8ea53fc1c317 commented 7 years ago

Last 10 new commits:

`ac44f7c`	`Merge branch 'u/roed/change_precision' of git://trac.sagemath.org/sage into develop`
`4c49226`	Working on deprecating list and `__getitem__` for p-adic elements
`4088f9b`	`Fixing doctest errors, changes to ZZ_pX p-adic types`
`24ee4ff`	`Fixing doctest errors due to switching from list to expansion`
`cbfeb34`	`Making behavior of teichmuller_expansion uniform across precision types, adding doctests`
`f5e2440`	`Fix 'x'->'var' typo in some docstrings, add polynomial method to ntl p-adic types`
`779ddb8`	`Remove added NOTES: in CR_template`
`985a23a`	`amend documentation of ccoefficients`
`cab0c9e`	`Merge branch 'u/saraedum/polynomial_representation_of_a_padic_number' of git://trac.sagemath.org/sage into develop`
`4df99a1`	`Created OMTree class, moved files from factor/ to omtree/, updated documentation, added access functions.`

2190d0ee-e4da-4602-8835-8ea53fc1c317 commented 7 years ago

Changed branch from u/roed/ticket/12561 to u/bsinclai/ticket/12561

2190d0ee-e4da-4602-8835-8ea53fc1c317 commented 7 years ago

Description changed:

--- 
+++ 
@@ -1 +1 @@
-A native sage implementation of padic polynomial factoring
+OM Tree construction and a native sage implementation of padic polynomial factoring using it.  This factorization works for polynomials over Zp as well as over unramified and totally ramified extensions of Zp.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from 4df99a1 to f699d63

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`dad389b`	`Merge branch 'u/bsinclai/ticket/12561' of git://trac.sagemath.org/sage into develop`
`f699d63`	`Fixed from-import lines made incorrect by the move from factor/ to omtree/`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Changed commit from f699d63 to 195abcc

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

195abcc Brought doctest coverage to 100%

saraedum commented 7 years ago

Changed branch from u/bsinclai/ticket/12561 to u/saraedum/ticket/12561

saraedum commented 7 years ago

Reviewer: Julian Rüth

saraedum commented 7 years ago

Last 10 new commits:

`8081eab`	`added doctests after fixing conflicts`
`063b58c`	`Merge branch 'develop' into t/20073/ticket/20073`
`48be601`	`Added documentation to verify that the extension has the right defining polynomial`
`921af5e`	`Changing modulus and defining_polynomial to use an exact keyword`
`39043f1`	`Merge branch 't/23331/allow_exact_defining_polynomials_for_p_adic_extensions' into t/20310/change_precision`
`77779ea`	`minor docstring changes`
`6e2495f`	`Merge branch 't/23331/allow_exact_defining_polynomials_for_p_adic_extensions' into t/20310/change_precision`
`7428353`	`minor docstring fixes`
`998b3c1`	`Merge branch 't/20310/change_precision' into t/12561/ticket/12561`
`8c171f9`	`remove conflict markers`

saraedum commented 7 years ago

Changed commit from 195abcc to 8c171f9

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 7 years ago

Branch pushed to git repo; I updated commit sha1. New commits:

`9a519ea`	`improve documentation`
`81ab3a8`	`Remove __cmp__`
`7366625`	`Implement __hash__`
`45dfd22`	`improve documentation`
`0af8e52`	`Added some high level documentation for associated factors`
`bd15d71`	`add exact keyword`
`9d01c94`	`Merge branch 't/23331/allow_exact_defining_polynomials_for_p_adic_extensions' into t/12561/ticket/12561`
`9ca7f24`	`fix doctest`

sagemath / sage

Factoring padic polynomials #12561