Implementación de la iteración lanczos en arquitectura CUDA

Abstract

Los autovalores y autovectores son elementos muy utilizados en diversos problemas como análisis de estructuras, reconocimiento de imágenes, compresión de datos, solución de problemas electrodinámicos, entre otros. Existen muchos algoritmos para calcular y tratar con autovalores y autovectores mediante el uso de computadoras, sin embargo, cuando solo se requiere uno o unos pocos autovalores (los más significativos) y autovectores, se puede optar por Power Method o la Iteración Lanczos. Por otro lado, factores como la cantidad de información a procesar o la precisión deseada pueden significar tiempos de ejecución no aceptables para ciertas aplicaciones, surgiendo la alternativa de realizar implementaciones paralelas, siendo la arquitectura CUDA una de la mejores opciones actualmente. En la presente tesis se propone diseñar e implementar un algoritmo paralelo para la iteración Lancos en arquitectura CUDA, el cual es un método para el cálculo del mayor autovalor y su correspondiente autovector. La propuesta esta dividia en tres bloques principales. El primer bloque realiza la tridiagonalización parcial de una matriz cuadrada simétrica. El segundo bloque calcula la descomposición de Schur de la matriz tridiagonal obteniendo los autovectores y autovalores de esta. El tercer bloque calcula el mayor autovalor y su correspondiente autovector de la matriz inicial a partir de lo obtenido en etapas anteriores y determinará si es necesario seguir realizando cálculos. Los bloques trabajan iterativamente hasta encontrar resultados que se ajusten a la precisión deseada. Además de la implementación paralela en CUDA, se realizaron implementaciones en el entorno de simulación MATLAB y en lenguaje C secuencial, con el propósito de comparar y verificar una correcta y eficiente implementación paralela. Los resultados computacionales evaluados para una matriz de 4000 _ 4000 elementos reflejan un rendimiento de 13;4 y 5;8 al compararse la implementación en CUDA con MATLAB y C secuencial respectivamente. Estos rendimientos tienden a crecer mientras mayor sea el tamaño de la matriz. La organización de la tesis es: en el primer capítulo se describe la problemática del tema. En el segundo capítulo se explica la teoría correspondiente a Power Method y Lanczos, así como los algoritmos necesarios. En el capítulo tres se exponen conceptos fundamentales sobre arquitectura CUDA. El diseño del algoritmo paralelo se desarrolla en el capítulo cuatro. Finalmente, en el capítulo cinco, se muestran y analizan los resultados computacionales, seguidos de las conclusiones, recomendaciones y bibliografía.