Complexité dans Xcas

[Noe Brucy]

Bonjour,

Je m'interroge sur la complexité des opérations de Calcul formel "basique", comme la simplification, ou le développement d'expressions formelles (construites à partir des opérations de bases (+, x, -, /, ^), de variables, des fonctions trigonométriques et des fonctions exp et ln) .

1ère question : Est-elle déterminante ? À partir de quelle "taille" d'expression le résultat n'est plus immédiat ? Quelles sont les expressions qui posent problème ?
2ème question : Comment la mesurer ? Le code permet t'il une estimation du nombre d'opérations élémentaires effectuées par l'algorithme et de l'occupation en mémoire ?
3ème question : Quelles sont les stratégies à mettre en œuvre pour réduire le temps d’exécution (pour ces deux opérations) ?

Question plus générale : Parmi les autres opérations "basiques" du calcul formel, quelles sont les plus problématiques en terme de complexité ?

Merci,

Noe

[parisse]

l'algorithme qui est le plus sollicite lors d'une simplification c'est le PGCD de polymomes a plusieurs variables sur un corps. Tout le travail preliminaire consiste a chercher des relations entre les inconnues (au sens large) d'une expression pour se ramener a ca.
Lors d'une simplification rationnelle (ratnormal de Xcas), le corps est Q (ou Q). Avec normal, c'est une extension algebrique de Q (dans des cas vraiment compliques, ca pourrait etre un corps de fraction rationnelle a coefficients dans ... dans une extension algebrique de Q).
La complexite d'un calcul de PGCD dans K[x1,..,xn] peut etre majoree, mais la borne est presque toujours ridiculement trop grande et n'a donc pas d'interet en pratique, il est donc impossible de savoir a priori combien de temps ca va prendre (donc impossible de mettre une barre de progression...). La raison est que deux polynomes sont presque toujours premiers entre eux (il n'y a rien a simplifier), et s'ils ne le sont pas, le PGCD est alors tres souvent de degre faible. Ceci se detecte rapidement en remplacant toutes les variables sauf une et en remplacant K par un corps fini (sur un corps fini et en une variable, le temps de calcul du pgcd de 2 polynomes de degre au plus n est borne par une constante*n^2).

[Noe Brucy]

Merci de votre réponse.

J'ai du mal à comprendre comment les polynômes sont utilisés pour la simplification. Pourriez vous me l'expliquer sur un exemple ?

[parisse]

par exemple (x^2-1)/(x^2+2x+1), on simplifie par le pgcd du numerateur et du denominateur.

[Noe Brucy]

D'accord, c'est donc uniquement pour des fractions rationnelles à une ou plusieurs variables, c'est ça ?

Dans le cas général, comment fonctionne en gros la commande simplify ? Pour mon TIPE j'ai codé (en OCaml) quelques fonctions de bases (simplification, développement, dérivation, ...), c'est intéressant pour moi de comparer avec de vrais logiciels, ça permet de voir si mes idées sont complètement à coté de la plaque et aussi de me donner des idées pour améliorer.

[parisse]

Le cas general consiste a se ramener a une fraction rationnelle a plusieurs variables (par ex. si on a (sin(x)^2-sin(y)^2)/(sin(x)^2+2*sin(x)*sin(y)+sin(y)^2) on commence par poser X=sin(x) et Y=sin(y)), la difficulte consiste a trouver des variables algebriquement independantes. Et le temps de calcul vient ensuite essentiellement des calculs de PGCD.

[Noe Brucy]

Qu'entendez vous par "algébriquement indépendantes" et pourquoi est-ce important ?

[parisse]

par exemple sin(x) et sin(y) sont independants (il n'y a pas de polynome non trivial qui les annule) alors que sin(x) et cos(x) ne le sont pas.

[Noe Brucy]

Pourquoi est-il important que les variables soit algébriquement indépendantes ?
Prendre des variables algébriquement dépendantes conduit-il à des résultats faux ou alors cela empêche-t-il simplement de voir certaines simplifications possibles ?

[parisse]

Le resultat ne sera pas faux, mais pourrait etre non simplifie, ce qui est embetant en particulier pour les tests d'egalite a 0.