Sistema de ecuaciones polinómicas

Un sistema de ecuaciones polinómicas (a veces simplemente un sistema polinómico ) es un conjunto de ecuaciones simultáneas $f 1 = 0, ..., f h = 0$ donde las $f i$ son polinomios en varias variables, digamos $x 1, ..., x n$ , sobre algún campo $k$ .

Una solución de un sistema polinómico es un conjunto de valores para los $xᵢ$ que pertenecen a alguna extensión de cuerpo $K$ $de$ k $,$ algebraicamente cerrada , y que hacen que todas las ecuaciones sean verdaderas. Cuando $k$ es el cuerpo de los números racionales , generalmente se asume que $K$ es el cuerpo de los números complejos , porque cada solución pertenece a una extensión de cuerpo de $k$ , que es isomorfa a un subcuerpo de los números complejos.

Este artículo trata sobre los métodos para resolver problemas, es decir, encontrar todas las soluciones o describirlas. Dado que estos métodos están diseñados para ser implementados en una computadora, se hace hincapié en los campos $k$ en los que el cálculo (incluida la comprobación de igualdad) es fácil y eficiente, es decir, el campo de los números racionales y los campos finitos .

La búsqueda de soluciones que pertenezcan a un conjunto específico es un problema generalmente mucho más difícil, y queda fuera del alcance de este artículo, salvo en el caso de las soluciones en un cuerpo finito dado. Para el caso de soluciones cuyos componentes son todos números enteros o racionales, véase la ecuación diofántica .

Definición

Los numerosos puntos singulares del sexto de Barth son las soluciones de un sistema polinómico.

Un ejemplo sencillo de un sistema de ecuaciones polinómicas es

{\begin{aligned}x^{2}+y^{2}-5&=0\\xy-2&=0.\end{aligned}}

Sus soluciones son los cuatro pares $(x, y) = (1, 2), (2, 1), (-1, -2), (-2, -1)$ . Estas soluciones se pueden comprobar fácilmente mediante sustitución, pero se necesita más trabajo para demostrar que no existen otras soluciones.

El objeto de este artículo es el estudio de generalizaciones de dichos ejemplos y la descripción de los métodos que se utilizan para calcular las soluciones.

Un sistema de ecuaciones polinómicas, o sistema polinómico, es una colección de ecuaciones.

{\begin{aligned}f_{1}\left(x_{1},\ldots ,x_{m}\right)&=0\\&\;\;\vdots \\f_{n}\left(x_{1},\ldots ,x_{m}\right)&=0,\end{aligned}}

donde cada $f h$ es un polinomio en las indeterminadas $x 1, ..., x m$ , con coeficientes enteros , o coeficientes en algún campo fijo , a menudo el campo de los números racionales o un campo finito . ^{[ 1 ]} Otros campos de coeficientes, como los números reales , se utilizan con menos frecuencia, ya que sus elementos no pueden representarse en una computadora (solo se pueden usar aproximaciones de números reales en los cálculos, y estas aproximaciones son siempre números racionales).

Una solución de un sistema polinómico es una tupla de valores $(x₁, ..., xᵐ)$ que satisface todas las ecuaciones del sistema. Las soluciones se buscan en los números complejos , o más generalmente en un cuerpo $algebraicamente$ cerrado que contenga los coeficientes. En particular, en característica cero , se buscan todas las soluciones complejas . La búsqueda de soluciones reales o racionales son problemas mucho más difíciles que no se abordan en este artículo.

El conjunto de soluciones no siempre es finito; por ejemplo, las soluciones del sistema

{\begin{aligned}x(x-1)&=0\\x(y-1)&=0\end{aligned}}

son un punto $(x, y) = (1,1)$ y una línea $x = 0$ . ^{[ 2 ]} Incluso cuando el conjunto de soluciones es finito, en general no hay una expresión de forma cerrada de las soluciones (en el caso de una sola ecuación, este es el teorema de Abel-Ruffini ).

La superficie de Barth , mostrada en la figura, es la representación geométrica de las soluciones de un sistema polinómico reducido a una única ecuación de grado 6 en 3 variables. Algunos de sus numerosos puntos singulares son visibles en la imagen. Estos son las soluciones de un sistema de 4 ecuaciones de grado 5 en 3 variables. Un sistema sobredeterminado de este tipo no tiene solución en general (siempre que los coeficientes no sean específicos). Si tiene un número finito de soluciones, este número es como máximo $5³ = 125,$ según el teorema de Bézout . Sin embargo, se ha demostrado que, para el caso de los puntos singulares de una superficie de grado 6, el número máximo de soluciones es 65, y se alcanza con la superficie de Barth.

