Computing syzygies in finite dimension using fast linear algebra
share
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