Name
Abstract | ||
|---|---|---|
We consider the computation of syzygies of multivariate polynomials in a finite-dimensional setting: for a K[X1,…,Xr]-module M of finite dimension D as a K-vector space, and given elements f1,…,fm in M, the problem is to compute syzygies between the fi’s, that is, polynomials (p1,…,pm) in K[X1,…,Xr]m such that p1f1+⋯+pmfm=0 in M. Assuming that the multiplication matrices of the r variables with respect to some basis of 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(mDω−1+rDωlog(D)) operations in the base field K, where ω is the exponent of matrix multiplication. Furthermore, assuming that M is itself given as M=K[X1,…,Xr]n∕N, under some assumptions on N we show that these multiplication matrices can be computed from a Gröbner basis of N within the same complexity bound. In particular, taking n=1, m=1 and f1=1 in 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. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1016/j.jco.2020.101502 | Journal of Complexity |
Keywords | DocType | Volume |
Gröbner basis,Syzygies,Complexity,Fast linear algebra | Journal | 60 |
ISSN | Citations | PageRank |
0885-064X | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vincent Neiger | 1 | 39 | 7.22 |
| Schost Éric | 2 | 0 | 0.34 |