Propiedades básicas y definiciones

Un sistema es sobredeterminado si el número de ecuaciones es mayor que el número de variables. Un sistema es inconsistente si no tiene solución compleja (o, si los coeficientes no son números complejos, no tiene solución en un cuerpo algebraicamente cerrado que contenga los coeficientes). Según el teorema de los ceros de Hilbert, esto significa que 1 es una combinación lineal (con polinomios como coeficientes) de los primeros términos de las ecuaciones. La mayoría $,$ pero no todos, los sistemas sobredeterminados, cuando se construyen con coeficientes aleatorios, son inconsistentes. Por ejemplo, el sistema $x³ - 1 = 0, x² - 1 = 0$ es sobredeterminado (tiene dos ecuaciones pero solo una incógnita), pero no es inconsistente ya que tiene la solución $x = 1$ .

Un sistema es subdeterminado si el número de ecuaciones es menor que el número de variables. Un sistema subdeterminado es inconsistente o tiene infinitas soluciones complejas (o soluciones en un cuerpo algebraicamente cerrado que contiene los coeficientes de las ecuaciones). Este es un resultado no trivial del álgebra conmutativa que involucra, en particular, el teorema de los ceros de Hilbert y el teorema del ideal principal de Krull .

Un sistema es cero-dimensional si tiene un número finito de soluciones complejas (o soluciones en un cuerpo algebraicamente cerrado). Esta terminología proviene del hecho de que la variedad algebraica de las soluciones tiene dimensión cero. Un sistema con infinitas soluciones se denomina de dimensión positiva .

$Se dice a veces que$ un sistema cero-dimensional con tantas ecuaciones como variables es bien comportado . ^{[ 3 ]} El teorema de Bézout afirma que un sistema bien comportado cuyas ecuaciones tienen grados $d₁ , ..., dₙ$ tiene como máximo $d₁ ... dₙ soluciones . Esta$ cota es óptima. Si todos los grados son iguales a $d$ , esta cota se convierte en $dₙ$ $y$ es exponencial en el número de variables. (El teorema fundamental del álgebra es el caso especial $n = 1$ ).

Este comportamiento exponencial dificulta la resolución de sistemas polinómicos y explica por qué existen pocos solucionadores capaces de resolver automáticamente sistemas con un límite de Bézout superior a, por ejemplo, 25 (tres ecuaciones de grado 3 o cinco ecuaciones de grado 2 superan este límite).

¿Qué es lo que se está resolviendo?

Lo primero que hay que hacer para resolver un sistema polinómico es determinar si es inconsistente, cero-dimensional o de dimensión positiva. Esto se puede hacer calculando una base de Gröbner de los segundos miembros de las ecuaciones. El sistema es inconsistente si esta base de Gröbner se reduce a 1. El sistema es cero-dimensional si, para cada variable, existe un monomio principal de algún elemento de la base de Gröbner que es una potencia pura de dicha variable. Para esta prueba, el mejor orden de monomios (es decir, el que generalmente conduce al cálculo más rápido) suele ser el orden lexicográfico inverso graduado (grevlex).

Si el sistema es de dimensión positiva , tiene infinitas soluciones. Por lo tanto, no es posible enumerarlas. En consecuencia, en este caso, resolverlo puede significar simplemente "encontrar una descripción de las soluciones a partir de la cual sea fácil extraer las propiedades relevantes de las mismas". No existe una descripción de este tipo comúnmente aceptada. De hecho, existen muchas "propiedades relevantes" diferentes, que abarcan casi todos los subcampos de la geometría algebraica .

Un ejemplo natural de este tipo de problema en sistemas de dimensión positiva es el siguiente: determinar si un sistema polinómico sobre los números racionales tiene un número finito de soluciones reales y calcularlas . Una generalización de este problema consiste en encontrar al menos una solución en cada componente conexa del conjunto de soluciones reales de un sistema polinómico . El algoritmo clásico para resolver este problema es la descomposición algebraica cilíndrica , que tiene una complejidad computacional doblemente exponencial y, por lo tanto, no puede utilizarse en la práctica, salvo en ejemplos muy pequeños.

