Projet

Méthode de Strassen

Vous devez écrire en pascal une procédure qui fait le produit de deux matrices carrées selon la méthode de Strassen décrite sommairement en cours. (Plus de détails)

Taille des matrices

On pourra se limiter à des matrices dont la taille est une puissance de 2.
Pour des matrices de taille quelconque, on pourra,
soit compléter la matrice par des zéros, pour que sa taille devienne une puissance de 2,
soit décomposer les matrices de taille 2n+1 en quatre blocs de taille : 2n x 2n, 1 x 2n, 2n x 1 et 1x1.
Le programme devra marcher avec des matrices 64x64.

Comparaison avec la méthode classique

Le programme devra aussi contenir une procédure qui fait le produit de matrices par la méthode classique avec n3 multiplications. Il calculera d'abord le produit de deux matrices, par la méthode en n3 et par la méthode de Strassen, puis la différence entre les deux résultats, et affichera enfin le plus grand coefficient (en valeur absolue) de cette différence.

Temps de calcul

Le programme devra compter et afficher le nombre total de multiplications et d'additions (ou de soustractions) de réels effectuées par la méthode de Strassen.
Eventuellement, pour optimiser le nombre total d'opérations élémentaires sur des réels, la procédure récursive de multiplication pourra choisir la méthode classique pour les petites tailles de matrices.

stockage des matrices de taille variable

Puisque le programme doit pouvoir faire des calculs sur des matrices de différentes tailles (Pour faire le produit de deux matrices 64x64, il faut faire 7 produits de matrices de 32x32, donc 49 produits de matrices 16x16, 343 produits de matrice 8x8, etc.) vous pourrez utilisez les types et procédures suivants : 
const nmax=64;
type vec=array[1..nmax] of real;
     mat=array[1..nmax] of ^vec;
procedure cree(var a:mat;n:integer);
var i:integer;
begin
  for i:=1 to n do (* new(a[i]) *) getmem(a[i],n*sizeof(a[i]^[1]))
end;
procedure detruit(var a:mat;n:integer);
var i:integer;
begin
  for i:=1 to n do (* dispose(a[i]) *) freemem(a[i],n*sizeof(a[i]^[1]))
end;
procedure muln3(var a,b,c:mat;n:integer);
...
   c[i]^[k]:=c[i]^[k]+a[i]^[j]*b[j]^[k]

documents à rendre

Vous devez rendre un programme écrit en pascal. De plus devez rendre le tableau suivant rempli avec pour chacune des tailles de matrice que votre programme peut multiplier, le nombre de multiplications de réels, le nombre d'additions ou de soustractions de réels, etc.
taille123...64
*
+ ou -
*, + ou -
2taille321654...524288
Ces documents doivent être rendus sur une disquette ou comme fichiers de texte joints à un courrier électronique envoyé à laurent.pierre@u-paris10.fr . Ils ne doivent pas être mis par un copier/coller dans le texte du message (cela change la mise en page et le transforme éventuellement en html) ni rendus sous forme de documents WORD (qui sont beaucoup plus gros, n'ont pas la même mise en page, ne peuvent pas être compilés directement et peuvent contenir des virus).

soutenance

Les projets sont à faire tout seul ou par groupe de deux. La note dépendra beaucoup de votre aptitude à faire des modifications dans le programme pendant la soutenance.
corrigé