¿Cómo demostrar que la multiplicación matricial de dos matrices 2x2 no se puede hacer en menos de 7 multiplicaciones?

En la multiplicación matricial de Strassen, afirmamos un hecho extraño (al menos para mí) de que la multiplicación matricial de dos 2 x 2 requiere 7 multiplicaciones.

Pregunta: ¿Cómo demostrar que es imposible multiplicar dos matrices de 2 x 2 en 6 multiplicaciones?

Tenga en cuenta que las matrices están sobre enteros.

algorithms complexity-theory lower-bounds Complejidad
fuente

Existen otros algoritmos de multiplicación de matrices que pueden ser más rápidos. Este artículo web de una clase Stanford CME 323 proporciona detalles sobre el algoritmo de Strassen, Matrix multiplication: algoritmo de Strassen . Hay un tema de Wikipedia, el algoritmo de Strassen que entra en detalles y tiene enlaces a información adicional.

Richard Chambers el

@RichardChambers Observe que el algoritmo de Strassen tiene multiplicaciones. Me parece plausible que este límite inferior sea cierto.

7

$7$

Stella Biderman

Tal como está redactado, esta pregunta es incorrecta. Hay muchas matrices que se pueden multiplicar con multiplicaciones. Te refieres a pedir una prueba de que, en el peor de los casos, se necesitan 7 aka, existe alguna matriz que requiere 7

6

$6$

Stella Biderman

@StellaBiderman sí, vi que Strassen tiene 7 multiplicaciones. No miré el otro, más rápido y algoritmos con menor complejidad. Por lo que puedo decir, usan el mismo enfoque de submatriz que el de Strassen, pero no estoy seguro. Solo estaba agregando información adicional sobre Strassen específicamente.

Richard Chambers

Parece que falta algo en su pregunta. Puedo dar fácilmente un algoritmo que puede multiplicar al menos algunas matrices con 0 multiplicaciones. Probablemente hay una restricción que no estás mencionando.

Jörg W Mittag

Respuestas:

Este es un resultado clásico de Winograd: sobre la multiplicación de matrices de 2x2 .

$n\times n$ $O(n^\alpha)$ $\langle n,n,n \rangle$ $n\times n$ $O(n^\alpha)$ Desde el límite superior . $O(n^{\log_27})$ $R(\langle 2,2,2 \rangle) \leq 7$

El resultado de Winograd implica que . Landsberg mostró que el rango límite de es también 7, y Bläser et al. recientemente extendió eso para apoyar el rango y el rango de soporte fronterizo El rango de borde y el rango de soporte son nociones más débiles (= más pequeñas) de rango que se han utilizado (en el caso de rango de borde) o propuesto (en el caso de rango de soporte) en los algoritmos de multiplicación de matriz rápida. $R(\langle 2,2,2 \rangle)=7$ $\langle 2,2,2 \rangle$

Yuval Filmus
fuente

Puede encontrar el resultado en:

S.Winograd, sobre la multiplicación de matrices 2 × 2 , álgebra lineal y aplicación. 4 (1971), 381–388, MR0297115 (45: 6173).

Stella Biderman
fuente