Re: decomposition of polynomials

Dave Rusin <rusin@xxxxxxxxxxxxxxxxxxxxx> wrote:

See also these news articles by Bill Dubuque,
which also give citations to the literature:
http://google.com/groups?selm=y8zn06nl4kr.fsf%40nestle.ai.mit.edu
http://google.com/groups?selm=y8zy8yy9500.fsf%40nestle.ai.mit.edu

Some of the links in my prior posts are now stale,
but Googling "polynomial decomposition" will reveal
links to many online expositions, e.g. see below.

--Bill Dubuque

Polynomial Decomposition
Jaime Gutierrez (Cantabria) and Dexter Kozen (Cornell)
http://www.fachgruppe-computeralgebra.de/CAR/CAR24/node6.html
http://www.fachgruppe-computeralgebra.de/CA-Rundbrief/car24.pdf

Polynomial decomposition is the problem of representing a given
polynomial f(x) as a functional composition g(h(x)) of polynomials of
smaller degree. Polynomial decomposition is useful in simplifying the
representation of field extensions of high degree and is provided as
a primitive by many major symbolic algebra systems. Decomposition
problems for multivariate polynomials and for rational and algebraic
functions are also of interest.

The theory of polynomial decomposition was initiated by Ritt in 1922
[19] and further developed in [9,8]. A survey was presented in [20].
Decompositions of f(x) in F[x] are intimately related to the
intermediate fields between F(f) and F(x) [8,19].

The problem breaks into two cases, the *tame* and the *wild*. The tame
case is when the characteristic of F does not divide the degree of g,
including characteristic 0. In the tame case, the problem is
rational--that is, if f decomposes over an extension of F, then it
decomposes over F [20]--and maximal decompositions are unique up to
insertion of linear decomposition factors and commutativity of powers
of x and Chebyshev polynomials [19]. Both facts may fail in the wild
case [8,20].

The first analyzed algorithms for decomposition of polynomials were
provided by Barton and Zippel [3] and Alagar and Thanh [1], who
considered polynomials over fields of characteristic zero. Both
solutions involved polynomial factorization and took exponential
time. For some time, the problem of finding nontrivial decompositions
was considered to be computationally hard; a cryptographic protocol
was based on its supposed intractability [5].

Kozen and Landau [17] discovered the first polynomial-time algorithms
in the tame case that do not require factorization. The time bounds
were O(n^3), O(n^2) if F supports an FFT. A similar algorithm was
discovered independently by Gutierrez et al. [15]. Kozen and Landau
also gave efficient NC algorithms (parallel polylog time on
polynomially many processors) with a time bound of O(log^2 n). In the
wild case, they reduced the problem to factorization and gave an
O(n^log(n)) algorithm for the decomposition of irreducible polynomials
over general fields admitting a polynomial-time factorization
algorithm and an NC algorithm for irreducible polynomials over finite
fields. The sequential bounds in the tame case were improved by von
zur Gathen [10] to O(n log^2(n) loglog n), O(n log^2 n) if F supports
an FFT. He also gave an improved algorithm for the wild case, yielding
a polynomial-time reduction to factorization, and observed
undecidability over sufficiently general fields [11].

Several extensions and variations have been investigated. Dickerson
[7] and von zur Gathen [10] investigated the decomposition of
multivariate polynomials. Gutierrez [13] gave a polynomial
decomposition algorithm over factorial domains. Von zur Gathen and
Weiss [12] gave an exponential method for finding decompositions of
the form f(x) = g(h(x),k(x)) for homogeneous g(y,z). Casperson et al.
[6] gave an algorithm that, given an irreducible f(x), finds g(x) and
h(x) such that f(x) divides g(h(x)). Binder [4] gave a fast method to
compute the Luroth generator of the union field of two polynomials.

Hommel and Kovacs [16] defined and investigated the sine-cosine
decomposition problem: determine whether a given bivariate polynomial
f(s,c) has a decomposition of the form f(s,c)=g(h(s,c)) mod s^2+c^2-1.
This problem has applications in robot kinematics. Gutierrez and
Recio [14] gave a cubic-time algorithm that does not require
factorization. It is based on approximating a root of f(s,c) mod
s^2+c^2-1.

