3.3.2. Multiplicación rápida de matrices.

• Multiplicación rápida de matrices (Strassen):

P = (A11+A22)(B11+B22)

Q = (A12+A22) B11 C11 = P + S - T + U

R = A11 (B12-B22) C12 = R + T

S = A22(B21-B11) C21 = Q + S

T = (A11+A12)B22 C22 = P + R - Q + U

U = (A21-A11)(B11+B12)

V = (A12-A22)(B21+B22)

• El tiempo de ejecución será:

t(n) = 7·t(n/2) + a·n2

• Resolviéndolo, tenemos que t(n) ? O(nlog27) ? O(n2.81).

• Las constantes que multiplican al polinomio son mucho mayores (tenemos muchas sumas), por lo que sólo es mejor cuando la entrada es muy grande (empíricamente, para valores de n).

• Sin embargo, se demuestra que la cota de complejidad del problema es menor que O(n3).

Diapositiva anterior

Diapositiva siguiente

Ir a la primera diapositiva

Ver versión gráfica