Compresión para multiplicación de matrices mediante bicliques en grafos con pesos.

Abstract

Las operaciones sobre matrices constituyen un área crucial en las ciencias de la computación, especialmente debido a su uso extensivo en diversas disciplinas para representar datos, y al constante crecimiento de estos datos. Por ende, resulta fundamental proponer algoritmos eficientes para operar sobre conjuntos de datos cada vez más grandes. Entre las aplicaciones destacadas de las matrices se encuentra la representación de grafos. En un trabajo anterior realizado por Hernández y Navarro [1] en 2014, propusieron un método para la compresión de grafos utilizando representaciones matriciales. Su enfoque se centró en la búsqueda y extracción de bicliques con el objetivo de eliminar subgrafos densos dentro del grafo, lo que resultó en una representación comprimida eficiente del mismo. Esta memoria de título se inspira en el enfoque propuesto por Hernández y Navarro [1], ampliando su aplicación a grafos de mayor tamaño y a grafos con pesos o ponderados. Se busca también aprovechar esta compresión para reducir el tiempo de cómputo en operaciones entre matrices, proponiendo un método alternativo para la multiplicación matriz-matriz. Para realizar la evaluación se utilizaron grafos generados artificialmente. Se busca analizar tanto las características de los grafos como de los bicliques, con el fin de medir la capacidad de búsqueda y extracción del algoritmo propuesto así como también medir el impacto que pueden en las operaciones matriciales. Los resultados muestran por un lado que el algoritmo es capaz de recuperar las aristas de los bicliques de los grafos y por otro lado muestran que los tiempos de multiplicación de matrices si se ven beneficiados por la compresión obtenida, dando mejores resultados en escenarios donde la compresión en mayor.