Le Groupe Symétrique
Option Algèbre et Calcul Formel, Préparation à l'Agrégation de Mathématiques d'Orsay
TP: Autour de l'algorithme d'Euclide
Document disponible au format: PDF, Postscript, DVI, Text, LaTeX, LyX.
1 TP: Wiedemann
Exercice 1
L'algorithme de Berlekamp-Massey permet, étant donné une suite (s1,...,sn)
d'éléments d'un corps de trouver la plus petite relation de récurrence
satisfaite par cette suite. Les coefficients de cette relation de
récurrence sont traditionnellement encodés sous la forme d'un polynôme.
Implanter l'algorithme de Berlekamp-Massey, soit en vous servant de
l'article de Massey (1969) Massey.1969.pdf, soit via l'algorithme
d'Euclide étendu.
Correction en MuPAD: Wiedemann.mu.
Exercice 2
Prendre n=10. Construire une matrice carrée M un peu aléatoire
de dimension n dont les valeurs propres sont dans {0,1,2}
(avec des multiplicités quelconques). Calculer son polynôme minimal
avec la fonction linalg::minpoly.
Construire un vecteur aléatoire colonne v et un vecteur aléatoire
ligne w de tailles n. Calculer la suite (w× Mk× v)k=0,...,2n,
et vérifier sur machine qu'elle suit une relation de récurence dont
les coefficients sont donnés par le polynôme minimal de M (attention:
les coefficients apparaissent dans l'ordre inverse de la convention
utilisée dans Massey (1969)). Le prouver.
Réciproquement, utiliser l'algorithme de Berlekamp-Massey pour retrouver
le polynôme minimal de M.
Exercice 3
Écrire une procédure matrix2fonction qui prend une matrice M en argument,
et renvoie l'endomorphisme correspondant, c'est-à-dire la fonction
qui à un vecteur v associe le vecteur M× v.
Finir d'implanter une procédure wiedemann(f, n) qui prend un endomorphisme
f et la dimension de l'espace, et qui calcule son polynôme minimal
en utilisant l'algorithme de Wiedemann.
Vérifier le résultat sur la matrice précédente.
Écrire la fonction de multiplication par une matrice diagonale, la
fonction de multiplication par une matrice tridiagonale. Utiliser
Wiedemann pour calculer le polynôme minimal de quelques matrices de
ce type.
Évaluer la complexité expérimentale de ces calculs. Comparer avec
la fonction linalg::minpoly du système.
Le Groupe Symétrique
Option Algèbre et Calcul Formel, Préparation à l'Agrégation de Mathématiques d'Orsay
TP: Autour de l'algorithme d'Euclide
TP: Algorithme de Wiedemann /
Option Algèbre et Calcul Formel /
Nicolas M. Thiéry
Dernière modification: Mer 28 Mar 2007 22:53:20