#15513: Generic factorization algorithms for polynomials over field extensions
and
similar constructions
---------------------------------+------------------------
Reporter: nthiery | Owner:
Type: task | 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:
---------------------------------+------------------------
Changes (by nthiery):
* type: enhancement => task
Old 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()
> }}}
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. 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()
}}}
--
--
Ticket URL: <http://trac.sagemath.org/ticket/15513#comment:28>
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.
