Introducción al Trabajo de Título
Entrar

Multiplicación de matrices esparsas Memoria Doble Titulación Ciencia e Ingeniería de datos Teoría de la computación

Profesor Guia
Sub Áreas Procesamiento masivo de datos, Análisis y diseño de algoritmos y estructuras de datos

Descripción


Una técnica reciente para multiplicar matrices esparsas (https://users.dcc.uchile.cl/~gnavarro/ps/spire23.1.pdf) utiliza una representación para las matrices llamada LOUDS, que es muy simple pero ha presentado algunas desventajas a la hora de realizar las multiplicaciones y clausuras transitivas. El objetivo de esta memoria es reemplazar LOUDS por otra construcción llamada DFUDS, que es más compleja pero promete mejores resultados. Se deberá modificar la implementación actual, en C, para usar la nueva representación, reejecutar los experimentos y reportar las diferencias. 

Para el caso de doble titulación, se deberá además modificar la representación de DFUDS para que sea cache-oblivious, lo que significa esencialmente cambiar la representación de un árbol perfecto que se usa entremedio para que recorra los nodos en orden DFS en vez de BFS. Puede llevar a una publicación si los resultados son buenos.