Décomposition triangulaire – Wikipedia wiki

Posted on by
before-content-x4

Algorithme sur les systèmes de polynômes

after-content-x4

En algèbre informatique, un décomposition triangulaire d’un système polynomial S est un ensemble de systèmes polynomiaux plus simples S d’abord , …, S C’est tel qu’un point est une solution de S Si et seulement si c’est une solution de l’un des systèmes S d’abord , …, S C’est .

Lorsque le but est de décrire l’ensemble de solution de S Dans la fermeture algébrique de son champ de coefficient, ces systèmes plus simples sont des chaînes régulières. Si les coefficients des systèmes polynomiaux S d’abord , …, S C’est sont des nombres réels, alors les vraies solutions de S Peut être obtenu par une décomposition triangulaire en systèmes semi-algégiques réguliers. Dans les deux cas, chacun de ces systèmes plus simples a une forme triangulaire et des propriétés remarquables, ce qui justifie la terminologie.

Histoire [ modifier ]]

Le Méthode d’ensemble caractéristique est le premier algorithme sans factorisation, qui a été proposé pour décomposer une variété algébrique en composants équidimensionnels. De plus, l’auteur, Wen-Tsun Wu, a réalisé une mise en œuvre de cette méthode et a rapporté des données expérimentales dans son article de Pioneer de 1987 intitulé “Un théorème de structure zéro pour la résolution d’équations polynomiales”. [d’abord] Pour mettre cette œuvre en contexte, rappelons quelle était l’idée commune d’une décomposition algébrique au moment de la rédaction de cet article.

Laisser K être un champ fermé algébrique et k être un sous-champ de K . Un sous-ensemble DANS ⊂ K n est une variété algébrique (affine) sur k S’il existe un ensemble polynôme F ⊂ k [ X d’abord , …, X n ]] tel que le set zéro DANS ( F ) ⊂ K n de F équivaut à DANS .

Rappeler que DANS est dit irréductible Si pour toutes les variétés algébriques DANS d’abord , DANS 2 ⊂ K n la relation DANS = DANS d’abord ∪ DANS 2 implique soit DANS = DANS d’abord ou DANS = DANS 2 . Un premier résultat de décomposition de variété algébrique est le célèbre théorème de Lasker-Noment qui implique ce qui suit.

after-content-x4
Théorème (Lasker – Noether). Pour chaque variété algébrique DANS ⊂ K n Il existe des variétés algébriques irréductibles DANS d’abord , …, DANS C’est ⊂ K n tel que nous avons

De plus, si DANS je ⊈ DANS J tient à 1 ≤ je < J ≤ C’est puis l’ensemble { DANS d’abord , …, DANS C’est } est unique et forme le décomposition irréductible de DANS .

Les variétés DANS d’abord , …, DANS C’est dans le théorème ci-dessus est appelé le composants irréductibles de DANS et peut être considéré comme une sortie naturelle pour un algorithme de décomposition, ou, en d’autres termes, pour un algorithme résolvant un système d’équations en k [ X d’abord , …, X n ]] .

Afin de conduire à un programme informatique, cette spécification d’algorithme devrait prescrire la façon dont les composants irréductibles sont représentés. Un tel encodage est introduit par Joseph Ritt [2] à travers le résultat suivant.

Théorème (conduite). Si DANS ⊂ K n est une variété non vide et irréductible alors on peut calculer un ensemble triangulaire réduit C contenu dans l’idéal

Nous appelons l’ensemble C Dans le théorème de Ritt Ensemble de caractéristique Ritt de l’idéal

⟨ F ⟩ {displaystyle langle Frangle }

. Veuillez vous référer à la chaîne ordinaire pour la notion d’un ensemble triangulaire.

Joseph Ritt a décrit une méthode de résolution de systèmes polynomiaux basés sur la factorisation polynomiale sur les extensions de champ et le calcul des ensembles caractéristiques des idéaux privilégiés.

Cependant, la dérivation d’une implémentation pratique de cette méthode était et reste un problème difficile. Dans les années 80, lorsque la méthode d’ensemble caractéristique a été introduite, la factorisation polynomiale était un domaine de recherche actif et certaines questions fondamentales à ce sujet ont été résolues récemment [3]

De nos jours, la décomposition d’une variété algébrique en composants irréductibles n’est pas essentiel pour traiter la plupart des problèmes d’application, car les notions plus faibles de décompositions, moins coûteuses à calculer, sont suffisantes.

Le Méthode d’ensemble caractéristique repose sur la variante suivante du théorème de Ritt.

Théorème (Wen-Tsun Wu). Pour tout ensemble polynôme fini F ⊂ k [ X d’abord , …, X n ]] , on peut calculer un ensemble triangulaire réduit

Différents concepts et algorithmes ont étendu le travail de Wen-Tsun Wu. Au début des années 1990, la notion de chaîne régulière, introduite indépendamment par Michael Kalkbrener en 1991 dans sa thèse de doctorat et, par Lu Yang et Jingzhong Zhang [4] conduit à des découvertes algorithmiques importantes.

Dans la vision de Limebren, [5] Des chaînes régulières sont utilisées pour représenter les zéros génériques des composants irréductibles d’une variété algébrique. Dans le travail original de Yang et Zhang, ils sont utilisés pour décider si une hypersurface coupe une quasi-variété (donnée par une chaîne ordinaire). Les chaînes régulières ont, en fait, plusieurs propriétés intéressantes et sont la notion clé dans de nombreux algorithmes pour la décomposition des systèmes d’équations algébriques ou différentielles.

Des chaînes régulières ont été étudiées dans de nombreux articles. [6] [7] [8]

