Algoritmo de Strassen

Algoritmo de Strassen

En la disciplina matemática del álgebra lineal, el algoritmo de Strassen, llamado así por Volker Strassen, es un algoritmo usado para la multiplicación de matrices. Es asintóticamente más rápido que el algoritmo de multiplicación de matrices estándar, pero más lento que el algoritmo más rápido conocido, y es útil en la práctica para matrices grandes.

Contenido

Historia

Volker Strassen publicó el algoritmo de Strassen en 1969. Pese a que su algoritmo es sólo ligeramente más rápido que el algoritmo estándar para la multiplicación de matrices, fue el primero en señalar que el enfoque estándar no es óptimo. Su artículo comenzó la búsqueda de algoritmos aún más rápidos, como el complejo algoritmo de Coppersmith–Winograd de Shmuel Winograd en 1910 (que utiliza 20 multiplicaciones binarias, pero utiliza 155 sumas binarias en lugar de las 18 del algoritmo de Strassen), publicado en 2000 .

Algoritmo

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

\mathbf{C} = \mathbf{A} \mathbf{B} \qquad \mathbf{A},\mathbf{B},\mathbf{C} \in R^{2^n \times 2^n}

Si las matrices A, B no son de tipo 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

\mathbf{A} = \begin{bmatrix} \mathbf{A}_{1,1} & \mathbf{A}_{1,2} \\ \mathbf{A}_{2,1} & \mathbf{A}_{2,2} \end{bmatrix} \mbox { , } \mathbf{B} = \begin{bmatrix} \mathbf{B}_{1,1} & \mathbf{B}_{1,2} \\ \mathbf{B}_{2,1} & \mathbf{B}_{2,2} \end{bmatrix} \mbox { , } \mathbf{C} = \begin{bmatrix} \mathbf{C}_{1,1} & \mathbf{C}_{1,2} \\ \mathbf{C}_{2,1} & \mathbf{C}_{2,2} \end{bmatrix}

Con

\mathbf{A}_{i,j}, \mathbf{B}_{i,j}, \mathbf{C}_{i,j} \in R^{2^{n-1} \times 2^{n-1}}

Entonces

\mathbf{C}_{1,1} = \mathbf{A}_{1,1} \mathbf{B}_{1,1} + \mathbf{A}_{1,2} \mathbf{B}_{2,1}
\mathbf{C}_{1,2} = \mathbf{A}_{1,1} \mathbf{B}_{1,2} + \mathbf{A}_{1,2} \mathbf{B}_{2,2}
\mathbf{C}_{2,1} = \mathbf{A}_{2,1} \mathbf{B}_{1,1} + \mathbf{A}_{2,2} \mathbf{B}_{2,1}
\mathbf{C}_{2,2} = \mathbf{A}_{2,1} \mathbf{B}_{1,2} + \mathbf{A}_{2,2} \mathbf{B}_{2,2}

Con esta construcción, no hemos reducido el nú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 de multiplicación de matrices.

Ahora viene la parte importante. Definimos las matrices de nuevo

\mathbf{M}_{1} := (\mathbf{A}_{1,1} + \mathbf{A}_{2,2}) (\mathbf{B}_{1,1} + \mathbf{B}_{2,2})
\mathbf{M}_{2} := (\mathbf{A}_{2,1} + \mathbf{A}_{2,2}) \mathbf{B}_{1,1}
\mathbf{M}_{3} := \mathbf{A}_{1,1} (\mathbf{B}_{1,2} - \mathbf{B}_{2,2})
\mathbf{M}_{4} := \mathbf{A}_{2,2} (\mathbf{B}_{2,1} - \mathbf{B}_{1,1})
\mathbf{M}_{5} := (\mathbf{A}_{1,1} + \mathbf{A}_{1,2}) \mathbf{B}_{2,2}
\mathbf{M}_{6} := (\mathbf{A}_{2,1} - \mathbf{A}_{1,1}) (\mathbf{B}_{1,1} + \mathbf{B}_{1,2})
\mathbf{M}_{7} := (\mathbf{A}_{1,2} - \mathbf{A}_{2,2}) (\mathbf{B}_{2,1} + \mathbf{B}_{2,2})

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

\mathbf{C}_{1,1} = \mathbf{M}_{1} + \mathbf{M}_{4} - \mathbf{M}_{5} + \mathbf{M}_{7}
\mathbf{C}_{1,2} = \mathbf{M}_{3} + \mathbf{M}_{5}
\mathbf{C}_{2,1} = \mathbf{M}_{2} + \mathbf{M}_{4}
\mathbf{C}_{2,2} = \mathbf{M}_{1} - \mathbf{M}_{2} + \mathbf{M}_{3} + \mathbf{M}_{6}

Iteramos n-veces el proceso de división hasta que las submatrices degeneran en números (elementos del anillo R).