Para sistemas de dimensión cero, la resolución consiste en calcular todas las soluciones. Existen dos maneras diferentes de obtener las soluciones. La más común, posible solo para soluciones reales o complejas, consiste en obtener aproximaciones numéricas de las soluciones. Dicha solución se denomina numérica . Una solución se certifica si se proporciona una cota para el error de las aproximaciones y si esta cota separa las diferentes soluciones.

La otra forma de representar las soluciones se denomina algebraica . Se basa en el hecho de que, para un sistema cero-dimensional, las soluciones pertenecen a la clausura algebraica del cuerpo k de los coeficientes del sistema. Existen varias formas de representar la solución en una clausura algebraica, las cuales se describen a continuación. Todas ellas permiten calcular una aproximación numérica de las soluciones resolviendo una o varias ecuaciones univariadas. Para este cálculo, es preferible utilizar una representación que implique resolver un solo polinomio univariado por solución, ya que calcular las raíces de un polinomio con coeficientes aproximados es un problema altamente inestable .

Extensiones

ecuaciones trigonométricas

Una ecuación trigonométrica es una ecuación $g = 0$ donde $g$ es un polinomio trigonométrico . Dicha ecuación se puede convertir en un sistema polinómico expandiendo los senos y cosenos en ella (usando fórmulas de suma y diferencia $)$ , reemplazando $sin(x)$ y $cos(x)$ por dos nuevas variables $s$ y $c$ y agregando la nueva ecuación $s² + c² - 1 = 0$ .

Por ejemplo, debido a la identidad

\cos(3x)=4\cos ^{3}(x)-3\cos(x),

resolver la ecuación

\sin ^{3}(x)+\cos(3x)=0

es equivalente a resolver el sistema polinómico

{\begin{cases}s^{3}+4c^{3}-3c&=0\\s^{2}+c^{2}-1&=0.\end{cases}}

Para cada solución $(c 0, s 0)$ de este sistema, existe una solución única $x$ de la ecuación tal que $0 \leq x < 2 π$ .

En este ejemplo sencillo, puede resultar confuso determinar si el sistema es más fácil de resolver que la ecuación. En ejemplos más complejos, no se dispone de métodos sistemáticos para resolver directamente la ecuación, mientras que existen programas informáticos para resolver automáticamente el sistema correspondiente.

Soluciones en un campo finito

Al resolver un sistema sobre un cuerpo finito $k$ con $q$ elementos, uno está interesado principalmente en las soluciones en $k$ . Como los elementos de $k$ son exactamente las soluciones de la ecuación $x q - x = 0$ , basta, para restringir las soluciones a $k$ , con agregar la ecuación $x i q - x i = 0$ para cada variable $x$ $i$ .

Coeficientes en un cuerpo numérico o en un cuerpo finito de orden no primo.

Los elementos de un cuerpo numérico algebraico se representan habitualmente como polinomios en un generador del cuerpo que satisface alguna ecuación polinómica univariada. Para trabajar con un sistema polinómico cuyos coeficientes pertenecen a un cuerpo numérico, basta con considerar este generador como una nueva variable y añadir su ecuación a las ecuaciones del sistema. De este modo, resolver un sistema polinómico sobre un cuerpo numérico se reduce a resolver otro sistema sobre los números racionales.

Por ejemplo, si un sistema contiene ${\sqrt {2}}$ , se obtiene un sistema sobre los números racionales sumando la ecuación $r 22 - 2 = 0$ y reemplazando ${\sqrt {2}}$ por $r 2$ en las otras ecuaciones.

En el caso de un campo finito, la misma transformación permite suponer siempre que el campo $k$ tiene un orden primo.

Representación algebraica de las soluciones

Cadenas regulares

La forma habitual de representar las soluciones es mediante cadenas regulares de dimensión cero. Dicha cadena consiste en una secuencia de polinomios $f 1 (x 1)$ , $f 2 (x 1, x 2)$ , ..., $f n (x 1, ..., x n)$ tales que, para cada $i$ tal que $1 \leq i \leq n$

$f i$ es un polinomio en $x 1, ..., x i$ solamente, que tiene un grado $d i > 0$ en $x i$ ;
El coeficiente de $x i d i$ en $f i$ es un polinomio en $x 1, ..., x i -1$ que no tiene ningún cero común con $f 1$ , ..., $f i - 1$ .

A dicha cadena regular se le asocia un sistema triangular de ecuaciones.

