Xcas

Pourquoi utiliser Xcas à l'épreuve de modélisation de l'agrégation?

• Certaines fonctionnalités de Xcas sont plus faciles à utiliser ou plus puissantes que celles des autres logiciels de calcul formel, en particulier pour l'option C (par exemple en arithmétique, Xcas donne accès aux fonctionnalités du logiciel PARI/GP).
• Si vous connaissez bien maple (ou mupad ou la TI89/92), Xcas est un équivalent libre (donc gratuit) que vous devriez pouvoir utiliser sans trop avoir à changer vos habitudes (bien entendu il y a des différences avec les logiciels cités ci-dessus, mais dans les cas favorables, des feuilles de calcul maple s'ouvrent et s'exécutent à l'identique dans Xcas).
• La documentation de Xcas est entièrement rédigée en français. Elle comprend de plus un manuel d'algorithmique et des exemples faciles à adapter pour la présentation sur ordinateur en particulier pour l'option C (dans les manuels ou depuis le menu Exemples).
• Xcas affiche les zones de parenthèses, crochets ou accolades correspondantes, ce qui facilite la recherche d'erreurs de parenthèsage par exemple. De plus, dans un niveau de programme, les mots clefs du language sont affichés en couleur.
• Xcas possède un débuggueur interactif permettant l'exécution d'un programme ligne à ligne et la visualisation des variables, facilitant la mise au point d'une fonction bugguée.

Retour à la barre de navigation

Télechargement de Giac/Xcas

• depuis la page d'installation de Xcas
• vous pouvez aussi charger sur le site de Francois Boisson une image CD permettant d'avoir sur un PC sans aucune installation la même configuration qu'à l'oral (naturellement ne sont présents que les dogiciels pouvant être redistribués, en particulier Xcas, mais aussi Pari, Maxima, Axiom, Scilab). Vous pouvez ensuite recopier le CD sur une clef USB et avoir la configuration de l'agregation sur cette clef.

Retour à la barre de navigation

Option C (algèbre et calcul formel)

• Notez que le programme de l'agreg a été allégé en 2009, cette page ne reprend pas les points qui ne sont plus au programme. Certains points restant en limite du programme, vous pouvez trouver l'ancienne version de cette page ici.
• N'oubliez pas de vérifier le style de programmation lorsque vous lancez Xcas (bouton d'état au centre en haut de la session)
• Notez aussi que vous pouvez utiliser PARI dans Xcas ce qui peut être utile en particulier pour accéder à des fonctions arithmétiques avancées. Pour cela tapez la commande pari(). Les commandes de PARI sont alors utilisables soit par leur nom PARI, soit en leur ajoutant le préfixe pari_ lorsque le nom existe déjà dans Xcas (par exemple weber(1+i) et pari_gcd(x^2-1,x^3-1)). Une aide succinte sur les commandes de pari est accessible par ?pari_nom_de_commande_pari. Le manuel plus complet de PARI se consulte depuis le menu Aide->Manuels->PARI-GP.
  On peut aussi utiliser les commandes de PARI sans les exporter, en tapant la commande pari( puis le nom de commande pari en chaine de caractères, puis les arguments de la commande pari, par exemple pari("weber",1+i).

C1: représentations

• Entiers
  Les entiers longs utilisent la librairie GMP 4, les algorithmes utilisés y sont documentés (cf. aussi la doc en ligne gmp*info en tapant info gmp en ligne de commande ou Ctrl-H I dans emacs puis chercher gmp, puis aller dans Algorithms). Par exemple, diverses méthodes de multiplication rapide sont implémentéees (Karatsuba, Toom3, FFT).
• Flottants
  La base de représentation des flottants utilisée par Xcas est 2 (et non 10 comme maple, c'est d'ailleurs pour cette raison que les calculs en flottants sont relativements lents en maple, sauf si on utilise evalhf qui force l'utilisation de l'arithmétique flottante du processeur). On peut le vérifier en calculant 0.3-3*0.1. Le programme suivant, tiré de V. Lefèvre et P.Zimmermann, permet de déterminer la base utilisée pour la représentation des flottants (fonctionne avec maple et avec xcas en mode maple)
  Base:=proc()
  local A,B;
  A:=1.0; B:=1.0;
  while evalf(evalf(A+1.0)-A)-1.0=0.0 do A:=2*A; od;
  while evalf(evalf(A+B)-A)-B<>0 do B:=B+1; od;
  B;
  end;
  Si Digits est plus petit ou egal à 13, les objets nouvellement créés utilisent l'arithmétique hardware "double" du standard IEEE en base 2, 52+1 bits de mantisse, 11 bits d'exposant, 1 bit de signe, mais pour le stockage les 8 bits de poids faible de la mantisse sont ramenés à 0, il n'y a donc que 45 bits de mantisse vraiment utilisables, Digits controle seulement l'affichage des flottants.
  Sinon, ce sont des flottants multiprécision utilisant la librairie MPFR. Digits qui est un nombre de chiffres significatifs en base 10 est alors arrondi en un nombre de bits en base 2. Certains calculs numériques utilisant la GSL (Gnu Scientific Library), par exemple l'algèbre linéaire numérique, convertissent les flottants longs en flottants hardware (avec évidemment des pertes de précision).
  Référence pour les erreurs: par exemple le livre Analyse numérique et équations différentielles de Demailly
• Polynômes
  Voir aussi 1-d et n-d.
  • On peut manipuler les polynômes sous forme symbolique comme dans maple (cf ici), mais aussi directement en représentation dense à une variable ou creuse à plusieurs variables.
  • Polynômes à 1 variable
    • la représentation est une liste des coefficients donnés par ordre décroissant, avec le préfixe poly1[ par exemple poly1[1,0,3] représente le polynôme x^2+3 (on peut omettre poly1[ s'il n'y a pas de risque de confusion). Les instructions arithmétiques de base s'appliquent sur les listes représentant des polynômes, par exemple rem([1,3,4,2],[1,1,1]) ou poly1[1,2.3]*poly1[1,1].
    • On passe de la représentation symbolique à la représentation liste et inversement avec les fonctions symb2poly et poly2symb en mettant comme second argument la variable.
    • La multiplication des polynômes en une variable est implémentée par Karatsuba lorsque les arguments sont de degré supérieur à 17. Exemples: multiplication par Karatsuba et par FFT sur C ou par FFT sur Z/nZ
  • Polynôme en plusieurs variables
    • On peut utiliser une représentation récursive à partir des polynômes denses en une variable ci-dessus, mais ce type est mal adapté s'il y a beaucoup de coefficients nuls. Xcas utilise une représentation creuse, une liste de monomes dont on stocke le coefficient et un vecteur d'indices entiers (correspondant aux puissances des variables de ce monome).
    • Les fonctions de conversion sont symb2poly et poly2symb avec comme second argument la liste de variables.
    • Le produit de polynômes n-d est implementé en utilisant des tables de hachage pour regrouper dans la somme les termes de meme degré et lorsque cela est possible le vecteur d'indices entiers est compressé en un unique entier hardware (long ou long long, cf. les fichiers header /usr/share/giac/poly.h et monomial.h pour les programmeurs C++). Cf. R. Fateman pour une discussion sur les produits de polynômes à plusieurs variables.
• Z/nZ
  
  • Xcas utilise les entiers modulo un premier petit dans de très nombreux algorithmes (par exemple le PGCD de polynôme par méthode modulaire).
  • En mode xcas, on utilise le signe % (comme en C) pour indiquer un nombre de Z/nZ, par exemple 3 % 5. Pour obtenir un entier x à partir de son représentant modulo n y := x % n, en mode xcas, on tape y % 0.
    En mode maple, on utilise la même syntaxe qu'en maple (forme inerte de l'instruction suivie de mod).
  • Xcas utilise la représentation symétrique des entiers modulo un nombre premier (on renvoie x % n avec x compris entre -n/2 et n/2), qui est la plus utile lorsqu'on veut reconstruire un entier dont on connait une majoration en valeur absolue à partir de son représentant modulo n (pour n assez grand).
• Corps finis
  
  • Pour représenter les corps finis, Xcas utilise la représentation polynomiale (additive) modulo un polynome irréductible primitif.
  • Pour vérifier qu'un polynôme est irréductible modulo un premier, utiliser en mode maple, Factor((x^8+x^6+x^5+x^4+1)) mod 2, en mode xcas factor((x^8+x^6+x^5+x^4+1) % 2).
  • Cette session Xcas explique comment construire un polynome irréductible primitif.
  • Pour définir un corps fini, on utilise l'instruction GF par exemple G:=GF(2,8,['a','G']) (GF pour Galois Field, ayant ici 2^8 éléments, G désigne le nom du corps et a la variable utilisée pour l'écriture polynomiale des éléments de G). Xcas renvoie alors la caractéristique du corps et un polynôme primitif irréductible. Les éléments du corps sont des restes de division euclidienne (modulo le nombre premier) de polynômes par le polynôme irréductible.
    On peut créer un élément du corps en tapant G(polynôme), par exemple g:=G(a) (c'est ici un générateur du corps car le polynôme minimal est primitif). On peut ensuite appliquer toutes les opérations arithmétiques sur g, par exemple calculer g^255 pour vérifier qu'il vaut 1, ou g^(255/3), g^(255/5) et g^(255/17) qui ne valent pas 1 (on vérifie ainsi que les puissances de g engendrent bien tout le corps).
  • Pour travailler avec des polynômes à coefficients dans un corps fini, vous pouvez utiliser la représentation symbolique habituelle ou la représentation dense expliquée ci-dessus. Par exemple rem(g*x^3+g^5*x^2+g*x,g*x+g^2) ou rem([g,g^5,g,0],[g,g^2]) calcule le reste d'un polynôme de degré 3 par un polynôme de degre 1 à coefficients dans le corps G (donnés par ordre décroissant dans le 2ème cas).
• Vecteurs, listes et matrices
  Xcas ne fait pas de différence entre listes et vecteurs, les matrices sont des listes de listes. L'affectation dans une liste, vecteur ou matrice se fait par création d'une copie de l'objet si on utilise := pour l'affectation, ou par référence si on utilise =< (à utiliser si vous travaillez sur de grosses matrices modifiables en place).

Retour à la barre de navigation

C2: algorithmes

• Puissance modulaire rapide
  Dans tous les modes, on peut utiliser powmod(a,b,n). En mode maple, on peut utiliser la syntaxe maple a &^ b mod n.
  Le manuel de programmation donne des versions de l'algorithme de puissance rapide comparé avec l'algorithme naif.
• Algorithme d'Euclide étendu
  (dit aussi algorithme de Bézout). La version pour les entiers est iegcd ou iabcuv, pour les polynômes egcd et abcuv.
  Le demi algorithme d'Euclide étendu (permettant par exemple de reconstruire une fraction par son représentant modulo un entier), est codé dans la fonction fracmod. La version polynômiale du demi algorithme d'Euclide est utilisée pour les approximants de Padé (fonction pade).
  Le manuel de programmation donne des versions itératives et récursives de l'algorithme d'Eculide étendu.
• Nombres premiers
  Les fonctions isprime et is_prime de Xcas effectuent, par l'intermédiaire de GP-PARI, un test de primalité et non un test de pseudo-primalité (instruction is_pseudoprime) mais Xcas ne renvoie pas de certificat de primalité (contrairement à ce qui est indiqué dans la documentation). Le manuel de programmation donne des exemples de code de tests de pseudo-primalité (Rabin et Miller-Rabin). Vous pouvez aussi pour avoir un certificat de primalité utiliser directement la fonction pari("isprime",) avec en 2ème argument l'entier à tester et en 3ème argument optionnel 0, 1 ou 2 (voir la documentation de PARI). Par exemple
  p:=nextprime(3*10^14)
  calcule le premier pseudo-premier supérieur à 3.10^14, puis
  pari("isprime",p,1)
  calcule un certificat de primalité de Selfridge-Pocklington-Lehmer (Cohen chapitre 8.3 ou Knuth section 4.5), voir aussi cette session. Si on remplace 1 par 2, on effectue le test APRCL (Adleman-Pomerance-Rumely-Cohen-Lenstra). Voici aussi un exemple de programme montrant la méthode de Pollard.
• Factorisation d'entiers
  La factorisation des entiers est faite dans Xcas par appel à GP/PARI et permet en général de factoriser relativement rapidement, par exemple ifactor(2^128+1).
  Voir le manuel de PARI/GP (depuis le menu Aide->Manuels->PARI-GP) pour des détails sur les algorithmes utilisés par PARI, ainsi que Cohen ou Knuth. Cette session illustre la méthode des fractions continues (cf. Knuth pour une implémentation plus efficace).
• RSA
  Les fonctions asc et char permettent de convertir une chaine de caractères en une liste de nombres (le code ASCII des caractères) et réciproquement (comme convert avec l'option bytes en maple). Par ailleurs, le menu Exemples->crypto->rsa.xws donne un exemple de programme de codage RSA et le manuel de programmation fournit de la documentation sur RSA. On peut illustrer graphiquement le choix des valeurs de clefs dans cette session.
  Quelques autres exemples (par Robert Rolland) échange de clefs de Diffie-Hellman, signature ombrée

Retour à la barre de navigation

C3: algèbre linéaire sur un corps.

• Pivot de Gauss
  Xcas utilise par défaut l'algorithme de Gauss-Bareiss (dans rref, det, etc.). Les éléments de matrice sont transformés en fractions rationnelles polynomiales par rapport aux variables (étendues), les relations algébriques entre variables étendues sont ignorées (par exemple entre le cosinus et le sinus d'un angle, vous pouvez utiliser les fonctions de réécriture, en particulier tsimplify, pour écrire une matrice en fonctions de variables étendues algébriquement indépendantes). Le ppcm des dénominateurs est ensuite retiré ligne par ligne, puis la réduction a lieu (réduction de Gauss habituelle mais avec division par le pivot utilisé pour la réduction de la colonne précédent la colonne actuelle).
  L'option keep_pivot de rref n'effectue pas l'opération finale de division de la matrice réduite par le premier coefficient non nul de chaque ligne.
• Déterminant
  Par defaut, l'algorithme est p-adique/modulaire et probabiliste si les coefficients sont entiers (cf. infra), et Bareiss pour des coefficients polynomiaux.
  • L'option rational_det impose l'utilisation de l'algorithme de Gauss (et non Gauss-Bareiss) et n'effectue pas la transformation en fractions rationnelles (ce qui peut créer des problèmes de non reconnaissance de 0 si des variables interviennent).
  • L'option lagrange impose le calcul par interpolation.
  • L'option minor_det impose le calcul du déterminant par l'algorithme de développement selon les mineurs, par exemple det(A,minor_det) donnera des résultats bien plus rapides si A est une matrice creuse avec beaucoup de variables symboliques.
• Codes correcteurs
  La session codelin.xws illustre quelques aspects des codes linéaires. Le menu Exemples->crypto->reed_s.xws donne une session de calcul xcas illustrant les codes correcteurs de Reed-Solomon (rédigé pour le master 2 crypto de Grenoble). Pour les explications, cf. PDF (TeX). Cf. par exemple Demazure pour une introduction plus complète aux codes correcteurs.

Retour à la barre de navigation

C4: algèbre linéaire sur Z.

• La fonction det calcule le déterminant d'une matrice à coefficients entiers en cherchant son plus grand facteur invariant par une méthode p-adique, le calcul du facteur restant du déterminant est modulaire et probabiliste (on arrete le calcul avant la borne deduite de la borne de Hadamard si le résultat se stabilise, la probabilité d'erreur est inférieure à la valeur du champ proba de la configuration du calcul formel). Ceci permet de calculer le déterminant pour des matrices génériques en C*n^3+eps*n^4 ou eps est petit (ne compte guère avant n de l'ordre de 300).
• Les fonctions ihermite et ismith calculent la forme normale de Hermite et de Smith d'une matrice à coefficients entiers. L'algorithme de réduction est expliqué rapidement dans le texte Algèbre linéaire sur les entiers. Le manuel de calcul formel donne un exemple d'application de ihermite au calcul d'une Z-base d'un noyau, voir par exemple Morandi pour l'utilisation de la forme de Smith.

Retour à la barre de navigation

C5 Polynômes 1-d

• Évaluation
  La fonction horner de Xcas permet d'évaluer un polynôme (symbolique ou liste par ordre décroissant des coefficients) par la méthode de Horner. Voir aussi la session horner.xws de Exemples->poly et le manuel de programmation.
• Interpolation
  La fonction lagrange (ou interp) calcule par la méthode des différences divisées le polynôme d'interpolation de Lagrange. Une session Xcas illustrant l'erreur d'interpolation pour des points equirepartis sur -10..10.
  Références: la doc en ligne de Xcas (Manuel->Algorithmes de calcul formel), le livre de Demailly, sur le web, le chapitre 2 du cours d'Analyse numérique de Ernst Hairer
• Localisation de racines
  Les fonctions sturm et sturmab permettent de compter le nombre de racines réelles dans un intervalle ou complexes dans un rectangle de C. La fonction sturm commence par effectuer une factorisation sans racines multiples (sqrfree), puis calcule la suite des restes d'Euclide en utilisant l'algorithme du sous-résultant avec multiplication à chaque étape par un facteur pour tenir compte des signes.
  La fonction proot (et solve dans certains cas) permettent de calculer numériquement les racines d'un polynôme, par la méthode de Newton avec préfacteur adaptatif. Lorsqu'une racine est trouvée, elle est éliminée par l'algorithme de Hörner. Les racines suivantes sont calculées en recommançant la recherche de racine sur le polynôme quotient, puis améliorées en effectuant 2 ou 3 itérations de Newton avec le polynôme de départ.

C6 Polynômes n-d

• Résultant
  La fonction resultant permet de calculer le résultant de 2 polynômes par rapport à une variable, en utilisant l'algorithme du sous-résultant. On peut aussi utiliser la fonction sylvester pour construire la matrice et en calculer le déterminant ou passer sylvester en dernier argument de la fonction resultant.
• Intersection de courbes/surfaces algébriques planes
  L'instruction implicitplot de Xcas permet de représenter une courbe ou une surface donnée par son équation cartésienne.

Retour à la barre de navigation

C7 Complexité

• De nombreux algorithmes sont expliqués en détails dans le manuel de programmation de Xcas (menu Aide->Manuels->Programmation) et illustrés en langage xcas. La fonction time permet de calculer le temps d'exécution d'une fonction de Xcas, pour obtenir plus de précision, elle exécute plusieurs fois la même fonction lorsque le temps d'exécution est trop rapide et affiche alors le temps moyen d'exécution. Certains algorithmes de Xcas peuvent être exécutés en affichant des détails (mais qui peuvent être difficiles à interpréter), pour cela il faut aller dans la configuration du cas, et changer la valeur du champ debug, les messages s'affichent dans la console (il faut donc lancer Xcas depuis un terminal). On peut faire des comparaisons avec maple en utilisant la commande infolevel[all]:=5; (ou 2, 3, 4) en maple et en affichant les procédures (interface(verboseproc=2); suivi de eval(nom_de_procedure)) en maple.
• L'instruction time de Xcas permet de savoir le temps nécessaire à l'exécution d'une commande, il n'y a pas d'équivalent pour connaitre l'espace mémoire nécessaire à une instruction (on peut toutefois regarder l'espace mémoire utilisé par Xcas dans la zone d'état en haut de la session ou utiliser top depuis un terminal).
• Pour générer des exemples aléatoires, on peut utiliser les fonctions dont le nom commencent par rand, taper rand puis la touche de tabulation. Pour générer des points aléatoires utiliser les commandes point2d et point3d avec en argument les noms des points aléatoires à créer.

Retour à la barre de navigation

Textes de modélisation option C

• Représentation des objets mathématiques et algorithmes: latex, pdf
• Algèbre linéaire sur les entiers: latex, pdf
• Cryptographie: latex, pdf
  Référence pour ce texte Gilles Zemor, Cours de Cryptographie
• PGCD: latex, pdf
• Approximation des fonctions: latex, pdf
• Résultant et applications: latex, pdf
• Localisation de racines d'un polynome: latex, pdf
• Session Xcas illustrant le texte sur les carrés magiques.
• Session Xcas calcul des polynomes du texte Construction explicite de surfaces algébriques dont la projection est imposée. Quelques exemples de surfaces algébriques du texte se projetant sur un carré, un triangle et un anneau.
• Session Xcas illustrant le texte sur les molecules a 6 atomes
• Session Xcas justifiant la formule arithmético-géométrique pour les intégrales elliptiques
• Correction du problème d'algèbre 2007, par R. De Graeve et B. Parisse, pdf, session Xcas, latex, figure 1, figure 2,

Retour à la barre de navigation

TP option C

Retour à la barre de navigation

• Polynomes (texte 590) , surfaces (texte 590)
• Problème Algèbre 2007
• Fraction continues
• Codes linéaires
• Cyclohexane
• Codes de Reed-Solomon
• Carrés magiques
• Multiplication par FFT
• Multiplication polynomes
• Approximant de Padé
• Methode de Pollard
• Primalité
• Erreur d'interpolation pour Lagrange
• Intégrales elliptiques

Quelques références option C

• A Computational Introduction to Number Theory and Algebra par Victor Shoup: existe en livre (payant) ou en téléchargement gratuit
• A Course in Computational Algebraic Number Theory, de Henri Cohen
• Modern Computer Algebra, par J. Von zur Gathen et J. Gerhard
• Modern Computer Arithmetic, Richard Brent and Paul Zimmermann, version 0.5.1, March 2010
• The Art of Computer Programming, par D. Knuth, en particulier le volume semi-numerical algorithms et le volume searching and sorting
• Cours d'algèbre, Demazure
• Cours de calcul formel (2 tomes), Saux Picart et Rannou.
• Calcul formel: Systèmes et algorithmes de manipulations algébriques, par Davenport, Siret, Tournier,
• Analyse numérique et équations différentielles, J.P. Demailly
• Les manuels de l'aide en ligne, ainsi que les sources de Giac/Xcas dans les répertoires /usr/share/giac/src et /usr/include/giac

Tronc commun: Monte-Carlo

(c) B. Parisse, 2007, 2011.
Si vous utilisez des données originales de cette page, je vous remercie de faire pointer un lien hypertexte vers cette page, afin que d'autres puissent la trouver plus facilement en utilisant un moteur de recherche.
Conditions d'utilisation:
La diffusion et l'utilisation des données de cette page est autorisée dans un but non commercial et vaut acceptation de ces conditions d'utilisation. Ces données sont fournies sans garantie aucune, le détenteur du copyright ne pourra en aucun cas être poursuivi pour quelque dommage que ce soit suite à l'utilisation des données ci-dessus, y compris s'il en a été averti.