Complexity of the Inversion Algorithm of Polynomial Mappings

• Autorzy: Bogdan P.

Identyfikatory

DOI

10.4467/20838476SI.16.016.6197

• Języki publikacji: EN

Abstrakty

EN

In this paper we will recall the inversion algorithm described in [1]. The algorithm classifies polynomial automorphisms into two sets: Pascal finite and Pascal infinite. In this article the complexity of the inversion algorithm will be estimated. To do so, we will present two popular ways how Computer Algebra Systems (CASes) keep the information about multivariate polynomials. We will define the complexity as the amount of simple operations performed by the algorithm as a function of the size of the input. We will define simple operations of the algorithm. Then we will estimate complexity of checking that the polynomial map is not a polynomial automorphism. To do so we will use theorem 3.1 from [1].

Słowa kluczowe

EN

polynomial automorphism; differential Galois theory; computational complexity; computer algebra system

• Wydawca: Wydawnictwo Uniwersytetu Jagiellońskiego
• Czasopismo: Schedae Informaticae
• Rocznik: 2016
• Tom: Vol. 25
• Strony: 209--225
• Opis fizyczny: Bibliogr. 14 poz., rys.

Twórcy

autor

Bogdan P.

• Chair of Effective Methods in Algebra, Department of Computer Science and Computer Mathematics Faculty of Mathematics and Computer Science ul. Łojasiewicza 6, 30-348 Kraków, Poland

Bibliografia

• [1] Adamu E., Bogdan P., Crespo T., Hajto Z., An effective study of polynomial maps. Journal of Algebra and Its Applications, 2017, 16(5).
• [2] Campbell L.A., A condition for a polynomial map to be invertible. Mathematische Annalen, 1973, 205(3), pp. 243–248.
• [3] Crespo T., Hajto Z., Picard-vVessiot theory and the Jacobian problem. Israel Journal of Mathematics, 2012, 186(1), pp. 401–406.
• [4] Adamus E., Bogdan P., Hajto Z., An effective approach to Picard-Vessiot theory and the Jacobian Conjecture, 2015, submitted.
• [5] Müller N.T., Uniform Computational Complexity of Taylor Series. In: 14th International Colloquium on Automata, Languages and Programming, London, UK, UK, Springer-Verlag, 1987, pp. 435–444.
• [6] Bardet M., Faugére J.C., Salvy B., On the complexity of the F5 Gröbner basis algorithm. Journal of Symbolic Computation, 2014, 70, pp. 1–24.
• [7] Faugére J.C., Safey El Din M., Spaenlehauer P.J., Gröbner Bases of Bihomogeneous Ideals Generated by Polynomials of Bidegree (1,1): Algorithms and Complexity. Journal of Symbolic Computation, 2011, 46(4), pp. 406–437 Available online 4 November 2010.
• [8] Adamus E., Bogdan P., Crespo T., Hajto Z., An effective study of polynomial maps, 2016, submitted.
• [9] Developers T.S., Sage Mathematics Software (Version 7.1). 2015.
• [10] Winkler F., Polynomial Algorithms in Computer Algebra. Texts & Monographs in Symbolic Computation. Springer Vienna, 1996.
• [11] van den Essen A., Polynomial Automorphisms: and the Jacobian Conjecture (Progress in Mathematics). Birkhuser, 2000.
• [12] Yagzhev A.V., Keller’s problem. Siberian Mathematical Journal, 1980, 21(5), pp. 747–754.
• [13] Bass H., Connell E.H., Wright D., The Jacobian conjecture: Reduction of degree and formal expansion of the inverse. Bulletin of the AMS – American Mathematical Society (NS), 1982, 7(2), pp. 287–330.
• [14] Druzkowski L.M., An Effective Approach to Keller’s Jacobian Conjecture. Mathematische Annalen, 1983, 264, pp. 303–314.

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).