Computing syzygies in finite dimension using fast linear algebra

Abstract

We consider the computation of syzygies of multivariate polynomials in a finite-dimensional setting: for a $\mathbb{K}[X_1,\dots ,X_r]$-module $\mathcal{M}$ of finite dimension $D$ as a $\mathbb{K}$-vector space, and given elements $f_1,\dots ,f_m$ in $\mathcal{M}$, the problem is to compute syzygies between the $f_i$'s, that is, polynomials $(p_1,\dots ,p_m)$ in $\mathbb{K}[X_1,\dots ,X_r{]}^m$ such that $p_1{f}_1+\cdots +p_m{f}_m=0$ in $\mathcal{M}$. Assuming that the multiplication matrices of the $r$ variables with respect to some basis of $\mathcal{M}$ are known, we give an algorithm which computes the reduced Gröbner basis of the module of these syzygies, for any monomial order, using $O(m{D}^{\omega -1}+r{D}^{\omega }\log (D))$ operations in the base field $\mathbb{K}$, where $\omega$ is the exponent of matrix multiplication. Furthermore, assuming that $\mathcal{M}$ is itself given as $\mathcal{M}=\mathbb{K}[X_1,\dots ,X_r{]}^n/\mathcal{N}$, under some assumptions on $\mathcal{N}$ we show that these multiplication matrices can be computed from a Gröbner basis of $\mathcal{N}$ within the same complexity bound. In particular, taking $n=1$, $m=1$ and $f_1=1$ in $\mathcal{M}$, this yields a change of monomial order algorithm along the lines of the FGLM algorithm with a complexity bound which is sub-cubic in $D$.

34 pages, 7 algorithms, Journal of Complexity

Cited by in corpus (3)

• $p$-adic algorithm for bivariate Gröbner bases
• A divide-and-conquer algorithm for computing Gröbner bases of syzygies in finite dimension
• A new algorithm for computing $\mu$-bases of the univariate polynomial vector