Resolución Paralelo Distribuida de Sistemas de Ecuaciones basada en Técnicas de Descomposición de Grafos

AXEL JUAN SOTO; IGNACIO PONZONI; GUSTAVO ESTEBAN VAZQUEZ

Buenos Aires, Argentina

Congreso; VIII Congreso de Mecánica Computacional - MECOM 2005; 2005

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.