Groebner Basis calculation for degree 2 polynomials

243 Views Asked by At

Gröbner Basis calculation on degree 1 polynomials, namely linear combinations of variables, is the same as Gaussian Elimination, which has a straightforward $O(v^3)$ algorithm: each variable is eliminated in all other equations one-by-one.

And for arbitrary degree polynomials, there's Buchberger's algorithm (and others) which eliminates monomials, but sometimes by increasing the degree (though always maintaining a downwards step in some finite metric). The problem is known to be PSPACE-complete but this algorithm is doubly exponential in $v$.

What is the known situation when restricted to degree 2 polynomials? Is there a specific algorithm just for this case that is tailored for degree 2? If so, what is its time/space complexity?

This is essentially asking if there's a special case for intersections of conic sessions, many equations but each over only two variables of degree at most 2.

1

There are 1 best solutions below

1
On

Any monomial over a set $V$ of variables, of whatever degree more than 2, can be factored into a monomial of degree 2.

That is, if $m = x \cdot \prod_{v\in V} v$, then let

$e: v' = \prod_{v\in V} $ and then

$m = x\cdot v$.

This allows for multiples of any particular variable $v \in V$.

This means that any system of equations of degree more than 2 can be converted into a system of equations of at most degree 2, and so any algorithm for degree 2 would be an algorithm for arbitrary degree.

Since general GB completion is in $PSPACE$, this reduction means that GB-at-mostdegree-2 is also in $PSPACE$.