Computing Minimal Generating Sets of Invariant Rings of Permutation Groups with SAGBI-Gröbner Basis
We present a characteristic-free algorithm for computing minimal generating sets of invariant rings of permutation groups. We circumvent the main weaknesses of the usual approaches (using classical Gröbner basis inside the full polynomial ring, or pure linear algebra inside the invariant ring) by re...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2001-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/2285/pdf |
| _version_ | 1797270635423989760 |
|---|---|
| author | Nicolas Thiéry |
| author_facet | Nicolas Thiéry |
| author_sort | Nicolas Thiéry |
| collection | DOAJ |
| description | We present a characteristic-free algorithm for computing minimal generating sets of invariant rings of permutation groups. We circumvent the main weaknesses of the usual approaches (using classical Gröbner basis inside the full polynomial ring, or pure linear algebra inside the invariant ring) by relying on the theory of SAGBI- Gröbner basis. This theory takes, in this special case, a strongly combinatorial flavor, which makes it particularly effective. Our algorithm does not require the computation of a Hironaka decomposition, nor even the computation of a system of parameters, and could be parallelized. Our implementation, as part of the library $permuvar$ for $mupad$, is in many cases much more efficient than the other existing software. |
| first_indexed | 2024-04-25T02:07:24Z |
| format | Article |
| id | doaj.art-81f867ed998843b18d5ae9817682d81d |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:07:24Z |
| publishDate | 2001-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-81f867ed998843b18d5ae9817682d81d2024-03-07T14:27:42ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502001-01-01DMTCS Proceedings vol. AA,...Proceedings10.46298/dmtcs.22852285Computing Minimal Generating Sets of Invariant Rings of Permutation Groups with SAGBI-Gröbner BasisNicolas Thiéry0https://orcid.org/0000-0002-2735-8921Université Claude Bernard Lyon 1We present a characteristic-free algorithm for computing minimal generating sets of invariant rings of permutation groups. We circumvent the main weaknesses of the usual approaches (using classical Gröbner basis inside the full polynomial ring, or pure linear algebra inside the invariant ring) by relying on the theory of SAGBI- Gröbner basis. This theory takes, in this special case, a strongly combinatorial flavor, which makes it particularly effective. Our algorithm does not require the computation of a Hironaka decomposition, nor even the computation of a system of parameters, and could be parallelized. Our implementation, as part of the library $permuvar$ for $mupad$, is in many cases much more efficient than the other existing software.https://dmtcs.episciences.org/2285/pdfpermutation groupinvariant theorydiscrete mathematicsminimal generating setmupadpermuvarsagbi-gröbner basishironaka decomposition[info] computer science [cs][math.math-co] mathematics [math]/combinatorics [math.co][info.info-cg] computer science [cs]/computational geometry [cs.cg][info.info-dm] computer science [cs]/discrete mathematics [cs.dm][info.info-hc] computer science [cs]/human-computer interaction [cs.hc] |
| spellingShingle | Nicolas Thiéry Computing Minimal Generating Sets of Invariant Rings of Permutation Groups with SAGBI-Gröbner Basis Discrete Mathematics & Theoretical Computer Science permutation group invariant theory discrete mathematics minimal generating set mupad permuvar sagbi-gröbner basis hironaka decomposition [info] computer science [cs] [math.math-co] mathematics [math]/combinatorics [math.co] [info.info-cg] computer science [cs]/computational geometry [cs.cg] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] [info.info-hc] computer science [cs]/human-computer interaction [cs.hc] |
| title | Computing Minimal Generating Sets of Invariant Rings of Permutation Groups with SAGBI-Gröbner Basis |
| title_full | Computing Minimal Generating Sets of Invariant Rings of Permutation Groups with SAGBI-Gröbner Basis |
| title_fullStr | Computing Minimal Generating Sets of Invariant Rings of Permutation Groups with SAGBI-Gröbner Basis |
| title_full_unstemmed | Computing Minimal Generating Sets of Invariant Rings of Permutation Groups with SAGBI-Gröbner Basis |
| title_short | Computing Minimal Generating Sets of Invariant Rings of Permutation Groups with SAGBI-Gröbner Basis |
| title_sort | computing minimal generating sets of invariant rings of permutation groups with sagbi grobner basis |
| topic | permutation group invariant theory discrete mathematics minimal generating set mupad permuvar sagbi-gröbner basis hironaka decomposition [info] computer science [cs] [math.math-co] mathematics [math]/combinatorics [math.co] [info.info-cg] computer science [cs]/computational geometry [cs.cg] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] [info.info-hc] computer science [cs]/human-computer interaction [cs.hc] |
| url | https://dmtcs.episciences.org/2285/pdf |
| work_keys_str_mv | AT nicolasthiery computingminimalgeneratingsetsofinvariantringsofpermutationgroupswithsagbigrobnerbasis |