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 la siguiente: este es un sistema disperso ya que solo las bolas adyacentes están acopladas. Por el contrario, si la misma línea de bolas tuviera resortes que conectaran cada bola con todas las demás bolas, 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 significativas. Las matrices dispersas grandes 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 y estructuras de datos especializados 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 de matriz densa estándar son lentos e ineficientes cuando se aplican a matrices dispersas grandes, 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 significativamente menos almacenamiento . Algunas matrices dispersas muy grandes no son factibles de manipular utilizando algoritmos de matriz densa estándar.
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 se anule 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 y 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 inferior y superior iguales 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 de matriz densa y ganar eficiencia simplemente recorriendo un número reducido de índices.
Al reorganizar las filas y columnas de una matriz A, es 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 la matriz de adyacencia de un gráfico no dirigido ; puede almacenarse eficientemente como una lista de adyacencia .
Una matriz diagonal por bloques consta de submatrices a lo largo de sus bloques diagonales. Una matriz diagonal por bloques A tiene la forma
donde A k es una matriz cuadrada para todos los k = 1, ..., n .
Los valores de 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 los valores de relleno intercambiando filas y columnas en la matriz. La descomposición simbólica de Cholesky se puede utilizar para calcular el peor valor de relleno posible antes de realizar la descomposición de Cholesky real .
Existen otros métodos en uso además de la descomposición de Cholesky . Los métodos de ortogonalización (como la factorización QR) son comunes, por ejemplo, cuando se resuelven problemas mediante métodos de mínimos cuadrados. Si bien el método de relleno teórico sigue siendo el mismo, en términos prácticos los "falsos distintos de cero" pueden ser diferentes para diferentes métodos. Y las versiones simbólicas de esos algoritmos se pueden utilizar de la misma manera que el método de Cholesky simbólico para calcular el método de relleno en el peor de los casos.
Existen métodos iterativos y directos para resolver matrices dispersas.
Los métodos iterativos, como el método del gradiente conjugado y el GMRES, utilizan cálculos rápidos de productos matriz-vector , donde la matriz es dispersa. El uso de preacondicionadores puede acelerar significativamente la convergencia de dichos métodos iterativos.
Una matriz se almacena típicamente como una matriz bidimensional. Cada entrada de 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 también es necesario almacenar las dimensiones de la matriz).
En el caso de una matriz dispersa, se pueden lograr reducciones sustanciales en los requisitos de memoria almacenando solo las entradas distintas de cero. Según la cantidad y la distribución de las entradas distintas de cero, se pueden utilizar diferentes estructuras de datos y generar enormes ahorros en 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 consiste en un diccionario que asigna pares ( fila, columna) al valor de los elementos. Los elementos que faltan en el diccionario se toman como cero. El formato es bueno para construir incrementalmente una matriz dispersa en orden aleatorio, pero deficiente para iterar sobre valores distintos de cero en orden lexicográfico. Normalmente, 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 útil 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 filas dispersas comprimidas (CSR) o almacenamiento de filas comprimidas (CRS) o formato Yale representa una matriz M por tres arreglos (unidimensionales), que contienen respectivamente valores distintos de cero, las extensiones de las filas y los índices de las columnas. Es similar a COO, pero comprime los índices de las filas, de ahí el nombre. Este formato permite un acceso rápido a las filas y multiplicaciones de matriz-vector ( M x ). El formato CSR se ha utilizado desde al menos mediados de la década de 1960, y la primera descripción completa apareció en 1967. [7]
El formato CSR almacena una matriz dispersa de m × n M en formato 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 basados en cero ).
Por ejemplo, la matriz es una matriz de 4 × 4 con 4 elementos distintos de cero, por lo tanto
V = [ 5 8 3 6 ]ÍNDICE_COL = [ 0 1 2 1 ]ÍNDICE_FILA = [ 0 1 2 3 4 ]
asumiendo un lenguaje de índice cero.
Para extraer una fila, primero definimos:
inicio_fila = ÍNDICE_FILA[fila]fin_fila = ÍNDICE_FILA[fila + 1]
Luego tomamos porciones 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, establecemos row_start=1y row_end=2. Luego, hacemos las porciones 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 en memoria solo cuando NNZ < ( m ( n − 1) − 1) / 2 .
Otro ejemplo, la matriz es una matriz de 4 × 6 (24 entradas) con 8 elementos distintos de cero, por lo que
V = [10 20 30 40 50 60 70 80]ÍNDICE_COL = [ 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), indicando 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 ] funcione para cualquier fila i . Además, el costo de memoria de este almacenamiento redundante es probablemente insignificante para una matriz lo suficientemente grande.
Los formatos de matriz dispersa de Yale (antiguo y nuevo) son instancias del esquema CSR. El antiguo formato de Yale funciona exactamente como se describió anteriormente, con tres matrices; el nuevo formato combina ROW_INDEX y COL_INDEX en una única matriz y maneja la diagonal de la matriz por separado. [9]
Para las matrices de adyacencia lógica , se puede omitir la matriz de datos, ya que la existencia de una entrada en la matriz de filas es suficiente para modelar una relación de adyacencia binaria.
Es probable que se le conozca como formato Yale porque se propuso 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 los 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 columna se comprime en relación con el formato COO. Normalmente se utiliza otro formato (LIL, DOK, COO) para la construcción. Este formato es eficiente para operaciones aritméticas, corte de columnas y productos 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 ofrecen solucionadores para ecuaciones de matrices dispersas. Las siguientes son de código abierto:
El término matriz dispersa posiblemente fue acuñado por Harry Markowitz , quien inició algunos trabajos pioneros pero luego abandonó el campo. [11]
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 se considera comúnmente una matriz densa. La fracción de elementos cero (elementos distintos de cero) en una matriz se denomina escasez (densidad). Las operaciones que utilizan estructuras y algoritmos de matriz densa estándar son relativamente lentos y consumen grandes cantidades de memoria cuando se aplican a matrices dispersas de gran tamaño.
El WSE contiene 400 000 núcleos de cómputo optimizados para IA. Los núcleos de cómputo, denominados SLAC™ (Sparse Linear Algebra Cores), 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 un área de 46.225 milímetros cuadrados, es 56,7 veces más grande que la unidad de procesamiento gráfico más grande. Contiene 78 veces más núcleos de cómputo 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.