Let f1, ..., fm be elements in a quotient Rn/N which has finite dimension as a K-vector space, where R = K[X1, ..., Xr] and N is an R-submodule of Rn. We address the problem of computing a Gröbner basis of the module of syzygies of (f1, ..., fm), that is, of vectors (p1, ..., pm) ∈ Rm such that p1f1 + ... + pm fm = 0. An iterative algorithm for this problem was given by Marinari, Möller, and Mora (1993) using a dual representation of Rn/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é and rational interpolation problems. To highlight the interest of this method, we focus on the specific case of bivariate Padé approximation and show that it improves upon the best known complexity bounds.
A divide-and-conquer algorithm for computing Gröbner bases of syzygies in finite dimension
Naldi S
;
2020-01-01
Abstract
Let f1, ..., fm be elements in a quotient Rn/N which has finite dimension as a K-vector space, where R = K[X1, ..., Xr] and N is an R-submodule of Rn. We address the problem of computing a Gröbner basis of the module of syzygies of (f1, ..., fm), that is, of vectors (p1, ..., pm) ∈ Rm such that p1f1 + ... + pm fm = 0. An iterative algorithm for this problem was given by Marinari, Möller, and Mora (1993) using a dual representation of Rn/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é and rational interpolation problems. To highlight the interest of this method, we focus on the specific case of bivariate Padé approximation and show that it improves upon the best known complexity bounds.
I metadati presenti in IRIS UNICA sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono protetti da diritto d'autore, salvo diversa indicazione.
