Representación de matrices en formato CSR

En una entrada anterior[1], explicaba los elementos y consideraciones para representar matrices dispersas en formato CSR.

Ahora explico con un ejemplo, como construir una matriz en formato CSR a partir de su representación en formato denso.

Suponiendo que se tiene una matriz como la siguiente:

/                                    
|  1.2  2.3  0.0  0.0  0.0  0.0  0.0  |
|  2.4  3.1  4.5  0.0  0.0  0.0  0.0  |
|  0.0  7.8  2.1  5.4  0.0  0.0  0.0  |
|  0.0  0.0  4.5  6.2  4.1  0.0  0.0  |
|  0.0  0.0  0.0  4.7  7.2  6.1  0.0  |
|  0.0  0.0  0.0  0.0  5.5  4.8  2.3  |
|  0.0  0.0  0.0  0.0  0.0  6.8  9.4  |
\                                     /

Recordando los elementos del formato CRS:

• n := dimensión de la matriz
• ia := índices para referirse a los renglones
• ja := índices para las columnas
• a := Elementos diferentes de cero
  

La matriz en formato CSR queda:

n = 7
ia = [1, 3, 6, 9, 12, 15, 18, 20]
ja = [1, 2, 1, 2, 3, 2, 3, 4, 3, 4, 5, 4, 5, 6, 5, 6, 7, 6, 7]
a = [1.2, 2.3, 2.4, 3.1, 4.5, 7.8, 2.1, 5.4, 4.5, 6.2, 4.1, 4.7, 7.2, 6.1, 5.5, 4.8, 2.3, 6.8, 9.4]

La longitud del vector ia es igual a la dimensión de la matriz más uno (7 + 1 = 8).

La longitud del vector ja es igual al del vector a, y se corresponde con él último elemento del vector ia menos uno (ia[7 + 1] - 1 = 20 -1 = 19).

Interpretando los vectores ia, ja y a; el primer elemento de ia es el índice que corresponde al vector ja y a, que representa la primera fila de la matriz, así:

ia[1] = 1

Ese 1 indica el índice en donde comienzan los elementos correspondientes al primer renglón, leídos en los vectores ja y al a siguientes:

ja[1] = 1
a[1] = 1.2
ja[2] = 2
a[2] = 2.3

Con lo que obtienes que en el renglón 1, columna 1, está el elemento 1.2; y en el renglón 1, columna 2, está el elemento 2.3. El resto de los elementos del renglón son ceros.

El elemento siguiente en ia es:

ia[2] = 3

Que indica el índice en donde comienzan los elementos del siguiente renglón.

ja[3] = 1
a[3] = 2.4
ja[4] = 2
a[4] = 3.1
ja[5] = 3
a[5] = 4.5

En el segundo renglón las columnas utilizadas son 1, 2 y 3, que se corresponden con los elementos 2.4, 3.1 y 4.5 respectivamente. Nuevamente, el resto de los elementos del renglón son ceros.

De esta manera se leen el resto de los elementos de la matriz en formato CSR.

Se observa que hay una relación uno a uno entre el vector ja y el vector a, que pueden ser movidos en el intervalo entre un renglón y otro, por ejemplo, de la matriz en formato CSR anterior, podemos modifica el orden de los dos primeros elementos en ja y a, que se corresponden con el primer renglón. También se puede alterar el orden de los tres siguientes elementos que corresponden al segundo renglón.

n = 7
ia = [1, 3, 6, 9, 12, 15, 18, 20]
ja = [2, 1, 3, 1, 2, 2, 3, 4, 3, 4, 5, 4, 5, 6, 5, 6, 7, 6, 7]
a = [2.3, 1.2, 3.1, 2.4, 4.5, 7.8, 2.1, 5.4, 4.5, 6.2, 4.1, 4.7, 7.2, 6.1, 5.5, 4.8, 2.3, 6.8, 9.4]

Hay que observar que en el mismo orden en que se modificó el vector ja, debe ser modificado el vector a. Si solo se altera el orden de ja o de a, ya no es una matriz equivalente. También hay que notar que no se debe modificar el orden de la matriz más allá de los índices que limitan los renglones, de hacerlo, se tendría una matriz diferente a la original.

En el caso del vector ia, el último elemento es un índice imaginario que no se refiere a ninguno de los elementos en el vector ja.

Una observación adicional, el vector ia se construye de la siguiente manera, el primer elemento siempre es 1, y los siguientes es la suma de todos los elementos del renglón diferentes de cero, más el elemento anterior en el vector ia.

Por ejemplo, el primer elemento de ia es 1, el siguiente es la suma de todos los elementos diferentes de cero del primer renglón, que son 2, más el elemento anterior en ia que es 1, da un total de tres, entonces, el segundo elemento de ia es 3; el tercer elemento de ia es 3 (total de elementos diferentes de cero del segundo renglón), más el elemento anterior que es 3, por lo que el tercer elemento en ia es 6. Así sucesivamente se construye el vector ia con el resto de los elementos de la matriz.