تعمیم الگوریتم بوخبرگر در جبرهای تفاضلی نسبت به ترتیب­های چندگانه

نویسندگان
حمزه حرف شنو
عبدالعلی بصیری
سجاد رحمانی
دانشگاه دامغان
10.52547/mmr.7.3.513
چکیده
پایه­­ی گربنر نسبت به چند ترتیب برای یک مدول تفاضلی، مهمترین ابزار برای یافتن چندجمله­ای بعد دستگاه­های دیفرانسیلی و تفاضلی است. در این مقاله، الگوریتمی برای محاسبه­ی این پایه­ی گربنر، ارایه شده است. برای این منظور، ابتدا برای هر عضو از یک مدول تفاضلی نوعی نمایش، موسوم به نمایش نسبت به چند ترتیب، معرفی می کنیم. سپس با استفاده از این نمایش، اثباتی برای تعمیم قضیه­ی بوخبرگر در مدول­های تفاضلی متناهی مولد، ارایه می­دهیم. همچنین شرط لازم و کافی برای وجود پایه­ی گربنر نسبت به چند ترتیب را برای یک مدول تفاضلی بیان می­کنیم. در ادامه، الگوریتمی برای محاسبه­ی پایه­ی­ گربنر یک زیر مدول تفاضلی متناهی مولد نسبت به چند ترتیب، ارایه می­شود.


p { margin-bottom: 0.1in; direction: ltr; line-height: 115%; text-align: left; }a:link { color: rgb(0, 0, 255); }




p { margin-bottom: 0.1in; direction: ltr; color: rgb(0, 0, 0); line-height: 115%; text-align: left; background: transparent none repeat scroll 0% 0%; }p.western { font-family: "Calibri", serif; font-size: 11pt; }p.cjk { font-family: "Calibri"; font-size: 11pt; }p.ctl { font-family: "Arial"; font-size: 11pt; }a:link { color: rgb(0, 0, 255); text-decoration: underline; }
کلیدواژه‌ها
حلقه ­ی تفاضلی
مدول تفاضلی
پایه ­ی­ گربنر
الگوریتم بوخبرگر

عنوان مقاله English

Generalization of Buchberger’s Algorithm with Respect to Several Orderings on Difference Modules

نویسندگان English

hamzeh harfsheno
abdolali basiri
sajjad rahmany
Damghan university
چکیده English

Grobner basis with respect to several orderings is a powerful tool to compute multivariate difference dimension polynomials. In this paper, an algorithm for computing a Grobner basis of a difference module over a ground difference field with respect to several term orderings is presented. In this direction, a representation of an element of a difference module with respect to several term orderings is introduced. Based on such representation, we generalize the Buchberger theorem to the case of free modules over difference rings with several term orderings associated with a partition of the set of variables. Furthermore, the necessary and sufficient condition is given for the existence of a Grobner basis with respect to several term orderings. In the sequel, we present our implementation of the algorithm on Maple.



./files/site1/files/%D8%AD%D8%B1%D9%81_%D8%B4%D9%86%D9%88%D8%A8%D8%B5%DB%8C%D8%B1%DB%8C(1).pdf


p { margin-bottom: 0.1in; direction: ltr; line-height: 115%; text-align: left; }

کلیدواژه‌ها English

Difference ring
Difference module
Groebner basis
Buchberger algorithm
1. Buchberger B., “On finding a vector space basis of the residue class ring modulo a zero dimensional polynomial ideal (in German)”, PhD Thesis, Universitate Innsbruck, Innsbruck (1965).

2. Cohn R.M., “Difference Algebra”, In: Tracts in Mathematics, vol. 17, Interscience, New York (1965).

3. Cox D., Little J., OShea D., “Ideals, Varieties and Algorithms. An Introduction to Computational Algebraic Geometry and Commutative Algebra”, 3rd edition, Springer, New York (2007).

4. Dönch C., “Standard Bases in Finitely Generated Difference-Skew-Differential Modules and Their Application to Dimension Polynomials”, PhD thesis, Johannes Kepler University Linz, Research Institute for Symbolic Computation (RISC) (2012).

