search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.44k stars 480 forks source link

Generic factorization algorithms for polynomials over field extensions and similar constructions #15513

Open nthiery opened 10 years ago

nthiery commented 10 years ago

Implement generic (univariate?) polynomial factorization algorithms over ground fields obtained through standard constructions.

Rationale: factorization is a fundamental building block of computer algebra. Students and colleagues are stumbling over this over on this missing feature while playing with not so exotic fields built from standard ones.

Here is for example a translation in Sage of my old favorite demo in MuPAD illustrating constructions and generic algorithms:

    sage: Qx.<x> = QQ[]
    sage: Qxz.<z> = Qx.fraction_field()[]
    sage: F.<z> = Qxz.quo(z^2-x)
    sage: P.<u> = F[]
    sage: z*u   * z
    x*u
    sage: (u^2 - x^3).factor()     # Should return (u + x z) (u - x z)
    *NotImplementedError*

TODO: review the literature, what's already implemented, and what could be; provide examples in each case. Split the ticket as appropriate.

Factorization over a transcendental extension F(x)

Assuming one can factor (univariate) polynomials over F, implement factorization for (univariate) polynomials over F(z).

Factorization over an algebraic extension F(a)

Assuming one can factor (univariate) polynomials over F, implement factorization for (univariate) polynomials over F(a).

Taken from the MuPAD library:

  faclib::algfactor(a,flag) factors the polynomial a in F(alpha)[z]
  or tests it for irreducibility only, depending on flag 

  Input: a is a bivariate polynomial in z and alpha, 
         flag: TRUE or FALSE
  Output: if flag <> FALSE then list of factors of a
          if flag is FALSE then TRUE if a is irreducible
                FALSE if a is reducible

  Reference: Geddes et al, Algorithms for Computer Algebra, algorithm
  AlgebraicFactorization page 383

Factorization over polynomial rings F[...]

    sage: K.<x0,x1> = QQ[]
    sage: R.<x> = K[]
    sage: factor(x^2 - (x0+x1)*x)
    NotImplementedError

Special case: bivariate polynomials

  factorization of bivariate polynomials over a field F
             or of univariate polynomials over F[y]

  The algorithm implemented in faclib::FACTOR is based on Hensel lifting
  and short vector computation. It works for the factorization of an
  univariate polynomial over F[y][x] over any ring y. 
  Reference: von zur Gathen, Hensel and Newton Methods in Valuation Rings, Math.Comp.
        166(1984), pp. 637-661.
  The complexity is O(n^6 m^2 + n log q) operations in F_q when
  F=F_q, and where n = deg(f,x) and m = deg(f,y).

Some old data points

For the record, there has been progress lately, with factorization implemented in more situations. Here are examples that used to fail with Sage 5.8 and work with Sage 6.4:

    sage: Px.<x> = QQ[]
    sage: Qx = Px.fraction_field()
    sage: Qxz = Qx['z']
    sage: z = Qxz.gen()
    sage: (z^2-x).factor()

CC: @defeo

Component: factorization

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

nthiery commented 10 years ago

Description changed:

--- 
+++ 
@@ -35,8 +35,24 @@
 factor(f);
                       (u + x z) (u - x z)

-This ought to work in Sage too, but it fails because Sage can't test -the primality of z^2-x below: +This ought to work in Sage too: + +```

jdemeyer commented 10 years ago

Replying to @nthiery:

Sage is still missing a generic implementation of factorization that would work over any (reasonable) field.

This issue is way too general. I think it fails bullet points 2 and 4 of http://www.sagemath.org/doc/developer/trac.html#guidelines-for-opening-tickets

nthiery commented 10 years ago

Description changed:

--- 
+++ 
@@ -12,7 +12,9 @@
 sage: factor(p)

-We might want this to work too: +Update: with Sage 6.4 this actually works now! + +We might want this to work too (it does not yet):

 sage: K = QQ['x0,x1']
@@ -42,17 +44,17 @@
     sage: x = Qx.gen()
     sage: Qxz = Qx['z']
     sage: z = Qxz.gen()
