Algoritmo de strassen

ESCUELA SUPERIOR POLITECNICA DEL LITORAL
Facultad de Ingeniería en Electricidad y Computación
Análisis de Algoritmos

Nombre: Jefferson Rubio Angulo
Paralelo: 1

DEBER
Análisis del Algoritmode Strassen

1. Explicar Strassen como División y Conquista

Sean A, B dos matrices cuadradas sobre un anillo R. Queremos calcular la matriz C como producto

Si las matrices A, B no son detipo 2n x 2n habrá que rellenar lo que falta de filas y columnas con ceros.
Partimos A, B y C en matrices de igual tamaño de bloque

Con

Entonces

Con esta construcción, no hemos reducido elnúmero de multiplicaciones. Todavía tenemos 8 multiplicaciones para calcular la matriz Ci, j , que es el mismo número de multiplicaciones que se necesitan cuando se usa el método estándar demultiplicación de matrices.

Ahora viene la parte importante. Definimos las matrices de nuevo

que luego se utilizan para expresar Ci, j en términos de Mk. Debido a nuestra definición de la Mk podemos eliminaruna multiplicación de matrices y reducir el número de multiplicaciones a 7 (una multiplicación por cada Mk) y expresar Ci, j como

Indicando lo anterior entonces la división, conquista y combinaciónson las siguientes:

División:
Como el algoritmo usa multiplicación de matrices de orden n x n, entonces se obtiene que el tiempo de división es:

tdivisión = (n)

Conquista:
Como alanalizar el algoritmo de Strassen requiere de 7 multiplicaciones de matrices de n2 x n2 , entonces se tiene que:

tconquista = 7tn2

Combinación:
Nada, porque ya el proceso termino en el tiempo deconquista.

2. Ecuación de recurrencia
Dado los parámetros en el literal anterior se obtiene que la ecuaci’on de recurrencia queda de la siguiente forma:
tn= 7tn2 + (n)

3. Resolver t en(nlg27)

tn= 7tn2 + (n)

tn= 7tn2 + n

Por teorema maestro:

a=7
b=2
f(n)=n

nlg27=n2,8

Caso 1: Si ∃ε>o fn∈O(nlgba-ε)

n2,8-ε
ε= 1,8

n ∈On, RO es reflexiva

Por lo...