4.1.1 La operación de multiplicación de matrices

En general la multiplicación de matrices no es conmutativa. Por otro lado, ésta sólo se puede realizar si las matrices cumplen cierta condición. Si el número de columnas en la matriz $B$ es igual al número de renglones en la matriz $A$, las matrices se denominan conformables, y pueden multiplicarse en el orden $B \times A$. Específicamente, si $B$ es una matriz de dimensiones $(q,n)$ y $A$ tiene dimensiones $(m,p)$ el producto $BA$ será una matriz $(q,p)$, es decir:

$$(q,n) \times (m,p) = (q,p)$$

Una vez conocidas las dimensiones de la matriz resultado, para obtener cada elemento de la misma se procede como sigue:

Para obtener el elemento $i$ en la columna $j$ del producto $P= BA$, se selecciona el $i$ésimo renglón de $B$ y la $j$ésima columna de $A$, y se suman los productos de sus elementos correspondientes, iniciando en el extremo izquierdo y la parte superior, respectivamente. Así:

$$P_{ij}=\sum_{r=1}^n B_{ir}A_{rj}$$

Se observa que la multiplicación de matrices es un problema muy fácilmente paralelizable; de hecho, se encuentra en la categoría de problemas conocidos como ``vergonzosamente paralelizables''<sup>4.1</sup>. Esto es porque cada nodo que participe en el cálculo únicamente necesita conocer, antes de iniciar, los valores de las dos matrices a multiplicar; y en ningún momento requerirá comunicarse con los demás nodos para realizar su trabajo. Como se verá más adelante, la implementación más sencilla involucra comunicación con un proceso ``maestro'' o ``padre'' que recoge y consolida los resultados parciales de los nodos, pero en ningún momento se requerirá que los nodos detengan su cálculo para esperar información de otro nodo.