Matriz dispersa - Sparse matrix

Ejemplo de matriz dispersa ${\ displaystyle \ left ({\ begin {smallmatrix} 11 & 22 & 0 & 0 & 0 & 0 & 0 & 0 & 33 & 44 & 0 & 0 & 0 & 0 \\ 0 & 0 & 55 & 66 & 77 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 88 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 99 \\\} end right)$

La matriz dispersa anterior contiene solo 9 elementos distintos de cero, con 26 elementos cero. Su escasez es del 74% y su densidad es del 26%.

Una matriz dispersa obtenida al resolver un problema de elementos finitos en dos dimensiones. Los elementos distintos de cero se muestran en negro.

En el análisis numérico y la computación científica , una matriz dispersa o una matriz dispersa es una matriz en la que la mayoría de los elementos son cero. 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 . El número de elementos de valor cero dividido por el número total de elementos (p. Ej., M × n para una matriz de 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 escaso ya que solo se acoplan las bolas adyacentes. Por el contrario, si la misma línea de bolas tuviera resortes que conectan 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 importantes. Las matrices dispersas grandes a menudo aparecen 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, ya que son comunes en el campo del aprendizaje automático. Las operaciones que utilizan estructuras y algoritmos de matriz densa estándar son lentas e ineficientes cuando se aplican a matrices grandes y dispersas, ya que el procesamiento y la memoria se desperdician en los ceros. Por naturaleza, los datos dispersos se comprimen más fácilmente 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.

Almacenar una matriz dispersa

Normalmente, una matriz 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 fila, numerado de arriba a abajo, y j es el índice de 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 realizar reducciones sustanciales de los requisitos de memoria almacenando solo las entradas distintas de cero. Dependiendo del número y la distribución de las entradas distintas de cero, se pueden usar diferentes estructuras de datos y producir grandes ahorros de memoria en comparación con el enfoque básico. La compensación es que acceder 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:

• Aquellos que soportan modificaciones eficientes, como DOK (Diccionario de claves), LIL (Lista de listas) o COO (Lista de coordenadas). Por lo general, se utilizan para construir las matrices.
• Aquellos que admiten operaciones matriciales y de acceso eficientes, como CSR (Compressed Sparse Row) o CSC (Compressed Sparse Column).

Diccionario de claves (DOK)

DOK consiste en un diccionario que mapea (fila, columna) - se empareja con el 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 pobre 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.

Lista de listas (LIL)

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.

Lista de coordenadas (COO)

El director de operaciones almacena una lista de tuplas (fila, columna, valor) . Idealmente, las entradas se ordenan 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.

Fila dispersa comprimida (formato CSR, CRS o Yale)

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 filas e índices de columna. Es similar al COO, pero comprime los índices de fila, de ahí el nombre. Este formato permite un rápido acceso a filas y multiplicaciones de matriz-vector ( M x ). El formato CSR ha estado en uso desde al menos mediados de la década de 1960, y la primera descripción completa apareció en 1967.

El formato CSR almacena una matriz M escasa m × n en forma de fila utilizando tres matrices ( unidimensionales) (V, COL_INDEX, ROW_INDEX) . Let NNZ denotan el número de elementos no nulos en M . (Tenga en cuenta que aquí se utilizarán índices de base cero ).

• Las matrices V y COL_INDEX son de longitud NNZ y contienen los valores distintos de cero y los índices de columna de esos valores, respectivamente.

• La matriz ROW_INDEX tiene una longitud de m + 1 y codifica el índice en V y COL_INDEX donde comienza la fila dada. Esto es equivalente a ROW_INDEX [j] que codifica el número total de no ceros arriba de la fila j . El último elemento es NNZ , es decir, el índice ficticio en V inmediatamente después del último índice válido NNZ - 1 .

Por ejemplo, la matriz

${\ displaystyle {\ begin {pmatrix} 5 & 0 & 0 & 0 \\ 0 & 8 & 0 & 0 \\ 0 & 0 & 3 & 0 \\ 0 & 6 & 0 & 0 \\\ end {pmatrix}}}$

es una matriz de 4 × 4 con 4 elementos distintos de cero, por lo tanto

   V         = [ 5 8 3 6 ]
   COL_INDEX = [ 0 1 2 1 ]
   ROW_INDEX = [ 0 1 2 3 4 ] 

asumiendo un lenguaje indexado cero.

Para extraer una fila, primero definimos:

   row_start = ROW_INDEX[row]
   row_end   = ROW_INDEX[row + 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 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 16 en la matriz original. El formato CSR se guarda en la memoria solo cuando NNZ <( m ( n - 1) - 1) / 2 . Otro ejemplo, la matriz

${\ displaystyle {\ begin {pmatrix} 10 & 20 & 0 & 0 & 0 & 0 \\ 0 & 30 & 0 & 40 & 0 & 0 \\ 0 & 0 & 50 & 60 & 70 & 0 \\ 0 & 0 & 0 & 0 & 0 & 80 \\\ end {pmatrix}}}$

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 ]
   COL_INDEX = [  0  1  1  3  2  3  4  5 ]   
   ROW_INDEX = [  0  2  4  7  8 ]

El conjunto se almacena como 21 entradas.

• ROW_INDEX divide la matriz V en filas: (10, 20) (30, 40) (50, 60, 70) (80);
• COL_INDEX valores se alinea en columnas: (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 es siempre NNZ , por lo que en cierto sentido son redundantes (aunque en los 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 costo de memoria de este almacenamiento redundante probablemente sea insignificante para una matriz suficientemente grande.

Los formatos de matriz dispersa de Yale (antiguos y nuevos) son instancias del esquema de RSE. 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 sola matriz y maneja la diagonal de la matriz por separado.

Para las 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.

Es probable que se lo conozca como el formato de Yale porque se propuso en el informe del paquete de matriz dispersa de Yale de 1977 del Departamento de Ciencias de la Computación de la Universidad de Yale.

Columna dispersa comprimida (CSC o CCS)

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 está comprimida en relación con el formato COO. Normalmente se usa otro formato (LIL, DOK, COO) para la construcción. Este formato es eficaz para operaciones aritméticas, división de columnas y productos de matriz-vector. Consulte scipy.sparse.csc_matrix . Este es el formato tradicional para especificar una matriz dispersa en MATLAB (a través de la sparsefunción).

Estructura especial

Con bandas

Un tipo especial importante de matrices dispersas es la matriz de bandas , que se define a continuación. El ancho de banda más bajo 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 anchos de banda inferior y superior iguales a 3. Observe que los ceros se representan con puntos para mayor claridad.

${\ Displaystyle \ left ({\ begin {smallmatrix} X & X & X & \ cdot & \ cdot & \ cdot & \ cdot & \\ X & X & \ cdot & X & X & \ cdot & \ cdot & \\ X & \ cdot & X & \ cdot & X & \ cdot & \ cdot & \\\ cdot & X & \ cdot & X & \ cdot & X & \ cdot & \\\ cdot & X & X & \ cdot & X & X & X & \\\ cdot & \ cdot & \ cdot & X & X & X & \ cdot & \\\ cdot & \ cdot & \ cdot & \ cdot & X & \ cdot & X & \\\ end {smallmatrix}} \ right)}$

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 haciendo un bucle sobre un número reducido de índices.

Reordenando las filas y columnas de una matriz A , puede ser posible obtener una matriz A ' con un ancho de banda menor. Varios algoritmos están diseñados para minimizar el ancho de banda .

Diagonal

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.

Simétrico

Una matriz dispersa simétrica surge como la matriz de adyacencia de un grafo no dirigido ; se puede almacenar de manera eficiente como una lista de adyacencia .

Diagonal de bloque

Una matriz de bloques diagonales consta de submatrices a lo largo de sus bloques diagonales. Una matriz diagonal de bloques A tiene la forma

${\ displaystyle \ mathbf {A} = {\ begin {bmatrix} \ mathbf {A} _ {1} & 0 & \ cdots & 0 \\ 0 & \ mathbf {A} _ {2} & \ cdots & 0 \\\ vdots & \ vdots & \ ddots & \ vdots \\ 0 & 0 & \ cdots & \ mathbf {A} _ {n} \ end {bmatrix}},}$

donde A _k es una matriz cuadrada para todo k = 1, ..., n .

Reducir el relleno

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 real de Cholesky .

Hay 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, 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 no ceros" pueden ser diferentes para diferentes métodos. Y las versiones simbólicas de esos algoritmos se pueden usar de la misma manera que el Cholesky simbólico para calcular el relleno en el peor de los casos.

Resolver ecuaciones matriciales dispersas

Ambos iterativos existen métodos y directos para la solución de matriz dispersa.

Los métodos iterativos, como el método de gradiente conjugado y GMRES, utilizan cálculos rápidos de productos matriz-vector , donde la matriz es escasa. El uso de preacondicionadores puede acelerar significativamente la convergencia de tales métodos iterativos. ${\ Displaystyle Ax_ {i}}$${\ Displaystyle A}$

Software

Muchas bibliotecas de software admiten matrices dispersas y proporcionan solucionadores para ecuaciones matriciales dispersas. Los siguientes son de código abierto:

• SuiteSparse , un conjunto de algoritmos de matriz dispersa, orientado hacia la solución directa de sistemas lineales dispersos.
• PETSc , una gran biblioteca de C, que contiene muchos solucionadores de matrices diferentes para una variedad de formatos de almacenamiento de matrices.
• Trilinos , una gran biblioteca de C ++, con sub-bibliotecas dedicadas al almacenamiento de matrices densas y dispersas y solución de los sistemas lineales correspondientes.
• Eigen3 es una biblioteca de C ++ que contiene varios solucionadores de matrices dispersos. Sin embargo, ninguno de ellos está paralelo .
• PAPERAS ( MU ltifrontal M assively P an paralelo escasa directa S Olver), escrito en Fortran90, es un solucionador frontal .
• DUNE , una biblioteca de elementos finitos que también tiene una sub-biblioteca para sistemas lineales dispersos y su solución.
• PaStix .
• SuperLU .
• Armadillo proporciona un contenedor C ++ fácil de usar para BLAS y LAPACK.
• SciPy proporciona soporte para varios formatos de matriz dispersa, álgebra lineal y solucionadores.
• Paquete SPArse Matrix (spam) R y Python para matrices dispersas.
• Wolfram Language Tools para manejar matrices dispersas
• ALGLIB es una biblioteca de C ++ y C # con escasa compatibilidad con álgebra lineal
• Biblioteca ARPACK Fortran 77 para manipulación y diagonalización de matrices dispersas, utilizando el algoritmo de Arnoldi
• SPARSE Reference (antiguo) paquete NIST para diagonalización de matriz dispersa (real o compleja)
• Biblioteca SLEPc para la solución de sistemas lineales a gran escala y matrices dispersas
• Sympiler , una biblioteca y un generador de código de dominio específico para resolver sistemas lineales y problemas de programación cuadrática.
• Scikit-learn Un paquete de Python para el análisis de datos que incluye matrices dispersas.

Historia

El término matriz dispersa posiblemente fue acuñado por Harry Markowitz, quien inició un trabajo pionero pero luego abandonó el campo.

Ver también

Notas

Referencias

• Golub, Gene H .; Van Loan, Charles F. (1996). Cálculos matriciales (3ª ed.). Baltimore: Johns Hopkins. ISBN 978-0-8018-5414-9.
• Stoer, Josef; Bulirsch, Roland (2002). Introducción al análisis numérico (3ª ed.). Berlín, Nueva York: Springer-Verlag . ISBN 978-0-387-95452-3.
• Tewarson, Reginald P. (mayo de 1973). Matrices dispersas (parte de la serie Matemáticas en ciencia e ingeniería) . Academic Press Inc. (Este libro, de un profesor de la Universidad Estatal de Nueva York en Stony Book, fue el primer libro dedicado exclusivamente a las matrices dispersas. En esa universidad se ofrecieron cursos de posgrado que utilizaban esto como libro de texto a principios de la década de 1980).
• Bank, Randolph E .; Douglas, Craig C. "Paquete de multiplicación de matriz dispersa" (PDF) .
• Pissanetzky, Sergio (1984). Tecnología de matriz dispersa . Prensa académica.
• Snay, Richard A. (1976). "Reducción del perfil de matrices simétricas dispersas". Boletín Géodésique . 50 (4): 341–352. Código Bibliográfico : 1976BGeod..50..341S . doi : 10.1007 / BF02521587 . hdl : 2027 / uc1.31210024848523 . S2CID  123079384 . También el Memorando Técnico de la NOAA NOS NGS-4, National Geodetic Survey, Rockville, MD.

Otras lecturas

• Gibbs, Norman E .; Poole, William G .; Stockmeyer, Paul K. (1976). "Una comparación de varios algoritmos de reducción de ancho de banda y perfil" . Transacciones ACM en software matemático . 2 (4): 322–330. doi : 10.1145 / 355705.355707 . S2CID  14494429 .
• Gilbert, John R .; Moler, Cleve; Schreiber, Robert (1992). "Matrices dispersas en MATLAB: diseño e implementación" . Revista SIAM sobre Análisis y Aplicaciones Matriciales . 13 (1): 333–356. CiteSeerX  10.1.1.470.1054 . doi : 10.1137 / 0613024 .
• Investigación de algoritmos de matriz dispersa en la Universidad A&M de Texas.
• Colección SuiteSparse Matrix
• Proyecto PEQUEÑO Un proyecto financiado con fondos europeos sobre modelos dispersos, algoritmos y aprendizaje de diccionarios para datos a gran escala.