Parallelization and compilation issues of sparse QR algorithms

Abstract

La tesis doctoral se centra en el estudio y desarrollo de métodos eficientes para la paralelización de algoritmos de factorización QR de matrices dispersas, La descomposición QR tiene diversas aplicaciones en el álgebra lineal, apareciendo en el núcleo de muchos códigos numéricos. En esta tesis se consideran tres métodos de factorización QR: el algoritmo de Gram-Schmidt modificado, las transformaciones de Householder y las rotaciones de Givens. También se considera la aplicación de dicha factorización a la resolución de problemas de mínimos cuadrados. El estudio de la paralelización de estos algoritmos se realiza sobre arquitecturas multiprocesador con memoria distribuida. Sobre esta clase de plataformas se siguen diversas aproximaciones. La primera de ellas consiste en el diseño y optimización manual de los diversos algoritmos paralelos. Se desarrollan diferentes estructuras de datos para almacenar las matrices dispersas, así como se prueban diferentes estrategias para su distribución en las memorias locales. También se aplica una nueva estrategia para reducir el llenado que se produce en la matriz dispersa mientras se realiza la factorización. En una segunda aproximación se incorporan las diversas operaciones de manejo y control de las estructuras de datos utilizadas, así como de las comunicaciones, en una librería, para ser llamada durante la ejecución de los algoritmos. De esta manera se facilita, y se generaliza, la programación paralela de algoritmos de factorización de matrices dispersas, especialmente QR. Estas funciones, a su vez, podrían ser llamadas por un compilador. El tercer enfoque supone un cambio cualitativo con respecto a los dos anteriores, y consiste en semiautomatizar el desarrollo de esta clase de algoritmos paralelos. En concreto, se analizan y se proponen nuevas extensiones a la sintaxis de HPF (High Performance Fortran), un lenguaje estándar de paralelismo de datos.