Structure de données polynomes multivariables

Bonsoir,

Je souhaiterais utiliser une stucture de donnees adaptée aux polynomes multivariables pour notament réaliser la pseudo-division.
Pour des polynomes univariables j'utilise habituellemnt une liste chainée des coefficients du polynome.
Pour des polynomes mutilivariables je sais pas trop quelle structure de donnees employer.
J'ai pensé à definir une class(C++) Monome et ainsi definir un polynome multivariable comme une liste de monome mais c'est pas encore au point.

Si vous avez des idées me soumettre pour une structure de données adaptée , je suis tout ouïe.

Merci de votre attentio, en esperant avoir été plus ou moins clair.

Bonjour,

tu peux traiter les polynômes multivariés de la même manière que les polynômes univariés à partir du moment où tu ordonnes tes monomes.
Exemple :

ordre univarié -> 1,x,x^2,...,x^k

ordre bivarié -> 1,x,y,xy,x^2,y^2,x^2y,xy^2,x^2y^2, etc

Pour des polynômes univariés, comme je l'ai indiqué precedement, on peut utiliser une liste chaînée, exemple

Code:

---

1 2	1->0->2->1 represente 1 + 2x^2 + x^3

---

Mais pour représenter 2x^2y par exemple, ça ne marche plus.
Je sais pas pas si j'ai été clair.

Pour l'instant j'ai défini 3 trois classes : Terme (ex: x^2, 1, y, z^3, ...), Monôme (xy, 2x^2y, xyz, ..), Polynôme (2x^2y + xyz + 3), avec une notion de terme dominant (ici x).
Faut encore que je reflechisse pour les opérations et notamment la multiplication de polynômes.

Vous avez été clair mais vous n'avez pas compris ma réponse.
Qu'est-ce qui ne marche pas selon vous?

Dans votre exemple,

1 + 2x^2 + x^3 = x^0y^0+2x^2y^0+x^3y^0,

pourquoi n'arrivez-vous pas à placer 2x^2y?

Je n'arrive pas a représenter 2x^2y par une liste chainées car ici y est le coefficient de x^2, en d'autres termes :

Code:

---

1 2	2x^2y <-> 0->0->'2y' // d'où le problème

---

Tu te trouves dans un anneau polynomial bivarié : le 'y' n'a pas à apparaître.

Si j'ordonne comme ceci la base canonique,

Citation:

---

1,x,y,xy,x^2,y^2,x^2y,

---

alors j'obtiens :

Citation:

---

2x^2y <-> 0->0->0->0->0->0->2

---

Remarque : évidemment, dans la base canonique, 1=x^0y^0, x=xy^0, etc

Je comprends à présent votre idée, vous représentez chaque coordonnée de la base par une cellule de la liste chaînée (ça pourrait se faire avec des matrices).
Cela a l'air de marcher pour deux variables, mais quid d'un système à 7 ou 8 variables.

C'est exactement la même chose quel que soit le nombre de variables.
Chaque élément de la base canonique de votre espace s'écrit sous la forme

Citation:

---

{x_1}^{k_1}{x_2}^{k_2}{x_3}^{k_3}... {x_n}^{k_n}

---

si n désigne le nombre de variables.
Le degré est donné k_1+k_2+...+k_n.
C'est à vous de choisir une manière d'ordonner les éléments de la base canonique, ce qui revient à ordonner des ensembles de n-uplets.

Concernant la représentation informatique, vous pouvez adopter une représentation creuse comportant un tableau d'entier donnant l'indice de l'élément de la base canonique et un tableau de réels donnant le coefficient associé. Cela vous permet de ne pas stocker les zéros et gagner ainsi en mémoire et en temps de calcul. Pour plus d'informations, vous pouvez vous documenter sur le format de matrice COO (Coordinate Matrix Format) pour les matrices creuses (sparse matrices).

Vous pouvez bien sûr adapter tout cela pour utiliser des listes chaînées.

Je suis désolé mais je comprends pas trop comment cela marcherait avec plusieurs variables. Pour l'ordre, on prend l'ordre lexicographique.
Qu'est ce que cela donnerait (en terme de représentation informatique (matrice ou autre)) pour le système suivant

Code:

---

1 2 3 4 5

h1 = u1x1 - u1u3 = 0 h2 = u3x2 -(u2-u1)x1 = 0 h3 = x1x4 - (x2-u1)x3 - u1x1 = 0 h4 = u3x4 - u2x3 = 0

