MATRIZ DISPERSA

Definición

Se dice que una matriz es dispersa cuando se puede hacer uso de técnicas especiales para sacar ventaja del gran número de elementos ceros que posee.

Reducir requerimientos de memoria:

En una matriz común, las casillas que no están siendo ocupadas por un elemento contienen un null, pero aun así se está reservando memoria para alojar este dato. Una matriz dispersa soluciona este problema usando encadenamientos que no necesitan reservar memoria para las posiciones de la matriz que son vacías.

podemos utilizar las matrices dispersas, que contienen tanta información como las matrices de adyacencia, pero, en principio, no ocupan tanta memoria como las matrices, ya que al igual que en las listas de adyacencia, sólo representaremos aquellos enlaces que existen en el grafo.

Reducir el coste aritmético de las operaciones.

(no hay que multiplicarlos)

(ELEMENTOS DE UNA MATRIZ) * 0 = 0

Lista enlazada

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, uno de ellos es la lista enlazada.

En la Figura se observa una matriz de 5x5 en donde solo 3 de sus elementos son diferentes de cero

Cada nodo almacena un elemento de la matriz, se puede observar que se tienen punteros de un nodo al siguiente, además de la información de la fila y la columna en la que se encuentra en dicha matriz.

El consiste en almacenar la misma información que se guardaba en el método de listas enlazadas, pero esta vez con 3 arreglos estáticos. Para la anterior matriz se tendría entonces los siguientes vectores

En el primer arreglo se almacenarán todos los datos no nulos de la matriz dispersa, por lo tanto el tamaño del vector dependerá de la cantidad de valores no nulos que tenga la matriz dispersa. En el segundo vector se almacenara la información pertinente para la fila que contiene dicho dato, y por último en el tercer vector estará almacenada la información que tiene que ver con el valor de la columna del dato.

Matriz dispersa como grafo

Una matriz dispersa con estructura simétrica se puede representar como un grafo no dirigido. En el grafo no están representados los valores de la matriz, sólo la estructura de las entradas distintas de cero .

Para una matriz cuadrada A, se asocia un nodo con cada fila. Si aij es un elemento no nulo (entrada) de una matriz dispersa, hay una arista dirigida del nodo i al j.

Matrices dispersas de mallas de elemento finito

En el método de elemento finito, se trabaja de forma contraria, se parte de la malla (grafo) y se genera la matriz dispersa.

[endif]

Dado que un nodo de la malla se conecta sólo con pocos nodos, tendremos una matriz muy dispersa. En general, el tamaño del número de entradas distintas de cero será O( n).