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

m a t h b b K [X_{1}, d o t s, X_{r}]

-module

m a t h c a l M

of finite dimension

D

as a

m a t h b b K

-vector space, and given elements

f_{1}, d o t s, f_{m}

in

m a t h c a l M

, the problem is to compute syzygies between the

f_{i}

's, that is, polynomials

(p_{1}, d o t s, p_{m})

in

m a t h b b K [X_{1}, d o t s, X_{r}]^{m}

such that

p_{1} f_{1} + d o t s + p_{m} f_{m} = 0

in

m a t h c a l M

. Assuming that the multiplication matrices of the

r

variables with respect to some basis of

m a t h c a l M

are known, we give an algorithm which computes the reduced Gr"obner basis of the module of these syzygies, for any monomial order, using

O (m D^{o m e g a - 1} + r D^{o} m e g a l o g (D))

operations in the base field

m a t h b b K

, where

o m e g a

is the exponent of matrix multiplication. Furthermore, assuming that

m a t h c a l M

is itself given as

m a t h c a l M = m a t h b b K [X_{1}, d o t s, X_{r}]^{n} / m a t h c a l N

, under some assumptions on

m a t h c a l N

we show that these multiplication matrices can be computed from a Gr"obner basis of

m a t h c a l N

within the same complexity bound. In particular, taking

n = 1

,

m = 1

and

f_{1} = 1

in

m a t h c a l 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

.

Recommendations

Cites work

Cited in

(18)

This page was built for publication: Computing syzygies in finite dimension using fast linear algebra