Checking if a System of Polynomial Equations is Consistent

I'm not sure you can hope for a fast algorithm in general. Suppose the first equation has the form

$$a_1x_1+a_2x_2+\cdots+a_nx_n=0$$

where $a_1,a_2,\ldots,a_n$ are positive integers, and the other $n$ equations are all of the form

$$x_k^2-1=0$$

Then what you're checking for is solutions of the partition problem for the set $S=\{a_1,a_2,\ldots,a_n\}$, which is NP-complete (although the Wikipedia article indicates it's an "easy" hard problem that can often be solved in practice via dynamic programming).

It is very easy to check whether a system of polynomial equation is consistent or not. All you have to do is calculate the grobner basis for the system. If the Grobner basis is $(1)$, then the system is inconsistent, otherwise not. Mathematica can easily calculate grobner basis for any system of polymonial equations. And for checking consistency, the monomial ordering won't matter at all.