Séminaire du 24 février 03, Emmanuel Thomé, LIX, École polytechnique.

Berlekamp-Massey matriciel rapide, résolution de gros systèmes linéaires par "block Wiedemann"

L'algorithme de Wiedemann par blocs est adapté à la résolution de systèmes linéaires creux, et a l'avantage d'être partiellement distribuable. Une des étapes du calcul est néanmoins sequentielle : c'est un cas particulier de calcul d'approximant de Padé matriciel. Le souci de distribuer l'algorithme de Wiedemann par blocs impose de réaliser ce calcul très efficacment. C'est ce que nous avons fait en proposant une résolution récursive du problème, basée sur la FFT. Nous avons ainsi pu résoudre un système de taille 500000 x 500000, sur un corps avec des éléments dont la taille est de 180 chiffres décimaux.


Virginie Collette
Last modified: Mon Feb 17 11:39:41 MET 2003