Idea común en la multiplicación de Karatsuba, Gauss y Strassen

19

Las identidades utilizadas en los algoritmos de multiplicación por

Parece muy relacionado. ¿Existe un marco abstracto general / generalización?

sdcvvc
fuente
3
Busque la desigualdad de suma asintótica de Schönhage.
Yuval Filmus
¿De qué identidades estás hablando? ¿Se supone que debemos leer los tres artículos para responder? Agregue la información relevante a su pregunta.
Raphael
1
@Raphael: las identidades que son la base de los algoritmos, que expresan 4 multiplicaciones numéricas con 3 multiplicaciones y 8 multiplicaciones matriciales con 7.
sdcvvc

Respuestas:

5

El marco clásico es el de algoritmos bilineales y descomposiciones de rango tensorial; básicamente, construye el tensor de 3 vías asociado al mapa bilineal F(UN,si)=UNsi , en base a los coeficientes, luego busca una descomposición del mismo como la suma de los tensores de rango uno (es decir, los de la forma Tyo,j,k=tuyovjwk ). Encontrará esto explicado con más detalle, por ejemplo, en este artículo de Bläser , o en el libro de Bürgisser, Clausen, Shokrollahi, Algebraic Complexity Theory.

Según tengo entendido, la reformulación en términos de representaciones grupales que Suresh menciona en su respuesta es posterior, y me parece menos adecuada para un primer acercamiento al tema (pero, por supuesto, eso podría ser un sesgo de mi parte )

Federico Poloni
fuente
1
Esta es la respuesta correcta. Un aspecto que falta es la tensorización / divide y vencerás, que está detrás del algoritmo de Karatsuba y los algoritmos de multiplicación de matriz rápida (cuadrada).
Yuval Filmus
8

Una respuesta parcial a su pregunta es el enfoque teórico grupal desarrollado por primera vez por Cohn y Umans y desarrollado por Cohn, Kleinberg, Szegedy y Umans. Puede "especie de" capturar Strassen y Coppersmith-Winograd para la multiplicación de matrices.

Suresh
fuente
Esto realmente pierde el punto. El enfoque teórico grupal es en realidad solo una forma de encontrar tales identidades en primer lugar.
Yuval Filmus