قالبي جديد براي محاسبه ي پايه هاي گربنر

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

A new framework for computing Gr bner bases Zahra Sadeghi Dinani zahra sadeghi1@math iut ac ir January 6 2019 Master of Science Thesis in Farsi Departement of Mathematical Sciences Isfahan University of Technology Isfahan 84156 8311 IranSupervisor Dr Amir Hashemi amir hashemi@cc iut ac irAdvisor Dr Reza Rezaeian Farashahi farashahi@cc iut ac ir2015 MSC 13P10 68W30Keywords Polynomial ideals Gr bner bases Signature Syzygy module Homogeneous polynomial ideals Minimalhomogeneous basis Abstract Polynomial systems are ubiquitous in mathematics science and engineering Gr bner basis theory is one of themost powerful tools for solving polynomial systems and is essential in many computational tasks in algebra andalgebraic geometry Buchberger introduced in 1965 the concept of Gr bner basis and the first algorithm for com puting Gr bner bases and this algorithm has been implemented in most computer algebra systems including Maple Mathematica Magma Sage Singular Macaulay 2 CoCoA etc There has been extensive effort in finding moreefficient algorithms for computing Gr bner bases In Buchberger s original algorithm one has to reduce many use less S polynomials i e those that reduce to 0 via long division and each reduction is time consuming It is naturalto avoid useless reductions as much as possible Buchberger discovered two simple criteria for detecting uselessS polynomials Note that a reduction of an S polynomial to 0 corresponds to a syzygy for the initial list of poly nomials M ller Mora and Traverso go a step further to present an algorithm using the full module of syzygies however their algorithm is not very efficient Faug re introduced the idea of signatures and rewriting rules that candetect many useless S polynomials hence saving a significant amount of time In fact for a regular sequence ofpolynomials his F5 algorithm detects all useless reductions By computer experiments Faug re showed that hisF5 algorithm is many times faster than previous algorithms In fact Faug re and Joux solved the first Hidden FieldEquation HFE Cryptosystem Challenge which involves a system of 80 polynomial equations with 80 variables overthe binary field In another direction of research one tries to speed up the reduction step Lazard pointed out theconnection between Gr bner bases and linear algebra that is a Gr bner basis can be computed by Gauss eliminationof a Sylvester matrix The XL algorithm of Courtois et al is an implementation of this Sylvester matrix which wasrecently improved by Ding et al A more clever approach is the F4 algorithm of Faug re which deals with muchsmaller matrices F4 is an efficient method for reducing several S polynomials simultaneously where the basic ideais to apply fast linear algebra methods to the submatrix of the Sylvester matrix consisting of only those rows that areneeded for the reductions of a given list of S polynomials This method benefits from the efficiency of fast linearalgebra algorithms The main problem with this approach however is that the memory usage grows quickly com pared to F5 for example even for medium systems of polynomials F5 as presented is difficult to understand theproofs of its correctness and finite termination contain significant gaps Stegers filled some details of the proofs underthe assumption of two conjectures but one of which was later shown to be false by Gash More recently Arri andPerry presented a simpler theory for signature based algorithms They gave a revised F5 criterion with correct proof however their proof of finite termination is flawed The main contribution of this thesis is to present a new simpletheory for computing Gr bner bases Every list of polynomials defines an ideal and a syzygy module Most papersin the literature focus on computing Gr bner bases for ideals while Gr bner bases for syzygies are computed by atotally different method We show that the two types of Gr bner bases can be computed by a unified framework Wework in a larger module that contains both the ideal a

صادقي ديناني، زهرا

قالبي جديد براي محاسبه ي پايه هاي گربنر

ايده آل هاي چند جمله اي , پايه هاي گربنر , شناسه , مدول سي زي جي , ايده آل هاي چند جمله اي همگن , پايه ي مينيمال همگن