1
$\begingroup$

If I have a random too way overdeterminate systems of homogenous non-linear equations and few variables, What's the better way too find a solution, finding a the Groener Basis or just using linearization ?

Thanks

$\endgroup$
3
$\begingroup$

I think this is better suited to be a question on the MSE site. However, I will answer it.

The first thing is that if your system is random, then the chances it admits at least one solution are extremely small, and it therefore does not make too much sense to "solve" the system. On the other hand, if you already know in advance that your system has a solution (for instance, the system arose by evaluating a value at some polynomials and subtracting the result), there are a couple of techniques that could be used depending on how large is the number of equations $m$ compared to the number of variables $n$ (I'll assume for simplicity that your equations are quadratic).

Intuition says that the more equations you have, the easier the system will be to solve. This is because equations represent "information" about the solution, and the more information you have, the easier it is to caractherize the solution. For instance, if you have many many more equations than variables (something like $m = \binom{n+2}{2}$), then linearization will work and actually will give you the solution in polynomial time. However, if you don't have this condition you are not guaranteed linearization will succeed.

On the other hand, if the ratio $m/n$ is equal to $C$, some work on semi-regular sequences shows that if you take a random system with these characteristics, then the fundamental parameter determining the running time of any Groebner basis algorithm (the Degree of Regularity) will be approximately equal to $$\left(C - \frac{1}{2} - \sqrt{C(C-1)}\right)n$$ (notice this is a decreasing function in $C$, as expected). Using the relation between the arithmetic complexity of general Groebner basis algorithms and this Degree of Regularity, one can show that this complexity is exponential in $n$ if $m = O(n)$, and sub-exponential if $m = \tilde{O}(n)$.

$\endgroup$
0
$\begingroup$

From your question I understand that you are talking about non-linear systems. So you may add it to your original question. Both methods you've suggested are good, but Grobner, with lex-order, (I believe) is better, especially if you have a state of the art implementation of F5 algorithm (for instance if you have magma). If you have too many equations and unknowns Grobner method becomes very costly. For the case of quadratic systems over finite fields you may also consider xL-algorithm (which is better than simple linearization). If your system is over the real numbers see

Solving polynomial equations: Foundations, algorithms, and applications. A. Dickenstein and I.Z. Emiris, eds., vol. 14 in: Algorithms and Computation in Mathematics, 2005

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.