La multiplicación de matrices y su costo

Componer aplicaciones

El producto $AB$ es la aplicación que se obtiene aplicando primero $B$ y luego $A$: $(AB)\mathbf{x}=A(B\mathbf{x})$. La entrada $(i,j)$ del producto es la fila $i$ de $A$ por la columna $j$ de $B$, así que los tamaños deben encajar: una matriz $m\times n$ por una $n\times p$ da una $m\times p$. El producto es asociativo, $(AB)C=A(BC)$, y distribuye sobre la suma, pero en general no es conmutativo: $AB\neq BA$, porque el orden de dos acciones importa.

Calcular $AB$ para una matriz $m\times n$ y una $n\times p$ cuesta $mnp$ multiplicaciones-sumas (unas $2mnp$ operaciones de coma flotante). Para dos matrices $n\times n$ son $n^3$: duplicar $n$ multiplica el trabajo por ocho. Una matriz por un vector cuesta solo $n^2$. Como el producto es asociativo, la posición de los paréntesis no cambia el resultado, pero puede cambiar enormemente el costo.

• Regla de tamaños: $(m\times n)(n\times p)=(m\times p)$; los tamaños interiores deben coincidir.
• No conmutativo: $AB\neq BA$ en general, así que nunca intercambie los factores.
• Costo: $mnp$ multiplicaciones-sumas; matriz por vector $n^2$, matriz por matriz $n^3$.

Lab: qué se califica

• El producto AB20 pts
• El producto BA15 pts
• El tamaño de un producto10 pts
• Contar multiplicaciones-sumas15 pts
• Dos formas de agrupar20 pts
• Por qué importa la agrupación20 pts