Computing syzygies in finite dimension using fast linear algebra
We consider the computation of syzygies of multivariate polynomials in a finite-dimensional setting: for a 𝕂[X_1,…,X_r]-module ℳ of finite dimension D as a 𝕂-vector space, and given elements f_1,…,f_m in ℳ, the problem is to compute syzygies between the f_i's, that is, polynomials (p_1,…,p_m) in 𝕂[X_1,…,X_r]^m such that p_1 f_1 + … + p_m f_m = 0 in ℳ. Assuming that the multiplication matrices of the r variables with respect to some basis of ℳ 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^ω-1 + r D^ωlog(D)) operations in the base field 𝕂, where ω is the exponent of matrix multiplication. Furthermore, assuming that ℳ is itself given as ℳ = 𝕂[X_1,…,X_r]^n/𝒩, under some assumptions on 𝒩 we show that these multiplication matrices can be computed from a Gröbner basis of 𝒩 within the same complexity bound. In particular, taking n=1, m=1 and f_1=1 in ℳ, 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.
READ FULL TEXT