Árboles de expansión de máximo peso como precondicionadores y su aplicación a matrices de grafos y de elementos finitos

Abstract

En este trabajo se estudian unos aspectos de grafos y subgrafos en dimensión 2, especialmente de árboles. Es conocido que a cada grafo se le asocian varios tipos de matrices que conectan de manera estrecha las propiedades geométricas de grafos y las propiedades espectrales de dichas matrices. El laplaciano es una de las matrices más importantes que se asocian a un grafo. Siendo el laplaciano una matriz simétrica semi definida positiva, es natural de pensar en algoritmos como el gradiente conjugado o el gradiente conjugado precondicionado cuando se necesita resolver sistemas lineales cuyas matrices son justamente laplacianos de grafos. En este trabajo se estudian preconcionadores que corresponden a subgrafos, en particular árboles. En este contexto, varios resultados teóricos se exponen para justificar el marco matemático del uso y los beneficios de precondicionamiento con árboles y especialmente el que corresponde a árboles de expansión de máximo peso. Al inicio de este trabajo, presentamos el método de Elementos Finitos para la solución de un problema elíptico clásico y el método del gradiente conjugado (el lector iniciado puede perfectamente saltar esta parte, pues está en casi todas las referencias de Análisis Numérico). Nuestro aporte principal en este trabajo es explotar las similitudes de las matrices de rigidez de elementos finitos con los laplacianos que provienen de grafos y utilizar la teoría espectral de grafos y el precondicionamiento con árboles de expansión de máximo peso para resolver los sistemas lineales que surgen de nuestros problemas elípticos. Los resultados son muy buenos y en ciertas ocasiones son de lejos mejores que en otros precondicionadores clásicos, como el precondicioandor SOR, que es en sí mismo muy eficiente cuando se trata de matrices de rigidez construidas por elementos finitos P1 con discretización regular.