محاسبه پايه گربنر يك ايده‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌آل نقاط و مطالعه پيچيدگي آن

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

Computing Gr bner basis for an ideal of points and studing its complexity Fateme Akbari akbarifateme@math iut ac ir January 5 2021 Master of Science Thesis in Farsi Departement of Mathematical Sciences Isfahan University of Technology Isfahan 84156 8311 IranSupervisor Dr Amir Hashemi Amir Hashemi@iut ac irAdvisor Dr Mahdi Tatari mtatari@iut ac ir2000 MSC 13P10 and 68W30Keywords Gr bner basis Ideal of points Buchberger M ller algorithm Vector space associated to idealsof points ComplexityAbstract This master thesis has been prepared based on the 27 26 and 12 Let P k x1 xn be the polynomialring in n variables over a field k The vanishing ideal with respect to a set of points X p1 pm k nis defined as the set of all elements in P that are zero on all of the pi s this set is an ideal of P and is denoted byI X The problem that we address in this thesis to compute the reduced Gr bner basis for the vanishing ideal ofany finite set of points under any given monomial order A polynomial time algorithm for this problem was firstgiven by Buchberger and M ller 1982 6 and significantly improved by Marinari M ller and Mora 1993 29 and Abbott Bigatti Kreuzer and Robbiano 2000 1 These algorithms perform Gauss elimination on a generalizedVandermonde matrix and have a polynomial time complexity Recently O Keefie and Fitzpatrick 2002 17 studiedthis problem from coding theory point of view They present an algorithm that is exponential in the number ofvariables and the G rbner basis which they compute is not reduced A new bound for the arithmetic complexity ofthe Buchberger M ller algorithm was given in 26 and is equal to O nm2 min m n m3 Algorithmically the main task is to compute the vanishing ideal of an affine point set from the coordinates of thepoints In principle this task can be done using the Gr bner basis methods explained in the first chapter In fact forX p1 pm to apply this approach we use the fact that I X I p1 I ps However for largerexamples this method is not efficient and we use the Buchberger M ller algorithm The Buchberger M ller algorithm returns a Gr bner basis for the ideal vanishing on the set X by applying the linearalgebra techniques A complementary result of the algorithm is a vector space basis for the quotient ring P I X However in many applications it turns out that it is the vector space basis rather than the Gr bner basis of the ideal which is of interest For instance it may be preferable to compute normal forms using vector space methods insteadof Gr bner basis techniques We will discuss four constructions of vector space bases all of which perform better than the Buchberger M lleralgorithm An application of the constructions will be that we can improve the method of the reverse engineering ofgene regulatory networks given in 24 We obtain a family of separators that is a family f1 fm of polynomials such that fi pi 1 and fi pi 0if i j It is easy to see that the separators form a k basis for the quotient ring P I X This will be the firstconstruction of vector space bases The second construction is a k basis formed by the residues of 1 f f m 1 where f is a linear form Also fromthis construction obtain an algebra isomorphism P I X k x J where J is a principal ideal The two remaining constructions give monomial k bases The third construction we discuss is a method that wasintroduced in 7 and improved in 16 It produces the set of monomials outside the initial ideal of I X with respectto the lexicographical ordering using only combinatorial methods The fourth construction gives a k basis which isthe complement of the initial ideal with respect to a class of admissible monomial orders namely elimination order

اكبري، فاطمه

محاسبه پايه گربنر يك ايده‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌آل نقاط و مطالعه پيچيدگي آن

حلقه چندجمله‌اي‌ها , پايه گربنر , ايده‌آل نقاط , الگوريتم بوخبرگر-مولر , پيچيدگي‌ محاسباتي , پايه استاندارد , فضاي برداري وابسته به ايده‌آل نقاط