MATRICES DISPERSAS
Es
aquella matriz de gran tamaño en la que la mayor parte de sus
elementos son cero.
Con matrices de gran tamaño los métodos
tradicionales para almacenar la matriz en la memoria de una computadora o para
la resolución de sistemas de ecuaciones lineales necesitan una gran
cantidad de memoria y de tiempo de proceso. Se han diseñado algoritmos
específicos para estos fines cuando las matrices son dispersas.
Con las matrices dispersas se pueden trabajar
fácilmente matrices de millones de renglones por millones de columnas. A veces
se requiere solo visualizar las entradas distintas de cero, para ello se usan
imágenes como las siguientes:
Las matrices llenas de tamaño n×n tienen un costo
de almacenamiento de O(n 2 ), las matrices dispersas suelen tener un costo de
almacenamiento de O(n). Como ejemplo, la siguiente matriz A∈ℝ 556×556 contiene 309,136 entradas,
con η(A)=1810, es decir sólo el 0.58% de las entradas son no cero.
Matrices estructuradas
Los elementos no cero forman un patrón regular, por ejemplo, se agrupan
a lo largo de un n´umero peque˜no de diagonales.
Matrices no estructuradas
Los elementos no cero se distribuyen de forma irregular. En el primer
caso se pueden diseñar métodos basados en la estructura de las matrices,
mientras que en el segundo caso solo se puede hacer uso de la ‘dispersidad’ de
la matriz. (UPV) Matrices dispersa
Esquema coordenado
Para representar la matriz A se utilizan tres vectores AA, IA, y JA de
dimension nz . En el vector AA se almacenan los elementos no nulos de A, en
IA, se almacenan los numeros de fila asociados a cada elemento de A y en JA el
numero de columna asociado a cada elemento de A.
No hay comentarios:
Publicar un comentario