Modular Algorithms For Computing Gröbner Bases in Free Algebras
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913693055320064 |
|---|---|
| author | Hofstadler, Clemens Levandovskyy, Viktor |
| author_facet | Hofstadler, Clemens Levandovskyy, Viktor |
| contents | In this work, we extend modular techniques for computing Gröbner bases involving rational coefficients to (two-sided) ideals in free algebras. We show that the infinite nature of Gröbner bases in this setting renders the classical approach infeasible. Therefore, we propose a new method that relies on signature-based algorithms. Using the data of signatures, we can overcome the limitations of the classical approach and obtain a practical modular algorithm. Moreover, the final verification test in this setting is both more general and more efficient than the classical one. We provide a first implementation of our modular algorithm in SageMath. Initial experiments show that the new algorithm can yield significant speedups over the non-modular approach. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_11606 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Modular Algorithms For Computing Gröbner Bases in Free Algebras Hofstadler, Clemens Levandovskyy, Viktor Symbolic Computation Rings and Algebras In this work, we extend modular techniques for computing Gröbner bases involving rational coefficients to (two-sided) ideals in free algebras. We show that the infinite nature of Gröbner bases in this setting renders the classical approach infeasible. Therefore, we propose a new method that relies on signature-based algorithms. Using the data of signatures, we can overcome the limitations of the classical approach and obtain a practical modular algorithm. Moreover, the final verification test in this setting is both more general and more efficient than the classical one. We provide a first implementation of our modular algorithm in SageMath. Initial experiments show that the new algorithm can yield significant speedups over the non-modular approach. |
| title | Modular Algorithms For Computing Gröbner Bases in Free Algebras |
| topic | Symbolic Computation Rings and Algebras |
| url | https://arxiv.org/abs/2502.11606 |