La littérature abondante sur le sujet peut s’expliquer par les nombreuses définitions équivalentes d’une chaîne ordinaire. En fait, la formulation originale de Kalkbrener est très différente de celle de Yang et Zhang. Un pont entre ces deux notions, le point de vue de Kalkbrener et celui de Yang et Zhang, apparaît dans le papier de Dongming Wang. [9]

Il existe différents algorithmes disponibles pour obtenir une décomposition triangulaire de DANS ( F ) à la fois dans le sens de Kalkbrener et dans le sens de Lazard et de Wen-Tsun Wu. Le Algorithme lextriangulaire par Daniel Lazard [dix] et le Algorithme de triade par Marc Moreno Maza [11] avec la Méthode d’ensemble caractéristique sont disponibles dans divers systèmes d’algèbre informatique, y compris l’axiome et l’érable.

Définitions formelles [ modifier ]]

Laisser k être un champ et X d’abord <... < X n être commandé des variables. Nous désignons R = k [ X d’abord , …, X n ]] l’anneau polynomial correspondant. Pour F ⊂ R , considéré comme un système d’équations polynomiales, il existe deux notions de décomposition triangulaire sur la fermeture algébrique de k . Le premier consiste à décomposer paresseusement, en ne représentant que les points génériques de l’ensemble algébrique DANS ( F ) Dans le soi-disant sens de Kalkbrener.

La seconde consiste à décrire explicitement tous les points de DANS ( F ) Dans le soi-disant sens de Lazard et Wen-Tsun Wu.

Dans les deux cas T d’abord , …, T C’est sont finis de nombreuses chaînes régulières de R et

sat( Ti) {displayStyle {sqrt {mathrm {sat} (t_ {i})}}}

désigne le radical du idéal saturé de T je alors que DANS ( T je ) indique le quasi-composant de T je . Veuillez vous référer à la chaîne ordinaire pour les définitions de ces notions.

Supposons à partir de maintenant k est un vrai champ fermé. Considérer S un système semi-algébrique avec des polynômes R . Il existe [douzième] des systèmes semi-algébriques réguliers finis S d’abord , …, S C’est tel que nous avons

où AVEC k ( S ) indique les points de k n qui résolvent S . Les systèmes semi-algèses réguliers S d’abord , …, S C’est former un décomposition triangulaire du système semi-algébrique S .

Exemples [ modifier ]]

Dénoter Q le champ de numéro rationnel. Dans

Q [ X , et , Avec ]] {displayStyle q [x, y, z]}

avec commande variable

X > et > Avec {displaystyle x> y> z}

S = {x2+y+z=1x+y2+z=1x+y+z2=1{displayStyle s = {begin {cas} x ^ {2} + y + z = 1 \ x + y ^ {2} + z = 1 \ x + y + z ^ {2} = 1end {cas}}}

Selon le code d’érable: 

avec ( Chaînes régulières ) :  R  : =  Polynôme ([[ X ,  et ,  Avec ]) :  système  : =  { X ^ 2 + et + Avec - d'abord ,  X + et ^ 2 + Avec - d'abord ,  X + et + Avec ^ 2 - d'abord } :  l  : =  Triangularisation ( système ,  R ) :  carte ( Équations ,  l ,  R ) ;

Une décompositions triangulaires possibles de l’ensemble de solution de S avec une utilisation Chaînes régulières La bibliothèque est:

Voir également [ modifier ]]

Les références [ modifier ]]

  1. ^ Wu, W. T. (1987). Un théorème de la structure zéro pour la résolution d’équations polynomiales. MM Research Preprints, 1, 2–12
  2. ^ Ritt, J. (1966). Algèbre différentielle. New York, Douvres Publications
  3. ^ A. M. Inséparabilité de la conquête de l’acier: décomposition primaire et factorisation multivariée sur les champs de fonction algébrique de caractéristique positive
  4. ^ Yang, L., Zhang, J. (1994). Recherche de dépendance entre les équations algébriques: un algorithme appliqué au raisonnement automatisé . Artificiel Intelligence in Mathematics, pp. 14715, Oxford University Press.
  5. ^ M. Kalkbrener: un algorithme euclidien généralisé pour calculer les représentations triangulaires des variétés algébriques. J. Symb. Comput. 15 (2): 143–167 (1993)
  6. ^ S.C. Chou et X.S. Gao. Sur la dimension d’une chaîne ascendante arbitraire. Bull chinois. of Sci., 38: 799–804, 1991.
  7. ^ Michael Kalkbrener. Propriétés algorithmiques des anneaux polynomiaux. J. Symb. Comput.}, 26 (5): 525–581, 1998.
  8. ^ P. Aubry, D. Lazard, M. Moreno Maza. Sur les théories des ensembles triangulaires . Journal of Symbolic Computation, 28 (1–2): 105–124, 1999.
  9. ^ D. Wang. Computer les systèmes triangulaires et les systèmes réguliers. Journal of Symbolic Computation 30 (2) (2000) 221–236
  10. ^ D. Lazard, Résolution de systèmes algébriques zéro dimensionnel . Journal of Symbolic Computation 13 , 1992
  11. ^ M. Moreno Maza: sur la décomposition triangulaire des variétés algébriques. Mega 2000 (2000).
  12. ^ Changbo Chen, James H. Davenport, John P. May, Marc Moreno-Maza, Bican Xia, Rong Xiao. Décomposition triangulaire des systèmes semi-algébriques . Actes de 2010 Symposium international sur le calcul symbolique et algébrique (ISSAC 2010), ACM Press, pp. 187-194, 2010.

after-content-x4