¿Pueden utilizarse las bases de Gröbner para calcular soluciones a grandes problemas del mundo real?

Question

En particular, supongamos que tengo una variedad algebraica afín sobre $\mathbb{R}^n$ descrito por los generadores de un ideal radical $I$ y quiero encontrar (quizás no todos) los puntos de la variedad. En la práctica surgen varias cuestiones importantes:

1. ¿hay versiones del algoritmo de Buchberger que funcionen con datos inexactos? Por ejemplo, supongamos que los coeficientes de los polinomios que generan $I$ se conocen sólo con precisión de punto flotante. Algunos CAS tratarán de encontrar soluciones asumiendo que estos coeficientes son exacto . ¿Existen CAS que hagan algo más inteligente (por ejemplo, que den ciertas garantías dado que los coeficientes numéricos son el truncamiento de los coeficientes exactos)?
2. ¿un sistema disperso de ecuaciones polinómicas produce una base de Gröbner con elementos dispersos? En otras palabras, si cada polinomio del sistema original tiene un pequeño número de coeficientes distintos de cero en relación con $n$ ¿los elementos de base también tienen esta propiedad?
3. ¿qué límites se conocen para el tamaño de una base de Gröbner en función del tamaño y la dispersión del sistema original?
4. ¿existen algoritmos más adecuados (que el de Buchberger) si sólo queremos encontrar un solo punto en la variedad? (Supongamos que cualquier punto de este tipo es suficiente.) En términos más generales, ¿qué algoritmos son más adecuados para abordar los tipos de problemas mencionados anteriormente?

Answer 1

En primer lugar, la base de Gröbner no es escasa. Estoy hablando un poco a destiempo, pero empíricamente cuando pido a SAGE la base de Gröbner de $(y^n-1,xy+x+1)$ en el ring $\mathbb{Q}[x,y]$ se pone cada vez peor a medida que $n$ aumenta. Cualquier límite tendría que ser en términos de los grados de los generadores originales, así como de su escasez, y sospecho que el panorama general es malo.

En general, tus preguntas juegan con las debilidades de las bases de Gröbner. Necesitarías nuevas ideas para hacer estables numéricamente no sólo los cálculos de las bases, sino también la respuesta real. También necesitarías nuevas ideas para hacer que las bases de Gröbner sean escasas.

Probablemente sea mejor utilizar tres ideas estándar del análisis numérico: Dividir y vencer, perseguir ceros con una EDO y el método de Newton. Si tienes los generadores de la variedad en una forma polinómica explícita, entonces estás mucho mejor que muchos usos de estos métodos que implican funciones trascendentales desordenadas. Porque puedes usar límites de análisis estándar, específicamente acotar las normas de las derivadas, para establecer rigurosamente una escala para cambiar entre dividir y conquistar y el método de Newton, por ejemplo. Además, puedes subdividir el espacio de forma adaptativa; las normas de las derivadas pueden permitirte detenerte mucho más rápido cuando estás lejos de la variedad.

---

Para explicar lo que quiero decir con los límites de la derivada, imagina para simplificar encontrar un cero de un polinomio en el intervalo unitario $[0,1]$ . Si el polinomio es $100-x-x^5$ entonces una simple derivada muestra que no tiene ceros. Si el polinomio es $40-100x+x^5$ Entonces, una simple derivada muestra que tiene un único cero y el método de Newton debe converger en todas partes dentro del intervalo. Si el polinomio es algo mucho más complicado como $1-x+x^5$ , entonces se puede subdividir el intervalo y eventualmente los límites de la derivada se vuelven verdaderos. También, con los polinomios, puedes hacer límites para saber que no hay ceros en un intervalo infinito bajo condiciones adecuadas.

Se puede hacer algo parecido en dimensiones superiores. Puedes dividir el espacio en cajas rectangulares, y sólo medianas subdivisiones. No es muy elegante, pero funciona bastante bien en dimensiones bajas. En dimensiones altas, todo el problema puede ser intratable; necesitas decir algo sobre por qué crees que el lugar de la solución se comporta bien para saber qué algoritmo es adecuado.

Answer 2

Deberías mirar los métodos (numéricos) de continuación de homotopía, que utilizan el seguimiento de la ODE y los métodos de Newton mencionados en la respuesta de Greg. Deberían funcionar mejor con datos inexactos que los métodos de las bases de Groebner. Está implementado en CAS Macaulay 2. También, la "continuación de homotopía poliédrica" explota la escasez de su sistema (implementado en PHCpack).

Las bases de Groebner tienen un límite de grado doblemente exponencial, y éste es ajustado.

Tanto las bases de Groebner como la continuación de homotopía te darán soluciones COMPLEJAS. Tú has pedido soluciones reales, lo cual es un mundo completamente distinto. Busca un método para calcular radicales reales utilizando métodos de momento.

Answer 3

Según la siguiente referencia, el algoritmo de Buchberger es generalmente inestable bajo pequeños cambios de los coeficientes del sistema, por lo que no puede ser ejecutado en aritmética de punto flotante o con datos de entrada inexactos. El documento introduce una base de Gröbner extendida para tratar de resolver el problema. véase lo siguiente:

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

Answer 4

En cuanto a sus preguntas 1 y 4, también debería echar un vistazo a las bases fronterizas:

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