{\begin{cases}f_{1}(x_{1})=0\\f_{2}(x_{1},x_{2})=0\\\quad \vdots \\f_{n}(x_{1},x_{2},\ldots ,x_{n})=0.\end{cases}}

Las soluciones de este sistema se obtienen resolviendo la primera ecuación univariada, sustituyendo las soluciones en las demás ecuaciones, luego resolviendo la segunda ecuación, que ahora es univariada, y así sucesivamente. La definición de cadenas regulares implica que la ecuación univariada obtenida a partir de $f i$ tiene grado $d i$ y, por lo tanto, que el sistema tiene $d 1 ... d n$ soluciones, siempre que no haya raíces múltiples en este proceso de resolución ( teorema fundamental del álgebra ).

Todo sistema de ecuaciones polinómicas de dimensión cero es equivalente (es decir, tiene las mismas soluciones) a un número finito de cadenas regulares. Pueden ser necesarias varias cadenas regulares, como ocurre en el siguiente sistema, que tiene tres soluciones.

{\begin{cases}x^{2}-1=0\\(x-1)(y-1)=0\\y^{2}-1=0.\end{cases}}

Existen varios algoritmos para calcular una descomposición triangular de un sistema polinomial arbitrario (no necesariamente de dimensión cero) ^{[ 4 ]} en cadenas regulares (o sistemas semialgebraicos regulares ).

También existe un algoritmo específico para el caso cero-dimensional que, en este caso, compite con los algoritmos directos. Consiste en calcular primero la base de Gröbner para el orden lexicográfico inverso graduado (grevlex) , luego deducir la base de Gröbner lexicográfica mediante el algoritmo FGLM ^{[ 5 ]} y, finalmente, aplicar el algoritmo Lextriangular ^{[ 6 ] .}

Esta representación de las soluciones resulta muy conveniente para coeficientes en un campo finito. Sin embargo, para coeficientes racionales, hay que tener en cuenta dos aspectos:

El resultado puede contener números enteros muy grandes, lo que puede dificultar el cálculo y el uso del resultado.
Para deducir los valores numéricos de las soluciones a partir de la salida, hay que resolver polinomios univariados con coeficientes aproximados, lo cual es un problema altamente inestable.

El primer problema fue resuelto por Dahan y Schost: ^{[ 7 ]}^{[ 8 ]} Entre los conjuntos de cadenas regulares que representan un conjunto dado de soluciones, existe un conjunto cuyos coeficientes están explícitamente acotados en función del tamaño del sistema de entrada, con una cota casi óptima. Este conjunto, denominado descomposición equiprojectable , depende únicamente de la elección de las coordenadas. Esto permite el uso de métodos modulares para calcular eficientemente la descomposición equiprojectable. ^{[ 9 ]}

El segundo problema se resuelve generalmente generando cadenas regulares de una forma especial, a veces llamada lema de forma , para las cuales todos $los d i$ excepto el primero son iguales a $1.$ Para obtener dichas cadenas regulares, puede ser necesario agregar una variable adicional, llamada variable separadora , a la que se le asigna el índice $0.$ La representación univariada racional , descrita a continuación, permite calcular una cadena regular especial de este tipo, que satisface la cota de Dahan-Schost, partiendo de una cadena regular o de una base de Gröbner.

Representación univariada racional

La representación univariada racional o RUR es una representación de las soluciones de un sistema polinómico cero-dimensional sobre los números racionales que fue introducida por F. Rouillier. ^{[ 10 ]}

Una RUR de un sistema cero-dimensional consiste en una combinación lineal $x 0$ de las variables, llamada variable separadora , y un sistema de ecuaciones ^{[ 11 ].}

{\begin{cases}h(x_{0})=0\\x_{1}=g_{1}(x_{0})/g_{0}(x_{0})\\\quad \vdots \\x_{n}=g_{n}(x_{0})/g_{0}(x_{0}),\end{cases}}

donde $h$ es un polinomio univariado en $x 0$ de grado $D$ y $g 0, ..., g n$ son polinomios univariados en $x 0$ de grado menor que $D$ .

Dado un sistema polinómico cero-dimensional sobre los números racionales, la RUR tiene las siguientes propiedades.

