Accéder directement au contenu Accéder directement à la navigation
Pré-publication, Document de travail

A divide-and-conquer algorithm for computing Gröbner bases of syzygies in finite dimension

Abstract : Let $f_1,\ldots,f_m$ be elements in a quotient $R^n / N$ which has finite dimension as a $K$-vector space, where $R = K[X_1,\ldots,X_r]$ and $N$ is an $R$-submodule of $R^n$. We address the problem of computing a Gr\"obner basis of the module of syzygies of $(f_1,\ldots,f_m)$, that is, of vectors $(p_1,\ldots,p_m) \in R^m$ such that $p_1 f_1 + \cdots + p_m f_m = 0$. An iterative algorithm for this problem was given by Marinari, M\"oller, and Mora (1993) using a dual representation of $R^n / N$ as the kernel of a collection of linear functionals. Following this viewpoint, we design a divide-and-conquer algorithm, which can be interpreted as a generalization to several variables of Beckermann and Labahn's recursive approach for matrix Pad\'e and rational interpolation problems. To highlight the interest of this method, we focus on the specific case of bivariate Pad\'e approximation and show that it improves upon the best known complexity bounds.
Type de document :
Pré-publication, Document de travail
Liste complète des métadonnées

Littérature citée [35 références]  Voir  Masquer  Télécharger

https://hal-unilim.archives-ouvertes.fr/hal-02480240
Contributeur : Vincent Neiger <>
Soumis le : jeudi 4 juin 2020 - 12:21:23
Dernière modification le : samedi 6 juin 2020 - 04:12:29

Fichier

syzygies_final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Simone Naldi, Vincent Neiger. A divide-and-conquer algorithm for computing Gröbner bases of syzygies in finite dimension. 2020. ⟨hal-02480240v2⟩

Partager

Métriques

Consultations de la notice

46

Téléchargements de fichiers

65