5. Dönch C., Winkler F., “Bivariate difference-differential dimension polynomials and their computation in Maple”, 8 th International Conference on Applied Informatics Eger, Hungary, January 27–30(2010).

6. Einstein A., “The Meaning of Relativity. Appendix II (Generalization of Gravitation Theory)”, 4th ed. Princeton, (1953) 133–165.

7. Gerdt V. P., “Groebner bases in perturbative calculations” , Nucl. Phys. 135 (Proc. Suppl.) 232 (2004) [hep-ph/0501053].

8. Gerdt V.P., Robertz D., “Computation of Difference Grobner Bases”, Computer Science Journal of Moldova, vol.20, no.2(59) (2012).

9. Johnson J., Sit W., “On the differential transcendence polynomials of finitely generated differential field extensions”, Amer. J. Math. 101 (6) (1978) 1249–1263.

10. Kolchin E. R., “Differential Algebra and Algebraic Groups”, Academic Press, NewYork –London (1973).

11. Kolchin E. R., “The notion of dimension in the theory of algebraic difierential equations”, Bull. Am. Math. Soc.,70 (1964) 570-573.

12. Levin A. B., “Computation of the Strength of Systems of Difference Equations via Generalized Grobner Bases”, Grobner Bases in Symbolic Analysis, Walter de Gruyter, Berlin, (2007) 43-74.

13. Levin A. B., “Characteristic polynomials of filtered difference modules and of difference fleld extensions”, Russ. Math. Surv., 33 (1978) 165-166.

14. Levin A. B., “Difference Algebra”, Springer (2008).

15. Levin A. B., “Grobner bases with respect to several orderings and multivariable dimension polynomials”, Journal of Symbolic Computation ,42 (2007) 561–578.

16. Levin A. B., “Difference dimension quasi-polynomials”, Advances in Applied Mathematics ,89 (2017) 1–17.

17. Levin A. B., “Multivariable Difference Dimension Polynomials”, Journal of Mathematical Sciences, Vol. 131, No. 6 (2005).

18. Martin, B., Levandovskyy V., “Symbolic Approach to Generation and Analysis of Finite Difierence Schemes of Partial Difierential Equations”,. In: U. Langer, P. Paule (Eds.) Numerical and Symbolic Scientiflc Computing: Progress and Prospects, Springer, Wien, (2012) 123-156.

19. Mikhalev A. V., Levin A. B., Pankratiev E. V., Kondratieva M. V., “Differential and Difference Dimension Polynomials”, Mathematics and Its Applications, Kluwer, Dordrecht (1999).

20. Mikhalev A. V., PankratevKahler E. V. “Computer Algebra, Computations in Differential and Difference Algebra”, Moscow: Moscow State Univ Press (1989).

21. Mikhalev A.V., Pankratev E.V., “Differential dimension polynomial of a system of differential equations”, In: Algebra, Moscow State Univ. Press, Moscow, (1980) 57–67. Collection of papers (in Russian).

22. Ritt J. F., “Differential Algebra”, Dover Publications Inc., New York (1950).http ://www.am.:org/onlinebks/coll33.

23. Ritt J. F., “Differential equations from the algebraic standpoint”, volume 14 of American Mathematical Society Colloquium Publications, AMS., New York (1932) .

24. Scala R.L., “Grobner bases and gradings for partial difference ideals”, Mathematics of computation, Vol. 84, No. 292 (2015) 959–985.

25. The Maple implementation of our algorithms is available at the address http :

//faculty.du.ac.ir/rahmani/.

26. Zhou M., Winkler F., “Computing difference-differential dimension polynomials by relative Grobner bases in difference-differential modules”, Journal of Symbolic Computation, no. 43 (2008) 726–745.

27. Zhou M., Winkler F., “Grobner bases in difference-differential modules and differencedifferential dimension polynomials”, Science in China, Ser. A, Mathematics, 51/9 (2008) 1732-1752.