Algoritmos divide y vencerás para la resolución de sistemas lineales tridiagonales en un computador BSP

Resumen

En esta memoria se estudian y comparan diversos algoritmos del tipo divide y vencerás para la resolución de sistemas lineales tridiagonales, utilizando el modelo de computación paralela Bulk-Computing (BSP), Concretamente, se implementan dos algoritmos basados en un método divide y vencerás que utiliza la fórmula de Sherman-Morrison para el cálculo de la inversa de una matriz. El primer algoritmo utiliza un esquema de comunicaciones de tipo fan-in, mientras que en el segundo las comunicaciones son hacia el procesador principal. Se implementan cuatro algoritmos basados en un método divide y vencerás que utiliza la fórmula Sherman-Morrison-Woodbury para obtener la solución del sistema inicial. Finalmente, se implementan tres algoritmos basados en el métodode Bondeli para sistemas tridiagonales. Se calcula el coste computacional de todos los algoritmos estudiados, siguendo el modelo de coste que nos proporciona el modelo de computación paralela BSP y se realiza un estudio del comportamiento paralelo de todos estos algoritmos, basándonos en el cálculo del speedup y de la eficiencia de los mismos. Las máquinas donde se predicen estos resultados son un IBM SP2, dotado con un switch de alto rendimiento y una conexión ethernet, un CRAY T3D y un cluster de Pentiums. El estudio comparativo de todos los algoritmos nos lleva a afirmar que los que presentan mejores tiempos de ejecución son los basados en la fórmula de Sherman-Morrison-Woodbury, especialmente los algoritmos que resuelven en paralelo el sistema tridiagonal auxiliar, junto con el algoritmo basado en el método de Bondeli que resulve en paralelo su sistema tridiagonal auxiliar. Los tiempos de estos dos algoritmos para valores grandes de n son prácticamente idénticos. En general, los peores tiempos se obtienen para los algoritmos basados en la fórmula de Sherman-Morrison. En general, los mejores valores de speedup y eficiencia los proporciona el algoritmo basado en