Realización manual de la multiplicación matricial en cadena

Question

Estoy intentando ganar intuición para escribir un algoritmo de multiplicación matricial en cadena resolviendo algunos problemas a mano. Veo un montón de soluciones trabajadas sobre conjuntos de tres o cuatro soluciones, pero no mucho para conjuntos mayores que eso. Pero el método que he visto hasta ahora es extremadamente tedioso para el escenario que estoy intentando:

Encuentra la mejor manera de multiplicar una cadena de matrices con dimensiones de $A = 10 \times 5$ , $B = 5 \times 2$ , $C = 2 \times 20$ , $D = 20 \times 12$ , $E = 12 \times 4$ et $F = 4 \times 60$ . Muestra tu trabajo.

En los ejemplos más pequeños que he hecho hasta ahora, he podido simplemente multiplicar las dimensiones de cada -- $AB, BC, ..., EF$ -- y añadir los valores mínimos para cubrir todas las matrices. Supongo que podría hacer lo mismo en un problema como este, pero sería extremadamente cansado y me pregunto si hay una manera mejor que la fuerza bruta para hacer esto. Ayuda.

Answer 1

Empiece por encontrar los costes de todas las subsecuencias de longitud 2, luego utilícelos para encontrar los costes mínimos de todas las subsecuencias de longitud 3, etc. Desgraciadamente, esto es $O(n^3)$ así que es tedioso, como has visto.

Hay un $n \ln n$ explicación del algoritmo aquí pero por lo que he ojeado parece que se basa en una simetría que sólo existe cuando la matriz resultante es cuadrada.

Answer 2

Si algunas de estas matrices tienen características especiales, por ejemplo, tienen muchos ceros, entonces eso ayudaría. Para matrices genéricas no se puede hacer mucho más.

Answer 3

Si puedes usa primero la reducción de Gauss o encuentra alguna matriz diagonalizable.