Functional decomposition of polynomials: the tame case
type: Item
instance of: scholarly article
title: Functional decomposition of polynomials: the tame case
zbMATH Open document ID: 0716.68053
DOI: 10.1016/S0747-7171(08)80014-4
author: Joachim von zur Gathen
published in: Journal of Symbolic Computation
publication date: 1990-01-01T00:00:00Z
review text: Let \(n\) and \(r\) be postitive integers with \(r\) dividing \(n\) and \(2\leq r<n\). Let \(F\) be a field such that \(\text{char}(F)\) does not divide \(r\). Then \(\text{DEC}^F_{n,r}\) is the decomposition problem of deciding whether a given polynomial \(f\in F[x]\) of degree \(n\) can be expressed as a composition \(f=g \odot h\) with \(g,h\in F[x]\) and \(\deg (g)=r\), and, in the affirmative case, computing \(g\) and \(h\). The author provides an algorithm which solves this problem and can be implemented with \({\mathcal O}(n \log^2n \log \log n)\) arithmetic operations. This is an improvement on the algorithm presented by \textit{D. Kozen} and \textit{S. Landau} [J. Symb. Comput. 7, No. 5, 445--456 (1989; Zbl 0691.68030)], which required \(\mathcal O(n^2)\) arithmetic operations. Moreover, if \(\varepsilon >0\) is given and \(\text{char}(F)\) does not divide \(n\), the author presents an algorithm which computes a complete decomposition of a given polynomial \(f\in F[x]\) of degree \(n\) into indecomposable polynomials using \({\mathcal O}(n^{1+\varepsilon})\) arithmetic operations. A parallel version with (optimal) depth \({\mathcal O}(\log n)\) is also given, as well as a multivariate generalization. Finally, the following problem is solved. If \(f_ 1,f_ 2\in F[x]\), the polynomial \(f_ 1(x)-f_ 2(y)\in F[x,y]\) is called a separated polynomial. It is well-known by \textit{M. D. Fried} and \textit{R. E. MacRae} [Math. Ann. 180, 220--226 (1969; Zbl 0185.28803)] that finding separated factors of separated polynomials is equivalent to simultaneous decomposition of two polynomials. Let \(n\) and \(r\) be positive integers, and let \(F\) be a field with \(\text{char}(F)\) not dividing \(r\). Then \(\text{SEP}^F_{n,r}\) is the problem of determining for two given polynomials \(f_1,f_2,\in F[x]\) of degree at most \(n\), whether there exists a separated factor \(h_1(x)-h_2(y)\) of \(f_1(x)-f_2(y)\) in \(F[x,y]\) with \(\deg (h_1)=\deg (f_1)/r\). The first polynomia…
reviewed by: Gary L. Ebert
Mathematics Subject Classification ID: 68W30
Mathematics Subject Classification ID: 12Y05
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 12E05
zbMATH DE Number: 4180807
MaRDI profile type: Publication
cites work: Polynomial decomposition algorithms
cites work: Factoring Polynomials Over Large Finite Fields
cites work: Q4190138
cites work: Fast Algorithms for Manipulating Formal Power Series
cites work: On fast multiplication of polynomials over arbitrary algebras
cites work: Prime and composite polynomials
cites work: Very Fast Parallel Polynomial Arithmetic
cites work: Polynomial Substitutions
cites work: On the invariance of chains of fields
cites work: On curves with separated variables
cites work: Effective procedures in field theory
cites work: Parallel Algorithms for Algebraic Problems
cites work: Irreducibility of multivariate polynomials
cites work: Q4725742
cites work: Functional decomposition of polynomials: the wild case
cites work: Q3826660
cites work: Q5772619
cites work: Greatest common divisors of polynomials given by straight-line programs
cites work: Composite Polynomials with Coefficients in an Arbitrary Field of Characteristic Zero
cites work: Fast computation of GCDs
cites work: Fast multiplication of polynomials over fields of characteristic 2
cites work: Fast Probabilistic Algorithms for Verification of Polynomial Identities
cites work: Fast Parallel Computation of Polynomials Using Few Processors
description: scientific article; zbMATH DE number 4180807