https://hal-unilim.archives-ouvertes.fr/hal-02392488v2Neiger, VincentVincentNeigerXLIM-MATHIS - Mathématiques & Sécurité de l'information - XLIM - XLIM - UNILIM - Université de Limoges - CNRS - Centre National de la Recherche ScientifiqueSchost, ÉricÉricSchostCS - Cheriton School of Computer Science [Waterloo] - University of Waterloo [Waterloo]Computing syzygies in finite dimension using fast linear algebraHAL CCSD2020Gröbner basissyzygiescomplexityfast linear algebra[INFO.INFO-SC] Computer Science [cs]/Symbolic Computation [cs.SC]Neiger, Vincent2020-06-19 12:00:262022-06-26 02:50:552020-06-25 10:48:26enJournal articleshttps://hal-unilim.archives-ouvertes.fr/hal-02392488v2/document10.1016/j.jco.2020.101502https://hal-unilim.archives-ouvertes.fr/hal-02392488v1application/pdf2We 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 + \dots + 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\"obner basis of the module of thesesyzygies, 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 multiplicationmatrices can be computed from a Gr\"obner basis of $\mathcal{N}$ within thesame 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 thelines of the FGLM algorithm with a complexity bound which is sub-cubic in$D$.