Matrices dispersas

Matrices dispersas

 Situación:  Matrices muy grandes  Previsible “gran porcentaje” de valores = 0 Se busca una forma de representar esas matrices que “cueste” menos memoria y permita acelerar los cálculos. Las matrices son naturalmente muy eficientes en el uso de memoria -para almacenar datos- y de procesador -para accederlos-. 06/11/11 Computación 1, 2011 - Facultad de Ingeniería 3 Matrices dispersas Representación en memoria de una matriz convencional La memoria es una secuencia de bits organizada en bloques de a 8

1 2 3 4 5 6 7 8 9 10 11

Si tenemos matriz( n, m) de reales de 4 Bytes

Trabajando en lenguajes como “C” que almacena por

“fila” (“Fortran” por “columna”).

La posición en bits de la celda (i, j) en la memoria es:

inicio_matriz + ((( i – 1) * n ) + j ) * (4 * 8)

1 2 3 4 5 6 7 8 9 10 11

06/11/11 Computación 1, 2011 - Facultad de Ingeniería 4

Matrices dispersas

Representación en memoria de una matriz

convencional

El caso inverso es igual de sencillo:

Dado un entero que representa una posición

dentro de una secuencia de bytes determinar

fila y columna (con sintaxis matlab):

Fila i = floor(posición_de_celda / n) + 1

Columna j = mod(posición_de_celda, n)

Si j = 0 ; j = 1 

Matrices dispersas

Conclusiones sobre el uso de matrices

convencionales

 Son pocos cálculos

 Esos cálculos son “elementales”: +

, -,

* y /

 Son cálculos con enteros

 parte entera y módulo se pueden hacer con

aritmética de punto fijo

 Si la matriz es n-dimensional (n > 2) se

agrega complejidad pero se mantienen

estas características generales

06/11/11 Computación 1, 2011 - Facultad de Ingeniería 6

Matrices dispersas

Definición de MATRIZ DISPERSA

Es aquella que está compuesta por muchos

elementos de valor = 0 de tal forma que los que

son distintos de 0 se encuentran muy dispersos

en la matriz y sin relación entre sí.

El qué tan dispersos están depende de las

circunstancias. En nuestro caso nos preocupa el

uso de memoria.

Eventualmente se podría definir como dispersa

con respecto a otro valor distinto de 0.

06/11/11 Computación 1, 2011 - Facultad de Ingeniería 7

Matrices dispersas

Forma de representación

Debemos tratar de preservar los principios de

economía:

 Mínimo consumo de memoria

 Mínimo uso de procesador

 “tiempo” para acceder a los datos (los usos

de esos datos de por sí pueden requerir su

cuota de procesador)

 “tiempo” de cálculos

 Localidad de datos

06/11/11 Computación 1, 2011 - Facultad de Ingeniería 8

Matrices dispersas

Forma de representación

 Formato simple o elemental

 3 vectores

 Vector_f ( fila ), enteros

 Vector_c ( columna ), enteros

 Vector_d ( dato ), pto flotante

06/11/11 Computación 1, 2011 - Facultad de Ingeniería 9

Matrices dispersas

forma de representación

 Formato CSR- (Compressed Storage Row) o CRS

 Vector_f ( columna )

 Vector_c ( índice de cada nueva fila )

 Vector_d ( dato )

06/11/11 Computación 1, 2011 - Facultad de Ingeniería 10

Matrices dispersas

forma de representación

 Formato CRS