Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Constructive Methods for SAGBI and SAGBI-Gröbner Bases

Öfverbeck, Hans LU (2006) In Doctoral Theses in Mathematical Sciences
Abstract
The thesis consists of an introduction and the following four papers:



Paper I: Using resultants for SAGBI basis verification in the univariate polynomial ring.



Authors: Anna Torstensson, Victor Ufnarovski and Hans Öfverbeck.



Abstract: A resultant-type identity for univariate polynomials is proved and used to characterise SAGBI bases of subalgebras generated by two polynomials. A new equivalent condition, expressed in terms of the degree of a field extension, for a pair of univariate polynomials to form a SAGBI basis is derived.



Paper II: Automaton Presentations of Noncommutative Invariant Rings.



Author: Hans Öfverbeck.



... (More)
The thesis consists of an introduction and the following four papers:



Paper I: Using resultants for SAGBI basis verification in the univariate polynomial ring.



Authors: Anna Torstensson, Victor Ufnarovski and Hans Öfverbeck.



Abstract: A resultant-type identity for univariate polynomials is proved and used to characterise SAGBI bases of subalgebras generated by two polynomials. A new equivalent condition, expressed in terms of the degree of a field extension, for a pair of univariate polynomials to form a SAGBI basis is derived.



Paper II: Automaton Presentations of Noncommutative Invariant Rings.



Author: Hans Öfverbeck.



Abstract: We introduce a new presentation of the noncommutative invariant ring of a finite permutation group. The core of the presentation is a finite state automaton which represents the leading words of the invariants. As an application we describe how the automaton presentation can be used to calculate the Hilbert series of the invariant ring. We also discuss how the automaton presentation can be used to find a free set of generators of the invariant ring.



Paper III: How to Calculate the Intersection of a Subalgebra and an Ideal.



Author: Hans Öfverbeck.



Abstract: A new characterisation of the intersection of an ideal and a subalgebra of a commutative polynomial ring is presented. This characterisation is used as the foundation for a pseudo-algorithm to calculate the intersection of a subalgebra and an ideal. The pseudo-algorithm uses SAGBI-Gröbner bases, and indirectly SAGBI bases. The article also contains a presentation of an implementation in Maple of the SAGBI and SAGBI-Gröbner basis construction algorithms, and a description of how this implementation can be used for calculating the intersection of an ideal and a subalgebra. A



comparison with a previously known method to calculate the



intersection of a subalgebra and an ideal is included.



Paper IV: A note on Computing SAGBI-Gröbner bases in a Polynomial Ring over a Field.



Author: Hans Öfverbeck.



Abstract: The purpose of this note is to present an observation, a sort of



