Вариант алгоритма Гердта для вычисления инволютивных базисов

Обложка

Цитировать

Полный текст

Аннотация

В работе первого автора был представлен эффективный алгоритм вычисления инволютивных базисов и приведенных базисов Гребнера. В данной работе мы рассмотрим модификацию указанного алгоритма, которая упрощает его понимание и облегчает программную реализацию. Мы докажем корректность модифицированного алгоритма и используемых вместе с использованными в нем критериями и его оканчиваемость. Предложенный алгоритм реализован на языке Maple. Путем вычислительных экспериментов с рядом полиномиальных систем мы сопоставим времена счета модифицированного алгоритма с его оригинальной формой, описанной в и также реализованной на языке Maple. При этом детали оба алгоритма были реализованы схожим образом, чтобы обеспечить корректность сравнения их вычислительной эффективности.

Об авторах

Владимир Петрович Гердт

Объединённый институт ядерных исследований

Email: gerdt@jinr.ru
Лаборатория информационных технологий; Объединённый институт ядерных исследований

Амир Хашеми

Исфаханский технологический университет

Email: Amir.Hashemi@cc.iut.ac.ir
Отделение математических нау; Исфаханский технологический университет

Бенджамин М-Ализадех

Исфаханский технологический университет

Email: B.Alizadeh@math.iut.ac.ir
Отделение математических нау; Исфаханский технологический университет

Список литературы

  2. 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.
  3. Buchberger B. Ein Algorithms zum Auffinden der Basiselemente des Restklassenrings nach einem nuildimensionalen Polynomideal: Ph.D. thesis / Universit.at Innsbruck. - 1965.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. Thomas J. Differential Systems. - New York: American Mathematical Society, 1937. - Pp. xx+363.
  9. 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.
  10. 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).
  11. 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.
  12. 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.
  13. 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.
  14. 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.
  15. 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.
  16. 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.
  17. Bini D., Mourrain B. Polynomial Test Suite. - http://www-sop.inria.fr/ saga/POL/.
  18. 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.

© Гердт В.П., Хашеми А., М-Ализадех Б., 2012

Creative Commons License
Эта статья доступна по лицензии Creative Commons Attribution 4.0 International License.

Данный сайт использует cookie-файлы

Продолжая использовать наш сайт, вы даете согласие на обработку файлов cookie, которые обеспечивают правильную работу сайта.

О куки-файлах