Abstract
In this paper, we discuss the decomposition problem for multivariate polynomials and the possible definitions of decomposable/indecomposable polynomial. We also present a polynomial time algorithm for decomposing multivariate polynomials over an arbitrary field.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alagar, V. S., Thanh, M.: Fast polynomial decomposition algorithms. Proceedings of EUROCAL’85. Vol. II. Lecture Notes in Comput. Sci., 204, Springer (1985), 150–153.
Alonso, C.: Desárrollo, análisis e implementación de algoritmos para la manipulación de variedades paramétricas. Departamento de Matemáticas, Estadística y Computación. Universidad de Cantabria. Thesis (1994), Spain.
Alonso, C., Gutierrez, J., Recio, T.: FRAC: A Maple package for computing in the rational function field K(x). In the book Maple V: Mathematics and Its Application. Birkhauser, (1994) 107–115.
Alonso, C., Gutierrez, J., Recio, T.: A rational function decomposition algorithm by near-separated polynomials. J. Symbolic Comput. 19 (1995), no. 6, 527–544.
Barton, R., Zippel, R.: Polynomial decomposition algorithms. J. Symbolic Comput. 1 (1985), no. 2, 159–168.
Binder, F.: Polynomial decomposition. Diplomarbeit, University of Linz, June (1995).
Cade, J.: A new public-key cipher which allows signatures. Proc. 2nd SIAM Conf. on Appl. Linear Algebra (1985), Raleigh NC.
Casperson, D., Ford, D., MacKay, J.: Ideal decomposition and subfields. J. Symbolic Comput. 21 (1996), no. 2, 133–137.
Dickerson, M.: Functional decomposition of polynomials. Tech. Rep. 89–1023, Dep. of Computer Science, Cornell University, (1989) Ithaca NY.
Gathen, J. von zur: Functional decomposition of polynomials: the tame case. J. Symbolic Comput. 9 (1990), no. 3, 281–299.
Gathen, J. von zur: Functional decomposition of polynomials: the wild case. J. Symbolic Comput. 10 (1990), no. 5, 437–452.
Gathen, J. von zur, Weiss, J.: Homogeneous bivariate decompositions. J. Symbolic Comput. 19 (1995), no. 5, 409–434.
Gutierrez, J.: A polynomial decomposition algorithm over factorial domains. Rep. Acad. Sci. Canada 13 (1991), no. 2–3, 81–86.
Gutierrez, J., Recio, T., Ruiz de Velasco, C.: Polynomial decomposition algorithm of almost quadratic complexity. Proc. AAECC-6/88. Lecture Notes in Comput. Sci., 357, Springer (1989), 471–475.
Gutierrez, J., Recio, T.: Advances on the simplification of sine-cosine equations. J. Symbolic Comput. 26 (1998), no. 1, 31–70.
Gutierrez, J., Rubio, R.: Reduced Gröbner basis under composition. J. Symbolic Comput. 26 (1998), no. 7, 433–444.
Gutierrez, J.,, Rubio, R.: The multivariate rational function decomposition problem. Tech. Report Dept. Matemáticas y Computación. Universidad de Cantabria, (1999) Spain.
Hommel, G., Kovács, R: Simplification of symbolic inverse kinematic transformations through functional decomposition. Proc. of the Conference Adv. in Robotics, Ferrara, (1992) 88–95.
Hong, H.: Gröbner basis under composition I. J. Symbolic Comput. 25 (1998), no. 5, 643–663.
Hong, H.: Gröbner basis under composition II. Proc. ISSAC-96, ACM press, (1996).
Kozen, D., Landau, S.: Polynomial decomposition algorithms. J. Symbolic Comput. 7 (1989), no. 5, 445–456.
Pilz, G., So, Y.: Near-rings of polynomials and polynomial functions. J. Austral. Math. Soc. Ser. A, 29 (1980), no. 1, 61–70.
Sweedler, M.: Using Groebner bases to determine the algebraic and transcendental nature of field extensions: return of the killer tag variables. Proc. AAECC-10/93, Lecture Notes in Comput. Sci., 673, (1993) 66–75.
Schinzel, A.: Selected topics on polynomials. Ann Arbor, University of Michigan Press. (1982).
Zippel, R.: Rational Function Decomposition. Proc. of ISSAC-91. ACM press, (1991), 1–6.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
von zur Gathen, J., Gutierrez, J., Rubio, R. (1999). On Multivariate Polynomial Decomposition. In: Ganzha, V.G., Mayr, E.W., Vorozhtsov, E.V. (eds) Computer Algebra in Scientific Computing CASC’99. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-60218-4_35
Download citation
DOI: https://doi.org/10.1007/978-3-642-60218-4_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66047-7
Online ISBN: 978-3-642-60218-4
eBook Packages: Springer Book Archive
Keywords
- Polynomial Time Algorithm
- Complete Decomposition
- Decomposition Problem
- Factorial Domain
- Multivariate Polynomial
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.