Matriz dispersa

Una matriz dispersa  es una matriz con elementos en su mayoría cero. De lo contrario, si la mayoría de los elementos de la matriz son distintos de cero, la matriz se considera densa .

Entre los expertos, no hay unidad para determinar exactamente cuántos elementos distintos de cero hacen que una matriz sea escasa. Diferentes autores ofrecen diferentes opciones. Para una matriz de orden n, el número de elementos distintos de cero [1] :

• es O(n) . Tal definición es adecuada solo para el análisis teórico de las propiedades asintóticas de los algoritmos matriciales;
• en cada línea no exceda de 10 en un caso típico;
• limitado donde .
• es tal que tiene sentido que un determinado algoritmo y sistema informático se beneficie de la presencia de ceros en él [1] .

Enormes matrices dispersas a menudo surgen cuando se resuelven problemas tales como ecuaciones diferenciales parciales .

Al almacenar y convertir matrices dispersas en una computadora , es útil, ya menudo necesario, utilizar algoritmos especiales y estructuras de datos que tengan en cuenta la estructura de la matriz dispersa. Las operaciones y los algoritmos utilizados para trabajar con matrices densas ordinarias, en relación con matrices dispersas grandes, son relativamente lentos y requieren cantidades significativas de memoria. Sin embargo, las matrices dispersas se pueden comprimir fácilmente escribiendo solo sus elementos distintos de cero, lo que reduce los requisitos de memoria de la computadora .

Presentación

Hay varias formas de almacenar (representar) matrices dispersas, que difieren:

• la conveniencia de cambiar la estructura de la matriz (se usa activamente el direccionamiento indirecto): estas son estructuras en forma de listas y diccionarios.
• la velocidad de acceso a los elementos y la posible optimización de los cálculos matriciales (los arreglos de bloques densos se usan con más frecuencia, lo que aumenta la localidad del acceso a la memoria).

Un diccionario de claves (DOK - Dictionary of Keys) se construye como un diccionario, donde la clave es un par ( fila, columna ), y el valor es el elemento de matriz correspondiente a la fila y la columna.

Una lista de listas (LIL - List of Lists) se construye como una lista de cadenas, donde una cadena es una lista de nodos de la forma ( columna, valor ).

La lista de coordenadas (COO - Coordinate list) es una lista de elementos del formulario (línea, columna, valor).

Almacenamiento de filas comprimidas (CSR: filas dispersas comprimidas, CRS: almacenamiento de filas comprimidas, formato Yale)

Representamos la matriz original que contiene valores distintos de cero como tres matrices:

• matriz de valores : una matriz de tamaño , que almacena valores distintos de cero tomados en una fila desde la primera fila no vacía, luego los valores de la siguiente fila no vacía, etc.
• matriz de índices de columna es una matriz de tamaño y almacena los números de columna correspondientes a los elementos de la matriz de valores.
• matriz de indexación de filas : una matriz de tamaño (número de filas + 1), para el índice almacena la cantidad de elementos distintos de cero en filas desde la primera hasta la fila inclusive, vale la pena señalar que el último elemento de la indexación de filas array es lo mismo que , y el primero siempre es igual a .

Ejemplos:

Deja entonces