Conozco dos grandes matrices se pueden multiplicar más rápidamente que uno esperaría ingenuamente. Un gran número de la misma matriz se puede multiplicar rápidamente utilizando cuadratura repetida. Pero ¿qué pasa con un gran número de pequeñas matrices? ¿En concreto, puedo encontrar el producto de 1,000002 millones matrices todas las entradas que son enteros positivos menos que cinco rápidamente (más rápido de lo esperado)?
Respuesta
¿Demasiados anuncios?
AlgorithmsX
Puntos
101
He estado mirando a su alrededor, y que en realidad no se parece a él. Los problemas vienen de no ser capaz de reorganizar las matrices debido a su falta de communitivity y todos la mejor de la multiplicación de la matriz algoritmos funcionan mejor en las grandes matrices que en la más pequeña de las matrices.
Su mejor apuesta sería la de ejecutar una búsqueda preliminar para patrones como $ABABABABABABABAB$, la cual puede ser reducido a $(AB)^8$, whicy puede ser calculado de forma rápida mediante el uso de métodos como la exponenciación al cuadrado. Incluso la búsqueda de un patrón parece un poco difícil. Usted probablemente todavía tomar alrededor de un millón de cálculos más o menos.
