jueves, enero 12, 2006

Representación de matrices dispersas de "gran" tamaño

Para representar matrices dispersas de gran tamaño, existen diferentes formatos, que tiene por finalidad el reducir al máximo el consumo de memoria.

Aquí hablaré sobre el formato estándar de almacenamiento por filas CSR (Compressed Row Storage), que utiliza un escalar y tres vectores para el almacenado de la matriz. Los nombres de los vectores (para la explicación), son: IA, JA, y AA. El escalar se denomina n y es el número de renglones de la matriz.

El vector AA contiene a todos los elementos [a]ij diferentes de cero guardados renglón a renglón, de 1 a n; y su longitud es Nz.

El vector JA contiene los índices de las columnas de los elementos [a]ij, almacenados en AA, y su longitud es Nz. Existe una correspondencia uno a uno entre los elementos de JA y AA. El elemento JA(i) > 0 y pertenece a los naturales.
El vector IA contiene los índices que indican el principio de cada renglón en los vectores JA y AA. El elemento IA(i) es la posición en JA y AA donde el i-esimo renglón comienza. Su longitud es n + 1. El elemento IA(n+1) es igual a Nz+1. Es importante notar que esté último elemento corresponde al comienzo de un renglón ficticio n + 1.

A partir de los elementos del vector IA, se pueden determinar cuantos elementos diferentes de cero contiene cada uno de los renglones. El primer elemento de IA es 1.

Nz no se requiere almacenar de manera explicita, porque se puede obtener a partir de restarle uno al elemento IA(n+1), que indica el número total de elementos en la matriz que son diferentes de cero.

Este tipo de representación de matrices tiene una gran importancia en el computo cientifico, porque los sistemas de ecuaciones pueden ser representados por matrices, y muchos de los sistemas que se utilizan contienen una gran cantidad de incognitas, que generan matrices con miles o incluso cientos de miles de elementos; y en muchas ocaciones las matrices son dispersas, así que no tiene sentido almacenar de manera identica una matriz.

Lo habitual cuando se utilizan matrices pequeñas es utilizar arreglos de dos dimensiones, pero se puede ver que la cantidad de memoria ocupada, crece mucho más rápido, a medida que se aumenta linealmente el tamaño de una de las dimensiones. Y no tiene sentido cuando muchos de esos valores contenidos en la matriz son ceros.

Si desean más información sobre sistemas lineales dispersos y representaciones, visiten el sitio de Yousef Saad

2 Comentarios:

Blogger Pablo dijo...

Buenas, hago un seminario sobre matrices dispersas y sus aplicaciones, conociendo ya sus distintos métodos de almacenamiento, pero quería saber cuál de estos métodos es el más práctico para la operatoria con estas matrices.
cualquier información la agradecería mucho

de antemano gracias
saludos.-

4:49 p.m.  
Blogger César dijo...

Saludos.

Yo solo he trabajado con matrices en formato CSR y en formato MSR.

Lo que he visto es que entre más pequeña sea su representación (más compacta quede), el computo empleado para manipularla, es mayor. Por lo que entre menos "eficiente" sea su representación, manipularla resulta mucho más simple.

También al implmentar un algoritmo, hay menos probabilidad de equivocarse, porque su representación es más simple (menos compacta, menos compleja).

Por ejemplo, entre usar msr y csr, es más práctico (por simplesa) csr.

10:30 a.m.  

Publicar un comentario

Suscribirse a Comentarios de la entrada [Atom]

<< Página Principal