Skip to main content
retag
Link
Greg Kuperberg
  • 56.6k
  • 10
  • 203
  • 282
Source Link
TerronaBell
  • 3.1k
  • 26
  • 29

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

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?