Salvo un número finito de combinaciones lineales de las variables, todas ellas son variables separadoras.
Cuando se elige la variable de separación, la RUR existe y es única. En particular, $h$ y $g i$ se definen independientemente de cualquier algoritmo para calcularlas.
Las soluciones del sistema están en correspondencia biunívoca con las raíces de $h$ y la multiplicidad de cada raíz de $h$ es igual a la multiplicidad de la solución correspondiente.
Las soluciones del sistema se obtienen sustituyendo las raíces de $h$ en las demás ecuaciones.
Si $h$ no tiene ninguna raíz múltiple, entonces $g 0$ es la derivada de $h$ .

Por ejemplo, para el sistema de la sección anterior, cada combinación lineal de la variable, excepto los múltiplos de $x$ , $y$ y $x + y$ , es una variable separadora. Si se elige $t = ⁠ x - y / 2 ⁠$ como variable separadora, entonces la RUR es

{\begin{cases}t^{3}-t=0\\x={\frac {t^{2}+2t-1}{3t^{2}-1}}\\y={\frac {t^{2}-2t-1}{3t^{2}-1}}.\\\end{cases}}

La RUR se define de forma única para una variable separadora dada, independientemente de cualquier algoritmo, y conserva las multiplicidades de las raíces. Esta es una diferencia notable con las descomposiciones triangulares (incluso la descomposición equiprojectable), que, en general, no conservan las multiplicidades. La RUR comparte con la descomposición equiprojectable la propiedad de producir un resultado con coeficientes de tamaño relativamente pequeño.

Para sistemas de dimensión cero, el método RUR permite recuperar los valores numéricos de las soluciones resolviendo un único polinomio univariado y sustituyéndolos en funciones racionales . Esto permite obtener aproximaciones certificadas de las soluciones con cualquier precisión.

Además, el polinomio univariado $h (x₀)$ de la RUR puede factorizarse, lo que proporciona una RUR para cada factor irreducible. Esto ofrece la descomposición prima del ideal dado (es decir, la $descomposición$ primaria del radical del ideal). En la práctica, esto proporciona un resultado con coeficientes mucho menores, especialmente en el caso de sistemas con multiplicidades elevadas.

A diferencia de las descomposiciones triangulares y las descomposiciones equiprojectables, la RUR no se define en dimensión positiva.

Resolver numéricamente

Algoritmos generales de resolución

Los algoritmos numéricos generales, diseñados para cualquier sistema de ecuaciones no lineales, también funcionan para sistemas polinómicos. Sin embargo, generalmente se prefieren los métodos específicos, ya que los generales no suelen permitir encontrar todas las soluciones. En particular, cuando un método general no encuentra ninguna solución, esto no suele indicar que no exista ninguna.

Sin embargo, cabe mencionar aquí dos métodos.

El método de Newton puede utilizarse si el número de ecuaciones es igual al número de variables. No permite hallar todas las soluciones ni demostrar que no existe ninguna. Sin embargo, es muy rápido cuando se parte de un punto cercano a una solución. Por lo tanto, constituye una herramienta fundamental para el método de continuación homotópica que se describe a continuación.
La optimización se utiliza raramente para resolver sistemas polinómicos, pero alrededor de 1970 logró demostrar que un sistema de 81 ecuaciones cuadráticas con 56 variables no es inconsistente. ^{[ 12 ]} Con los demás métodos conocidos, esto sigue estando fuera del alcance de la tecnología moderna, a fecha de 2022.Este método consiste simplemente en minimizar la suma de los cuadrados de las ecuaciones. Si se encuentra un mínimo local igual a cero, entonces se alcanza en una solución. Este método funciona para sistemas sobredeterminados, pero no produce información si todos los mínimos locales encontrados son positivos.

Método de continuación homotópica

Este es un método seminumérico que supone que el número de ecuaciones es igual al número de variables. Este método es relativamente antiguo, pero ha mejorado notablemente en las últimas décadas. ^{[ 13 ]}

Este método se divide en tres pasos. Primero se calcula una cota superior para el número de soluciones. Esta cota debe ser lo más precisa posible. Por lo tanto, se calcula mediante, al menos, cuatro métodos diferentes y el mejor valor, digamos $N$ , se conserva.

En el segundo paso, un sistema $g_{1}=0,\,\ldots ,\,g_{n}=0$ Se genera un conjunto de ecuaciones polinómicas que tiene exactamente $N$ soluciones que son fáciles de calcular. Este nuevo sistema tiene el mismo número $n$ de variables y el mismo número $n$ de ecuaciones y la misma estructura general que el sistema a resolver, $f_{1}=0,\,\ldots ,\,f_{n}=0$ .

