Multiplicacion de matrices y analisis de complejidad

La idea en simple

Como multiplicar. Cada casilla del resultado es “fila por columna”: multiplicas emparejando y sumas. Para $c_{11}$ tomas la fila 1 de $A$ y la columna 1 de $B$: $2\cdot1 + 3\cdot2 + 1\cdot3 = 11$. Repitiendo:

$A\times B = \begin{pmatrix} 11 & 11 \\ 19 & 16 \end{pmatrix}.$

Se puede $B\times A$? Si, porque las dimensiones internas encajan ($2 = 2$), y da una matriz $3\times3$ distinta. Ojo: multiplicar matrices no es como con numeros, el orden importa.

Por que es lento ($O(n^3)$). Para llenar una matriz $n\times n$ recorres filas ($n$) por columnas ($n$), y cada casilla necesita una sumatoria de $n$ productos. Son tres bucles encajados: $n\times n\times n = n^3$. Con $n = 1000$ eso son $1000^3 =$ mil millones de multiplicaciones.

Se puede acelerar? Si:

• Strassen hace la cuenta con 7 multiplicaciones de bloques en vez de 8 y baja el exponente a $\approx 2.807$, util para matrices grandes.
• Si la matriz es dispersa (casi todo ceros), guardas solo los numeros que no son cero y te saltas los ceros al multiplicar (cualquier cosa por cero es cero). Con 90% de ceros haces como $10\times$ menos trabajo.

Solucion formal

(a) $A_{2\times3}\,B_{3\times2} = C_{2\times2}$, con $c_{ij} = \sum_{k=1}^{3} a_{ik} b_{kj}$:

$C = \begin{pmatrix} 11 & 11 \\ 19 & 16 \end{pmatrix}.$

(b) $B_{3\times2}\,A_{2\times3} = (BA)_{3\times3}$, con $(BA)_{ij} = \sum_{k=1}^{2} b_{ik} a_{kj}$:

$BA = \begin{pmatrix} 18 & 3 & 21 \\ 8 & 6 & 7 \\ 6 & 9 & 3 \end{pmatrix}.$

Como $AB \neq BA$, el producto no es conmutativo.

(c) El producto de $M_{n\times n}$ requiere $c_{ij}=\sum_{k=1}^{n}a_{ik}b_{kj}$ para cada uno de los $n^2$ pares $(i,j)$, y cada suma tiene $n$ terminos:

$\#\text{mult} = \sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n} 1 = n^3 \;\Rightarrow\; O(n^3).$

Tres bucles anidados; el interno hace una multiplicacion-acumulacion.

(d) $n = 1000 \Rightarrow n^3 = 10^9$ multiplicaciones escalares.

(e) Strassen: $O(n^{\log_2 7}) = O(n^{2.807})$, dividiendo en bloques $\tfrac{n}{2}\times\tfrac{n}{2}$ y usando 7 (no 8) multiplicaciones recursivas. Como $\log_2 7 < 3$, es asintoticamente mejor para $n$ grande.

(f) Matriz dispersa: almacenar solo elementos no nulos (COO: $(i,j,v)$; o CSR). En la multiplicacion se omiten los productos con factor cero, reduciendo el costo de $O(n^3)$ a $O(nnz\cdot n)$, proporcional al numero de no nulos $nnz$. $\blacksquare$

Solucion

(a) Producto $C = A \times B$

$A$ es $2\times 3$ y $B$ es $3\times 2$; como las dimensiones internas coinciden ($3 = 3$), el producto existe y $C$ es $2\times 2$. Cada entrada es $c_{ij} = \sum_{k=1}^{3} a_{ik}\,b_{kj}$:

$$\begin{aligned} c_{11} &= 2\cdot 1 + 3\cdot 2 + 1\cdot 3 = 2 + 6 + 3 = 11\\ c_{12} &= 2\cdot 4 + 3\cdot 1 + 1\cdot 0 = 8 + 3 + 0 = 11\\ c_{21} &= 4\cdot 1 + 0\cdot 2 + 5\cdot 3 = 4 + 0 + 15 = 19\\ c_{22} &= 4\cdot 4 + 0\cdot 1 + 5\cdot 0 = 16 + 0 + 0 = 16 \end{aligned}$$

