Una matriz se almacena normalmente como una matriz bidimensional. Cada entrada de la matriz representa un elemento ai,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 también hay que almacenar las dimensiones de la matriz).

En el caso de una matriz dispersa, se pueden conseguir reducciones sustanciales de los requisitos de memoria almacenando sólo las entradas no nulas. Dependiendo del número y la distribución de las entradas no nulas, se pueden utilizar diferentes estructuras de datos y obtener un gran ahorro de memoria en comparación con el enfoque básico. La contrapartida 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 pueden dividirse en dos grupos:

• Los que admiten una modificación eficiente, como DOK (Diccionario de claves), LIL (Lista de listas) o COO (Lista de coordenadas). Estos se utilizan normalmente para construir las matrices.
• Los que apoyan el acceso eficiente y las operaciones de la matriz, como CSR (Compressed Sparse Row) o CSC (Compressed Sparse Column).

Diccionario de claves (DOK)Editar

DOK consiste en un diccionario que asigna (fila, columna)-pares 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 pobre para iterar sobre valores no nulos 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)Editar

LIL almacena una lista por fila, con cada entrada que 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)Edit

COO almacena una lista de tuplas (fila, columna, valor). Lo ideal es que las entradas se ordenen primero por el índice de la fila y luego por el índice de la columna, para mejorar los tiempos de acceso aleatorio. Este es otro formato que es bueno para la construcción de matrices incrementales.

Fila escasa comprimida (CSR, CRS o formato Yale)Editar

El formato de fila escasa comprimida (CSR) o almacenamiento de fila comprimida (CRS) o Yale representa una matriz M por tres matrices (unidimensionales), que contienen respectivamente valores no nulos, los extensiones de las filas y los índices de las columnas. Es similar a COO, pero comprime los índices de las filas, de ahí su nombre. Este formato permite un acceso rápido a las filas y a las multiplicaciones matriciales-vectoriales (Mx). El formato CSR ha estado en uso desde al menos mediados de la década de 1960, con la primera descripción completa que aparece en 1967.

El formato CSR almacena una matriz dispersa m × n M en forma de fila utilizando tres matrices (unidimensionales) (V, COL_INDEX, ROW_INDEX). Sea NNZ el número de entradas no nulas en M. (Obsérvese que aquí se utilizarán índices basados en cero.)

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

• La matriz ROW_INDEX es de longitud m + 1 y codifica el índice en V y COL_INDEX donde comienza la fila dada. 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

( 5 0 0 0 8 0 0 0 3 0 0 6 0 0 ) {\displaystyle {\begin{pmatrix}5&0&0&0&0&8&0&0&0&0&03&0&6&0&0\\\\\bend{pmatrix}}

es una matriz de 4 × 4 con 4 elementos no nulos, por lo tanto

 V = COL_INDEX = ROW_INDEX = 

suponiendo un lenguaje con índice cero.

Para extraer una fila, primero definimos:

 row_start = ROW_INDEX row_end = ROW_INDEX

Después tomamos rodajas de V y COL_INDEX empezando por row_start y terminando por row_end.

Para extraer la fila 1 (la segunda fila) de esta matriz ponemos row_start=1 y row_end=2. Luego hacemos los cortes V = y COL_INDEX = . 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, frente a las 16 de la matriz original. El formato CSR ahorra en memoria sólo cuando NNZ < (m (n – 1) – 1) / 2.Otro ejemplo, la matriz

( 10 20 0 0 0 0 30 0 40 0 0 0 50 60 70 0 0 0 0 80 ) {\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 no nulos, por lo que

 V = COL_INDEX = ROW_INDEX = 

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 alinea los valores en columnas: (10, 20, ...) (0, 30, 0, 40, ...)(0, 0, 50, 60, 70, 0) (0, 0, 0, 0, 0, 80).

Nótese que en este formato, el primer valor de ROW_INDEX es siempre cero y el último es siempre NNZ, por lo que son en cierto sentido redundantes (aunque en los lenguajes de programación en los que 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 cuando se calcula la longitud de cada fila, ya que garantiza que la fórmula ROW_INDEX – ROW_INDEX funciona para cualquier fila i. Además, el coste 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 ha descrito 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 puede omitirse, ya que la existencia de una entrada en la matriz de filas es suficiente para modelar una relación de adyacencia binaria.

Es probablemente conocido como el formato de Yale porque fue propuesto en el informe de 1977 Yale Sparse Matrix Package del Departamento de Ciencias de la Computación de la Universidad de Yale.

Columna dispersa comprimida (CSC o CCS)Editar

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 un array de los valores (de arriba a abajo, y luego de izquierda a derecha) distintos de cero de la matriz; row_ind son los índices de fila correspondientes a los valores; y, col_ptr es la lista de índices de val donde empieza cada columna. El nombre se basa en el hecho de que la información de los índices de columna está comprimida en relación con el formato COO. Normalmente se utiliza otro formato (LIL, DOK, COO) para su construcción. Este formato es eficiente para las operaciones aritméticas, el corte de columnas y los productos matriz-vector. Ver scipy.sparse.csc_matrix.Este es el formato tradicional para especificar una matriz dispersa en MATLAB (a través de la función sparse).