Skip to main content
SUPERVISOR
Mojtaba Aghaei,Amir Hashemi
مجتبی آقائی فروشانی (استاد مشاور) امیر هاشمی (استاد راهنما)
 
STUDENT
Elaheh Mohammadifard
الهه محمدی فرد

FACULTY - DEPARTMENT

دانشکده ریاضی
DEGREE
Master of Science (MSc)
YEAR
1389

TITLE

Approximate Grobner Basis
The process of computing a Gr?bner basis may involve large numbers of intermediate coefficients, even when the final Gr?bner basis does not involve large coefficients.Shirayanagi proposed a new approach based on floating point arithmetic in the case K is a subfield of the real numbers [20]. Basically he mimiced Buchberger’s algorithm. However, the big question then would be ”How small must floating point coefficients be to be considered zero?”. For this purpose, Shirayanagi can construct the floating point approximation of with precision , and then apply Buchberger’s algorithm to . Gr?bner basis. First, we should guess the support of the desired Gr?bner basis from a floating point Gr?bner basis. Next, assuming this support to be correct, then, we use linear algebra, namely, the method of indeterminate coefficients to determine the exact values for the coefficients. Related work includes the FGLM algorithm and its modular version. This method is new in the sense that it can be considered as a floating point approach to the linear algebra method. The result of Maple computing experiments indicate that this method can be very effective in the case of nonrational coefficients, especially the ones including transcendental constants. Finally, it is well known that in the computation of Gr?bner bases an arbitrary small perturbation in the coefficients of polynomials may lead to a completely different staircase even if the roots of the polynomials change continuously. This phenomenon is called pseudo singularity in this paper. Faugère and Liang showed how such phenomenon may be detected and even repaired by adding a new variable and a binomial relation each time. Their main algorithm, named TSVn corresponding to Buchberger’s algorithm, can compute more stable Gr?bner bases of equivalent ideals (with the same set of zeros) and thus are suitable for the computation of Gr?bner bases for ideals generated by polynomials with floating point coefficients. The main theorem of this part is that any monomial basis (containing 1) of the quotient ring can be found using TSV strategy.
پایه ی گربنر یکی از ابزارهای محاسباتی برای مطالعه ی ایده آل های چندجمله ای است که توسط بوخبرگر در سال 1965 معرفی شد. اما در عمل برخی از ایده آل ها دارای مجموعه ی مولد با ضرایب اعشاری هستند. از طرفی با روش های معمول محاسبه ی پایه ی گربنر در حالت کلی نمی توان پایه ی گربنر این ایده آل ها را محاسبه کرد. به همین دلیل از سال 1996، این موضوع به یکی از موضوع های مهم در جبر محاسباتی تبدیل شده است. در سال 1996 شیرایاناگی با استفاده از روش های محاسباتی عددی، الگوریتم FPGB را برای این منظور معرفی کرد. در سال 1999، وی با همکاری سکی گاوا الگوریتم BASECONV-STAB را برای تغییر پایه ی گربنر، به کمک پایه ی گربنر تقریبی ارائه کرد. فوژر و لیانگ در سال 2011 با استفاده از محاسبات نمادین و روش TSV، الگوریتم های TSVn و TSVh را ارائه کردند. در این پایان نامه پس از بیان مقدمات لازم، الگوریتم های بالا را معرفی و با ارائه ی چند مثال مقایسه می کنیم.

ارتقاء امنیت وب با وف بومی