Las implementaciones prácticas del algoritmo de Strassen, permiten cambiar a métodos estándar de multiplicación de matrices para submatrices lo suficientemente pequeñas, para las cuales son más eficientes. El punto a partir del cual el algoritmo de Strassen es más eficiente depende de la implementación específica y del hardware. Se ha estimado que el algoritmo de Strassen es más rápido para matrices con anchura desde 32 a 128 para implementaciones optimizadas,[1] y 60.000 o más para implementaciones básicas.[2]

Análisis numérico

La multiplicación de matrices estándar requiere aproximadamente 2N3 (donde N = 2n)operaciones aritméticas (sumas y multiplicaciones); la complejidad asintótica es O(N3).

El número de sumas y multiplicaciones requeridas en el algoritmo de Strassen puede ser calculado como sigue: sea f(n) el número de operaciones para una matriz de 2^n \times 2^n. Entonces por aplicación recursiva del algoritmo de Strassen, vemos que f(n) = 7f(n − 1) + l4n, para alguna constante l que depende del número de sumas realizadas en cada aplicación del algoritmo. Por lo tanto f(n) = (7 + o(1))n,esto es, la complejidad asintótica para multiplicar matrices de tamaño N = 2n usando el algoritmo de Strassen es

O((7+o(1))^n) = O(N^{\log_{2}7+o(1)}) \approx O(N^{2.807}).

La reducción en el número de operaciones aritméticas se obtiene a cambio de reducir un tanto la estabilidad numérica.

Referencias

  1. ↑ Skiena, Steven S. (1998), «§8.2.3 Multiplicación de matrices», El manual de diseño de algoritmos, Berlín, Nueva York: Springer-Verlag, ISBN 978-0-387-94860-7 .
  2. ↑ Kakaradov, Boyko (2004), «Multiplicación de matrices ultra-rápida: Un análisis empirico de algoritmos de vector altamente optimizados», Stanford Undergraduate Research Journal 3: 33–36, http://surj.stanford.edu/2004/pdfs/kakaradov.pdf .
  • Strassen, Volker, La eliminación gaussiana no es óptima, Numer. Math. 13, p. 354-356, 1969
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, y Clifford Stein. Introducción a los algoritmos, Segunda edición. MIT Press y McGraw-Hill, 2001. ISBN 0-262-03293-7. Capítulo 28: Sección 28.2: Algoritmo de Strassen para multiplicación de matrices, pp.735–741.

Enlaces externos


Wikimedia foundation. 2010.

Игры ⚽ Нужен реферат?

Mira otros diccionarios:

  • Algoritmo de Karatsuba — El algoritmo de Karatsuba es un procedimiento para multiplicar números grandes eficientemente, que fue descubierto por Anatolii Alexeevitch Karatsuba en 1960 y publicado en 1962.[1] [2] El algoritmo consigue reducir la múltiplicación de dos… …   Wikipedia Español

  • Algoritmo de multiplicación — Para ver definiciones sobre multiplicación, véase multiplicación. Un algoritmo de multiplicación es un algoritmo (o método) para multiplicar dos números. Dependiendo del tamaño de los números, existen diferentes algoritmos. Los algoritmos de… …   Wikipedia Español

  • Volker Strassen — dando la conferencia del premio Knuth en SODA 2009. Volker Strassen es un matemático alemán, profesor emérito del departamento de matemáticas y estadística de la Universidad de Constanza.[1] …   Wikipedia Español

  • P (Complejidad computacional) — Saltar a navegación, búsqueda Contenido 1 Introducción 2 La clase P 3 Problemas notables en P 4 Propiedades …   Wikipedia Español

  • P (clase de complejidad) — Se ha sugerido que este artículo o sección sea fusionado con Tiempo polinómico (discusión). Una vez que hayas realizado la fusión de artículos, pide la fusión de historiales aquí …   Wikipedia Español

  • Complejidad y criptografía — La criptografía es la ciencia encargada del estudio y diseño de sistemas que permiten ocultar información. Desde sus inicios, esta capacidad de encubrimiento se ha basado en la dificultad que supondría a una entidad no autorizada el obtener la… …   Wikipedia Español

  • Test de primalidad — El 39º número primo de Mersenne era el mayor conocido hasta la fecha de creación de este artículo. La cuestión de la determinación de si un número n …   Wikipedia Español

  • Número primo — Un número primo es un número natural mayor que 1, que tiene únicamente dos divisores distintos: él mismo y el 1. Se contraponen así a los números compuestos, que son aquellos que tienen algún divisor natural aparte de sí mismos y del 1. El número …   Wikipedia Español

  • Multiplicador modular inverso — Saltar a navegación, búsqueda El multiplicador modular inverso de un entero n módulo p es un entero m tal que n 1 ≡ m (mod p) Esto significa que es el multiplicador inverso en el anillo de los enteros módulo p. Es equivalente a mn ≡ 1 (mod p) El… …   Wikipedia Español

  • Inverso multiplicativo (aritmética modular) — Este artículo o sección sobre matemáticas necesita ser wikificado con un formato acorde a las convenciones de estilo. Por favor, edítalo para que las cumpla. Mientras tanto, no elimines este aviso puesto el 16 de abril de 2011. También puedes …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”