# Overdeterminate system of multivariate equation

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

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)$.