A Divide-and-conquer Algorithm for Computing Grobner Bases of Syzygies in Finite Dimension

Let f(1),..., f(m) be elements in a quotient R-n/N which has finite dimension as a K-vector space, where R = K[X-1,..., X-r] and N is an R-submodule of R-n. We address the problem of computing a Grobner basis of the module of syzygies of (f(1),..., f(m)), that is, of vectors (p(1),..., p(m)) is an element of R-m such that p(1)f(1) + . . . + p(m)f(m) = 0. An iterative algorithm for this problem was given by Marinari, Moller, 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 Pade and rational interpolation problems. To highlight the interest of this method, we focus on the specific case of bivariate Pade approximation and show that it improves upon the best known complexity bounds.