27.2: Multiplicaciones Matriz-Vector

Para introducir el concepto de operaciones escasas, primero consideremos la multiplicación de una matriz\(n \times n\) dispersa con un\(n\) vector (denso). Recordemos que la multiplicación matriz-vector puede interpretarse en forma de filas o de columnas. En la interpretación fila-wise, consideramos la tarea de computar\(w=A v\) como realizar productos\(n\) internos, uno por cada entrada de\(w\), es decir,\[w_{i}=\left(\begin{array}{llll} A_{i 1} & A_{i 2} & \ldots & A_{i n} \end{array}\right)\left(\begin{array}{c} v_{1} \\ v_{2} \\ \vdots \\ v_{n} \end{array}\right), \quad i=1, \ldots, n\] Si la matriz\(A\) es densa, los productos\(n\) internos de \(n\)-vectores requiere\(n \cdot(2 n)=2 n^{2}\) FLOP. Sin embargo, si la matriz\(A\) es escasa, entonces cada fila de\(A\) contiene pocas entradas diferentes de cero; así, podemos saltarnos una gran cantidad de multiplicaciones triviales en nuestros productos internos. En particular, el recuento de operaciones para el producto interno de un\(n\) vector escaso con un\(n\) vector denso es igual al doble del número de entradas diferentes de cero en el vector escaso. Así, el recuento de operaciones para toda la multiplicación matriz-vector es igual al doble del número de entradas diferentes de cero en la matriz, es decir\(2 \cdot \operatorname{nnz}(A)\), donde\(\operatorname{nnz}(A)\) está el número de entradas diferentes de cero en\(A\). Esto concuerda con nuestra intuición porque el producto matriz-vector requiere simplemente visitar cada entrada distinta de cero de\(A\), identificar el multiplicador apropiado en\(v\) base al índice de columna, y agregar el producto a la entrada apropiada de\(w\) basado en el índice de filas.

Ahora consideremos una interpretación de columna de la multiplicación matriz-vector. En este caso, interpretamos\(w=A v\) como\[\left(\begin{array}{c} w_{1} \\ w_{2} \\ \vdots \\ w_{n} \end{array}\right)=v_{1}\left(\begin{array}{c} A_{11} \\ A_{21} \\ \vdots \\ A_{n 1} \end{array}\right)+v_{2}\left(\begin{array}{c} A_{12} \\ A_{22} \\ \vdots \\ A_{n 2} \end{array}\right)+\cdots+v_{n}\left(\begin{array}{c} A_{1 n} \\ A_{2 n} \\ \vdots \\ A_{n n} \end{array}\right) .\] Si\(A\) es escaso entonces, cada columna de\(A\) contiene pocas entradas diferentes de cero. Así, para cada columna simplemente necesitamos escalar estas pocas entradas diferentes de cero por la entrada apropiada de\(v\) y aumentar las entradas correspondientes de\(w\); el recuento de operaciones es el doble del número de entradas diferentes de cero en la columna. Repitiendo la operación para todas las columnas de\(A\), el recuento de operaciones para toda la multiplicación matriz-vector es nuevamente\(2 \cdot \mathrm{nnz}(A)\).

Debido a que el número de entradas diferentes de cero en una matriz dispersa es (por definición)\(\mathcal{O}(n)\), el recuento de operaciones para el producto de vector de matriz dispersa es\(2 \cdot \operatorname{nnz}(A) \sim \mathcal{O}(n)\). Por ejemplo, para una matriz de bandas con ancho de banda\(m_{\mathrm{b}}\), el recuento de operaciones es como máximo\(2 n\left(2 m_{\mathrm{b}}+1\right)\). De esta manera, se logra una reducción significativa en el conteo de operaciones en comparación con la multiplicación matriz-vector densa, lo que requiere\(2 n^{2}\) operaciones.