Un Nuevo Algoritmo Paralelo Distribuido para Resolución de Sistemas de Ecuaciones Lineales

SOTO, AXEL J.; VAZQUEZ, GUSTAVO E.; PONZONI, IGNACIO

Bariloche, Argentina

Congreso; ENIEF 2004, (14º Congreso sobre Métodos Numéricos y sus Aplicaciones); 2004

AMCA (Asociación Argentina de Mecánica Computacional)

En este artículo se propone un nuevo algoritmo paralelo distribuido diseñado para resolver sistemas de ecuaciones lineales ralos, lo cual brinda la posibilidad de obtener la solución a numerosos problemas grandes y/o complejos en forma muy eficiente. Esto reviste gran relevancia práctica dado que la resolución de los modelos matemáticos de un sinnúmero de problemas reales en los campos de la física, química, economía y comunicaciones involucran la resolución de sistemas algebraicos. El procesamiento distribuido típicamente agiliza el tratamiento de un problema, reduciéndolo a un conjunto de subproblemas más pequeños. En particular, resulta factible emplear la técnica de descomposición de dominios, mediante la aplicación de algoritmos de reordenamiento estructural. De este modo es posible particionar el sistema original en una familia de subsistemas que puedan ser resueltos simultáneamente. Una importante ventaja de esta metodología es que permitiría el manejo de problemas actualmente intratables por su gran dimensión. La idea central que inspiró este trabajo es que cualquier sistema de ecuaciones puede ser reordenado, en cuanto a la estructura de su matriz de ocurrencia, a una forma que permita su descomposición en subsistemas. Nuestra propuesta es llevar a cabo este reordenamiento mediante la técnica de descomposición de grafos propuesta por Ponzoni et al. (Industrial & Engineering Chemistry Research, Vol. 43, No. 2, 577-588, 2004). El patrón obtenido corresponderá a una matriz triangular inferior en bloques, no necesariamente cuadrada, donde los bloques sobre la diagonal son cuadrados y corresponden a subsistemas Si no singulares. Cada uno de los subsistemas Si puede o no depender de los anteriores. Esta relación se expresa mediante un grafo dirigido acíclico (DAG), donde Si será dependiente de Sj si al menos una de las ecuaciones de Si contiene variables de Sj. Una vez efectuado el reordenamiento y obtenido su DAG correspondiente, es posible paralelizar la resolución del sistema respetando los niveles de dependencias existentes entre los subsistemas. Luego, los subsistemas pueden resolverse simultáneamente en diferentes procesadores empleando técnicas tradicionales, dependiendo de las características del sistema. Por ejemplo, para los sistemas lineales es posible trabajar con métodos directos, tipo Gauss, o técnicas iterativas, tales como Gauss-Seidel o SOR. En este trabajo en particular, se utilizó la librería de pasaje de mensajes PVM para implementar el procesamiento paralelo distribuido siguiendo un modelo master-worker, mientras que los resultados reportados fueron obtenidos empleando métodos iterativos para la resolución de los subsistemas de ecuaciones.