Can Gröbner bases be used to compute solutions to large, real-world problems?

First, the Gröbner basis is not sparse. I am speaking a little off-the-cuff, but empirically when I ask SAGE for the Gröbner basis of $(y^n-1,xy+x+1)$ in the ring $\mathbb{Q}[x,y]$, it gets worse and worse as $n$ increases. Any bound would have to be in terms of the degrees of the original generators as well as their sparseness, and I suspect that the overall picture is bad.

Overall your questions play to the weaknesses of Gröbner bases. You would need new ideas to make not just the computations of the bases, but also the actual answer numerically stable. You would also need new ideas to make Gröbner bases sparse.

You are probably better off with three standard ideas from numerical analysis: Divide and conquer, chasing zeroes with an ODE, and Newton's method. If you have the generators for the variety in an explicit polynomial form, then you are actually much better off than many uses for these methods that involve messy transcendental functions. Because you can use standard analysis bounds, specifically bounding the norms of derivatives, to rigorously establish a scale to switch between divide-and-conquer and Newton's method, for instance. Moreover you can subdivide space adaptively; the derivative norms might let you stop much faster when you are far away from the variety.


To explain what I mean by derivative bounds, imagine for simplicity finding a zero of one polynomial in the unit interval $[0,1]$. If the polynomial is $100-x-x^5$, then a simple derivative bound shows that it has no zeroes. If the polynomial is $40-100x+x^5$, then a simple derivative bound shows that it has a unique zero and Newton's method must converge everywhere within the interval. If the polynomial is something much more complicated like $1-x+x^5$, then you can subdivide the interval and eventually the derivative bounds become true. Also, with polynomials, you can make bounds to know that there are no zeroes in an infinite interval under suitable conditions.

You can do something similar in higher dimensions. You can divide space into rectangular boxes, and just median subdivisions. It's not very elegant, but it works well enough in low dimensions. In high dimensions, the whole problem can be intractable; you need to say something about why you think that the solution locus is well-behaved to know what algorithm is suitable.


According to the following reference the Buchberger algorithm is generally unstable under small changes of the coefficients of the system so it cannot be executed in floating point arithmetic or with inexact input data. The paper introduces an extended Gröbner bases to try to deal with the problem. see the following:

http://www.risc.uni-linz.ac.at/publications/download/risc_273/Nr.7_paper-revised.pdf


You should look into (numerical) homotopy continuation methods, which uses ODE tracking and Newton methods mentioned in Greg's answer. They should work better with inexact data than Groebner bases methods do. It's implemented in CAS Macaulay 2. Also, "polyhedral homotopy continuation" exploits sparsity of your system (implemented in PHCpack).

Groebner bases have a doubly exponential degree bound, and this is tight.

Both Groebner bases and homotopy continuation will give you COMPLEX solutions. You asked for real solutions, which is a whole another world. Look into method for computing real radicals using moment methods.