-    sage: F = Qxz.extension(z^2-x, 'z')
+    sage: F = Qxz.quo(z^2-x)   # or Qx.extension(z^2-x, 'z')
     sage: z = F.gen()
     sage: P = F['u']
     sage: u = P.gen()
     sage: (u*z) * z
     x*u
     sage: (u^2 - x^3).factor()
-    *bang*
+    *NotImplementedError*

-This fails because Sage can't test the primality of z^2-x: +This used to fail because Sage could not test the primality of z^2-x:

 sage: Px.<x> = QQ[]
@@ -63,13 +65,13 @@
 ---------------------------------------------------------------------------
 NotImplementedError                       Traceback (most recent call last)

- -So the algebraic extension is not recognized as giving a field: +and the algebraic extension was not recognized as giving a field:

-sage: F = Qxz.quo(z^2-x)
 sage: F in Fields()

+This still fails, for some reason. + Having a factorization over generic fields should do the job.

nthiery commented 10 years ago
comment:8

Replying to @jdemeyer:

Replying to @nthiery:

Sage is still missing a generic implementation of factorization that would work over any (reasonable) field.

This issue is way too general. I think it fails bullet points 2 and 4 of http://www.sagemath.org/doc/developer/trac.html#guidelines-for-opening-tickets

Why too general? It asks for a very specific feature: having a default generic implementation of multivariate polynomials over (reasonably computable) fields. There exists algorithms for this, e.g. implemented in MuPAD.

jdemeyer commented 10 years ago
comment:9

Please remove the working examples from the ticket description such that it's more clear what you actually want.

jdemeyer commented 10 years ago

Description changed:

--- 
+++ 
@@ -1,18 +1,6 @@
 Factorization is a fundamental building block of computer algebra, yet Sage is
 still missing a generic implementation of factorization that would
 work over any (reasonable) field. Students and colleagues are stumbling over this over and over.
-
-For example, the following currently raise NotImplementedError:
-
-```
-sage: K = QQ['x0,x1'].fraction_field()
-sage: x0,x1 = K.gens()
-sage: x = K['x'].gen()
-sage: p = x^2 - (x0+x1)*x
-sage: factor(p)
-```
-
-*Update:* with Sage 6.4 this actually works now!

 We might want this to work too (it does not yet):
jdemeyer commented 10 years ago

Description changed:

--- 
+++ 
@@ -5,11 +5,9 @@
 We might want this to work too (it does not yet):

-sage: K = QQ['x0,x1'] -sage: x0,x1 = K.gens() -sage: x = K['x'].gen() -sage: p = x^2 - (x0+x1)x -sage: factor(p) +sage: K.<x0,x1> = QQ[] +sage: R. = K[] +sage: factor(x^2 - (x0+x1)x)


 By the way, here is one of my favorite MuPAD demo about genericity:
@@ -30,36 +28,11 @@
 sage: Qx = QQ['x'].fraction_field()
 sage: x = Qx.gen()

-This used to fail because Sage could not test the primality of z^2-x:

-``` -sage: Px. = QQ[] -sage: Qx = Px.fraction_field() -sage: Qxz = Qx['z'] -sage: z = Qxz.gen() -sage: (z^2-x).is_irreducible()

-NotImplementedError Traceback (most recent call last) -``` -and the algebraic extension was not recognized as giving a field:

- -sage: F in Fields() -

-This still fails, for some reason.

Having a factorization over generic fields should do the job.

jdemeyer commented 10 years ago

Description changed:

--- 
+++ 
@@ -1,14 +1,6 @@
 Factorization is a fundamental building block of computer algebra, yet Sage is
 still missing a generic implementation of factorization that would
 work over any (reasonable) field. Students and colleagues are stumbling over this over and over.
-
-We might want this to work too (it does not yet):
-
-```
-sage: K.<x0,x1> = QQ[]
-sage: R.<x> = K[]
-sage: factor(x^2 - (x0+x1)*x)
-```

 By the way, here is one of my favorite MuPAD demo about genericity:

