摘要：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.
