El método de Neville : un enfoque basado en computación de altas prestaciones

Abstract

En esta memoria se ha llevado a cabo un trabajo original sobre las prestaciones de varios algoritmos organizados por bloques para aplicar la eliminación de Neville sobre un sistema de ecuaciones lineales (Ax=b) en un computador paralelo, utilizando el paradigma de paso de mensajes y distintas métricas que nos han permitido analizar las prestaciones de los algoritmos estudiados. La eliminación de Neville es un procedimiento alternativo a la eliminación de Gauss para transformar una matriz cuadrada A en una matriz triangular superior. Estrictamente hablando, la eliminación de Neville hace ceros en una columna de A añadiendo a cada fila un múltiplo de la fila previa. Esta estrategia se ha probado especialmente útil cuando se trabaja con cierto tipo de matrices, como por ejemplo, las totalmente positivas o las signo-regulares. Una matriz se dice totalmente positiva si todos sus menores son no negativos. Este tipo de matrices aparecen en muchas ramas de la ciencia, como por ejemplo en, Matemáticas, Estadística, Economía, o en Diseño Geométrico Asistido por Ordenador. En esta línea, los trabajos de un amplio número de autores han mostrado en los últimos años que la eliminación de Neville es una alternativa interesante a la de Gauss para cierto tipo de estudios. En el desarrollo de algoritmos paralelos para resolver problemas de Algebra Lineal Numérica la organización por bloques se muestra como la más eficiente para obtener el máximo provecho de las máquinas actuales, tanto en cuanto al buen uso de la jerarquía de memorias en máquinas con memoria compartida como al aprovechamiento del paralelismo explícito en máquinas de memoria distribuida. Con esta organización se suelen obtener algoritmos eficientes y escalables. Dos librerías bien conocidas como Lapack y ScaLapack utilizan como principal estrategia de diseño de sus algoritmos paralelos la organización por bloques. Para poder llegar a códigos óptimos es necesario definir los parámetros del problema y hacer un análisis profundo del comportamiento de los algoritmos desarrollados en función de las propiedades de éstos. Este análisis debe tener en cuenta el comportamiento de los algoritmos en cuanto a tiempo de ejecución, speedup/eficiencia y escalabilidad. Cuando los algoritmos se organizan por bloques es especialmente importante la relación entre el tamaño del bloque y las prestaciones en cada una de las métricas citadas. El tamaño de los bloques puede influir notablemente en las prestaciones. Es importante conocer como influye en cada una de ellas, si se desea un tipo de algoritmo concreto que optimice las prestaciones en una u otra métrica, o en el conjunto de todas ellas. En nuestro trabajo proponemos una organización del algoritmo de eliminación de Neville para computadores que sigan el modelo de paso de mensajes, y llevamos a cabo un análisis general basado en tres métricas: tiempo, speedup/eficiencia y escalabilidad. Este análisis se considera para las distribuciones por bloques más usuales de los datos, distribuciones unidimensionales (por filas y columnas) y bidimensionales, y se compara con el caso experimental en dos tipos de máquinas representativas del modelo de paso de mensajes: una red de estaciones de trabajo y un multicomputador, para lo que previamente se ha modelizado el comportamiento de ambos entornos.