$C = A \times B = \begin{pmatrix} 11 & 11 \\ 19 & 16 \end{pmatrix}_{2\times 2}$

(b) Producto $B \times A$

$B$ es $3\times 2$ y $A$ es $2\times 3$; las dimensiones internas coinciden ($2 = 2$), asi que $B\times A$ si existe y tiene dimension $3\times 3$. Aqui $(BA)_{ij} = \sum_{k=1}^{2} b_{ik}\,a_{kj}$:

$$\begin{aligned} &(BA)_{11}=1\cdot2+4\cdot4=18, &&(BA)_{12}=1\cdot3+4\cdot0=3, &&(BA)_{13}=1\cdot1+4\cdot5=21\\ &(BA)_{21}=2\cdot2+1\cdot4=8, &&(BA)_{22}=2\cdot3+1\cdot0=6, &&(BA)_{23}=2\cdot1+1\cdot5=7\\ &(BA)_{31}=3\cdot2+0\cdot4=6, &&(BA)_{32}=3\cdot3+0\cdot0=9, &&(BA)_{33}=3\cdot1+0\cdot5=3 \end{aligned}$$

$B \times A = \begin{pmatrix} 18 & 3 & 21 \\ 8 & 6 & 7 \\ 6 & 9 & 3 \end{pmatrix}_{3\times 3}$

Observacion: $A\times B \neq B\times A$ (ni siquiera tienen la misma dimension). El producto de matrices no es conmutativo.

(c) Por que el algoritmo clasico es $O(n^3)$

for (int i = 0; i < n; i++)        // fila de C
  for (int j = 0; j < n; j++) {    // columna de C
    C[i][j] = 0;
    for (int k = 0; k < n; k++)    // producto punto
      C[i][j] += A[i][k] * B[k][j];  // operacion del bucle interno
  }

Son tres bucles anidados de $n$ iteraciones cada uno. El bucle mas interno ejecuta una multiplicacion-acumulacion ($C[i][j] \gets C[i][j] + A[i][k]\cdot B[k][j]$). El total de multiplicaciones escalares es

$n \cdot n \cdot n = n^3 \;\Rightarrow\; O(n^3).$

(d) Dos matrices de $1000 \times 1000$

$n^3 = 1000^3 = 10^9 \text{ multiplicaciones escalares}$

Es decir, mil millones de multiplicaciones (y aproximadamente la misma cantidad de sumas). Esto ilustra por que el crecimiento cubico se vuelve costoso rapidamente.

(e) Algoritmo de Strassen

Strassen multiplica dos matrices en

$O\!\left(n^{\log_2 7}\right) = O\!\left(n^{2.807\ldots}\right).$

La idea es dividir cada matriz en cuatro bloques $\tfrac{n}{2}\times\tfrac{n}{2}$ y calcular el producto usando 7 multiplicaciones de bloques en lugar de las 8 del metodo clasico (a cambio de mas sumas/restas). Al aplicarlo recursivamente, el exponente baja de $3$ a $\log_2 7 \approx 2.807$. Como $2.807 < 3$, para $n$ grande Strassen realiza asintoticamente menos operaciones. En la practica solo compensa por encima de cierto umbral (matrices grandes), porque las constantes ocultas y las sumas extra lo hacen mas lento para $n$ pequeno.

(f) Matriz dispersa (90% ceros)

Si el 90% de las entradas son cero, guardar $n^2$ valores desperdicia memoria y tiempo. Representaciones eficientes:

• Lista de coordenadas (COO): se guardan solo las triplas $(fila, columna, valor)$ de los elementos no nulos.
• CSR (Compressed Sparse Row): tres vectores — valores, indices_columna y punteros_fila — que permiten recorrer por filas sin almacenar ceros.

Multiplicacion aprovechando la dispersion: como $0 \cdot x = 0$, se omiten todos los productos donde algun factor es cero. El costo pasa a ser proporcional al numero de elementos no nulos ($nnz$) en lugar de $n^3$. Con un 90% de ceros hay ~$10\times$ menos entradas activas, de modo que la multiplicacion dispersa realiza del orden de $O(nnz \cdot n)$ operaciones en vez de $O(n^3)$, un ahorro enorme para matrices grandes y muy dispersas.