En análisis numérico y computación científica , una matriz dispersa o matriz dispersa es una matriz en la que la mayoría de los elementos son cero. [1] No existe una definición estricta con respecto a la proporción de elementos de valor cero para que una matriz califique como dispersa, pero un criterio común es que el número de elementos distintos de cero es aproximadamente igual al número de filas o columnas. Por el contrario, si la mayoría de los elementos son distintos de cero, la matriz se considera densa . [1] El número de elementos de valor cero dividido por el número total de elementos (por ejemplo, m × n para una matriz m × n ) a veces se denomina escasez de la matriz.
Conceptualmente, la escasez corresponde a sistemas con pocas interacciones por pares. Por ejemplo, considere una línea de bolas conectadas por resortes de una a otra: este es un sistema disperso ya que sólo se acoplan bolas adyacentes. Por el contrario, si la misma línea de bolas tuviera resortes que conectaran cada bola con todas las demás, el sistema correspondería a una matriz densa. El concepto de escasez es útil en combinatoria y áreas de aplicación como la teoría de redes y el análisis numérico , que normalmente tienen una baja densidad de datos o conexiones importantes. Las matrices grandes y dispersas suelen aparecer en aplicaciones científicas o de ingeniería al resolver ecuaciones diferenciales parciales .
Al almacenar y manipular matrices dispersas en una computadora , es beneficioso y, a menudo, necesario utilizar algoritmos especializados y estructuras de datos que aprovechen la estructura dispersa de la matriz. Se han creado computadoras especializadas para matrices dispersas, [2] ya que son comunes en el campo del aprendizaje automático. [3] Las operaciones que utilizan estructuras y algoritmos estándar de matriz densa son lentas e ineficientes cuando se aplican a matrices grandes y dispersas, ya que el procesamiento y la memoria se desperdician en los ceros. Los datos dispersos se comprimen más fácilmente por naturaleza y, por lo tanto, requieren mucho menos almacenamiento . Algunas matrices dispersas muy grandes no son factibles de manipular utilizando algoritmos estándar de matriz densa.
Un tipo especial importante de matrices dispersas es la matriz de bandas , definida de la siguiente manera. El ancho de banda inferior de una matriz A es el número más pequeño p tal que la entrada a i , j desaparece siempre que i > j + p . De manera similar, el ancho de banda superior es el número más pequeño p tal que a i , j = 0 siempre que i < j − p (Golub & Van Loan 1996, §1.2.1). Por ejemplo, una matriz tridiagonal tiene un ancho de banda inferior 1 y un ancho de banda superior 1 . Como otro ejemplo, la siguiente matriz dispersa tiene un ancho de banda superior e inferior igual a 3. Observe que los ceros se representan con puntos para mayor claridad.
Las matrices con un ancho de banda superior e inferior razonablemente pequeño se conocen como matrices de banda y, a menudo, se prestan a algoritmos más simples que las matrices dispersas generales; o a veces se pueden aplicar algoritmos matriciales densos y ganar eficiencia simplemente haciendo un bucle sobre un número reducido de índices.
Reorganizando las filas y columnas de una matriz A puede ser posible obtener una matriz A ' con un ancho de banda menor. Se han diseñado varios algoritmos para minimizar el ancho de banda .
Una estructura muy eficiente para un caso extremo de matrices de bandas, la matriz diagonal , es almacenar solo las entradas en la diagonal principal como una matriz unidimensional , por lo que una matriz diagonal n × n requiere solo n entradas.
Una matriz dispersa simétrica surge como matriz de adyacencia de un gráfico no dirigido ; se puede almacenar eficientemente como una lista de adyacencia .
Una matriz diagonal de bloques consta de submatrices a lo largo de sus bloques diagonales. Una matriz diagonal de bloques A tiene la forma
donde A k es una matriz cuadrada para todo k = 1, ..., n .
El relleno de una matriz son aquellas entradas que cambian de un valor inicial cero a un valor distinto de cero durante la ejecución de un algoritmo. Para reducir los requisitos de memoria y el número de operaciones aritméticas utilizadas durante un algoritmo, es útil minimizar el relleno cambiando filas y columnas en la matriz. La descomposición simbólica de Cholesky se puede utilizar para calcular el peor relleno posible antes de realizar la descomposición de Cholesky real .
Se utilizan otros métodos además de la descomposición de Cholesky . Los métodos de ortogonalización (como la factorización QR) son comunes, por ejemplo, al resolver problemas mediante métodos de mínimos cuadrados. Si bien el relleno teórico sigue siendo el mismo, en términos prácticos los "falsos distintos de ceros" pueden ser diferentes para diferentes métodos. Y las versiones simbólicas de esos algoritmos se pueden utilizar de la misma manera que el Cholesky simbólico para calcular el relleno en el peor de los casos.
Existen métodos iterativos y directos para la resolución de matrices dispersas .
Los métodos iterativos, como el método del gradiente conjugado y GMRES, utilizan cálculos rápidos de productos matriz-vector , donde la matriz es escasa. El uso de precondicionadores puede acelerar significativamente la convergencia de dichos métodos iterativos.
Una matriz normalmente se almacena como una matriz bidimensional. Cada entrada en la matriz representa un elemento a i , j de la matriz y se accede a ella mediante los dos índices i y j . Convencionalmente, i es el índice de la fila, numerado de arriba a abajo, y j es el índice de la columna, numerado de izquierda a derecha. Para una matriz m × n , la cantidad de memoria necesaria para almacenar la matriz en este formato es proporcional a m × n (sin tener en cuenta el hecho de que las dimensiones de la matriz también deben almacenarse).
En el caso de una matriz dispersa, se pueden lograr reducciones sustanciales en los requisitos de memoria almacenando sólo las entradas distintas de cero. Dependiendo del número y la distribución de las entradas distintas de cero, se pueden utilizar diferentes estructuras de datos y generar enormes ahorros de memoria en comparación con el enfoque básico. La desventaja es que el acceso a los elementos individuales se vuelve más complejo y se necesitan estructuras adicionales para poder recuperar la matriz original sin ambigüedades.
Los formatos se pueden dividir en dos grupos:
DOK consta de un diccionario que asigna (fila, columna) : pares al valor de los elementos. Los elementos que faltan en el diccionario se consideran cero. El formato es bueno para construir incrementalmente una matriz dispersa en orden aleatorio, pero pobre para iterar sobre valores distintos de cero en orden lexicográfico. Por lo general, se construye una matriz en este formato y luego se convierte a otro formato más eficiente para su procesamiento. [4]
LIL almacena una lista por fila, y cada entrada contiene el índice de la columna y el valor. Normalmente, estas entradas se mantienen ordenadas por índice de columna para una búsqueda más rápida. Este es otro formato bueno para la construcción de matrices incrementales. [5]
COO almacena una lista de tuplas (fila, columna, valor) . Lo ideal es que las entradas se ordenen primero por índice de fila y luego por índice de columna, para mejorar los tiempos de acceso aleatorio. Este es otro formato que es bueno para la construcción de matrices incrementales. [6]
El formato de fila dispersa comprimida (CSR) o almacenamiento de fila comprimida (CRS) o Yale representa una matriz M por tres matrices (unidimensionales), que contienen respectivamente valores distintos de cero, la extensión de las filas y los índices de las columnas. Es similar a COO, pero comprime los índices de filas, de ahí el nombre. Este formato permite un acceso rápido a filas y multiplicaciones de matrices y vectores ( M x ). El formato CSR se ha utilizado al menos desde mediados de la década de 1960, y la primera descripción completa apareció en 1967. [7]
El formato CSR almacena una matriz M escasa de m × n en forma de fila utilizando tres matrices (unidimensionales) (V, COL_INDEX, ROW_INDEX) . Sea NNZ el número de entradas distintas de cero en M . (Tenga en cuenta que aquí se utilizarán índices de base cero ).
Por ejemplo, la matriz
V = [ 5 8 3 6 ]COL_INDEX = [0 1 2 1]ÍNDICE_FILA = [0 1 2 3 4]
suponiendo un lenguaje indexado a cero.
Para extraer una fila, primero definimos:
inicio_fila = ROW_INDEX[fila]fin_fila = ÍNDICE_FILA[fila + 1]
Luego tomamos sectores de V y COL_INDEX comenzando en row_start y terminando en row_end.
Para extraer la fila 1 (la segunda fila) de esta matriz configuramos row_start=1y row_end=2. Luego hacemos las rodajas V[1:2] = [8]y COL_INDEX[1:2] = [1]. Ahora sabemos que en la fila 1 tenemos un elemento en la columna 1 con valor 8.
En este caso, la representación CSR contiene 13 entradas, en comparación con las 16 de la matriz original. El formato CSR guarda memoria solo cuando NNZ < ( m ( n − 1) − 1) / 2 .
Otro ejemplo, la matriz.
V = [10 20 30 40 50 60 70 80]COL_INDICE = [ 0 1 1 3 2 3 4 5 ] ÍNDICE_FILA = [0 2 4 7 8]
El total se almacena como 21 entradas: 8 en V , 8 en COL_INDEX y 5 en ROW_INDEX .
(10, 20) (30, 40) (50, 60, 70) (80), indica el índice de V (y COL_INDEX ) donde comienza y termina cada fila;(10, 20, ...) (0, 30, 0, 40, ...)(0, 0, 50, 60, 70, 0) (0, 0, 0, 0, 0, 80).Tenga en cuenta que en este formato, el primer valor de ROW_INDEX siempre es cero y el último siempre es NNZ , por lo que en cierto sentido son redundantes (aunque en lenguajes de programación donde la longitud de la matriz debe almacenarse explícitamente, NNZ no sería redundante). No obstante, esto evita la necesidad de manejar un caso excepcional al calcular la longitud de cada fila, ya que garantiza que la fórmula ROW_INDEX[ i + 1] − ROW_INDEX[ i ] funciona para cualquier fila i . Además, el coste de la memoria de este almacenamiento redundante probablemente sea insignificante para una matriz suficientemente grande.
Los formatos de matriz dispersa de Yale (antiguos y nuevos) son ejemplos del esquema de RSE. El antiguo formato de Yale funciona exactamente como se describe anteriormente, con tres matrices; el nuevo formato combina ROW_INDEX y COL_INDEX en una sola matriz y maneja la diagonal de la matriz por separado. [9]
Para matrices de adyacencia lógica , la matriz de datos se puede omitir, ya que la existencia de una entrada en la matriz de filas es suficiente para modelar una relación de adyacencia binaria.
Probablemente se le conozca como formato de Yale porque fue propuesto en el informe Yale Sparse Matrix Package de 1977 del Departamento de Ciencias de la Computación de la Universidad de Yale. [10]
CSC es similar a CSR excepto que los valores se leen primero por columna, se almacena un índice de fila para cada valor y se almacenan punteros de columna. Por ejemplo, CSC es (val, row_ind, col_ptr) , donde val es una matriz de valores distintos de cero (de arriba a abajo, luego de izquierda a derecha) de la matriz; row_ind son los índices de fila correspondientes a los valores; y col_ptr es la lista de índices val donde comienza cada columna. El nombre se basa en el hecho de que la información del índice de columnas está comprimida en relación con el formato COO. Normalmente se utiliza otro formato (LIL, DOK, COO) para la construcción. Este formato es eficaz para operaciones aritméticas, corte de columnas y productos de matriz-vector. Este es el formato tradicional para especificar una matriz dispersa en MATLAB (a través de la sparsefunción).
Muchas bibliotecas de software admiten matrices dispersas y proporcionan solucionadores para ecuaciones matriciales dispersas. Los siguientes son de código abierto:
El término matriz dispersa posiblemente fue acuñado por Harry Markowitz, quien inició un trabajo pionero pero luego abandonó el campo. [11]
El núcleo de cálculo de DNN es la multiplicación de matrices grandes escasamente densas. En el campo del análisis numérico, una matriz dispersa es una matriz poblada principalmente con ceros como elementos de la tabla. Por el contrario, si el número de elementos distintos de cero en una matriz es relativamente grande, entonces comúnmente se la considera una matriz densa. La fracción de elementos cero (elementos distintos de cero) en una matriz se llama escasez (densidad). Las operaciones que utilizan algoritmos y estructuras de matriz densa estándar son relativamente lentas y consumen grandes cantidades de memoria cuando se aplican a matrices dispersas grandes.
El WSE contiene 400.000 núcleos informáticos optimizados para IA. Llamados SLAC™ para núcleos de álgebra lineal dispersa, los núcleos de computación son flexibles, programables y optimizados para el álgebra lineal dispersa que sustenta todos los cálculos de redes neuronales.
El WSE es el chip más grande jamás fabricado, con 46.225 milímetros cuadrados de superficie, es 56,7 veces más grande que la unidad de procesamiento de gráficos más grande. Contiene 78 veces más núcleos informáticos optimizados para IA, 3.000 veces más memoria en chip de alta velocidad, 10.000 veces más ancho de banda de memoria y 33.000 veces más ancho de banda de comunicación.