Algoritmos paralelos para la triangularizacion de givens de matrices dispersas en multicomputadores

Resumen

La tesis se inicia con la descripcion de algunos de los aspectos mas relevantes de los multicomputadores, sistemas de interes debido a su escalabilidad y a su reducido coste. Tambien se hace una breve descripcion del contexto en el que se ha hecho uso de estos sistemas: la resolucion de problemas dispersos de minimos cuadrados. Asi mismo, se describen las matrices utlizadas de la harwell boeing sparse matrix collection y de problemas de elementos finitos. En la tesis se estudian algoritmos para la reduccion a forma triangular de matrices dispersas mediante rotaciones de givens. En primer lugar se abordan los algoritmos secuenciales, comparando algoritmos existentes con un algoritmo propuesto. Dicha comparacion, basada en una novedosa caracterizacion funcional del problema indica que el algoritmo propuesto es competitivo con los existentes. Los algoritmos secuenciales sirven como referencia y punto de partida para el diseño y la evaluacion de algoritmos paralelos sobre multicomputadores. Se proponen dos algoritmos paralelos, uno basado en el algoritmo secuencial propuesto, el otro esta basado en uno de los algoritmos existentes. En el primer caso, se puede reducir a la mitad el mejor tiempo secuencial de los algoritmos considerados, haciendo uso de 3 o 4 procesadores. En el segundo caso se puede esperar una reduccion entre la mitad y la octava parte utilizando entre 8 y 32 procesadores, dependiendo tambien del problema. La evaluacion de los algoritmos paralelos se realiza haciendo uso de una tecnica novedosa que combina el analisis del paralelismo medio con la utilizacion de un simulador. El analisis permite estimar el grado de paralelismo potencial del problema, asi como el numero de procesadores que puede ser de interes utilizar. El simulador permite un analisis detallado del comportamiento de los algoritmos respecto de parametros de interes de los multicomputadores, concretamente respecto del numero de procesadores y del