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