Complexity of the inversion algorithm of polynomial mappings

doi:10.4467/20838476SI.16.016.6197

Complexity of the inversion algorithm of polynomial mappings

Communities & Collections

pcg.skipToMenu

Complexity of the inversion algorithm of polynomial mappings

View Usage Statistics

Show full item record

dc.contributor.author	Bogdan, Paweł [SAP14010193]	pl
dc.date.accessioned	2017-10-18T07:31:27Z
dc.date.available	2017-10-18T07:31:27Z
dc.date.issued	2016	pl
dc.identifier.issn	1732-3916	pl
dc.identifier.uri	https://ruj.uj.edu.pl/xmlui/handle/item/45267
dc.language	eng	pl
dc.rights	Dozwolony użytek utworów chronionych	*
dc.rights.uri	http://ruj.uj.edu.pl/4dspace/License/copyright/licencja_copyright.pdf	*
dc.title	Complexity of the inversion algorithm of polynomial mappings	pl
dc.type	JournalArticle	pl
dc.description.physical	209-225	pl
dc.abstract.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].	pl
dc.subject.en	polynomial automorphism	pl
dc.subject.en	computational complexity	pl
dc.subject.en	differential Galois theory	pl
dc.subject.en	computer algebra system	pl
dc.description.volume	25	pl
dc.identifier.doi	10.4467/20838476SI.16.016.6197	pl
dc.identifier.eissn	2083-8476	pl
dc.title.journal	Schedae Informaticae	pl
dc.language.container	eng	pl
dc.affiliation	Wydział Matematyki i Informatyki : Instytut Informatyki i Matematyki Komputerowej	pl
dc.subtype	Article	pl
dc.rights.original	OTHER; otwarte czasopismo; ostateczna wersja wydawcy; w momencie opublikowania; 0	pl
dc.identifier.project	ROD UJ / P	pl
.pointsMNiSW	[2016 B]: 11