Zippel [21] presented a polynomial-time algorithm to decompose
rational functions over any field admitting efficient polynomial
factorization. His approach uncovers a strong relation to Luroth's
theorem. Alonso et al. [2] gave two exponential-time algorithms for
rational function decomposition that compare favorably with Zippel's
in practice. They also presented several applications: faithful
reparametrization of unfaithfully parameterized curves, computing
intermediate fields in a simple purely transcendental extension of F,
and providing a birationality test for subfields of F(x).

Kozen, Landau, and Zippel [18] addressed the decomposition problem
for algebraic functions. They uncovered a connection to univariate
resultants over algebraic function fields and showed that the
decomposition problem essentially asks whether some power of a given
irreducible bivariate polynomial f(x,z) can be expressed as the
resultant with respect to y of two bivariate polynomials g(x,y),
h(y,z). They determined necessary and sufficient conditions for the
existence of a nontrivial decomposition and classified all such
decompositions up to isomorphism. They also gave an exponential-time
algorithm for finding a nontrivial decomposition if one exists.

Literature

1 V. S. Alagar and M. Thanh. Fast polynomial decomposition
algorithms. In Proc. EUROCAL85, pages 150-153. Springer-Verlag
Lect. Notes in Comput. Sci. 204, 1985.

2 C. Alonso, J. Gutierrez, and T. Recio. A rational function
decomposition algorithm by near-separated polynomials.
J. Symbolic Computation, 19:527-544, 1995.

3 D. R. Barton and R. E. Zippel. Polynomial decomposition algorithms.
J. Symb. Comp., 1:159-168, 1985.

4 F. Binder. Fast computations in the lattice of polynomial rational
function fields. In Proc. ISSAC-96. ACM Press, 1995.

5 J. J. Cade. A public key cipher which allows signatures.
In Proc. 2nd Conf. on Appl. Linear Algebra. SIAM, 1985.

6 D. Casperson, D. Ford, and J. MacKay. An ideal decomposition
algorithm. J. Symbolic Computation, 21(2):133-137, 1996.

7 M. Dickerson. Polynomial decomposition algorithms for multivariate
polynomials. Technical Report TR87-826, Comput. Sci., Cornell Univ.,
April 1987.

8 F. Dorey and G. Whaples. Prime and composite polynomials.
J. Algebra, 28:88-101, 1974.

9 M. D. Fried and R. E. MacRae. On curves with separated variables.
Math. Ann., 180:220-226, 1969.

10 J. von zur Gathen. Functional decomposition of polynomials:
the tame case. J. Symb. Comput., 9:281-299, 1990.

11 J. von zur Gathen. Functional decomposition of polynomials:
the wild case. J. Symb. Comput., 10:437-452, 1990.

12 J. von zur Gathen and J. Weiss. Homogeneous bivariate
decompositions. J. Symbolic Computation, 19:409-434, 1995.

13 J. Gutierrez. A polynomial decomposition algorithm over factorial
domains. Comptes Rendus Mathematiques de l'Academie des Sciences,
13(2-3):81-86, April-June 1991.

14 J. Gutierrez and T. Recio. Advances on the simplification
of sine-cosine equations. J. Symbolic Computation, 26:31-70, 1998.

15 J. Gutierrez, T. Recio, and C. Ruiz de Velasco. A polynomial
decomposition algorithm of almost quadratic complexity.
In Proc. AAECC-6/88, volume 357 of Lect. Notes in Comput. Sci.,
pages 471-476. Springer-Verlag, 1989.

16 G. Hommel and P. Kov'acs. Simplification of symbolic inverse
kinematic transformations through functional decomposition.
In Proc. of the Conference Adv. in Robotics, pages 88-95, 1992.

17 D. Kozen and S. Landau. Polynomial decomposition algorithms.
J. Symb. Comput., 7:445-456, 1989.

18 D. Kozen, S. Landau, and R. Zippel. Decomposition of algebraic
functions. Journal of Symbolic Computation, 22(3):235-246, Sep. 1996.

19 J. F. Ritt. Prime and composite polynomials.
Trans. Amer. Math. Soc., 23:51-66, 1922.

20 A. Schinzel. Selected topics on polynomials.
University of Michigan Press, 1982.

21 R. E. Zippel. Rational function decomposition.
In Stephen Watt, editor, International Symposium on Symbolic
and Algebraic Computation, pages 1-6, New York, July 1991. ACM.
.

Loading