La forma más rápida de multiplicar matrices 2D
Leí en el artículo sobre la entrevista de aprendizaje automático, hay una pregunta:
"Multiplicar 2 matrices con la forma 10000x10000. ¿Cómo acelerar el cálculo?"
El candidato dijo: "Multi-hilo", pero el entrevistador dijo que había otra forma de hacerlo, la forma matemática.
¿Alguien puede darme una solución? ¿Está relacionado con el "valor propio"?
Respuestas
La pregunta no era justa, porque si no sabe la respuesta es difícil de adivinar. Lo más probable es que el entrevistador se refiriera al método de multiplicación más rápido (más) de Strassen y similares.https://en.wikipedia.org/wiki/Strassen_algorithm#:~:text=In%20linear%20algebra%2C%20the%20Strassen,algorithms%20for%20extremely%20large%20matrices.
La idea básica es que si descompone ambas matrices cada una en cuatro bloques, puede realizar el producto en multiplicaciones de 7 bloques en lugar de los 8. Y al aplicar este principio de forma recursiva, se rompe el $O(n^3)$ barrera.
Pero no veo cómo esto pertenece al aprendizaje automático.