Matriz dispersa
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. [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 (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 aprovechan 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 lentas e ineficientes cuando se aplican a matrices dispersas grandes, 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.
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 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 requerida 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 en la 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.
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. [4]
