Algoritmos paralelos para el cálculo de los valores propios de matrices estructuradas

Abstract

ESTA TESIS SE CENTRA FUNDAMENTALMENTE EN LA RESOLUCION DEL PROBLEMA DE CALCULO DE LOS VALORES PROPIOS DE MATRICES ESTRUCTURADAS, PARA ELLO COMENZAMOS POR ESTUDIAR LOS PRINCIPALES METODOS EXISTENTES PARA LA RESOLUCION DE ESTE PROBLEMA, HACIENDO ESPECIAL HINCAPIE EN SUS POSIBILIDADES DE PARALELISMO. A CONTINUACION IMPLEMENTAMOS VERSIONES SECUENCIALES Y PARALELAS DE LOS DISTINTOS METODOS ESTUDIADOS, Y FINALMENTE REALIZAMOS UN ANALISIS EXPERIMENTAL EXHAUSTIVO DE LOS ALGORITMOS SOBRE DIVERSAS ARQUITECTURAS PARALELAS Y UTILIZANDO DISTINTOS ENTORNOS DE PROGRAMACION. BASICAMENTE, SE TRATA CON DOS TIPOS DE MATRICES, TRIDIAGONALES Y EFICIENTEMENTE ESTRUCTURADAS (TOEPLITZ DENSAS Y BANDA, TOEPLITZ+HANKEL). TAMBIEN SON DOS LOS TIPOS DE METODOS UTILIZADOS: BISECCION/MULTISECCION Y DIVIDE Y VENCERAS. LOS DISTINTOS ALGORITMOS EXPLOTAN Y COMBINAN LOS DISTINTOS NIVELES DE PARALELISMO DE LOS METODOS. LOS RESULTADOS EXPERIMENTALES DEMUESTRAN LA ENORME DEPENDENCIA DEL PROBLEMA DE LOS ALGORITMOS IMPLEMENTADOS, ASI COMO LAS GRANDES POSIBILIDADES DE PARALELIZACION DE LOS DOS METODOS. POR PRIMERA VEZ SE PARALELIZA EL METODO DE BISECCION EN EL CASO DE MATRICES ESTRUCTURADAS NO TRIDIAGONALES CON BUENOS RESULTADOS. EN EL CASO TRIDIAGONAL EL MEJOR PROCEDIMIENTO DE APROXIMACION A UTILIZAR EN EL METODO DE BISECCION HA DEMOSTRADO SER EL ITERATIVO DE LAGUERRE. LOS RESULTADOS SECUENCIALES OBTENIDOS EN ESTE CASO LLEGAN A SUPERAR A LOS DE LAS MEJORES RUTINAS IMPLEMENTADAS EN PAQUETES NUMERICOS COMO EL LAPACK Y OBTIENEN RESULTADOS MAS PRECISOS. EN EL CASO PARALELO LOS INCREMENTOS DE VELOCIDAD OBTENIDOS POR EL MEJOR ALGORITMO PARALELO SE APROXIMAN A LOS MAXIMOS POSIBLES, INCLUSO CON UN GRAN NUMERO DE PROCESADORES. POR OTRO LADO, SE HA DEMOSTRADO LA UTILIDAD DE APLICAR TECNICAS DE DISTRIBUCION DINAMICA DE LA CARGA CUANDO EL COSTE DE CALCULO ES LO SUFICIENTEMENTE ELEVADO, COMO EN EL CASO DE LAS MATRICES EFICIENTEMENTE ESTRUCTURADAS.