Multiplicación y exponenciación de cadenas matriciales

13

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 .AB1000×22×1000(AB)5000A(BA)4999BAB1000×1000BA2×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:(A1A2Ak)n

  • (A1A2Ak)n
  • A1(A2AkA1)n1A2Ak
  • A1A2(A3AkA1A2)n1A3Ak
  • ...
  • A1A2Ak1(AkA1A2Ak1)n1Ak

... 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.KAnAnKKK

pyon
fuente
@ gnasher729: Lo siento, debería haber sido más explícito. No quiero forzar todas las posibilidades, por la misma razón por la que no querrías resolver la multiplicación de la cadena de la matriz por la fuerza bruta. Acabo de editar la pregunta en consecuencia.
pyon
A(BA)4999B
A(BA)2(21249+1)+1B
A(BA)n1BAB(AB)n2ABABA(BA)n3BAB
Cambiamos la base al vector Eigen para la exponenciación de la matriz y cuando toda la matriz tiene potencia 1, entonces podemos usar la multiplicación de la cadena de la matriz.
Deep Joshi
n×nn

Respuestas:

3

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.

(ABC)50(ABC)2ABCABCABC

ABCABC

A(B(CA))BCA(B(CA))49BC


(A1A2An)m(A1A2An)2
(A1A2An)2
GA1A2Gm1An


(AB)nABX×YY×XAB

X×Y
Y×X
Y×Y
X×X

X<YYX

X<Y
ABX×XAB(AB)n

YX
BAY×YABA(BA)n1B

ABAB

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:

julia> a=rand(1000,2);
julia> b=rand(2,1000);
julia> c=rand(1000,100);
julia> d=rand(100,1000);
julia> e=rand(1000,1000);

julia> @time (a*b*c*d*e)^30;
  0.395549 seconds (26 allocations: 77.058 MB, 1.58% gc time)

# Here I use an MCM solver to find out the optimal ordering for the square problem
julia> Using MatrixChainMultiply
julia> matrixchainmultiply("SOLVE_SQUARED", a,b,c,d,e,a,b,c,d,e)
Operation: SOLVE_SQUARED(A...) = begin  # none, line 1:
    A[1] * (((((A[2] * A[3]) * (A[4] * (A[5] * A[6]))) * (A[7] * A[8])) * A[9]) * A[10])
  end
Cost: 6800800

# Use the ordering found, note that exponentiation is applied to the group of 5 elements
julia> @time a*(((((b*c)*(d*(e*a)))^29*(b*c))*d)*e);
  0.009990 seconds (21 allocations: 7.684 MB)

# I also tried using the MCM for solving the problem directly
julia> @time matrixchainmultiply([30 instances of a,b,c,d,e]);
  0.094490 seconds (4.02 k allocations: 9.073 MB)
matteyas
fuente
1
(ABC)2
ABCABC(ABC)n(ABC)nA(BCA)n1BCAB(CAB)n1C
@DavidRicherby es la prueba informal agregada de algún uso?
matteyas
@matteyas: Eso es más o menos lo que dije en la primera edición de mi pregunta, ¿verdad?
pyon
ABCABC