@@ -23,6 +15,7 @@
 factor(f);
                       (u + x z) (u - x z)

+ This ought to work in Sage too:

jdemeyer commented 10 years ago

Description changed:

--- 
+++ 
@@ -19,13 +19,12 @@
 This ought to work in Sage too:
  • sage: Qx = QQ['x'].fraction_field()
  • sage: x = Qx.gen()
  • sage: Qxz. = Qx[]
  • sage: F. = Qxz.quo(z^2-x)
  • sage: P. = F[]
  • sage: (u^2 - x^3).factor()

  • NotImplementedError +sage: Qx. = QQ[] +sage: Qxz. = Qx.fraction_field()[] +sage: F. = Qxz.quo(z^2-x) +sage: P. = F[] +sage: (u^2 - x^3).factor() +NotImplementedError

    
Having a factorization over generic fields should do the job.
jdemeyer commented 10 years ago
comment:14

Replying to @nthiery:

Why too general? It asks for a very specific feature: having a default generic implementation of multivariate polynomials over (reasonably computable) fields.

Fine, but none of the examples in your description was an example of a factorization of a multi-variate polynomial over a field which currently fails in Sage.

jdemeyer commented 10 years ago

Description changed:

--- 
+++ 
@@ -1,30 +1,3 @@
 Factorization is a fundamental building block of computer algebra, yet Sage is
 still missing a generic implementation of factorization that would
 work over any (reasonable) field. Students and colleagues are stumbling over this over and over.
-
-By the way, here is one of my favorite MuPAD demo about genericity:
-
-```
-Q  := Dom::Rational:
-Qx := Dom::Fraction(Dom::UnivariatePolynomial(x, Q)):
-F  := Dom::AlgebraicExtension(Qx, poly(z^2 - x, [z])):
-P  := Dom::UnivariatePolynomial(u,F):
-P(u*z)*P(z)
-                              x u
-f := P(u^2 - x^3);
-factor(f);
-                      (u + x z) (u - x z)
-```
-
-This ought to work in Sage too:
-
-```
-sage: Qx.<x> = QQ[]
-sage: Qxz.<z> = Qx.fraction_field()[]
-sage: F.<z> = Qxz.quo(z^2-x)
-sage: P.<u> = F[]
-sage: (u^2 - x^3).factor()
-*NotImplementedError*
-```
-
-Having a factorization over generic fields should do the job.
jdemeyer commented 10 years ago
comment:16

Note: I'm not trying to deny that there are issues with factorization of polynomials in Sage, but at least make it clear what this ticket is really about.

nthiery commented 10 years ago

Description changed:

--- 
+++ 
@@ -1,3 +1,42 @@
-Factorization is a fundamental building block of computer algebra, yet Sage is
-still missing a generic implementation of factorization that would
-work over any (reasonable) field. Students and colleagues are stumbling over this over and over.
+Implement a generic implementation of univariate polynomial
+factorization that would work over any (computable enough) field.
+
+Rationale: factorization is a fundamental building block of computer
+algebra. Students and colleagues are stumbling over this over on this
+missing feature while playing with not so exotic fields. As an
+illustration, here is for example a translation in Sage of my old
+favorite demo in MuPAD illustrating generic algorithms:
+
+```
+    sage: Qx.<x> = QQ[]
+    sage: Qxz.<z> = Qx.fraction_field()[]
+    sage: F.<z> = Qxz.quo(z^2-x)
+    sage: P.<u> = F[]
+    sage: z*u   * z
+    x*u
+    sage: (u^2 - x^3).factor()     # Should return (u + x z) (u - x z)
+    *NotImplementedError*
+```
+
+It would be nice to further support base rings which themselves
+support factorization:
+
+```
+    sage: K.<x0,x1> = QQ[]
+    sage: R.<x> = K[]
+    sage: factor(x^2 - (x0+x1)*x)
+```
+
+
+For the record, there has been progress lately, with factorization
+implemented for more fields, though not yet all. Here are examples
+that used to fail with Sage 5.8 and work with Sage 6.4:
+
+```
+    sage: Px.<x> = QQ[]
+    sage: Qx = Px.fraction_field()
+    sage: Qxz = Qx['z']
+    sage: z = Qxz.gen()
+    sage: (z^2-x).factor()
+```
+
nthiery commented 10 years ago