---

Il s'agit d'un exemple (diagonales se coupent en leurs milieux) pour la méthode de Wu.

Une variable est donnée par un tiplet (coefficient,symbole,puissance) (ex 3*x² est caractérisé par (3,x,2)) Après suffit de dire que ton coefficient ou ta puissance puissent être des variables et ca rulz ! Suffit de faire une liste et suffit de procéder par récurrence.

Ex 3*x^(2*y^4) est représenté par (3,x,(2,y,4))
Ex2 : 2x + 3y + 3*x^(2*y^4) est représenté par ((2,x,1),(3,y,1),(3,x,(2,y,4))) et ca rulz.

PS: Je m'inspire du Lisp à fond.

Citation:

---

Envoyé par Davidbrcz

Ex 3*x^(2*y^4) est représenté par (3,x,(2,y,4))
Ex2 : 2x + 3y + 3*x^(2*y^4) est représenté par ((2,x,1),(3,y,1),(3,x,(2,y,4)))

---

Ce ne sont pas des polynomes ... (ou alors tu places mal tes parenthèses 3*(x^2)*(y^4) est un polynome mais pas 3*x^(2*y^4), ou on a pas la même convention)

Pour faire ce que tu veus il suffit que tu arrives à construire une base de tes plynomes, par exemple avec 3 variables (x y z)
degré 1 : x, y, z
degré 2 : x^2, x*y, x*z, y^2, y*z, z^2
dégré 3 : x^3, (x^2)*y, (x^2)*z, x*(y^2), x*y*z, x*(z^2), y^3, (y^2)*z, y*(z^2), z^3
... (pour tout les dégrés, informatiquement tu t'arretes au dernier termes non nul, existe nécessairement car sinon ce n'est pas un polynome)

Exemple : 10+4x+45xy+35(x^2)*z donne (10,4,0,0,0,45,0,0,0,0,0,0,35)

Si je me trompe pas c'est ce que t'expliquais Aleph69 en le généralisant à n variable (fixés !)

En clair, mathématiquement vous devez exhiber une famille qui forme une base de l'ensemble des polynomes à n variables et que l'ensemble des indices de la famille soit ordonné.

NB: Le problème de cette solution c'est évidament les polynomes dont "beaucoup" de coeffecients sont nul (je me comprends pour le "beaucoup", je te laisse trouver tout seul sa signification), dans ce cas un conteneur associatif (ou normal qui stocke des paires), peut être utilisé.

Flob90 >> Je me suis basé sur 2x^2y que j'ai interprété en 2x*^(2y) pour construire mon système mais ca paraissait étrange, mais je ne me suis pas posé plus de question que ca. Sauf que si c'était 2*x²*y et dans ce cas il suffit de passer par un vecteur de tupple ((coeff,symbole,puissance), coeff,symbole,puissance)) s'i n'y a que deux variables et au besoin on peut augmenter le nombre de composant du tupple s'il y a plus de variable.

Pour exhiber une base, si on est dans une dimension infinie, pas facile ^^

Citation:

---

Envoyé par Davidbrcz

Flob90 >> Je me suis basé sur 2x^2y que j'ai interprété en 2x*^(2y) pour construire mon système sauf que si c'était 2*x²*y et dans ce cas il suffit de passer par une somme de tupple ((coeff,symbole,puissance), coeff,symbole,puissance)).

Pour exhiber une base, si on est dans une dimension infinie, pas facile ^^

---

Oui, mais 2x^(2y) ce n'est pas un polynome, donc l'auteur entendait bien 2*(x^2)*y

Et pour la base, je l'ai fait avec 3 (me suis arreté au degré 3, mais l'on peut continuer très facilement, on pourrait surment la définir correctement mathématiquement, mais j'ai la flemme de chercher), ca se fait avec n'importe quel nombre de variable, même si en effet la dimension de l'espace vectoriel des polynomes est infinie (on peut avoir une base en dimension infinie, ce n'est pas contradictoire, pour les polynomes à 1 variable c'est les X^n, pour les autres ca se généralise).

Après il peut effectivement il y avoir un problème pour la base si l'on se base sur un anneau non commutatif (je me base sur un anneau commutatif pour mon exemple), mais je suppose que ce n'est pas le cas de l'auteur.

