In particular, suppose I have an affine algebraic variety over $\mathbb{R}^n$ described by generators of a radical ideal $I$ and I want to find (perhaps not all of the) points in the variety. Several important questions come up in practice:
- are there versions of Buchberger's algorithm that work with inexact data? For instance, suppose that the coefficients of the polynomials generating $I$ are known only to floating point precision. Some CAS will try to find solutions assuming that these coefficients are exact. Are there CAS that do something more intelligent (e.g., make certain guarantees given that the numerical coefficients are the truncation of exact coefficients)?
- does a sparse system of polynomial equations yield a Gröbner basis with sparse elements? In other words, if each polynomial in the original system has a small number of non-zero coefficients relative to $n$, do the basis elements also have this property?
- what bounds are known for the size of a Gröbner basis in terms of size and sparsity of the original system?
- are there more appropriate algorithms (than Buchberger's) if we just want to find a single point in the variety? (Suppose that any such point is sufficient.) More generally, which algorithms are better suited to address the kinds of issues mentioned above?
Best Answer
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.