Resolución Paralelo Distribuida De Sistemas De Ecuaciones Basada En Técnicas De Descomposición De Grafos.

Abstract

En este trabajo se presenta la implementación paralelo distribuida de un nuevo
método para la resolución de sistemas de ecuaciones algebraicos lineales ralos, el cual está
basado en técnicas de descomposición de grafos. Nuestra hipótesis de partida fue que la
técnica de descomposición de dominios, combinada con el procesamiento paralelo
distribuido, permitiría la reducción de los tiempos de cómputo requeridos para resolver
sistemas de ecuaciones de gran dimensión. Así surgió la propuesta de particionar el sistema
original en un conjunto de subsistemas de menor dimensión que puedan ser resueltos en
forma simultánea. Se decidió efectuar dicho reordenamiento empleando la técnica de
descomposición de grafos denominada Método Directo. Este método reestructura la matriz
original a un forma triangular inferior en bloques, donde los bloques sobre la diagonal
corresponden a subsistemas de ecuaciones no singulares. Dado que cada uno de los
subsistemas puede depender o no de los anteriores, nuestro algoritmo calcula las relaciones
de dependencia mediante la generación de un grafo dirigido acíclico (DAG). El trabajo
experimental se realizó sobre un cluster de monoprocesadores conectados a través de una
red Ethernet. En la implementación del algoritmo se usó la librería de pasaje de mensajes
PVM, mientras que la estrategia de paralelización siguió un esquema master-worker. Los
resultados obtenidos fueron altamente satisfactorios en términos de speed-up, eficiencia y
estabilidad. A su vez, los mismos permiten observar que el método propuesto posee un mejor
desempeño cuanto más grandes y ralas sean las matrices asociadas a los sistemas.