Go to page
 

Bibliographic Metadata

Title
Gröbner bases and generalized Sylvester matrices / eingereicht von: Manuela Wiesinger-Widi
AuthorWiesinger-Widi, Manuela
CensorBuchberger, Bruno ; Mayr, Ernst W.
Published2015
DescriptionVIII, 108 S.
Institutional NoteLinz, Univ., Diss., 2015
Annotation
Zsfassung in dt. Sprache
LanguageEnglish
Bibl. ReferenceOeBB
Document typeDissertation (PhD)
Keywords (DE)Gröbnerbasis / lineare Algebra / Sylvestermatrix / Macaulaymatrix / Gradschranke / Polynomideal / Binomideal
Keywords (EN)Gröbner basis / linear algebra / Sylvester matrix / Macaulay matrix / degree bound / polynomial ideal / binomial ideal
Keywords (GND)Gröbner-Basis / Sylvester-Matrix / Multivariates Polynom
URNurn:nbn:at:at-ubl:1-4373 Persistent Identifier (URN)
Restriction-Information
 The work is publicly available
Files
Gröbner bases and generalized Sylvester matrices [0.75 mb]
Links
Reference
Classification
Abstract (German)

In dieser Arbeit untersuchen wir den Zusammenhang zwischen Gröbnerbasen und verallgemeinerten Sylvestermatrizen. Motiviert durch nützliche Resultate im univariaten Fall mit zwei Input-Polynomen, zeigen wir, wie verallgemeinerte Sylvestermatrizen im multivariaten Fall mit mehreren Input-Polynomen dazu verwendet werden können, eine Gröbnerbasis für die Inputmenge zu berechnen. Teilmatrizen der Sylvestermatrix werden schon seit geraumer Zeit dazu verwendet, die Gröbnerbasenberechnung zu beschleunigen. In dieser Arbeit zeigen wir, wie eine Gröbnerbasis berechnet werden kann, indem man eine große Matrix, bestehend aus bestimmten Shifts der Input-Polynome, konstruiert und diese trianguliert. Bestimme Zeilen dieser triangulierten Matrix bilden eine minimale Gröbnerbasis. Wir geben eine obere Schranke für die Größe dieser Matrix an, die vom größten Grad der Input-Polynome, der Anzahl der Variablen und der Anzahl der Input-Polynome abhängt. Als einen Spezialfall untersuchen wir den univariaten Fall mit mehr als zwei Input-Polynomen und geben schärfere Schranken an als die in der Literatur bekannten.

Im zweiten Teil der Arbeit untersuchen wir als einen wichtigen Spezialfall Binomideale. Wir betrachten den Fall mit zwei multivariaten Input-Binomen. Als ersten Schritt behandeln wir das Membership-Problem und geben obere Schranken für den Grad der Kofaktoren eines potentiellen Elementes in der reduzierten Gröbnerbasis an. Diese Schranken sind schärfer als die Schranken, die man von der Hermannschranke durch Spezialisierung bekommt. Als zweiten Schritt geben wir obere Schranken für die Größe der verallgemeinerten Sylvestermatrix an, die ausreichen, um nach obiger Methode eine Gröbnerbasis für bestimmte Fälle von Binomidealen, abhängig vom Support der zwei Input-Binome, zu berechnen.

Diese Schranken sind schärfer als die, die man von der Schranke aus dem ersten Teil der Arbeit durch Spezialisierung bekommt.

Abstract (English)

In this thesis we investigate the connection between Gröbner bases computation and generalized Sylvester matrices. Motivated by useful results in the univariate case with two input polynomials, we show how generalized Sylvester matrices can be used in the multivariate case with several input polynomials to compute a Gröbner basis of the input set. Submatrices of the Sylvester matrix have been used for quite some time to speed up the Gröbner bases computation. In this thesis we show how we can compute a Gröbner basis by constructing one big matrix consisting of certain shifts of the input polynomials and triangularizing this matrix. Certain rows of the triangularized matrix form a minimal Gröbner basis. We give an upper bound on the size of this matrix that depends on the highest degree of the input polynomials, the number of variables and the number of input polynomials. As a special case, we treat the univariate case with more than two input polynomials and give sharper bounds than were previously known in the literature.

In the second part of the thesis we investigate as an important special case binomial ideals. We consider the case of two multivariate input binomials. As a first step we treat the membership problem and give upper bounds on the degree of the cofactors of a potential element in the reduced Gröbner basis. These bounds are sharper than the ones obtained by the Hermann bound after specialization. As a second step we give upper bounds for the size of the generalized Sylvester matrix for computing a Gröbner basis for certain cases of binomial ideals depending on the support of the two input binomials. These bounds are sharper than the ones derived from the bound in the first part of the thesis by specialization.