پايه ي گربنر تقريبي

چكيده انگليسي :

Approximate Gr bner basis o Elaheh Mohammadifard e mohammadifard@math iut ac ir January 19 2013 Master of Science Thesis Department of Mathematical Sciences Isfahan University of Technology Isfahan 84156 83111 IranSupervisor DR Amir Hashemi amir hashemi@cc iut ac irAdvisor DR Mojtaba Aghaei aghaei@cc iut ac ir2000 MSC 13P10Key words Gr bner basis Buchberger s algorithm Buchberger s criterion Approximate Gr bner o obasis Arti cial discontinuity F5 algorithm F5 criterion FGLM algorithmAbstractGr bner bases is a powerful tool in polynomial ideal theory and it was introduced in 1965 by oBuchberger in his PhD thesis 4 The method of Gr bner bases is a valuable technique for solving many problems in commutative oalgebra and algebraic geometry But the process of computing a Gr bner basis may involve large onumbers of intermediate coe cients from a eld K even when the nal Gr bner basis does not oinvolve large coe cients In fact the cost of performing exact arithmetic in K with the intermediatecoe cients is a major factor determining the computational cost of computing Gr bner basis oIn 1996 Shirayanagi proposed a new approach based on oating point arithmetic in the case K isa sub eld of the real numbers 20 Basically he mimiced Buchberger s algorithm However thebig question then would be How small must oating point coe cients be to be considered zero Shirayanagi proposed a criterion for answering this question His key idea was to calculate and keeptrack of an error term for every coe cients that occurs at each step of the S polynomial calculationor polynomial reduction and to judge coe cients as zero by estimation of their accumulatederrors To keep track of these errors bracket coe cients for polynomials were introduced Theseare like oating point numbers together with error terms Let us de ne the support of a polynomial of a nite set of polynomials The support of a polynomialf i1 in ai1 in xi1 xin is the set of power products n 1 supp f xi1 xin ai1 in 0 n 1The support of a nite set F f1 fn of polynomials is supp F supp f1 supp fn Note that supp 0 Next we discuss the general notion of coe cientwise convergence and the specialized notionof supportwise convergence that we use further Let f be a sequence of polynomials andf be a polynomial Then f coe cientwise converges to f f f coe cientwise if f i1 i1 in in i1 in ai1 in x1 xn and f i1 in ai1 in x1 xn such that lim ai1 in ai1 infor all i1 in The stronger property of supportwise convergence is one of the central de nition in this thesis Let f be a sequence of polynomials and f be a polynomial Then f supportwise convergesto f f f supportwise if1 f coe cientwise converges to f and2 there is an integer N such that supp f supp f for all N Moreover let f be a sequence of nite sets of polynomials and F f1 fn be a nite setof polynomials Then F supportwise converges to F F F supportwise if there is an integerN such that for all N F f1 fn where fi fi supportwise for all i In the other words supportwise convergence emphasizes that coe cients that converge to zero reach zero in a nite number of steps

محمدي فرد، الهه

پايه ي گربنر تقريبي