Et finalement on sait qu'on aura pas de problème même si la base n'admet pas de cardinal finie, car l'on sait qu'un polynome est forcément une combinaison linéaire finie d'éléments d'une base (en particulier de celle que l'on choisie), donc si l'on stocke les coefficients dans un tableau il suffit de s'arreter au denier coefficient non nul.

Et on peut bien recontruire le polynome si la base est "ordonné" (on a une bijection entre N et l'ensemble des indices de la base, de même entre N et les indices du tableau, donc on a une bijection entre les indices du tableau et les indices de la base, d'où la réalisation possible).

Bonsoir,

Citation:

---

Envoyé par juve1897

Qu'est ce que cela donnerait (en terme de représentation informatique (matrice ou autre)) pour le système suivant

Code:

---

1 2 3 4 5

h1 = u1x1 - u1u3 = 0 h2 = u3x2 -(u2-u1)x1 = 0 h3 = x1x4 - (x2-u1)x3 - u1x1 = 0 h4 = u3x4 - u2x3 = 0

---

---

Pour commencer, il ne faut pas factoriser les polynômes à la Hörner : (x2-u1)x3 =-u1x3+x2x3.
Ensuite, il faut ordonner les éléments de ta base canonique.
En l'occurence, là tes polynômes sont des combinaisons linéaires des éléments de l'ensemble
{1,x1,x2,x3,x4,x1x2,x1x3,x1x4,x2x3} (<- arbitraire!)
Note qu'ici, j'utilise un ordre particulier que je choisis arbitrairement. C'est la raison pour laquelle le x1x3 apparaît alors que tu ne l'utilises pas dans ton cas. Pour définir un ordre, il te suffit de déterminer comment ranger des 4-uplets d'entiers. L'idée consiste à associer (k1,k2,k3,k4) à x1^k1*x2^k2*x2^k3*x4^k4. Dans mon ensemble, j'ai donc ordonné les couples comme ceci :
{(0,0,0,0),(1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1),(1,1,0,0),(1,0,1,0),(1,0,0,1),(0,1,1,0)}

Si tu représentes h1, h2, h3 etc sous forme de tableaux tu obtiens :

Citation:

---

h1 = [-u1u3,u1,0,0,0,0,0,0,0]
h2 = [0,-(u2-u1),u3,0,0,0,0,0,0]
h3 = [0,-u1,0,-u1,0,0,0,1,1]
h4 = [0,0,-u2,u3,0,0,0,0,0]

---

Concernant le choix de tes base et l'ordre, je te conseille de procéder par degrés croissants (somme des puissances=degré), ce que je n'ai pas fait ici car mon ensemble se trouve entre le degré 1 et le degré 2 (c'est un degré 2 incomplet). Pour compléter jusqu'au degré 2, il compléter la base canonique :

{1,x1,x2,x3,x4,x1x2,x1x3,x1x4,x2x3,x2x4,x3x4,x1²,x2²,x3²,x4²}

Normalement, avec ça, tu peux écrire n'importe quel polynôme à 4 variables qui est de degré 2. Dans tes tableaux, ca va ajouter des zéros à la fin.

Concernant le stockage, par besoin de stocker les zéros! Il suffit d'adopter un stockage creux : pour chaque coefficient non nul, un tableau auxiliaire fournit l'indice de l'élément de la base canonique selon l'ordre que tu as déterminé. J'appelle ind1 le tableau d'indices pour h1, ind2 pour h2 etc .

On obtient (j'indexe à partir de zéro puisque tu fais du C++) :

Citation:

---

h1 = [-u1u3,u1] avec ind1 = [0,1]
h2 = [-(u2-u1),u3] avec ind2 = [1,2]
h3 = [-u1,-u1,1,1] avec ind3 = [1,3,7,8]
h4 = [-u2,u3] avec ind4 = [2,3]

---

C'est ça le principe du format COO dont je te parlais.
Si tu veux stocker sous forme de tableau2D, il faut aussi un tableau d'entiers pour les indices de lignes (en considérant que les colonnes correspondent aux éléments de la base canonique mais on peut faire l'inverse).

PS : si tu est gourmand, tu peux adopter un format plus économique que COO. Par exemple, CRS (Compressed Row Storage) ou CCS (Compressed Column Storage) selon que tu orientes tes tableaux par ligne ou par colonne. Si tu t'y connais un peu en graphe, tu as dû rencontrer ce type de stockage pour les relations d'adjacence entre sommets (mais il porte un autre nom je crois).