A divide-and-conquer algorithm for computing Gröbner bases of syzygies in finite dimension
Résumé
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.
Domaines
Calcul formel [cs.SC]
Origine : Fichiers produits par l'(les) auteur(s)
Loading...