Luego se considera una homotopía entre los dos sistemas. Consiste, por ejemplo, en la línea recta entre los dos sistemas, pero se pueden considerar otros caminos, en particular para evitar algunas singularidades en el sistema.

(1-t)g_{1}+tf_{1}=0,\,\ldots ,\,(1-t)g_{n}+tf_{n}=0

.

La continuación homotópica consiste en deformar el parámetro $t$ de 0 a 1 y siguiendo el $N$ soluciones durante esta deformación. Esto proporciona las soluciones deseadas para $t=1$ . Lo siguiente significa que, si $t_{1}<t_{2}$ , las soluciones para $t=t_{2}$ se deducen de las soluciones para $t=t_{1}$ por el método de Newton. La dificultad aquí radica en elegir bien el valor de $t_{2}-t_{1}:$ Si el tamaño es demasiado grande, la convergencia del método de Newton puede ser lenta e incluso puede saltar de una solución a otra. Si es demasiado pequeño, el número de pasos ralentiza el método.

Resolución numérica a partir de la representación univariada racional

Deducir los valores numéricos de las soluciones de una ecuación diferencial recurrente parece sencillo: basta con calcular las raíces del polinomio univariado y sustituirlas en las demás ecuaciones. Sin embargo, esto no es tan fácil, ya que la evaluación de un polinomio en las raíces de otro polinomio es altamente inestable.

Por lo tanto, las raíces del polinomio univariado deben calcularse con alta precisión, la cual no siempre se define de una sola vez. Existen dos algoritmos que cumplen con este requisito.

El método de Aberth , implementado en MPSolve , calcula todas las raíces complejas con cualquier precisión.
El algoritmo de Uspensky de Collins y Akritas ^{[ 14 ]} , mejorado por Rouillier y Zimmermann ^{[ 15 ]} y basado en la regla de los signos de Descartes , calcula las raíces reales, aisladas en intervalos de ancho arbitrariamente pequeño. Está implementado en Maple (funciones fsolve y RootFinding[Isolate] ).

Paquetes de software

Existen al menos cuatro paquetes de software capaces de resolver sistemas de dimensión cero automáticamente (por automático, se entiende que no se requiere intervención humana entre la entrada y la salida, y por lo tanto, que el usuario no necesita conocer el método). También existen otros paquetes de software que pueden ser útiles para resolver sistemas de dimensión cero. Algunos de ellos se enumeran después de los solucionadores automáticos.

La función RootFinding[Isolate] de Maple toma como entrada cualquier sistema polinómico sobre los números racionales (si algunos coeficientes son números de coma flotante , se convierten a números racionales) y devuelve las soluciones reales representadas (opcionalmente) como intervalos de números racionales o como aproximaciones de coma flotante de precisión arbitraria. Si el sistema no es de dimensión cero, se indica como un error.

Internamente, este solucionador, diseñado por F. Rouillier, calcula primero una base de Gröbner y luego una representación univariada racional, a partir de la cual se deduce la aproximación requerida de las soluciones. Funciona de forma rutinaria para sistemas con hasta varios cientos de soluciones complejas.

La representación univariada racional se puede calcular con la función Groebner[RationalUnivariateRepresentation] de Maple .

Para extraer todas las soluciones complejas de una representación univariada racional, se puede utilizar MPSolve , que calcula las raíces complejas de polinomios univariados con cualquier precisión. Se recomienda ejecutar MPSolve varias veces, duplicando la precisión en cada iteración, hasta que las soluciones se estabilicen, ya que la sustitución de las raíces en las ecuaciones de las variables de entrada puede ser muy inestable.

El segundo solucionador es PHCpack, ^{[ 13 ]}^{[ 16 ]} escrito bajo la dirección de J. Verschelde. PHCpack implementa el método de continuación homotópica. Este solucionador calcula las soluciones complejas aisladas de sistemas polinomiales con tantas ecuaciones como variables.

El tercer solucionador es Bertini, ^{[ 17 ]}^{[ 18 ]} escrito por DJ Bates, JD Hauenstein, AJ Sommese y CW Wampler. Bertini utiliza la continuación homotópica numérica con precisión adaptativa. Además de calcular conjuntos de soluciones de dimensión cero, tanto PHCpack como Bertini son capaces de trabajar con conjuntos de soluciones de dimensión positiva.

