MathGroup Archive 2003

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: how does Decompose work?

  • To: mathgroup at
  • Subject: [mg43685] Re: [mg43620] how does Decompose work?
  • From: Daniel Lichtblau <danl at>
  • Date: Mon, 29 Sep 2003 01:48:00 -0400 (EDT)
  • Sender: owner-wri-mathgroup at

David Fass wrote:
> Hi.  I understand that Mathematica has "Decompose" function for polynomials.
> Can anyone point me to some sources for the algorithm? Also, where might I
> find some theorems related to polynomial decomposition (e.g., how many
> decompositions are there for polynomials of various degrees, etc.).
> Thanks very much for any help.
> -- Dave

There are several relevant papers. The oldest of which I am aware is

D. Barton and R. Zippel. 1976. A polynomial decomposition algorithm.
Proceedings of the 1976 Symposium on Symbolic and Algebraic Computation.

The method we use, a relative of the one above, is from

V. S. Alagar and M. Thanh. 1985. Fast polynomial decomposition
algorithms. Proceedings of Eurocal 1985. Lecture Notes in Computer
Science 204. Springer-Verlag Heidelberg. 150-153.

A slightly more recent method, in general faster, may be found in the
reference below.

D. Kozen and S. Landau. 1989. Polynomial decomposition algorithms. J.
Symbolic Computation 7. 445-456.

There was roughly at the same time an article by Guiterrez, Recio, and
Ruiz de Velasco. I think their method was substantially similar to that
of Kozen and Landau. I don't have a full reference but could probably
find it if need be.

The papers above discuss the theory as well as algorithms.

Daniel Lichtblau
Wolfram Research

  • Prev by Date: Re: start question
  • Next by Date: Re: Eigenvalues, any suggestions?
  • Previous by thread: how does Decompose work?
  • Next by thread: Re: how does Decompose work?