Polynomial decomposition algorithms

DOI10.1016/S0747-7171(85)80012-2MaRDI QIDQ5903274zbMATH OpenOpenAlexFDO

Authors David R. Barton, Richard Zippel

Publication date 1985

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0747-7171(85)80012-2

zbMATH Keywords

polynomial decomposition algorithms

Mathematics Subject Classification ID

Polynomials in real and complex fields: factorization (12D05) Polynomials in general fields (irreducibility, etc.) (12E05)

Review text

\textit{M. Fried} and \textit{R. MacRae} [Math. Ann. 180, 220--226 (1969; Zbl 0185.28803)] proved the following theorem: Let \(f,g,p,q\) be univariate polynomials over an arbitrary field \(k\). Then \(p(x)-q(z)\) divides \(f(x)-g(z)\) if and only if there exists a polynomial \(F(t)\) over \(k\) such that \(f(t)=F(p(t))\) and \(g(t)=F(q(t)).\) The authors present two polynomial decomposition algorithms based on this result (they find a complete decomposition of a polynomial \(f\) in the form \(f=g\circ\dots\circ h\), where \(\circ\) denotes functional composition).

Recommendations

• Functional decomposition of polynomials: the tame case
• Functional decomposition of polynomials: the wild case
• Polynomial decomposition algorithms
• A proof of a theorem by Fried and MacRae and applications to the composition of polynomial functions
• scientific article; zbMATH DE number 1263355

Cites work

• Arithmetical properties of function fields (II). The generalized Schur problem
• Composite Polynomials with Coefficients in an Arbitrary Field of Characteristic Zero
• scientific article; zbMATH DE number 3765914 (Why is no real title available?)
• scientific article; zbMATH DE number 3443743 (Why is no real title available?)
• On curves with separated variables
• On the invariance of chains of fields
• Polynomial Substitutions
• Prime and composite polynomials

Cited in

(31)

• Computational problems in the theory of finite fields
• The inverse of an automorphism in polynomial time
• A note on separated factors of separated polynomials
• Polynomial algorithms in computer algebra
• Counting invariant subspaces and decompositions of additive polynomials
• Normal form for Ritt's second theorem
• Compositions and collisions at degree \(p^2\)
• On the decomposition of rational functions
• Counting decomposable polynomials with integer coefficients
• A recombination algorithm for the decomposition of multivariate rational functions
• scientific article; zbMATH DE number 5957430 (Why is no real title available?)
• Algorithms for the Polar Decomposition
• scientific article; zbMATH DE number 4208240 (Why is no real title available?)
• scientific article; zbMATH DE number 4154575 (Why is no real title available?)
• Decomposition of polynomials and approximate roots
• scientific article; zbMATH DE number 4101330 (Why is no real title available?)
• Algorithmic Polynomials
• Algorithmic polynomials
• Algorithms for the universal decomposition algebra
• Algorithms for computing triangular decompositions of polynomial systems
• Polynomial decomposition algorithms
• Tame decompositions and collisions
• A proof of a theorem by Fried and MacRae and applications to the composition of polynomial functions
• Interpolation by decomposable univariate polynomials
• Number of equivalence classes of rational functions over finite fields
• On the problem of separating variables in multivariate polynomial ideals
• An approximate decomposition of a multivariate polynomial and its application
• Functional decomposition of polynomials: the tame case
• Functional decomposition of polynomials: the wild case
• An algorithm for the decomposition of differential polynomials in the general case
• Nearly optimal algorithms for the decomposition of multivariate rational functions and the extended Lüroth theorem

This page was built for publication: Polynomial decomposition algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5903274)