El cuarto solucionador es la biblioteca RegularChains de Maple , escrita por Marc Moreno-Maza y colaboradores. Contiene varias funciones para resolver sistemas polinomiales mediante cadenas regulares .

Véase también

Referencias

↑ Bates et al. 2013 , pág. 4
↑ Bates et al. 2013 , pág. 8
↑ Songxin Liang, J. Gerhard, DJ Jeffrey, G. Moroz, Un paquete para resolver sistemas polinomiales paramétricos . Communications in Computer Algebra (2009)
↑ Aubry, P.; Maza, M. Moreno (1999). "Conjuntos triangulares para resolver sistemas polinomiales: una implementación comparativa de cuatro métodos" . J. Symb. Comput . 28 ( 1–2 ): 125–154 . doi : 10.1006/jsco.1999.0270 .
↑ Faugère, JC; Gianni, P. ; Lazard, D.; Mora, T. (1993). "Cálculo eficiente de bases de Gröbner de dimensión cero mediante cambio de orden" . Journal of Symbolic Computation . 16 (4): 329– 344. doi : 10.1006/jsco.1993.1051 .
↑ Lazard, D. (1992). "Resolución de sistemas algebraicos cero-dimensionales". Journal of Symbolic Computation . 13 (2): 117– 131. doi : 10.1016/S0747-7171(08)80086-7 .
↑ Xavier Dahan y Eric Schost. Estimaciones precisas para conjuntos triangulares . Además, algoritmos recientes para descomponer sistemas polinomiales en descomposiciones triangulares producen cadenas regulares con coeficientes que coinciden con los resultados de Dahan y Schost. En actas de ISSAC'04, páginas 103-110, ACM Press, 2004.
↑ Dahan, Xavier; Moreno Maza, Marc; Schost, Eric; Wu, Wenyuan; Xie, Yuzhen (2005). "Técnicas de elevación para descomposiciones triangulares" (PDF) . Actas de ISAAC 2005. ACM Press. págs. 108–105 .
↑ Changbo Chen y Marc Moreno-Maza. Algoritmos para el cálculo de la descomposición triangular de sistemas polinomiales . En actas de ISSAC'2011, páginas 83-90, ACM Press, 2011 y Journal of Symbolic Computation (próxima publicación).
↑ Rouillier, Fabrice (1999). "Resolución de sistemas cero-dimensionales mediante la representación univariada racional". Appl. Algebra Eng. Commun. Comput . 9 (9): 433– 461. doi : 10.1007/s002000050114 . S2CID 25579305 .
↑ Saugata Basu; Richard Pollack; Marie-Françoise Roy (2006). Algoritmos en geometría algebraica real, capítulo 12.4 . Springer-Verlag .
↑ Lazard, Daniel (2009). "Treinta años de resolución de sistemas polinomiales, ¿y ahora?" . J. Symb. Comput . 44 (3): 2009. doi : 10.1016/j.jsc.2008.03.004 .
1 2 Verschelde, Jan (1999). "Algoritmo 795: PHCpack: Un solucionador de propósito general para sistemas polinomiales mediante continuación homotópica" (PDF) . ACM Transactions on Mathematical Software . 25 (2): 251– 276. doi : 10.1145/317275.317286 . S2CID 15485257 .
↑ George E. Collins y Alkiviadis G. Akritas, Aislamiento de raíces reales de polinomios mediante la regla de los signos de Descartes . Actas del Simposio ACM de 1976 sobre Computación Simbólica y Algebraica.
↑ Rouillier, F.; Zimmerman, P. (2004). "Aislamiento eficiente de las raíces reales de un polinomio" . Journal of Computational and Applied Mathematics . 162 (1): 33– 50. Bibcode : 2004JCoAM.162...33R . doi : 10.1016/j.cam.2003.08.015 .
↑ Versión 2.3.86 de PHCpack
↑ Bates et al. 2013
↑ Bertini: Software para geometría algebraica numérica

