Разработка системы для оценки производительности алгоритмов компьютерной алгебры при нахождении базисов Грёбнера

Yury Blinkov; Soltan Salpagarov; Anton Mamonov; Izabella Akopian

doi:10.32603/2071-2340-2024-2-39-47

Yury Blinkov Saratov Chernyshevsky State University, 83 Astrakhanskaya st., 410012, Saratov, Russia http://orcid.org/0000-0001-7340-0919
Soltan Salpagarov RUDN University, 6 Miklukho-Maklaya str., 117198, Moscow, Russia http://orcid.org/0000-0002-5321-9650
Anton Mamonov RUDN University, 6 Miklukho-Maklaya str., 117198, Moscow, Russia
Izabella Akopian RUDN University, 6 Miklukho-Maklaya str., 117198, Moscow, Russia

DOI: https://doi.org/10.32603/2071-2340-2024-2-39-47

Keywords: Gröbner bases, сomputer algebra, testing system, GInv

Abstract

This work presents the development of a specialized system for evaluating the performance of computer algebra algorithms in finding Gr¨obner bases. To verify the functionality and evaluate the performance of the improved GInv 2.0 version, a special automated testing tool has been developed. This tool allows loading test data sets in JSON format, calculating Gr¨obner bases using various algorithms, and visualizing test results. The modules for data import, basis calculation, and test result output are described in detail. GInv 2.0 was tested on a set of systems of equations of varying complexity. The test results are presented, including time characteristics of calculations for each test.

Author Biographies

Yury Blinkov, Saratov Chernyshevsky State University, 83 Astrakhanskaya st., 410012, Saratov, Russia

Professor, Doctor of Sciences (Phys.-Math.), Chair of Department of Mathematic and Computer Modeling, Saratov State University, blinkovua@info.sgu.ru

Soltan Salpagarov, RUDN University, 6 Miklukho-Maklaya str., 117198, Moscow, Russia

Cand. of Sciences (Phys.-Math.), Associate Professor of Department of Computational Mathematics and Artificial Intelligence of Peoples’ Friendship University of Russia (RUDN University), salpagarov_si@pfur.ru

Anton Mamonov, RUDN University, 6 Miklukho-Maklaya str., 117198, Moscow, Russia

Postgraduate of Department of Computational Mathematics and Artificial Intelligence of Peoples’ Friendship University of Russia (RUDN University), anton.mamonov.golohvastogo@mail.ru

Izabella Akopian, RUDN University, 6 Miklukho-Maklaya str., 117198, Moscow, Russia

Student of the bachelor’s degree program of Department of Computational Mathematics and Artificial Intelligence of Peoples’ Friendship University of Russia (RUDN University), szafgvsdg@gmail.com

References

D. Cox, J. Little, and D. O’Shea, Ideals, varieties, and algorithms, Springer Cham, 2007.

A. Yu. Zharkov and Yu. A. Blinkov, “Involution approach to solving systems of algebraic equations,” in Proc. of the 1993 Inter. IMACS Symp. on Symbolic Comput, Lille, France: Laboratoire d’Informatique Fondamentale de Lille, pp. 11–16, 1993.

A. Yu. Zharkov, Involutive Polynomial Bases: General Case, Dubna, Russia: Dubna Publ., 1994.

A. Yu. Zharkov and Yu. A. Blinkov, “Algorithm for constructing involutive bases of polynomial ideal,” in Proc. of Int. Conf. on Interval and Computer-Algebraic Methods in Science and Engineering, St.Petersburg, Russia, pp. 258–260, 1994.

A. Yu. Zharkov and Yu. A. Blinkov, Involutive bases of zero-dimensional ideals, Dubna, 1994.

A. Yu. Zharkov, “Solving zero-dimensional involutive systems,” Algorithms in Algebraic Geometry and Applications, pp. 389–399, 1996; doi:10.1007/978-3-0348-9104-2_20.

V. P. Gerdt, “Gr¨obner bases and involutive methods for algebraic and differential equations,” in Computer Algebra in Science and Engineering, Singapore: World Scientific, pp. 117–137, 1995.

V. P. Gerdt, “Involutive divisions in mathematica: Implementation and some applications,” Sankt Augustin, Germany: Institute for Algorithms and Scientific Computing (GMD-SCAI), 1998.

C. Riquier, Les systemes d’ ˋ equations aux d ˊ eriv ˊ ees partielles ˊ , Paris: Gauthier Villars, 1910 (in French).

M. Janet, “Systemes d’ ˋ equations aux d ˊ eriv ˊ ees partielles,” ˊ Journals de mathematiques ˊ , no. 3, pp. 65–151, 1920 (in French).

J. Thomas, Differential systems, New York: American Mathematical Society, 1937.

Yu. A. Blinkov and V. P. Gerdt,“Specialized computer algebra system GINV,” Programming and Compute Software, vol. 34, no. 2, pp. 112–123, 2008; doi:10.1134/s0361768808020096

V. P. Gerdt, D. Robertz, and Yu. A. Blinkov, “Strong Consistency and Thomas Decomposition of Finite Difference Approximations to Systems of Partial Differential Equations,” in arxiv.org, 2020. [Online]. Available: https://arxiv.org/abs/2009.01731

B. Buchberger, “Gr¨obner bases: An algorithmic method in polynomial ideal theory, in recent trends in multidimensional system theory,” in Multidimensional system theory, Dordrecht, Netherlands: D. Reidel Publ. Comp., pp. 184–232, 1985.

Yu. A. Blinkov and E. Yu. Shchetinin, “Using Dynamic Memory Reallocation in GInv,” Programmirovanie, no. 4, pp. 21–26, 2023 (in Russian); doi:10.31857/s0132347423020061

Development of a System for Evaluating the Performance of Computer Algebra Algorithms in Finding Grobner Bases

Abstract

Author Biographies

References