En álgebra computacional , una descomposición triangular de un sistema polinomial S es un conjunto de sistemas polinomiales más simples S 1 , ..., S e tal que un punto es una solución de S si y solo si es una solución de uno de los sistemas S 1 , ..., S e .
Cuando el propósito es describir el conjunto solución de S en el cierre algebraico de su campo de coeficientes , esos sistemas más simples son cadenas regulares . Si los coeficientes de los sistemas polinomiales S 1 , ..., S e son números reales, entonces las soluciones reales de S se pueden obtener mediante una descomposición triangular en sistemas semi-algebraicos regulares . En ambos casos, cada uno de estos sistemas más simples tiene una forma triangular y propiedades notables, lo que justifica la terminología.
Historia
El método del conjunto de características es el primer algoritmo libre de factorización, que se propuso para descomponer una variedad algebraica en componentes equidimensionales. Además, el autor, Wen-Tsun Wu , realizó una implementación de este método e informó datos experimentales en su artículo pionero de 1987 titulado "Un teorema de estructura cero para la resolución de ecuaciones polinómicas". [1] Para poner este trabajo en contexto, recordemos cuál era la idea común de una descomposición de conjuntos algebraicos en el momento en que se escribió este artículo.
Deje que K sea un cuerpo algebraicamente cerrado y k sea un subcampo de K . Un subconjunto V ⊂ K n es una variedad algebraica (afín) sobre k si existe un conjunto polinomial F ⊂ k [ x 1 , ..., x n ] tal que el conjunto cero V ( F ) ⊂ K n de F es igual a V .
Recuerde que V se dice irreductible si para todas las variedades algebraicas V 1 , V 2 ⊂ K n la relación V = V 1 ∪ V 2 implica V = V 1 o V = V 2 . Un primer resultado de descomposición de variedades algebraicas es el famoso teorema de Lasker-Noether que implica lo siguiente.
- Teorema (Lasker - Noether). Para cada variedad algebraica V ⊂ K n existen un número finito de variedades algebraicas irreductibles V 1 , ..., V e ⊂ K n tales que tenemos
- Por otra parte, si V i ⊈ V j es válido para 1 ≤ i < j ≤ e entonces el conjunto { V 1 , ..., V e } es única y forma la descomposición irreducible de V .
Las variedades V 1 , ..., V e en el teorema anterior se denominan componentes irreducibles de V y pueden considerarse como una salida natural para un algoritmo de descomposición o, en otras palabras, para un algoritmo que resuelve un sistema de ecuaciones en k [ x 1 , ..., x n ] .
Para conducir a un programa de computadora, esta especificación de algoritmo debe prescribir cómo se representan los componentes irreducibles. Joseph Ritt [2] introduce una codificación de este tipo mediante el siguiente resultado.
- Teorema (Ritt). Si V ⊂ K n es una variedad no vacía e irreducible, entonces se puede calcular un conjunto triangular reducido C contenido en el ideal generado por F en k [ x 1 , ..., x n ] y tal que todos los polinomios g en reduce a cero por pseudo-división wrt C .
Llamamos al conjunto C en el Teorema de Ritt un conjunto característico de Ritt del ideal. Consulte la cadena regular para conocer la noción de un conjunto triangular.
Joseph Ritt describió un método para resolver sistemas polinomiales basado en la factorización de polinomios sobre extensiones de campo y el cálculo de conjuntos de características de ideales primos.
Sin embargo, derivar una implementación práctica de este método fue y sigue siendo un problema difícil. En la década de 1980, cuando se introdujo el Método del conjunto de características , la factorización de polinomios era un área de investigación activa y recientemente se resolvieron algunas cuestiones fundamentales sobre este tema [3]
Hoy en día, descomponer una variedad algebraica en componentes irreductibles no es esencial para procesar la mayoría de los problemas de aplicación, ya que son suficientes nociones más débiles de descomposición, menos costosas de calcular.
El método del conjunto de características se basa en la siguiente variante del teorema de Ritt.
- Teorema (Wen-Tsun Wu). Para cualquier conjunto polinomial finito F ⊂ k [ x 1 , ..., x n ] , se puede calcular un conjunto triangular reducido de tal manera que todo polinomio g en F reduce a cero por pseudo-división wrt C .
Diferentes conceptos y algoritmos ampliaron el trabajo de Wen-Tsun Wu . A principios de la década de 1990, la noción de cadena regular , introducida de forma independiente por Michael Kalkbrener en 1991 en su tesis doctoral y, por Lu Yang y Jingzhong Zhang [4], condujo a importantes descubrimientos algorítmicos.
En la visión de Kalkbrener, [5] las cadenas regulares se utilizan para representar los ceros genéricos de los componentes irreducibles de una variedad algebraica. En el trabajo original de Yang y Zhang, se utilizan para decidir si una hipersuperficie se cruza con una cuasi-variedad (dada por una cadena regular). Las cadenas regulares tienen, de hecho, varias propiedades interesantes y son la noción clave en muchos algoritmos para descomponer sistemas de ecuaciones algebraicas o diferenciales.
Las cadenas regulares se han investigado en muchos artículos. [6] [7] [8]
La abundante literatura sobre el tema puede explicarse por las muchas definiciones equivalentes de una cadena regular. En realidad, la formulación original de Kalkbrener es bastante diferente de la de Yang y Zhang. Un puente entre estas dos nociones, el punto de vista de Kalkbrener y el de Yang y Zhang, aparece en el artículo de Dongming Wang. [9]
Hay varios algoritmos disponibles para obtener la descomposición triangular de V ( F ) tanto en el sentido de Kalkbrener como en el sentido de Lazard y Wen-Tsun Wu . El Algoritmo Lextriangular de Daniel Lazard [10] y el Algoritmo Triade de Marc Moreno Maza [11] junto con el Método del Conjunto de Características están disponibles en varios sistemas de álgebra computacional, incluyendo Axiom y Maple .
Definiciones formales
Sea k un campo y x 1 <... < x n variables ordenadas. Denotamos por R = k [ x 1 , ..., x n ] el anillo polinomial correspondiente . Para F ⊂ R , considerado como un sistema de ecuaciones polinomiales, hay dos nociones de descomposición triangular sobre el cierre algebraico de k . La primera consiste en descomponer perezosamente, representando solo los puntos genéricos del conjunto algebraico V ( F ) en el llamado sentido de Kalkbrener.
El segundo es describir explícitamente todos los puntos de V ( F ) en el llamado sentido de en Lazard y Wen-Tsun Wu .
En ambos casos T 1 , ..., T e son un número finito de cadenas regulares de R ydenota el radical del ideal saturado de T i mientras que W ( T i ) denota el cuasi componente de T i . Consulte la cadena regular para conocer las definiciones de estas nociones.
Suponga a partir de ahora que k es un campo cerrado real . Considere S un sistema semi-algebraica con polinomios en R . Existen [12] un número finito de sistemas semi-algebraicos regulares S 1 , ..., S e tales que tenemos
donde Z k ( S ) denota los puntos de k n que resuelven S . Los sistemas semi-algebraicos regular de S 1 , ..., S e forman una descomposición triangular del sistema semi-algebraica S .
Ejemplos de
Denote Q el campo del número racional. En con orden variable , considere el siguiente sistema polinomial:
Según el código de Maple :
con ( RegularChains ) : R : = PolynomialRing ([ x , y , z ]) : sys : = { x ^ 2 + y + z - 1 , x + y ^ 2 + z - 1 , x + y + z ^ 2 - 1 } : l : = triangularizar ( sys , R ) : mapa ( ecuaciones , l , R ) ;
Una posible descomposición triangular del conjunto de soluciones de S con el uso de la biblioteca RegularChains es:
Ver también
Referencias
- ^ Wu, WT (1987). Un teorema de estructura cero para la resolución de ecuaciones polinómicas. Preprints de investigación de MM, 1, 2–12
- ^ Ritt, J. (1966). Álgebra diferencial. Nueva York, Publicaciones de Dover
- ^ AM Steel Conquering inseparability: Descomposición primaria y factorización multivariante sobre campos de función algebraica de característica positiva
- ^ Yang, L., Zhang, J. (1994). Búsqueda de dependencia entre ecuaciones algebraicas: un algoritmo aplicado al razonamiento automatizado . Inteligencia artificial en matemáticas, págs. 14715, Oxford University Press.
- ^ M. Kalkbrener: Un algoritmo euclidiano generalizado para calcular representaciones triangulares de variedades algebraicas. J. Symb. Computación. 15 (2): 143–167 (1993)
- ^ SC Chou y XS Gao. Sobre la dimensión de una cadena ascendente arbitraria. Toro chino. of Sci., 38: 799-804, 1991.
- ^ Michael Kalkbrener. Propiedades algorítmicas de anillos polinomiales. J. Symb. Computación.}, 26 (5): 525--581, 1998.
- ^ P. Aubry, D. Lazard, M. Moreno Maza. Sobre las teorías de conjuntos triangulares . Journal of Symbolic Computation, 28 (1-2): 105-124, 1999.
- ^ D. Wang. Computación de sistemas triangulares y sistemas regulares. Journal of Symbolic Computation 30 (2) (2000) 221-236
- ^ D. Lazard, Resolución de sistemas algebraicos de dimensión cero . Revista de Computación Simbólica 13 , 1992
- ^ M. Moreno Maza: Sobre la descomposición triangular de variedades algebraicas. MEGA 2000 (2000).
- ^ Changbo Chen, James H. Davenport, John P. May, Marc Moreno-Maza, Bican Xia, Rong Xiao. Descomposición triangular de sistemas semi-algebraicos . Actas del Simposio Internacional de 2010 sobre Computación Simbólica y Algebraica (ISSAC 2010), ACM Press, págs. 187-194, 2010.