ALGORITMOS PARALELOS PARA LA RESOLUCIÓN DE PROBLEMAS DE MÍNIMOS CUADRADOS BASADOS EN TRANSFORMACIONES ORTOGONALES SOBRE GPUs Y MULTIPROCESADORES

Abstract

La resolución de sistemas de ecuaciones lineales sobredeterminados es un problema que se presenta con frecuencia en la computación científica. Algunos ejemplos pueden encontrarse en campos como el procesado de señal, resolución de problemas en electromagnetismo, simulación de dinámica molecular, econometría etc. La modelización de estos problemas da lugar a sistemas de ecuaciones lineales o problemas lineales de mínimos cuadrados con matrices densas, a veces enormes. Uno de los métodos que se utiliza habitualmente para resolver sistemas de ecuaciones lineales sobredeterminados es el de mínimos cuadrados. Los procedimientos más fiables para resolver este problema conllevan la reducción de la matriz a alguna forma canónica mediante transformaciones ortogonales, como por ejemplo: la descomposición de Cholesky, descomposición en valores singulares o descomposición QR, siendo esta última la más comúnmente utilizada. En la actualidad, las plataformas multicore, entre ellas las GPUs, lideran el mercado de los computadores, El rápido avance, tanto en la programabilidad de los procesadores gráficos como en su flexibilidad, ha permitido utilizarlos para resolver un amplio rango de complejos problemas con altas necesidades computacionales. Es lo que se conoce como GPGPU (General-Purpose Computing on the GPU). En la presente tesis, se han implementado distintos algoritmos para la resolución de problemas de mínimos cuadrados: mínimos cuadrados ordinarios, generalizados, ponderados, Modelos de Ecuaciones Simultáneas y mínimos cuadrados sobre conjuntos discretos con aplicaciones en sistemas MIMO. Para ello se han utilizando distintos entornos como UPC, OMP, CUDA y librerías como LAPACK y CULA. Nuestros algoritmos están basados en la descomposición QR calculada mediante rotaciones de Givens, aunque también se han utilizado librerías como LAPACK, CULA o MAGMA que utilizan transformaciones de Householder para obtener esta descomposición.