Cálculo del número de operaciones en la multiplicación de matrices

Question

¿Existe alguna fórmula para calcular el número de multiplicaciones que tienen lugar al multiplicar 2 matrices? Por ejemplo

$$\begin{pmatrix}1&2\\3&4\end{pmatrix} \times \begin{pmatrix}5&6\\7&8\end{pmatrix} = \text{8 multiplications and 4 additions} $$

Answer 1

Hacer un $k\times l$ veces $l\times m$ multiplicación de matrices de forma directa, cada entrada del resultado es un producto escalar de dos $l$ -vectores, lo que requiere $l$ multiplicaciones y $l-1$ adiciones. Multiplícalo por el número $km$ de entradas del resultado (o no multiplique si tiene suficientes procesadores para hacerlo todo en paralelo).

Answer 2

Me gustaría dar una respuesta sencilla para la plaza, $n$ x $n$ matrices utilizando el algoritmo estándar de multiplicación de matrices.

Supongamos que tenemos dos matrices cuadradas $A$ y $B$ . Elemento de cálculo $a_{ij}$ de $AB$ requiere tomar el producto punto de la fila $i$ en $A$ y columna $j$ en B. El cálculo del producto punto requiere $n$ multiplicaciones y $n-1$ adiciones. Puesto que hay $n^2$ elementos, debe calcularse el producto punto $n^2$ veces.

Por tanto, el número total de operaciones es $n^2(n+(n-1))=2n^3-n^2 = O(n^3).$