Méthode de Wiedemann pour la solution de systèmes creux

Mots clés: algèbre linéaire, algèbre linéaire dense, corps finis.

Le but de ce projet est d’implanter des méthodes rapides de multiplication de matrices sur les corps finis, et de construire une bibliothèque de fonctions d’algèbre linéaire rapides au dessus de ces méthodes.

Résumé

Objectifs

• Implanter l’algorithme de Strassen pour la multiplication de matrices.

• Implanter les algorithmes asymptotiquement bons pour le déterminant, l’inversion, la solution de systèmes linéaires, la diagonalisation.

Prérequis

• Connaissances de base en algèbre linéaire et corps finis.

Références

• https://en.wikipedia.org/wiki/Strassen_algorithm.

• P. Giorgi, C.-P. Jeannerod, G. Villard. On the Complexity of Polynomial Matrix Computations.