Si tengo dos matrices y B , de dimensiones 1000 × 2 y 2 × 1000 , respectivamente, y quiero calcular ( A B ) 5000 , es más eficiente reescribir primero la expresión como A ( B A ) 4999 B y solo entonces evalúe numéricamente, porque A B es de dimensión 1000 × 1000 pero B A es de dimensión 2 × 2 .
Quiero resolver una versión generalizada de este problema. ¿Existe un algoritmo razonablemente eficiente (no fuerza bruta) para optimizar una expresión que contiene:
- Variables matriciales libres de dimensiones conocidas
- Productos de subexpresiones arbitrarias
- Subexpresiones arbitrarias elevadas al poder natural
... para que se requiera la menor cantidad de trabajo para evaluar numéricamente, después de sustituir las variables de matriz libre con valores de matriz concretos?
El problema de multiplicación de la cadena de la matriz es un caso especial de mi problema.
Editar:
Esta es una respuesta tentativa. Me parece intuitivamente correcto, pero no tengo pruebas de que sea correcto. Si resulta ser correcto, todavía estoy interesado en la prueba. (Si no es correcto, por supuesto, corrígeme).
Por cada producto elevado a una potencia, digamos, , considere cada permutación cíclica de los factores:
- ...
... recursivamente. Cada potencia debe calcularse utilizando la exponenciación al cuadrado (obviamente), y todos los demás productos deben calcularse utilizando el orden óptimo devuelto por el algoritmo de multiplicación de la cadena de la matriz.
Editar:
La idea esbozada en mi edición anterior todavía es algo no óptima. La exponenciación mediante el algoritmo de cuadratura en realidad evalúa expresiones de la forma o A n K , donde K no es necesariamente la matriz de identidad. Pero mi algoritmo no considera la posibilidad de utilizar la exponenciación mediante el algoritmo de cuadratura con K no igual a la matriz de identidad.
Respuestas:
Descargo de responsabilidad: El siguiente método no ha sido rigurosamente probado para ser óptimo. Se proporciona una prueba informal.
El problema se reduce a encontrar el pedido más eficiente al considerar el cuadrado del producto.
Usando más matrices, el argumento es similar. Quizás una prueba inductiva es posible? La idea general es que resolver el MCM para el cuadrado encontrará el tamaño óptimo para las operaciones con todas las matrices involucradas consideradas.
Caso de estudio:
fuente
fuente