Geometria Complessa e Geometria Differenziale
Geometria Complessa e Geometria Differenziale
home | mail | people | news | seminars | events | open positions | login

S. Naldi - V. Neiger

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

created by naldi on 18 May 2020
modified on 11 Apr 2021


Published Paper

Inserted: 18 may 2020
Last Updated: 11 apr 2021

Journal: ISSAC 20: Proceedings of the 2020 ACM International Symposium on Symbolic and Algebraic Computation
Volume: 1
Pages: 380--387
Year: 2020

ArXiv: 2002.06404 PDF


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 in univariate contexts. 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.

Credits | Cookie policy | HTML 5 | CSS 2.1