I agree that the description was crappy, and my latest update had not improved it. I was in the middle of discussion with the Singular people and just wanted to make sure I had updated the datapoints, before going back to it later.

But please don't destroy data points! Those are vital to reproduce issues and measure progress.

jdemeyer commented 10 years ago
comment:18

Replying to @nthiery:

But please don't destroy data points!

Initially, I planned to remove all examples which didn't fit the description. Until I realized I had no examples left...

jdemeyer commented 10 years ago
comment:19

Implement a generic implementation of univariate polynomial factorization that would work over any (computable enough) field.

This is still way too general. I think the two examples you mention really should be 2 tickets, and those tickets should be just about those examples, nothing too general.

jdemeyer commented 10 years ago
comment:20

Replying to @nthiery:

But please don't destroy data points! Those are vital to reproduce issues and measure progress.

What's the point of having information like "this used to fail, but now works"?

nthiery commented 10 years ago
comment:21

Replying to @jdemeyer:

This is still way too general. I think the two examples you mention really should be 2 tickets, and those tickets should be just about those examples, nothing too general.

I agree we could split a second ticket for factorization over a ring. But for fields I don't see how it is too general: as far as I know, there exist generic algorithms that cover all cases.

nthiery commented 10 years ago
comment:22

Replying to @jdemeyer:

Replying to @nthiery:

But please don't destroy data points! Those are vital to reproduce issues and measure progress.

What's the point of having information like "this used to fail, but now works"?

Tracking progress, and keeping a trace of history. For example, people may stumble on similar issues with various versions of Sage and want to report it. And learn from the ticket "nice, my special case is now fixed, but I should be careful because not all cases are".

And honestly I don't see, with the new layout, what disadvantage there can be of having this information.

Anyway, I am bailing out of this discussion. It's not my area, I have tried to bring in as much useful information I could, if you know better how to lay it out so that the job gets done, go ahead.

jdemeyer commented 10 years ago
comment:23

Replying to @nthiery:

as far as I know, there exist generic algorithms that cover all cases.

I have very strong doubts about this. Factorization algorithms over CC, over QQ and over GF(q) are very different, so I don't see how one algorithm could work in all cases.

jdemeyer commented 10 years ago
comment:24

Replying to @nthiery:

And honestly I don't see, with the new layout, what disadvantage there can be of having this information.

Too much irrelevant information can be confusing. But I'll leave it for now.

jdemeyer commented 10 years ago
comment:25

as far as I know, there exist generic algorithms that cover all cases.

There are generic algorithms for factorization of multi-variate polynomials, assuming you can do uni-variate factorization. Perhaps that's what you had in mind?

nthiery commented 10 years ago
comment:26

Oh, wait, wait, wait, where is my mind ... Yes, of course factorization over K[x] for K=QQ, CC, ... is completely different; I am even illustrating this in my usuals intros to Sage :-)

So, let's see. What I had in mind was indeed generic factorization algorithm for the standard constructions of fields from existing ones.

Ok, I'll try now to rewrite the description in a proper way. It's not my area, so please clarify it :-)

nthiery commented 10 years ago

Description changed:

--- 
+++ 
@@ -1,11 +1,13 @@
-Implement a generic implementation of univariate polynomial
-factorization that would work over any (computable enough) field.
+Implement generic (univariate?) polynomial factorization algorithms
+over ground fields obtained through standard constructions.

 Rationale: factorization is a fundamental building block of computer
 algebra. Students and colleagues are stumbling over this over on this
-missing feature while playing with not so exotic fields. As an
-illustration, here is for example a translation in Sage of my old
-favorite demo in MuPAD illustrating generic algorithms:
+missing feature while playing with not so exotic fields built from
+standard ones.
+
+Here is for example a translation in Sage of my old favorite demo in
+MuPAD illustrating constructions and generic algorithms:

 sage: Qx.<x> = QQ[]

