Constructive Methods for SAGBI and SAGBI-Gröbner Bases
(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:
https://lup.lub.lu.se/record/546579
- author
- Öfverbeck, Hans LU
- supervisor
- opponent
-
- Professor Robbiano, Lorenzo, Dipartimento di Matematica, Genova, Italy
- organization
- publishing date
- 2006
- 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}},
keywords = {{Matematik; Mathematics; elimination; intersection; automata; resultants; noncommutative invariants}},
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}},
}