Uso de bases de Gröbner y descomposición algebraica cilíndrica para resolver sistemas polinómicos reales

Estoy trabajando en un proyecto que consiste en resolver sistemas de ecuaciones polinómicas multivariadas sobre los reales (y encontrar sus soluciones reales). Suponiendo que un sistema tiene un número finito de soluciones complejas, los dos métodos principales que he encontrado para esta tarea involucran bases de Gröbner (calculadas usando el algoritmo de Buchberger) y descomposición algebraica cilíndrica (CAD). Para el cálculo real, planeamos usar Mathematica, pero esperaba aprender sobre las siguientes preguntas teóricas (ignorando la complejidad o la logística informática):

  1. Dado un sistema polinomial arbitrario sobre los reales, ¿se pueden usar las bases de Gröbner/CAD para encontrar todas las soluciones reales (en teoría)? Si no, ¿existen ciertas restricciones sobre el sistema que se pueden colocar para garantizar el retorno de todas las soluciones reales?

  2. ¿Podría el uso de cualquiera de los métodos producir un "falso positivo" (devolver algo que no es una solución)? Si esto está claro dadas las descripciones de cada método, puede ser útil cierta intuición de por qué.

  3. ¿Dónde puedo encontrar literatura o materiales del curso mediante los cuales pueda responder lo anterior?

Gracias por leer y por tu ayuda.

Ya existe una restricción para encontrar todas las soluciones reales de F ( X ) = 0 para un polinomio F en una sola variable. Si el grado de F es ≥ 5 , entonces no hay fórmula en general para las raíces.
@DietrichBurde Los polinomios de una variable generalmente se consideran una caja negra. En otras palabras, la solución se expresa en términos de números algebraicos juntos para los cuadros delimitadores que localizan el conjugado específico que necesita. Ningún radical necesita ser dañado.
@IgorRivin Sí, lo sé. Solo quería recordar esto.
¿Estás de acuerdo con mis ediciones?
Es posible que desee echar un vistazo a Verification and Synthesis Using Real Quantifier Elimination [PDF] de Sturm & Tiwari, que contiene algunos comentarios potencialmente interesantes sobre el rendimiento.

Respuestas (1)

La referencia estándar es

Basu, Saugata; Pollock, Richard; Roy, Marie-Françoise , Algoritmos en geometría algebraica real, Algoritmos y Computación en Matemáticas. 10. Berlín: Springer. viii, 602 pág. (2003). ZBL1031.14028 .

No, no se pueden encontrar falsos positivos, y sí, en teoría se puede encontrar toda la solución. En la práctica suele ser muy lento.

Uso de bases de Gröbner y descomposición algebraica cilíndrica para resolver sistemas polinómicos reales
RespuestasAquíPolítica de privacidad1y, 0v