       Re: how does Decompose work?

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

```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.
356-358.

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?