Статья 'Анализ алгоритма декомпозиции полиномов, основанного на разбиениях' - журнал 'Кибернетика и программирование' - NotaBene.ru
Journal Menu
> Issues > Rubrics > About journal > Authors > About the Journal > Requirements for publication > Council of Editors > Peer-review process > Policy of publication. Aims & Scope. > Article retraction > Ethics > Online First Pre-Publication > Copyright & Licensing Policy > Digital archiving policy > Open Access Policy > Open access publishing costs > Article Identification Policy > Plagiarism check policy
Journals in science databases
About the Journal

MAIN PAGE > Back to contents
Cybernetics and programming

The analysis of partitions based algorithm of polynomials decomposition

Perminova Mariya Yur'evna

graduate student, Department of Industrial Electronics, Tomsk State University of Control Systems and Radioelectronics

634045, Russia, Tomskaya oblast', g. Tomsk, pr. Lenina, 40




Review date:


Publish date:


Abstract: The research focuses on the generating function, which is an effective tool for solving various mathematical problems in combinatorics, probability theory, mathematical physics, analysis of algorithms, etc. The subject of research is one class of generating functions – polynomials. Special attention is paid to the problem of polynomial decomposition, which has a number of solutions. The author proposes a new polynomial decomposition algorithm based on partitions. The article gives a brief description of the algorithm and gives an example of its usage. The study determines computational complexity of the algorithm, which consists of the time complexity of generating partitions, producing a monomial and solving the equation. The time complexity of the polynomial decomposition algorithm based on partitions is calculated on the basis of the results obtained by D. Knuth and given in the On-Line Encyclopedia of Integer Sequences. The original polynomial decomposition algorithm is also given. It is shown that the time complexity of the algorithm is O (n^2). The author compares the described algorithm with its analogs. The analysis shows that most of the decomposition algorithms have polynomial computational complexity of O (n^2). The experimental curves of the computational complexity of the polynomial decomposition algorithm based on partitions and known algorithms are shown.

Keywords: Decomposition of polynomials, Generation of partitions, algorithm, the computational complexity of the algorithm, generating functions, polynomial, computer algebra systems, composition, monomial, solution of equations
This article written in Russian. You can find full text of article in Russian here .

Bukhberger B., Kalme Zh., Kaltofen E. i dr. Komp'yuternaya algebra. Simvol'nye i algebraicheskie vychisleniya / per. s angl. M.: Mir, 1986. 392 s.
Mysovskikh V. I. Sistemy komp'yuternoi algebry i simvol'nye vychisleniya // Zapiski nauchnykh seminarov POMI RAN. 2001. T. 281. S. 227–236.
Kulyabov D. S., Kokotchikova M. G. Analiticheskii obzor sistem simvol'nykh vychislenii // Vestnik RUDN, seriya «Matematika. Informatika. Fizika». 2007. № 1-2. S. 38–45.
Barton D. R., Zippel R. E. Polynomial decomposition algorithms // Journal of Symbolic Computation. 1985. Vol. 1. No. 2. Pp. 159–168.
Alagar V. S., Thanh M. Fast polynomial decomposition algorithms // Proceedings of European Conference on Computer Algebra. 1985. Pp. 150–153.
Kozen D., Landau S. Polynomial decomposition algorithms // Journal of Symbolic Computation. 1989. No. 7. Pp. 445–456.
Seong J.-K., Elber G., Kim M.-S. Polynomial Decomposition and Its Applications. 2003. 12 p. URL: http://www.cs.utah.edu/~seong/decomposition.pdf (data obrashcheniya: 09.07.2015).
Kruchinin V.V., Kruchinin D.V. Stepeni proizvodyashchikh funktsii i ikh primenenie. Tomsk: TUSUR, 2013. 234 s.
Perminova M. Yu., Kruchinin V. V. Algoritmy rekursivnoi generatsii ogranichennykh razbienii natural'nogo chisla // Doklady Tomskogo gosudarstvennogo universiteta sistem upravleniya i radioelektroniki. №4(34), 2014. Str. 89–94.
Perminova M. Yu., Kruchinin V. V. Algoritm dekompozitsii polinomov, osnovannyi na razbieniyakh // Doklady Tomskogo gosudarstvennogo universiteta sistem upravleniya i radioelektroniki. №4(38), 2015 [v pechati].
Knut D. Iskusstvo programmirovaniya / per. s angl. M.: OOO «I. D. Vil'yams», 2007. T. 4, vyp. 3. 208 s.
OEIS — onlain-entsiklopediya tselochislennykh posledovatel'nostei. URL: https://oeis.org/A029895 (data obrashcheniya: 03.08.2015).
Link to this article

You can simply select and copy link from below text field.

Other our sites:
Official Website of NOTA BENE / Aurora Group s.r.o.
"History Illustrated" Website