Geometría algebraica numérica

La geometría algebraica numérica es un campo de las matemáticas computacionales , en particular la geometría algebraica computacional , que utiliza métodos del análisis numérico para estudiar y manipular las soluciones de sistemas de ecuaciones polinómicas . ^{[ 1 ] [ 2 ] [ 3 ]}

El método computacional principal utilizado en geometría algebraica numérica es la continuación homotópica, en la que se establece una homotopía entre dos sistemas polinómicos y las soluciones aisladas (puntos) de uno se extienden al otro. Este es un método especializado del método más general de continuación numérica .

Dejar${\displaystyle z}$representan las variables del sistema. Por abuso de notación, y para facilitar el espectro de espacios ambientales sobre los que se puede resolver el sistema, no utilizamos notación vectorial para${\displaystyle z}$De forma similar ocurre con los sistemas polinomiales.${\displaystyle f}$y${\displaystyle g}$.

La notación canónica actual llama al sistema de inicio${\displaystyle g}$y el sistema objetivo, es decir, el sistema a resolver,${\displaystyle f}$. ^{[ 4 ] [ 5 ]} Una homotopía muy común, la homotopía de línea recta, entre${\displaystyle f}$y${\displaystyle g}$es $${\displaystyle H(z,t)=(1-t)f(z)+tg(z).}$$

En la homotopía anterior, se comienza la variable de trayectoria en${\displaystyle t_{\text{inicio}}=1}$y continúa hacia${\displaystyle t_{\text{fin}}=0}$Otra opción común es huir de${\displaystyle 0}$a${\displaystyle 1}$En principio, la elección es completamente arbitraria. En la práctica, con respecto a los métodos de final de juego para calcular soluciones singulares usando continuación homotópica, el tiempo objetivo es${\displaystyle 0}$puede facilitar significativamente el análisis, por lo que aquí se adopta esta perspectiva. ^{[ 6 ]}

Independientemente de la elección de las horas de inicio y de llegada, el${\displaystyle H}$debe formularse de tal manera que${\displaystyle H(z,t_{\text{inicio}})=g(z)}$, y${\displaystyle H(z,t_{\text{end}})=f(z)}$.

Uno tiene la opción de elegir${\displaystyle g(z)}$, incluido

• Raíces de la unidad
• Grado total
• Poliédrico
• Multihomogéneo

y más allá de estos, sistemas de inicio específicos que reflejan fielmente la estructura de${\displaystyle f}$pueden formarse para sistemas particulares. La elección del sistema inicial afecta el tiempo de cálculo que se tarda en resolverlo.${\displaystyle f}$En este sentido, los métodos fáciles de formular (como el grado total) tienden a tener un mayor número de rutas que rastrear, mientras que los que requieren un esfuerzo considerable (como el método poliédrico) son mucho más precisos. Actualmente, no existe una buena manera de predecir cuál permitirá resolver el problema en el menor tiempo.

La continuación real se realiza normalmente mediante métodos predictor-corrector , con características adicionales según se implementen. La predicción se realiza mediante un método predictor de ecuaciones diferenciales ordinarias estándar , como Runge-Kutta , y la corrección suele emplear la iteración de Newton-Raphson.

Porque${\displaystyle f}$y${\displaystyle g}$son polinomiales, la continuación homotópica en este contexto está teóricamente garantizada para calcular todas las soluciones de${\displaystyle f}$Esto se debe al teorema de Bertini . Sin embargo, esta garantía no siempre se cumple en la práctica, debido a problemas derivados de las limitaciones de la informática moderna, principalmente la precisión finita. Es decir, a pesar de la solidez del argumento de probabilidad 1 que sustenta esta teoría, sin utilizar métodos de seguimiento previamente certificados, algunas trayectorias pueden no seguirse a la perfección por diversas razones.

Un testigo establecido ${\displaystyle W}$es una estructura de datos utilizada para describir variedades algebraicas . El conjunto testigo para una variedad afín que es equidimensional consta de tres piezas de información. La primera pieza de información es un sistema de ecuaciones${\displaystyle F}$Estas ecuaciones definen la variedad algebraica.${\displaystyle {\mathbf {V} }(F)}$que se está estudiando. La segunda información es un espacio lineal.${\displaystyle {\mathcal {L}}}$. La dimensión de${\displaystyle {\mathcal {L}}}$es la codimensión de${\displaystyle {\mathbf {V} }(F)}$y elegido para intersecarse${\displaystyle {\mathbf {V} }(F)}$transversalmente. La tercera información es la lista de puntos en la intersección.${\displaystyle {\mathcal {L}}\cap {\mathbf {V} }(F)}$Esta intersección tiene un número finito de puntos y el número de puntos es el grado de la variedad algebraica.${\displaystyle {\mathbf {V} }(F)}$Así, los conjuntos testigo codifican la respuesta a las dos primeras preguntas que se plantean sobre una variedad algebraica: ¿Cuál es su dimensión y cuál es su grado? Los conjuntos testigo también permiten realizar una descomposición numérica irreducible, pruebas de pertenencia a componentes y muestreo de componentes. Esto convierte a los conjuntos testigo en una buena descripción de una variedad algebraica.

Las soluciones a sistemas polinomiales calculadas mediante métodos geométricos algebraicos numéricos pueden certificarse , lo que significa que la solución aproximada es "correcta". Esto puede lograrse de varias maneras, ya sea a priori utilizando un rastreador certificado, ^{[ 7 ] [ 8 ]} o a posteriori demostrando que el punto se encuentra, por ejemplo, en la cuenca de convergencia del método de Newton. ^{[ 9 ]}

Varios paquetes de software implementan partes del cuerpo teórico de la geometría algebraica numérica. Estos incluyen, en orden alfabético:

• alphaCertified ^{[ 9 ]}
• Bertini ^{[ 5 ]}
• Hom4PS ^{[ 10 ] [ 11 ]}
• HomotopyContinuation.jl ^{[ 12 ]}
• Macaulay2 (implementación principal del seguimiento de homotopía y paquete NumericalAlgebraicGeometry^{[ 3 ] )}
• MiNuS : Marco de trabajo C++ optimizado para la continuación homotópica rápida. El solucionador más rápido hasta la fecha para ciertos problemas cuadrados de 100 a 320 grados.
• PHCPack ^{[ 13 ]}

• Página principal de Bertini
• Hom4PS-3
• HomotopíaContinuación.jl
• MiNuS, framework rápido de C++