عنوان پایان‌نامه
جنبه های الگوریتمی ایده‌آل چندجمله ای پارامتری و کاربردهای آن
- رشته تحصیلی
- ریاضی‌محض
- مقطع تحصیلی
- دکتری تخصصی PhD
- محل دفاع
- کتابخانه پردیس علوم شماره ثبت: 6472;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 79366;کتابخانه پردیس علوم شماره ثبت: 6472;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 79366
- تاریخ دفاع
- ۱۱ اسفند ۱۳۹۵
- دانشجو
- مهدی دهقانی درمیان
- استاد راهنما
- سیامک یاسمی
- چکیده
- امروزه حل بسیاری از مسائل جبر محاسباتی به پایه‌ی گربنر ختم می‌شود که مجموعه‌ی مولدی خاص برای ایده‌آل‌های چندجمله‌ای است. پیچیدگی محاسبات این پایه که در سال 1965 توسط برونو بوخبرگر معرفی شد وابسته به ترتیب تک‌جمله‌ای اتخاذ شده است.اجرای بسیاری از مثال‌ها نشان می‌دهد که محاسبه‌ی پایه‌ی گربنر نسبت به ترتیب الفبایی معکوس مدرج (drl) کم هزینه تر از محاسبه‌ی پایه‌ی گربنر نسبت به ترتیب الفبایی (lex) است. متاسفانه، در بسیاری از کاربردها نیاز به محاسبه‌ی پایه‌ی گربنر نسبت به ترتیب الفبایی است. پس ایده‌ی خوبیست که در ابتدا پایه‌ی گربنر را نسبت به ترتیب drl محاسبه و سپس آن‌را به پایه‌ی گربنر نسبت به ترتیب lex تبدیل کنیم. این روند را تبدیل پایه‌ی گربنر می‌نامند که با توجه به بعد ایده‌آل با یکی از الگوریتم‌های FGLM یا generic Grobner walk انجام می‌شود.توسیع پایه‌ی گربنر برای چندجمله‌ای‌های با ضرایب پارامتری را پایه‌ی گربنر فراگیر (CGB) و دستگاه گربنر (GS) می‌نامند. وایزفنینگ در سال 1965 این مفاهیم را معرفی و وجود آن‌ها را برای هر ایده‌آل چندجمله‌ای پارامتری ثابت کرد. پس از آن چندین الگوریتم برای محاسبه‌ی این مفاهیم ارائه شد که سریع‌ترین و موثرترین آن‌ها الگوریتمPGBMain کاپور و همکاران است که در سال 2010 طراحی گردید. در این رساله به منظور بهبود محاسبات دستگاه گربنر، مسئله‌ی تبدیل پایه‌های گربنر پارامتری را معرفی می‌کنیم. با بیانی دقیق‌تر، فرض کنیم دستگاه گربنر ایده‌آلی نسبت به ترتیب drl داده شده است. با معرفی نمونههای پارامتری الگوریتم‌های FGLM وgeneric Grobner walk دستگاه گربنر این ایده‌آل را نسبت به ترتیب lex محاسبه می‌کنیم. تمامی الگوریتم‌های موجود در این رساله در نرم افزار Maple اجرا شده‌اند و عملکرد آن‌ها با اجرای چند مثال بررسی شده است. نتایج حاصل از این بررسی نشان می‌دهد که این دو الگوریتم جدید به‌طور قابل ملاحظه‌ای عملکرد بهتری نسبت به الگوریتم کاپور دارند.
- Abstract
- Many problems in computer algebra may lead to the computation of Grobner bases; a particular kind of generating set for an ideal in a polynomial ring over a field. These bases were introduced in 1965 by Bruno Buchberger in his Ph.D. thesis. The complexity of computing Grobner bases depends on the underlying monomial ordering. Experiments show that computing Gr\"obner bases w.r.t. degree reverse lexicographical ordering (drl) is more efficient than lexicographical ordering (lex). On the other hand, for many applications of Grobner bases we are interested in lex Grobner bases. One idea for computing a lex Gr\"obner basis is to compute a drl basis and then change it into the desired basis. This process is called Grobner basis conversion which can be performed by either the FGLM algorithm (in zero-dimensional case) or the walk algorithm (in positive dimensional case).Some of the problems arising from applications are parametrical systems; i.e. the coefficients are polynomials in terms of certain parameters. Weispfenning in 1992 studied Grobner bases for such ideals and called them comprehensive Grobner systems (CGS). Recently, Kapur et al. proposed PGBMain algorithm which is the most efficient algorithm to compute CGS. In this dissertation, we consider the non-trivial problem of converting parametric Grobner bases to improve the computation of lex CGS which is the most practical among them. In this direction, we develop first linear algebra tools to study linear parametric systems. Then, using these tools, we develop the parametric variants of FGLM and generic Grobner walk algorithms. All proposed algorithms have been implemented in Maple and their efficiency is discussed on a diverse set of benchmark polynomials. Results from the experiments show that our new algorithms are considerably more efficient than PGBMain algorithm.Keywords:Grobner bases, Parametric Gaussian elimination, Comprehensive Grobner systems, FGLM algorithm, Parametric FGLM algorithm, Grobner walk algorithm, Parametric Grobner walk algorithm.
