Matrices
dispersas
[Link] Zárraga
Introducción
Las matrices dispersas son aquellas en las
que la mayoría de sus elementos son ceros.
En muchos problemas de álgebra lineal
numérica y aplicaciones computacionales,
trabajar con matrices dispersas es
fundamental para optimizar el uso de
memoria y reducir el tiempo de cálculo, ya
que sólo se almacenan y procesan los
elementos no nulos.
¿Por qué es importante el
estudio de matrices
dispersas?
• El uso de matrices dispersas es crucial
cuando se abordan sistemas de ecuaciones
lineales de gran tamaño.
Área de aplicación
Ingeniería (simulación estructural, circuitos
eléctricos, dinámica de fluidos)
Física computacional y química cuántica
Ciencia de datos y machine learning (modelos de
recomendación, análisis de texto)
Computación científica (resolución de sistemas
lineales, métodos iterativos)
Teoría de grafos y análisis de redes
Objetivos de aprendizaje:
Almacenar las matrices dispersas en un ordenador.
Ordenar las ecuaciones e incógnitas del sistema a
resolver con el fin de reducir el número de elementos no
nulos que se crean al factorizar la matriz.
Adaptar e implementar eficazmente los métodos
numéricos directos tradicionales con el fin de resolver
sistemas de ecuaciones lineales con matriz de coeficientes
dispersa.
Almacenamiento en ordenador de matrices dispersa
La efectividad del trabajo con matrices
dispersas se mide no sólo en términos de
los algoritmos que las manipulan sino
también por la forma en que el ordenador
se integra dentro del proceso que
generan esos algoritmos.
Almacenamiento por coordenadas
La forma más intuitiva de almacenar en un ordenador los elementos
no nulos de una matriz dispersa es haciéndolo mediante un
conjunto ordenado o desordenado de triples (aij, i, j), donde aij ≠ 0
Ejemplo:
Vamos a representarla utilizando la idea de la
matriz dispersa almacenando solo los elementos
no nulos como triples (valor,fila,columna).
Recuerda que los índices de fila y columna
empiezan desde 0.
Almacenamiento por coordenadas •Fila 1:
• 2 en la columna 0 → (2,1,0)
•-2 en la columna 2 → (−2,1,2)
•3 en la columna 4 → (3,1,4)
•Fila 2:
•-3 en la columna 1 → (−3,2,1)
(valor,fila,columna) •Fila 3:
Los elementos no nulos de esta •4 en la columna 1 → (4,3,1)
matriz son: •-4 en la columna 3 → (−4,3,3)
•Fila 0: •Fila 4:
•1 en la columna 0 → (1,0,0) • 5 en la columna 0 → (5,4,0)
•-1 en la columna 3 → (−1,0,3) •-5 en la columna 2 → (−5,4,2)
•6 en la columna 4 → (6,4,4)
Almacenamiento por coordenadas
Por lo tanto, la representación de esta matriz dispersa
como un conjunto de triples sería:
[(1, 0, 0), (-1, 0, 3), (2, 1, 0), (-2, 1, 2), (3, 1, 4), (-3, 2, 1), (4, 3, 1), (-4, 3, 3), (5, 4, 0), (-5, 4, 2),
(6, 4, 4)]
Siguiendo este orden para la matriz A:
Almacenamiento por filas o columnas
[Link] fila: [1,0,0,−1,0] se almacena primero.
[Link] fila: [2,0,−2,0,3] se almacena a conti
[Link] fila: [0,−3,0,0,0] le sigue.
[Link] fila: [0,4,0,−4,0] después.
[Link] fila: [5,0,−5,0,6] al final.
Siguiendo este orden para la matriz A:
[Link] columna: [1,2,0,0,5]T se almacena primero (es decir, 1, 2, 0, 0, 5).
[Link] columna: [0,0,−3,4,0]T se almacena a continuación (es decir, 0, 0, -3, 4, 0).
[Link] columna: [0,−2,0,0,−5]T le sigue (es decir, 0, -2, 0, 0, -5).
[Link] columna: [−1,0,0,−4,0]T después (es decir, -1, 0, 0, -4, 0).
[Link] columna: [0,3,0,0,6]T al final (es decir, 0, 3, 0, 0, 6).
Almacenamiento por filas o columnas
Para trabajar con almacenamiento por filas y
columnas en Python, la biblioteca principal que
se utiliza es NumPy.
NumPy proporciona la estructura de datos
ndarray
(n-dimensional array), que puede almacenar
datos en memoria tanto en orden de filas (C-
style, que es el predeterminado) como en orden
de columnas (Fortran-style).
Almacenamiento por perfil envolvente
El almacenamiento por perfil envolvente (también conocido como almacenamiento
de banda variable o almacenamiento skyline) es una técnica de almacenamiento
eficiente para matrices simétricas dispersas.
Para la primera columna, el primer elemento no nulo está en la fila 0 (valor 4).
El perfil hasta la diagonal incluye [4, 1, 0, 2].
Para la segunda columna, el primer elemento no nulo está en la fila 0 (valor 1).
El perfil hasta la diagonal incluye [1, 3, 0].
Para la tercera columna, el primer elemento no nulo está en la fila 2 (valor 2).
El perfil hasta la diagonal incluye [2, 1].
Para la cuarta columna, el primer elemento no nulo está en la fila 0 (valor 2).
El perfil hasta la diagonal incluye [2, 0, 1, 5].
Almacenamiento por perfil envolvente
Imagina dibujar una línea desde el primer
elemento no nulo de cada columna hacia abajo
hasta la diagonal. El perfil envolvente contiene
todos los elementos bajo esta línea.
Donde '.' representa los ceros que podrían estar
dentro del perfil.
Los elementos se almacenarían columna por columna dentro de su
perfil:
Columna 0: [4]
Columna 1: [1, 3]
Columna 2: [2] (el primer no nulo es en la fila 2)
Columna 3: [2, 0, 1, 5] (el primer no nulo es en la fila 0)
El array de valores sería: [4, 1, 3, 2, 2, 0, 1, 5]
Almacenamiento por lista encadenadas
Representación por filas:
Para cada fila, se crea una lista encadenada que contiene los elementos no
nulos de esa fila. Cada nodo en la lista contendría:
•El valor del elemento (aij).
•El índice de la columna (j).
•Un puntero al siguiente nodo en la lista de la misma fila.
La representación por listas encadenadas (por filas) sería
algo así:
•Fila 0: (valor=1, columna=0) → (valor=-1, columna=3) →
None
•Fila 1: (valor=2, columna=2) → None
•Fila 2: (valor=3, columna=1) → None
Almacenamiento por lista encadenadas
Operaciones algebraicas elementales con matrices dispersas
Producto interno de dos vectores
Supongamos los vectores
U=(2,3), V=(1,4).
El producto interno se calcula multiplicando componente a componente
y sumando los resultados:
U⋅V=2×1+3×4 = 2+12 =14.
Este resultado es un número real (escalar), no un vector
Operaciones algebraicas elementales con matrices dispersas
Ejemplo con vectores en R³
Si tienes
A=(1,2,3), B=(4,5,6)
A.B = 1x4 + 2x5 + 3x6 = 4 + 10 + 18 = 32
Operaciones algebraicas elementales con matrices dispersas
Multiplicación de una matriz dispersa por un vector
𝑏1 = 1𝑥9 + 0𝑥10 + 2𝑥11 + 0𝑥12 = 31
𝑏2 = 0𝑥9 + 3𝑥10 + 0𝑥11 + 4𝑥12 = 78
𝑏3 = 5𝑥9 + 0𝑥10 + 6𝑥11 + 0𝑥12 = 111
𝑏4 = 0𝑥9 + 7𝑥10 + 0𝑥11 + 8𝑥12 = 166
Operaciones algebraicas elementales con matrices dispersas
Multiplicación de una matriz dispersa por un vector
Operaciones algebraicas elementales con matrices dispersas
Multiplicación de un vector por una matriz dispersa
Vector fila: 𝑤1 = 2𝑥4 + 0𝑥5 + 3𝑥6 + 0𝑥0 = 26
𝑤2 = 2𝑥0 + 0𝑥0 + 3𝑥0 + 0𝑥0 = 0
𝑤3 = 2𝑥0 + 0𝑥7 + 3𝑥0 + 0𝑥8 = 0
Matriz dispersa:
Operaciones algebraicas elementales con matrices dispersas
Suma de matrices dispersas:
Suma o resta simbólica
Operaciones algebraicas elementales con matrices dispersas
Suma de matrices dispersas:
Operaciones algebraicas elementales con matrices dispersas
Multiplicación de matrices dispersas
Multiplicación A^TA
Operaciones algebraicas elementales con matrices dispersas
Multiplicación de matrices dispersas
Operaciones algebraicas elementales con matrices dispersas
Conclusión
Las matrices dispersas son estructuras fundamentales en la
computación científica y el análisis numérico, caracterizadas
por contener principalmente elementos cero y unos pocos
valores significativos. Esta particularidad permite optimizar de
manera sustancial el uso de memoria y acelerar los cálculos al
evitar operaciones innecesarias sobre ceros, lo cual es crucial
en problemas a gran escala como simulaciones físicas,
análisis de redes, teoría de grafos y métodos numéricos para
ecuaciones diferenciales parciales
