La complejidad de la informática $ABx$ depende del orden de la multiplicación

Question

Para calcular el $y = ABx$ donde $A$ $B$ dos $N\times N$ matrices y $x$ es un vector en $N$espacio tridimensional. hay dos métodos. Uno es primero calcular el $z=Bx$, y, a continuación,$y = Az$. De esta manera se lleva aproximadamente el $2N^2$ multiplicaciones. El otro es primero calcular el $C = AB$, y, a continuación,$y=Cx$. De esta manera, sin embargo, tarda $N^3+N^2$ multiplicaciones!

Estoy en lo cierto en esto? No entiendo por qué el cambio de la orden del cálculo introduce tanta diferencia en el cálculo de la complejidad.

Answer 1

Me gusta esta pregunta. He visto la solución de manera eficiente el cálculo de una cadena de matriz de multiplicaciones en una clase de algoritmos, pero no es muy esclarecedor. Siempre he destinado a pensar más en el problema debido a que la asociatividad es muy interesante. Así que, déjame probar mi mano en una explicación.

Cuando usted tiene un $N$ $N$ matriz, es una abreviatura para describir una transformación lineal de un $N$-dimensional espacio vectorial a sí mismo. Esto hace que al seguir la pista de dónde $N$ vectores de la base son enviados (estas son las columnas de la matriz).

Ahora, sólo voy a hablar de forma heurística y no será muy preciso. Voy a decir que para escribir una matriz, usted sólo tiene que seguir la pista de donde $N$ vectores linealmente independientes se envían, no necesariamente una base. Esto es cierto, pero todos los tipos de real computacional cosas dependen de la base exacta (como de hecho la escritura de un vector, o haciendo cálculos estándar como $Bx$).

Cuando se compute $AB$, usted está guardando la pista de donde $N$ vectores linealmente independientes se envían. Pero cuando usted va en y el uso de su recién calculadas $AB$ a calcular $(AB)x$, que solo se preocupaba por donde $1$ vector se envía -- aunque fue a través de todos los problemas de mantener un registro de lo $AB$, $N - 1$ otros vectores!

Computación $A(Bx)$ es genial, porque en cada paso, sólo presta atención a lo que pasa con los vectores que te importa; no tiene idea de lo que pasa al otro $N - 1$ vectores linealmente independientes, y tan sólo se tarda alrededor de una $N$th tanto trabajo como computación en la $(AB)x$.

Aunque no es exactamente preciso, me gustaría creer que esta es la idea detrás de por qué computing $A(Bx)$ es más eficiente que la $(AB)x$, que es lo que creo que usted está después.

Answer 2

Sí estás en lo correcto, esto se utiliza mucho en la ingeniería. Dos de los más conocidos casos:

1. Sabiendo $AB$ y tratando de encontrar $A$ $B$ que, individualmente, contienen mayor porcentaje 0 de $AB$ multiplicados juntos. Generalmente se llama factoring o "fast transforma". Si perdemos el suficiente número cero podemos guardar los cálculos de esta manera.
2. Precomputing $AB$ si tenemos individuo $A$ $B$ y se desea calcular $ABv$ para los lotes de $v$:s. Esto se debe hacer si $AB$ es más simple que $A$, $B$ por separado.

Answer 3

Esto es debido a que el paso de $C = AB$ lleva más multiplicaciones como estamos multiplicar dos matrices, el primer método que mencionas no hacerlo.

Cada paso $z=Bx$ $y = Az$ contribuye $N^2$ multiplicaciones sólo, como es un vector se multiplica por una matriz y no de una matriz se multiplica por una matriz.