×

Algorithms for the functional decomposition of Laurent polynomials. (English) Zbl 1247.68329

Carette, Jacques (ed.) et al., Intelligent computer mathematics. 16th symposium, Calculemus 2009, 8th international conference, MKM 2009, held as part of CICM 2009, Grand Bend, Canada, July 6–12, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-02613-3/pbk). Lecture Notes in Computer Science 5625. Lecture Notes in Artificial Intelligence, 186-200 (2009).
Summary: Recent work has detailed the conditions under which univariate Laurent polynomials have functional decompositions. This paper presents algorithms to compute such univariate Laurent polynomial decompositions efficiently and gives their multivariate generalization.
One application of functional decomposition of Laurent polynomials is the functional decomposition of so-called “symbolic polynomials”. These are polynomial-like objects whose exponents are themselves integer-valued polynomials rather than integers. The algebraic independence of \(X, X ^{n }\), \(X^{n^2/2}\), etc. and some elementary results on integer-valued polynomials allow problems with symbolic polynomials to be reduced to problems with multivariate Laurent polynomials. Hence we are interested in the functional decomposition of these objects.
For the entire collection see [Zbl 1165.68005].

MSC:

68W30 Symbolic computation and algebraic computation
16S34 Group rings
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Ritt, J.: Prime and composite polynomials. Trans. American Math. Society 23(1), 51–66 (1922) · JFM 48.0079.01
[2] Engstrom, H.T.: Polynomial substitutions. American Journal of Mathematics 63(2), 249–255 (1941) · Zbl 0025.10403
[3] Levi, H.: Composite polynomials with coefficients in an arbitrary field of characteristic zero. American Journal of Mathematics 64(1), 389–400 (1942) · Zbl 0063.03512
[4] Barton, D.R., Zippel, R.E.: A polynomial decomposition algorithm. In: Proc. 1976 ACM Symposium on Symbolic and Algebraic Computation, pp. 356–358. ACM Press, New York (1976)
[5] Kozen, D., Landau, S.: Polynomial decomposition algorithms. J. Symbolic Computation 22, 445–456 (1989) · Zbl 0691.68030
[6] Zippel, R.E.: Rational function decomposition. In: Proc. ISSAC 2001, pp. 1–6. ACM Press, New York (1991) · Zbl 0959.12006
[7] Kozen, D., Landau, S., Zippel, R.: Decomposition of algebraic functions. J. Symbolic Computation 22(3), 235–246 (1996) · Zbl 0876.68062
[8] von zur Gathen, J., Gutierrez, J., Rubio, R.: Multivariate polynomial decomposition. Applied Algebra in Engineering, Communication and Computing 14, 11–31 (2003) · Zbl 1103.12004
[9] Zieve, M.E.: Decompositions of Laurent polynomials (2007) Preprint: arXiv.org:0710.1902v1
[10] Watt, S.M.: Making computer algebra more symbolic. In: Proc. Transgressive Computing 2006: A conference in honor of Jean Della Dora, pp. 43–49 (2006) · Zbl 1204.68278
[11] Watt, S.M.: Two families of algorithms for symbolic polynomials. In: Kotsireas, I., Zima, E. (eds.) Computer Algebra 2006: Latest Advances in Symbolic Algorithms – Proceedings of the Waterloo Workshop, pp. 193–210. World Scientific, Singapore (2007)
[12] Watt, S.M.: Symbolic polynomials with sparse exponents. In: Proc. Milestones in Computer Algebra 2008: A conference in honour of Keith Geddes’ 60th birthday, Stonehaven Bay, Trinidad and Tobago, University of Western Ontario, pp. 91–97 (2007) ISBN 978-0-7714-2682-7
[13] Weispfenning, V.: Gröbner bases for binomials with parametric exponents. Technical report, Universität Passau, Germany (2004)
[14] Yokoyama, K.: On systems of algebraic equations with parametric exponents. In: Proc. ISSAC 2004, pp. 312–319. ACM Press, New York (2004) · Zbl 1134.13309
[15] Pan, W., Wang, D.: Uniform gröbner bases for ideals generated by polynomials with parametric exponents. In: Proc. ISSAC 2006, pp. 269–276. ACM Press, New York (2006) · Zbl 1356.13038
[16] Watt, S.: Functional decomposition of symbolic polynomials. In: Proc. International Conference on Computatioanl Sciences and its Applications (ICCSA 2008), pp. 353–362. IEEE Computer Society, Los Alamitos (2008)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.