@@ -18,19 +20,64 @@ NotImplementedError


-It would be nice to further support base rings which themselves
-support factorization:
+TODO: review the literature, what's already implemented, and what could be; provide examples in each case.
+
+# Factorization over a transcendental extension F(x)
+
+Assuming one can factor (univariate) polynomials over F, implement
+factorization for (univariate) polynomials over F(z).
+
+
+# Factorization over an algebraic extension F(a)
+
+Assuming one can factor (univariate) polynomials over F, implement
+factorization for (univariate) polynomials over F(a).
+
+Taken from the MuPAD library:
+
+```
+/* faclib::algfactor(a,flag) factors the polynomial a in F(alpha)[z]
+  or tests it for irreducibility only, depending on flag 
+  
+  Input: a is a bivariate polynomial in z and alpha, 
+         flag: TRUE or FALSE
+  Output: if flag <> FALSE then list of factors of a
+          if flag is FALSE then TRUE if a is irreducible
+               FALSE if a is reducible
+
+  Reference: Geddes et al, Algorithms for Computer Algebra, algorithm
+  AlgebraicFactorization page 383
+*/
+```
+
+# Factorization over polynomial rings F[...]

 sage: K.<x0,x1> = QQ[]
 sage: R.<x> = K[]
 sage: factor(x^2 - (x0+x1)*x)
  • NotImplementedError

+# Special case: bivariate polynomials + +/* factorization of bivariate polynomials over a field F

  • or of univariate polynomials over F[y]
  • The algorithm implemented in faclib::FACTOR is based on Hensel lifting
  • and short vector computation. It works for the factorization of an
  • univariate polynomial over F[y][x] over any ring y.
  • Reference: von zur Gathen, Hensel and Newton Methods in Valuation Rings, Math.Comp.
  • 166(1984), pp. 637-661.
  • The complexity is O(n^6 m^2 + n log q) operations in F_q when
  • F=F_q, and where n = deg(f,x) and m = deg(f,y). +*/

  • +# Some old data points

    For the record, there has been progress lately, with factorization -implemented for more fields, though not yet all. Here are examples -that used to fail with Sage 5.8 and work with Sage 6.4: +implemented in more situations. Here are examples that used to fail +with Sage 5.8 and work with Sage 6.4:

     sage: Px.<x> = QQ[]
nthiery commented 10 years ago

Description changed:

--- 
+++ 
@@ -20,7 +20,9 @@
     *NotImplementedError*

-TODO: review the literature, what's already implemented, and what could be; provide examples in each case. +TODO: review the literature, what's already implemented, and what +could be; provide examples in each case. Split the ticket as +appropriate.

Factorization over a transcendental extension F(x)

@@ -36,7 +38,7 @@ Taken from the MuPAD library:

-/* faclib::algfactor(a,flag) factors the polynomial a in F(alpha)[z]
+  faclib::algfactor(a,flag) factors the polynomial a in F(alpha)[z]
   or tests it for irreducibility only, depending on flag 

   Input: a is a bivariate polynomial in z and alpha, 
@@ -47,7 +49,6 @@

   Reference: Geddes et al, Algorithms for Computer Algebra, algorithm
   AlgebraicFactorization page 383
-*/

Factorization over polynomial rings F[...]

@@ -61,7 +62,8 @@

Special case: bivariate polynomials

-/* factorization of bivariate polynomials over a field F +```

  • factorization of bivariate polynomials over a field F or of univariate polynomials over F[y]

    The algorithm implemented in faclib::FACTOR is based on Hensel lifting @@ -71,7 +73,7 @@ 166(1984), pp. 637-661. The complexity is O(n^6 m^2 + n log q) operations in F_q when F=F_q, and where n = deg(f,x) and m = deg(f,y). -*/ +```

    Some old data points

nthiery commented 10 years ago
comment:29

Ok, a first draft is there. Please, someone competent, expand it as appropriate!

  • © Githubissues.
  • Githubissues is a development platform for aggregating issues.