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

  1. Tortosa Grau, Leandro
Dirigida por:
  1. Joan-Josep Climent Coloma Director

Universidad de defensa: Universitat d'Alacant / Universidad de Alicante

Fecha de defensa: 25 de febrero de 2000

Tribunal:
  1. Rafael Bru García Presidente/a
  2. José Penadés Martínez Secretario
  3. Josep Mas Marí Vocal
  4. Domingo Giménez Cánovas Vocal
  5. Violeta Migallón Gomis Vocal
Departamento:
  1. MATEMATICAS

Tipo: Tesis

Teseo: 74503 DIALNET lock_openRUA editor

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