¿Cómo se puede paralelizar un método de múltiples cuadrículas para resolver un sistema lineal de ecuaciones?

11

Según tengo entendido, el método de cuadrícula múltiple resuelve un sistema lineal resolviendo una versión más gruesa del mismo problema (eliminando el error de baja frecuencia) y luego proyectando de nuevo a la cuadrícula fina para suavizar los errores de alta frecuencia. Para sistemas grandes, puedo ver cómo se puede implementar un método iterativo en paralelo en cada nivel de cuadrícula. ¿Este enfoque escala bien en paralelo? ¿Hay alguna otra fuente de concurrencia en el algoritmo que se pueda explotar en paralelo?

Paul
fuente

Respuestas:

14

La cuadrícula geométrica paralela es fácil de implementar en cuadrículas estructuradas. Las multirredes algebraicas y no estructuradas son más técnicas, consulte esta respuesta para obtener enlaces a implementaciones.

VlogcNNc2d3ddlog2logcN. Todavía tengo que ver una demostración en hardware real en el que la mayor concurrencia justifique las constantes más pobres y la robustez reducida de los métodos aditivos.

O(N/P)

En la práctica, las grillas gruesas alcanzan rápidamente el fuerte límite de escalabilidad (más allá del cual agregar más procesos aumenta el tiempo de ejecución), por lo que deberían residir en comunicadores MPI cada vez más pequeños. Esto agrega cierta complejidad leve a la implementación. Para los problemas en los que los niveles gruesos tienen demasiada estructura para continuar engrosándose, la resolución del nivel grueso puede convertirse en un cuello de botella.

Para probar varios métodos multirredes paralelos, recomiendo usar una biblioteca como PETSc que le permite ejecutar muchos algoritmos diferentes con muy poco código de usuario.

Jed Brown
fuente
El enlace Adams (2001) ya no funciona. Creo que el artículo al que te referías es este: ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1592790&tag=1 . "Algoritmo de Gauss-Seidel no estructurado de memoria distribuida para suavizadores de múltiples cuadrículas" Avíseme si me equivoco.
nukeguy