Departamento de Computación

El algoritmo de Cuppen (o algoritmo divide y vencerás) es un algoritmo numéricamente estable y eficiente que calcula todos los valores y vectores propios de una matriz tridiagonal simétrica. Los problemas regulares de Sturm-Liouville son ecuaciones diferenciales lineales de segundo orden que tienen una forma especial y cuyos valores en la frontera deben respetar ciertas condiciones. El cálculo numérico de los valores propios de este tipo de problemas es de gran importancia, debido a las distintas áreas de aplicación que tienen, tales como: vibración de cuerdas, propagación de ondas, termodinámica, mecánica y química cuánticas. Entre los métodos numéricos para resolver este problema se encuentran, el método de disparo y el método de diagonalización de matrices. Estos métodos tienen un alto costo computacional, por lo que, en esta tesis se desarrollaron implementaciones paralelas de ellos para reducir su tiempo de ejecución, y se utilizaron en casos específicos del problema regular de valores propios de Sturm-Liouville. En este trabajo se presenta, a nuestro conocimiento, la primera implementación paralela heterogénea en un cluster con múltiples GPUs y CPUs del algoritmo divide y vencerás para valores propios. Una de las principales desventajas de implementar dicho algoritmo en GPUs es que el cómputo esta limitado por la cantidad de memoria del GPU. Para superar este problema nosotros utilizamos múltiples nodos con CPUs y GPUs para resolver subproblemas que encajan en la memoria de un GPU en paralelo y reunimos sus resultados para obtener la solucióon completa. Experimentos preliminares muestran resultados prometedores. Nuestro enfoque tiene mejor desempeño que el de librerías actuales. Además, las soluciones obtenidas muestran un alto grado de exactitud con respecto a la ortogonalidad de los vectores propios y a la calidad de los eigenpares.

Abstract

Cuppen's algorithm (or divide-and-conquer algorithm) is a numerically stable and efficient algorithm that computes all eigenvalues and eigenvectors of a symmetric tridiagonal matrix. Regular Sturm-Liouville problems are second order differential equations with special form those boundary values accomplish certain conditions. The considerable importance of the numerical calculation of their eigenvalues laid on the many eigenvalue problems that arise in scientific and engineering applications such as: vibrating strings, propagation of waves, thermodynamics, quantum mechanics and quantum chemistry. Among the variety of methods to solve these problems are shooting methods and matrix diagonalization. These methods have a high computational cost, for this reason in this thesis parallel implementations of them were developed in order to reduce running times. Also, they were applied to specific cases of the regular Sturm-Liouville eigenvalue problem. In this work we present, to the best of our knowledge, the first heterogeneous parallel implementation on a cluster with multiple GPUs and CPUs of the divide-and-conquer eigenvalue algorithm. A major drawback of implementing such algorithm on GPUs is that computation is limited by the amount of GPU memory. We overcome the issue by using multiple nodes with CPUs and GPUs to solve subproblems, which fit on device memory in parallel, and merging those subproblems to get the whole result. Preliminary experiments show promising results. Our approach has better performance than state-of-the-art libraries. Furthermore, it exhibits a meaningful degree of accuracy with respect to orthogonality of eigenvectors and quality of egeinpairs.