28
$\begingroup$

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:

  1. 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)?
  2. 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?
  3. what bounds are known for the size of a Gröbner basis in terms of size and sparsity of the original system?
  4. 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?
Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ All math problems are real world problems $\endgroup$
    – Fernando Muro
    Commented Dec 8, 2011 at 22:48
  • $\begingroup$ It's worth pointing out that even basic invariants such as dimension are sensitive to small changes in the defining polynomials. For example, there are plenty of curves in 3-space which require three defining polynomials (as opposed to the 2 you might expect for easy cases). Perturb one of those polynomials and you find that they now define a point instead of a curve. I suppose you have to look at sets of the form $|f_i| < \epsilon$ instead of $f_i=0$. $\endgroup$
    – Martin Bright
    Commented Dec 9, 2011 at 10:28

4 Answers 4

Reset to default
25
$\begingroup$

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.

Improve this answer
$\endgroup$
9
$\begingroup$

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.

Improve this answer
$\endgroup$
8
$\begingroup$

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

Improve this answer
$\endgroup$
6
$\begingroup$

Concerning your questions 1 and 4, you should also have a look at border bases:

http://www.risc.jku.at/Groebner-Bases-Bibliography/gbbib_files/publication_1140.pdf

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .