Matriz dispersa

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.

Casos especiales

Con bandas

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 ambos iguales a 3. Observe que los ceros se representan con puntos para mayor claridad. ${\begin{bmatrix}X&X&\cdot &\cdot &\cdot &\cdot &\cdot &\\X&X&\cdot &X&\cdot &\cdot &\\X&\cdot &X&\cdot &\cdot &\\\cdot &X&\cdot &X&\cdot &X&\cdot &\\\cdot &X&X&\cdot &X&X&\cdot &\\\cdot &X&X&\cdot &X&X&\cdot &\cdot &\cdot &X&X&\cdot &\\\cdot &X& ...\cdot &\cdot &\cdot &X&\cdot &\cdot &X&\cdot &\cdot &X&\cdot &\cdot &X&\cdot &\cdot &X&\cdot &\cdot &X&\cdot &\cdot &X&\cdot &\\\cdot &X&\cdot &\cdot &X&\cdot &X&\\\end{bmatrix}}$

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 .

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 \times n$ requiere solo $n$ entradas.

Simétrico

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 .

Bloque diagonal

Una matriz diagonal por bloques consta de submatrices a lo largo de sus bloques diagonales. Una matriz diagonal por bloques $A$ tiene la forma $\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 todos $los k = 1, ..., n$ .

Usar

Reducción del relleno

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.

Solución de ecuaciones de matrices dispersas

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. $Estilo de visualización Ax_{i}$ ${\estilo de visualización A}$

Almacenamiento

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 \times n$ , la cantidad de memoria necesaria para almacenar la matriz en este formato es proporcional a $m \times 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:

Los que admiten modificaciones eficientes, como DOK (Diccionario de claves), LIL (Lista de listas) o COO (Lista de coordenadas), se utilizan normalmente 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 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]

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 útil para la construcción de matrices incrementales. ^[5]

Lista de coordenadas (COO)

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]

Fila dispersa comprimida (formato CSR, CRS o Yale)

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 \times n$ $M$ 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 basados en cero ).

Las matrices $V$ y $COL_INDEX$ tienen una longitud $NNZ$ y contienen los valores distintos de cero y los índices de columna de esos valores respectivamente.
$COL_INDEX$ contiene la columna en la que se encuentra la entrada correspondiente $V.$
La matriz $ROW_INDEX$ tiene una longitud $m + 1$ y codifica el índice en $V$ y $COL_INDEX$ donde comienza la fila dada. Esto es equivalente a que $ROW_INDEX[j]$ codifique el número total de valores distintos de cero por encima 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.$ ^[8 ]

Por ejemplo, la matriz es una matriz de $4 \times 4$ con 4 elementos distintos de cero, por lo tanto ${\begin{pmatrix}5&0&0&0\\0&8&0&0\\0&0&3&0\\0&6&0&0\\\end{pmatrix}}$

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 \times 6$ (24 entradas) con 8 elementos distintos de cero, por lo que ${\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&0&80\\\end{pmatrix}}$

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$ .

$ROW_INDEX$ divide la matriz $V$ en filas: (10, 20) (30, 40) (50, 60, 70) (80), indicando el índice de $V$ (y $COL_INDEX$ ) donde comienza y termina cada fila;
$COL_INDEX$ alinea los valores en las 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 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 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]

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 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).

Software

Muchas bibliotecas de software admiten matrices dispersas y ofrecen solucionadores para ecuaciones de matrices dispersas. Las siguientes son de código abierto:

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 subbibliotecas dedicadas al almacenamiento de matrices densas y dispersas y a la solución de los sistemas lineales correspondientes.
Eigen3 es una biblioteca de C++ que contiene varios solucionadores de matrices dispersas. Sin embargo, ninguno de ellos está paralelizado .
MUMPS ( Multifrontal Massiively Parallel Sparse Direct Solver ) , escrito en Fortran90, es un solucionador frontal .
deal.II , una biblioteca de elementos finitos que también tiene una subbiblioteca para sistemas lineales dispersos y su solución.
DUNE , otra biblioteca de elementos finitos que también tiene una subbiblioteca para sistemas lineales dispersos y su solución.
Armadillo proporciona un contenedor C++ fácil de usar para BLAS y LAPACK.
SciPy proporciona soporte para varios formatos de matrices dispersas, álgebra lineal y solucionadores.
ALGLIB es una biblioteca de C++ y C# con soporte de álgebra lineal dispersa
Biblioteca ARPACK Fortran 77 para diagonalización y manipulación de matrices dispersas, utilizando el algoritmo Arnoldi
Biblioteca SLEPc para la solución de sistemas lineales de gran escala y matrices dispersas
scikit-learn , una biblioteca de Python para aprendizaje automático , proporciona soporte para matrices dispersas y solucionadores.

Historia

El término matriz dispersa posiblemente fue acuñado por Harry Markowitz , quien inició algunos trabajos pioneros pero luego abandonó el campo. ^[11]

Véase también

Notas

^ ab Yan, Di; Wu, Tao; Liu, Ying; Gao, Yang (2017). "Una multiplicación eficiente de matrices escasamente densas en un sistema multinúcleo". 2017 IEEE 17ª Conferencia Internacional sobre Tecnologías de la Comunicación (ICCT) . IEEE. págs. 1880–3. doi :10.1109/icct.2017.8359956. ISBN 978-1-5090-3944-9El núcleo computacional de DNN es la multiplicación de matrices dispersas por densas de gran tamaño. 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 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.
^ "Cerebras Systems presenta el primer chip de transistores de un billón de la industria". www.businesswire.com . 19 de agosto de 2019 . Consultado el 2 de diciembre de 2019 . 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.
^ "Argonne National Laboratory Deploys Cerebras CS-1, the World's Fastest Artificial Intelligence Computer | Argonne National Laboratory". www.anl.gov (Nota de prensa) . Consultado el 2 de diciembre de 2019. 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.
^ Véase scipy.sparse.dok_matrix
^ Véase scipy.sparse.lil_matrix
^ Véase scipy.sparse.coo_matrix
^ Buluç, Aydın; Fineman, Jeremy T.; Frigo, Matteo; Gilbert, John R.; Leiserson, Charles E. (2009). Multiplicación paralela de matriz dispersa-vector y matriz transpuesta-vector usando bloques dispersos comprimidos (PDF) . Simposio ACM sobre paralelismo en algoritmos y arquitecturas. CiteSeerX 10.1.1.211.5256 .
^ Saad 2003
^ Bank, Randolph E.; Douglas, Craig C. (1993), "Paquete de multiplicación de matrices dispersas (SMMP)" (PDF) , Advances in Computational Mathematics , 1 : 127–137, doi :10.1007/BF02070824, S2CID 6412241
^ Eisenstat, SC; Gursky, MC; Schultz, MH; Sherman, AH (abril de 1977). «Yale Sparse Matrix Package» (PDF) . Archivado (PDF) del original el 6 de abril de 2019. Consultado el 6 de abril de 2019 .
^ Entrevista de historia oral con Harry M. Markowitz, págs. 9, 10.

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.). Springer. doi :10.1007/978-0-387-21738-3. ISBN 978-0-387-95452-3.
Tewarson, Reginald P. (1973). Matrices dispersas. Matemáticas en ciencia e ingeniería. Vol. 99. Academic Press. ISBN 0-12-685650-8.OCLC 316552948 .(Este libro, escrito por un profesor de la Universidad Estatal de Nueva York en Stony Book, fue el primer libro dedicado exclusivamente a las matrices dispersas. A principios de los años 1980 se ofrecieron en esa universidad cursos de posgrado que utilizaban este libro de texto).
Bank, Randolph E.; Douglas, Craig C. "Paquete de multiplicación de matrices dispersas" (PDF) .
Pissanetzky, Sergio (1984). Tecnología de matrices dispersas . Academic Press. ISBN 978-0-12-557580-5.OCLC 680489638 .
Snay, Richard A. (1976). "Reducción del perfil de matrices simétricas dispersas". Bulletin Géodésique . 50 (4): 341–352. Bibcode :1976BGeod..50..341S. doi :10.1007/BF02521587. hdl : 2027/uc1.31210024848523 . S2CID 123079384.También Memorándum Técnico NOS NGS-4 de la NOAA, National Geodetic Survey, Rockville, Maryland. Referencia a Saad 2003.
Scott, Jennifer; Tuma, Miroslav (2023). Algoritmos para sistemas lineales dispersos . Birkhauser. doi :10.1007/978-3-031-25820-6.(Acceso abierto)

Lectura adicional

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". ACM Transactions on Mathematical Software . 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 de matrices y aplicaciones . 13 (1): 333–356. CiteSeerX 10.1.1.470.1054 . doi :10.1137/0613024.
Investigación sobre algoritmos de matrices dispersas en la Universidad Texas A&M.
Colección de matrices SuiteSparse
Proyecto SMALL Un proyecto financiado por la UE sobre modelos dispersos, algoritmos y aprendizaje de diccionarios para datos a gran escala.
Hackbusch, Wolfgang (2016). Solución iterativa de grandes sistemas dispersos de ecuaciones (2.ª ed.). Springer. doi :10.1007/978-3-319-28483-5.
Saad, Yousef (2003). Métodos iterativos para sistemas lineales dispersos . SIAM. doi :10.1137/1.9780898718003. ISBN. 978-0-89871-534-7.OCLC 693784152 .
Davis, Timothy A. (2006). Métodos directos para sistemas lineales dispersos . SIAM. doi :10.1137/1.9780898718881. ISBN 978-0-89871-613-9.OCLC 694087302 .