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

Let $f_1,\ldots,f_m$ be elements in a quotient $R^n / N$ which has finitedimension 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 basisof 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, andMora (1993) using a dual representation of $R^n / N$ as the kernel of acollection of linear functionals. Following this viewpoint, we design adivide-and-conquer algorithm, which can be interpreted as a generalization toseveral variables of Beckermann and Labahn's recursive approach for matrixPad\'e and rational interpolation problems. To highlight the interest of thismethod, we focus on the specific case of bivariate Pad\'e approximation andshow that it improves upon the best known complexity bounds