SAGBI-Gr{"o}bner analogue of Buchberger's first criterion, which justifies substantial shrinking of the so called syzygy family of a pair of polynomials. Fewer elements in the syzygy family means that fewer syzygy-polynomials need to be checked in the SAGBI-Gröbner basis construction/verification algorithm, thus decreasing the time needed for computation. (Less)
Abstract (Swedish)
Popular Abstract in Swedish

Avhandlingen består av en introduktion och följande artiklar:



Artikel I: Using resultants for SAGBI basis verification in the univariate polynomial ring.



Författare: Anna Torstensson, Victor Ufnarovski och Hans Öfverbeck.



Sammanfattning: En resultant-identitet för polynom i en variabel bevisas och används för att karakterisera SAGBI-baser för underalgebror genererade av två polynom. Ett nytt villkor, uttryckt i graden av en kroppsutvidgning, ekvivalent med att två polynom i en variabel bildar en SAGBI-bas härleds.



Artikel II: Automaton Presentations of Noncommutative Invariant Rings.



Författare: Hans... (More)
Popular Abstract in Swedish

Avhandlingen består av en introduktion och följande artiklar:



Artikel I: Using resultants for SAGBI basis verification in the univariate polynomial ring.



Författare: Anna Torstensson, Victor Ufnarovski och Hans Öfverbeck.



Sammanfattning: En resultant-identitet för polynom i en variabel bevisas och används för att karakterisera SAGBI-baser för underalgebror genererade av två polynom. Ett nytt villkor, uttryckt i graden av en kroppsutvidgning, ekvivalent med att två polynom i en variabel bildar en SAGBI-bas härleds.



Artikel II: Automaton Presentations of Noncommutative Invariant Rings.



Författare: Hans Öfverbeck.



Sammanfattning: En ny presentation av den ickekommutativa invariantringen under en ändlig permutationsgrupp introduceras. Hjärtat i denna presentation är en ändlig tillståndsmaskin som representerar invarianternas ledande ord. Som en tillämpning så beskriver vi hur den nya presentationen kan användas för att beräkna Hilbert-serien för invariantringen. Vi beskriver även hur presentationen kan användas för att bestämma en fri genererande mängd för invariantringen.



Artikel III: How to Calculate the Intersection of a Subalgebra and an Ideal.



Författare: Hans Öfverbeck.



Sammanfattning: En ny karakterisering av snittet mellan ett ideal och en underalgebra i en kommutativ polynomring visas. Karakteriseringen används som grund för en pseudo-algoritm för att beräkna snittet av en underalgebra och ett ideal. Pseudo-algoritmen bygger på SAGBI-Gröbner-baser, och indirekt även SAGBI-baser. Artikeln innehåller även en beskrivning av en implementation i Maple av konstruktionsalgoritmerna för SAGBI och SAGBI-Gröbner-baser, samt en beskrivning av hur denna implementation kan användas för att beräkna snittet mellan ett ideal och en underalgebra. En jämförelse med en sedan tidigare känd metod för att beräkna snittet mellan ett ideal och en underalgebra är inkluderad.



Artikel IV: A note on Computing SAGBI-Gröbner bases in a Polynomial Ring over a Field.



Författare: Hans Öfverbeck.



Sammanfattning: Miller har konkretiserat Sweedlers teori för ideal-baser i kommutativa värderingsringar till fallet underalgebror i en polynomring över en kropp, ideal-baserna kallas SAGBI-Gröbner-baser i detta fall. Miller bevisar en konkret algoritm för att konstruera och verifiera en SAGBI-Gröbner-bas, givet en mängd av generatorer för ett ideal i en underalgebra. Syftet med denna artikel är att presentera en observation, ett slags SAGBI-Gröbner motsvarighet till Buchbergers första kriterium, som visar att man, utan att förlora något, kan minska storleken på den så kallade syzygy-familjen hörande till ett par av polynom. Färre element i syzygy-familjen betyder att färre syzygy-polynom behöver kontrolleras i konstruktions/verifieringsalgoritmen för SAGBI-Gröbner-baser, således minskas beräkningstiden. (Less)
Please use this url to cite or link to this publication:
author
supervisor
opponent
  • Professor Robbiano, Lorenzo, Dipartimento di Matematica, Genova, Italy
organization
publishing date
type
Thesis
publication status
published
subject
keywords
Matematik, Mathematics, elimination, intersection, automata, resultants, noncommutative invariants
in
Doctoral Theses in Mathematical Sciences
pages
92 pages
publisher
Centre for Mathematical Sciences, Lund University
defense location
Centre for Mathematical Sciences Sölvegatan 18, Lund room MH:C
defense date
2006-05-05 10:15:00
ISSN
1404-0034
ISBN
91-628-6770-9
language
English
LU publication?
yes
id
8e81dd4d-3d96-4163-b68b-98f79a88bbee (old id 546579)
date added to LUP
2016-04-01 17:14:56
date last changed
2019-05-21 13:41:50
@phdthesis{8e81dd4d-3d96-4163-b68b-98f79a88bbee,
  abstract     = {The thesis consists of an introduction and the following four papers:<br/><br>
<br/><br>
Paper I: Using resultants for SAGBI basis verification in the univariate polynomial ring.<br/><br>
<br/><br>
Authors: Anna Torstensson, Victor Ufnarovski and Hans Öfverbeck.<br/><br>
<br/><br>
Abstract: A resultant-type identity for univariate polynomials is proved and used to characterise SAGBI bases of subalgebras generated by two polynomials. A new equivalent condition, expressed in terms of the degree of a field extension, for a pair of univariate polynomials to form a SAGBI basis is derived.<br/><br>
<br/><br>
Paper II: Automaton Presentations of Noncommutative Invariant Rings.<br/><br>
<br/><br>
Author: Hans Öfverbeck.<br/><br>
<br/><br>
Abstract: We introduce a new presentation of the noncommutative invariant ring of a finite permutation group. The core of the presentation is a finite state automaton which represents the leading words of the invariants. As an application we describe how the automaton presentation can be used to calculate the Hilbert series of the invariant ring. We also discuss how the automaton presentation can be used to find a free set of generators of the invariant ring.<br/><br>
<br/><br>
Paper III: How to Calculate the Intersection of a Subalgebra and an Ideal.<br/><br>
<br/><br>
Author: Hans Öfverbeck.<br/><br>
<br/><br>
Abstract: A new characterisation of the intersection of an ideal and a subalgebra of a commutative polynomial ring is presented. This characterisation is used as the foundation for a pseudo-algorithm to calculate the intersection of a subalgebra and an ideal. The pseudo-algorithm uses SAGBI-Gröbner bases, and indirectly SAGBI bases. The article also contains a presentation of an implementation in Maple of the SAGBI and SAGBI-Gröbner basis construction algorithms, and a description of how this implementation can be used for calculating the intersection of an ideal and a subalgebra. A<br/><br>
<br/><br>
comparison with a previously known method to calculate the<br/><br>
<br/><br>
intersection of a subalgebra and an ideal is included.<br/><br>
<br/><br>
Paper IV: A note on Computing SAGBI-Gröbner bases in a Polynomial Ring over a Field.<br/><br>
<br/><br>
Author: Hans Öfverbeck.<br/><br>
<br/><br>
Abstract: The purpose of this note is to present an observation, a sort of<br/><br>
<br/><br>
SAGBI-Gr{"o}bner analogue of Buchberger's first criterion, which justifies substantial shrinking of the so called syzygy family of a pair of polynomials. Fewer elements in the syzygy family means that fewer syzygy-polynomials need to be checked in the SAGBI-Gröbner basis construction/verification algorithm, thus decreasing the time needed for computation.},
  author       = {Öfverbeck, Hans},
  isbn         = {91-628-6770-9},
  issn         = {1404-0034},
  language     = {eng},
  publisher    = {Centre for Mathematical Sciences, Lund University},
  school       = {Lund University},
  series       = {Doctoral Theses in Mathematical Sciences},
  title        = {Constructive Methods for SAGBI and SAGBI-Gröbner Bases},
  year         = {2006},
}