#15513: Generic factorization algorithms for polynomials over field extensions
and
similar constructions
---------------------------------+------------------------
Reporter: nthiery | Owner:
Type: enhancement | Status: new
Priority: major | Milestone: sage-6.4
Component: factorization | Resolution:
Keywords: | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
---------------------------------+------------------------
Description changed by nthiery:
Old description:
> 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()
> }}}
New description:
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.
= 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()
}}}
--
--
Ticket URL: <http://trac.sagemath.org/ticket/15513#comment:27>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
