Introduction au calcul formel

lemaire1995

Bonjour tout le monde !
J'ai un problème pour résoudre cet exercice.

Évaluer la complexité binaire du calcul du produit de deux matrices n*n dont les coefficients sont des entiers plus petits que M.

lemaire1995

Apparemment personne n'est en mesure de me donner un coup de main ?

Joaopa

algorithme de Coppersmith-Winograd

Poirot

La question ne veut rien dire en soi, quelle est la méthode utilisée ? Si c'est la multiplication bête et méchante, eh bien compte le nombre de multiplications et additions que tu devras faire si tu multiplies deux telles matrices.

parisse

O(n^3*ln(M)^2) en utilisant des algorithmes naifs. On peut faire asymptotiquement mieux, par exemple O(n^(ln(7)/ln(2))*ln(M)^(ln(3)/ln(2)) avec Strassen (pour multiplier les matrices) et Karatsuba (pour multiplier les entiers).