论文标题
用于计算有限尺寸的Syzygiesgröbner基础的分裂和诱导算法
A divide-and-conquer algorithm for computing Gröbner bases of syzygies in finite dimension
论文作者
论文摘要
令$ f_1，\ ldots，f_m $为商$ r^n / n $中的元素，其有限尺寸为$ k $ - 矢量空间，其中$ r = k [x_1，\ ldots，x_r] $ and $ n $ is $ r $ r $ -r $ -r $ -r $ -submodule of $ r^n $。我们解决了计算$（f_1，\ ldots，f_m）$的syzygies模块的gröbner基础的问题，即vectors $（p_1，\ ldots，p_m）\ in r^m $ in r^m $，因此$ p_1 f_1 f_1 f_1 f_1 + \ cd cdots + cdots + p_m p_m f_m f_m = 0 $ = 0 $ = 0 $。 Marinari，Möller和Mora（1993）使用$ r^n / n $作为线性函数集合的内核给出了这个问题的迭代算法。遵循此观点，我们设计了一种分裂和诱导算法，可以将其解释为贝克曼（Beckermann）的几个变量和拉巴恩（Labahn）的递归方法的概括和理性插值问题。为了强调这种方法的兴趣，我们专注于双变量帕德近似的特定情况，并表明它在最著名的复杂性范围上有所改善。
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öbner 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öller, 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é 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.
