| Titre Comparaison et extension de programmes rapides d'algèbre linéaire exacte. |
English version
|
Lieu
INRIA, Projet
CAFÉ
BP 93, 06902 France
Information
Description
Le projet Café à développé et/ou implementé
des algorithmes récents et efficaces en algèbre linéaire
exacte [1,2,3]. Par exemple, nous disposons maintenant de 6 algorithmes
différents pour le calcul de déterminants de matrices de
polynômes, la résolution exacte de systèmes linéaires,
etc. Or, les premiers résultats expérimentaux montrent que
le choix de l'algorithme à utiliser dépend de plusieurs paramètres,
dont la taille des matrices mais aussi le type des coefficients (nombres
entiers, rationels, algébriques ou bien dans un corps fini) des
polynômes qu'elles contiennent, leur degrés et probablement
la distribution de ces degrés. Nous avons donc besoin d'une étude
comparative poussée afin de déterminer une stratégie
de sélection automatique du meilleur algorithme à utiliser
sur une matrice donnée. Cette étude devra aussi permettre
de mieux comprendre le comportement en pratique de ces algorithmes et de
les améliorer le cas écheant. Enfin on étudiera aussi
leur extension à des problèmes voisins tels que le calcul
de résultants ou de vecteurs cycliques et/ou l'implémentation
distribuée de certains de ces algorithmes.
[1] J.Abbott, M.Bronstein & T.Mulders, Fast
Deterministic Computation of Determinants of Dense Matrices , Proceedings
of ISSAC'99, ACM Press, 197-204 (1999).
[2] T.Mulders & A.Storjohann, Rational
Solutions of Singular Linear Systems , Proceedings of ISSAC'2000, ACM
Press, 242-249 (2000).
[3] T.Mulders & A.Storjohann, Triangular
Factorization of Polynomial Matrices, ISSAC'2000 Poster.
Objectifs du stage
Un premier objectif intermédiaire sera de générer
une suite de tests suffisamment importante et variée pour déduire
des résultats une stratégie de sélection automatique
de l'algorithme approprié pour chaque entrée. Ensuite, on
étudiera l'extension de certains de ces algorithmes aux calculs
des résultants et vecteur cycliques (dépendences linéaires),
ainsi que leur implémentation distribuée sur un réseau
de stations de travail à l'aide de la bibliothèque de communication
de haut niveau 
.
Outils
Station de travail Unix, langage Aldor, bibliothèques 
et .
Durée
3 - 4 mois, niveau maîtrise, continuation possible sur 6 mois ou en thè.