Bates, Daniel J.; Sommese, Andrew J.; Hauenstein, Jonathan D.; Wampler, Charles W. (2013). Resolución numérica de sistemas polinomiales con Bertini . Filadelfia: Society for Industrial and Applied Mathematics. ISBN 978-1-61197-269-6.
Cox, David ; Little, John ; O'Shea, Donal (1997). Ideales, variedades y algoritmos : una introducción a la geometría algebraica computacional y al álgebra conmutativa (2.ª ed.). Nueva York: Springer. ISBN 978-0387946801.
Morgan, Alexander (1987). Resolución de sistemas polinomiales mediante continuación para problemas de ingeniería y científicos ( ed. SIAM). Sociedad de Matemáticas Industriales y Aplicadas (SIAM, 3600 Market Street, Piso 6, Filadelfia, PA 19104). ISBN 9780898719031.
Sturmfels, Bernd (2002). Resolución de sistemas de ecuaciones polinómicas . Providence, RI: American Mathematical Soc. ISBN 0821832514.

[Bates_p4-1] Bates et al. 2013 , pág. 4

[2] Bates et al. 2013 , pág. 8

[3] Songxin Liang, J. Gerhard, DJ Jeffrey, G. Moroz, Un paquete para resolver sistemas polinomiales paramétricos . Communications in Computer Algebra (2009)

[4] Aubry, P.; Maza, M. Moreno (1999). "Conjuntos triangulares para resolver sistemas polinomiales: una implementación comparativa de cuatro métodos" . J. Symb. Comput . 28 ( 1–2 ): 125–154 . doi : 10.1006/jsco.1999.0270 .

[5] Faugère, JC; Gianni, P. ; Lazard, D.; Mora, T. (1993). "Cálculo eficiente de bases de Gröbner de dimensión cero mediante cambio de orden" . Journal of Symbolic Computation . 16 (4): 329– 344. doi : 10.1006/jsco.1993.1051 .

[6] Lazard, D. (1992). "Resolución de sistemas algebraicos cero-dimensionales". Journal of Symbolic Computation . 13 (2): 117– 131. doi : 10.1016/S0747-7171(08)80086-7 .

[7] Xavier Dahan y Eric Schost. Estimaciones precisas para conjuntos triangulares . Además, algoritmos recientes para descomponer sistemas polinomiales en descomposiciones triangulares producen cadenas regulares con coeficientes que coinciden con los resultados de Dahan y Schost. En actas de ISSAC'04, páginas 103-110, ACM Press, 2004.

[8] Dahan, Xavier; Moreno Maza, Marc; Schost, Eric; Wu, Wenyuan; Xie, Yuzhen (2005). "Técnicas de elevación para descomposiciones triangulares" (PDF) . Actas de ISAAC 2005. ACM Press. págs. 108–105 .

[9] Changbo Chen y Marc Moreno-Maza. Algoritmos para el cálculo de la descomposición triangular de sistemas polinomiales . En actas de ISSAC'2011, páginas 83-90, ACM Press, 2011 y Journal of Symbolic Computation (próxima publicación).

[10] Rouillier, Fabrice (1999). "Resolución de sistemas cero-dimensionales mediante la representación univariada racional". Appl. Algebra Eng. Commun. Comput . 9 (9): 433– 461. doi : 10.1007/s002000050114 . S2CID 25579305 .

[11] Saugata Basu; Richard Pollack; Marie-Françoise Roy (2006). Algoritmos en geometría algebraica real, capítulo 12.4 . Springer-Verlag .

[12] Lazard, Daniel (2009). "Treinta años de resolución de sistemas polinomiales, ¿y ahora?" . J. Symb. Comput . 44 (3): 2009. doi : 10.1016/j.jsc.2008.03.004 .

[Vers99-13] 1 2 Verschelde, Jan (1999). "Algoritmo 795: PHCpack: Un solucionador de propósito general para sistemas polinomiales mediante continuación homotópica" (PDF) . ACM Transactions on Mathematical Software . 25 (2): 251– 276. doi : 10.1145/317275.317286 . S2CID 15485257 .

[14] George E. Collins y Alkiviadis G. Akritas, Aislamiento de raíces reales de polinomios mediante la regla de los signos de Descartes . Actas del Simposio ACM de 1976 sobre Computación Simbólica y Algebraica.

[15] Rouillier, F.; Zimmerman, P. (2004). "Aislamiento eficiente de las raíces reales de un polinomio" . Journal of Computational and Applied Mathematics . 162 (1): 33– 50. Bibcode : 2004JCoAM.162...33R . doi : 10.1016/j.cam.2003.08.015 .

[16] Versión 2.3.86 de PHCpack

[17] Bates et al. 2013

[18] Bertini: Software para geometría algebraica numérica

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ] .

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ].

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]