Discrete and Continuous Models and Applied Computational ScienceDiscrete and Continuous Models and Applied Computational ScienceDiscrete and Continuous Models and Applied Computational Science2658-46702658-7149Peoples' Friendship University of Russia named after Patrice Lumumba (RUDN University)8659ArticlesСтатьиA Variant of Gerdts Algorithm for Computing Involutive BasesВариант алгоритма Гердта для вычисления инволютивных базисовGerdtV PГердтВладимир Петрович ; Joint Institute for Nuclear ResearchЛаборатория информационных технологий; Объединённый институт ядерных исследованийgerdt@jinr.ruHashemiAmirХашемиАмир ; Isfahan University of TechnologyОтделение математических нау; Исфаханский технологический университетAmir.Hashemi@cc.iut.ac.irM-AlizadehBenyaminМ-АлизадехБенджамин ; Isfahan University of TechnologyОтделение математических нау; Исфаханский технологический университетB.Alizadeh@math.iut.ac.irJoint Institute for Nuclear ResearchОбъединённый институт ядерных исследованийIsfahan University of TechnologyИсфаханский технологический университет150220122NO2 (2012)№2 (2012)667708092016Copyright ©; 2012, Гердт В.П., Хашеми А., М-Ализадех Б.2012Гердт В.П., Хашеми А., М-Ализадех Б.http://creativecommons.org/licenses/by/4.0https://journals.rudn.ru/miph/article/view/8659In , the fist author presented an efficient algorithm for computing involutive (and reduced Gr̈obner) bases. In this paper, we consider a modification of the algorithm which simplifies matters to understand it and to implement. We prove correctness and termination of the modified algorithm and also correctness of the used criteria. The proposed algorithm has been implemented in Maple. We present experimental comparison, via some examples, of performance of the modified algorithm with its original form described in and implemented in Maple too. In doing so, we have taken care to provide uniform implementation details for the both algorithms.В работе первого автора был представлен эффективный алгоритм вычисления инволютивных базисов и приведенных базисов Гребнера. В данной работе мы рассмотрим модификацию указанного алгоритма, которая упрощает его понимание и облегчает программную реализацию. Мы докажем корректность модифицированного алгоритма и используемых вместе с использованными в нем критериями и его оканчиваемость. Предложенный алгоритм реализован на языке Maple. Путем вычислительных экспериментов с рядом полиномиальных систем мы сопоставим времена счета модифицированного алгоритма с его оригинальной формой, описанной в и также реализованной на языке Maple. При этом детали оба алгоритма были реализованы схожим образом, чтобы обеспечить корректность сравнения их вычислительной эффективности.Gr̈obner basesBuchberger's criteriainvolutive basesGerdt's algorithmбазисы Гребнеракритерии Бухбергераинволютивные базисыалгоритм Гердта1.Gerdt V.P. Involutive Algorithms for Computing Gr.obner Bases // Computational Commutative and Non-Commutative Algebraic Geometry. - Amsterdam: IOS, 2005. - Vol. 196 of NATO Sci. Ser. III Comput. Syst. Sci. - Pp. 199-225.2.Buchberger B. Ein Algorithms zum Auffinden der Basiselemente des Restklassenrings nach einem nuildimensionalen Polynomideal: Ph.D. thesis / Universit.at Innsbruck. - 1965.3.Buchberger B. A Criterion for Detecting Unnecessary Reductions in the Construction of Gr.obner-bases // Symbolic and algebraic computation (EUROSAM '79, Internat. Sympos., Marseille, 1979). - Berlin: Springer, 1979. - Vol. 72 of Lecture Notes in Comput. Sci. - Pp. 3-21.4.Gr.obner Bases and Applications / Ed. by B. Buchberger, F. Winkler. - Cambridge: Cambridge University Press, 1998. - Vol. 251 of London Mathematical Society Lecture Note Series. - ISBN 0-521-63298-6, Pp. viii+552. - Papers from the Conference on 33 Years of Gr.obner Bases held at the University of Linz, Linz, February 2-4, 1998.5.Janet M. Les syst`emes d'.equations aux d.eriv.ees partielles // J. Math. Pures Appl. - 1920. - Vol. 3. - Pp. 65-151. - ISSN 0021-7824.6.Seiler W.M. Involution. - Berlin: Springer-Verlag, 2010. - Vol. 24 of Algorithms and Computation in Mathematics. - ISBN 978-3-642-01286-0, Pp. xxii+650. - http://dx.doi.org/10.1007/978-3-642-01287-7. - The formal theory of differential equations and its applications in computer algebra.7.Thomas J. Differential Systems. - New York: American Mathematical Society, 1937. - Pp. xx+363.8.Pommaret J.-F. Systems of Partial Differential Equations and Lie Pseudogroups. - New York: Gordon & Breach Science Publishers, 1978. - Vol. 14 of Mathematics and its Applications. - ISBN 0-677-00270-*, Pp. xiv+411. - With a preface by Andr.e Lichnerowicz.9.Zharkov A.Y., Blinkov Y.A. Involution Approach to Investigating Polynomial Systems // Math. Comput. Simulation. - 1996. - Vol. 42, No 4-6. - Pp. 323- 332. - ISSN 0378-4754. - http://dx.doi.org/10.1016/S0378-4754(96) 00006-7. - Symbolic computation, new trends and developments (Lille, 1993).10.Gerdt V.P., Blinkov Y.A. Involutive Bases of Polynomial Ideals // Math. Comput. Simulation. - 1998. - Vol. 45, No 5-6. - Pp. 519-541. - ISSN 0378-4754. - http://dx.doi.org/10.1016/S0378-4754(97)00127-4. - Simplification of systems of algebraic and differential equations with applications.11.Apel J., Hemmecke R. Detecting Unnecessary Reductions in an Involutive Basis Computation // J. Symbolic Comput. - 2005. - Vol. 40, No 4-5. - Pp. 1131- 1149. - ISSN 0747-7171. - http://dx.doi.org/10.1016/j.jsc.2004.04.004.12.Gerdt V.P. On an Algorithmic Optimization in the Computation of Involutive Bases // Programming and Computer Software. - 2002. - Vol. 28, No 2. - Pp. 62-65. - ISSN 0132-3474. - http://dx.doi.org/10. 1023/A:1014816631983.13.Becker T., Weispfenning V. Gr.obner Bases. - New York: Springer-Verlag, 1993. - Vol. 141 of Graduate Texts in Mathematics. - ISBN 0-387-97971-9, Pp. xxii+574. - A computational approach to commutative algebra, In cooperation with Heinz Kredel.14.Gerdt V.P., Yanovich D.A. Effectiveness of Involutive Criteria in Computation of Polynomial Janet Bases // Programming and Computer Software. - 2006. - Vol. 32, No 3. - Pp. 134-138. - ISSN 0132-3474. - http://dx.doi.org/10. 1134/S0361768806030030.15.The Maple package "Janet": I. Polynomial Systems and II. Linear Partial Differential Equations / Y.A. Blinkov, V.P. Gerdt, C.F. Cid et al. // Computer Algebra in Scientific Computing (CASC 2003), V.G. Ganzha, E.W. Mayr, and E.V. Vorozhtsov, eds. - Institute of Informatics, Technical University of Munich, Garching, 2003. - Pp. 31-54.16.Bini D., Mourrain B. Polynomial Test Suite. - http://www-sop.inria.fr/ saga/POL/.17.Gerdt V.P., Blinkov Y.A. On Selection of Nonmultiplicative Prolongations in Computation of Janet Bases // Programming and Computer Software. - 2007. - Vol. 33, No 3. - Pp. 147-153. - ISSN 0132-3474. - http://dx.doi.org/10. 1134/S0361768807030048.