Comment paralléliser une méthode multigrille pour résoudre un système linéaire d'équations?

Si je comprends bien, la méthode multigrille résout un système linéaire en résolvant une version plus grossière du même problème (en éliminant les erreurs de basse fréquence) puis en se projetant sur la grille fine pour atténuer les erreurs de haute fréquence. Pour les grands systèmes, je peux voir comment une méthode itérative peut être mise en œuvre en parallèle à chaque niveau de grille. Cette approche évolue-t-elle bien en parallèle? Existe-t-il une autre source de concurrence dans l'algorithme que l'on peut exploiter en parallèle?

La multigrille géométrique parallèle est simple à mettre en œuvre sur des grilles structurées. Les multigrilles algébriques et non structurées sont plus techniques, voir cette réponse pour les liens vers les implémentations.

$V$$\log_{c} N$$N$$c$$2^d$$3^d$$d$$\log_2 \log_c N$. Je n'ai pas encore vu de démonstration sur du matériel réel dans lequel l'augmentation de la concurrence justifie les constantes les plus pauvres et la robustesse réduite des méthodes additives.

$\mathcal O (N/P)$

En pratique, les grilles grossières atteignent rapidement la forte limite d'évolutivité (au-delà de laquelle l'ajout de processus augmente la durée d'exécution), elles doivent donc résider sur des communicateurs MPI toujours plus petits. Cela ajoute une légère complexité à la mise en œuvre. Pour les problèmes dans lesquels les niveaux grossiers ont trop de structure pour continuer à grossir, la résolution des niveaux grossiers peut devenir un goulot d'étranglement.

Pour tester différentes méthodes multigrilles parallèles, je recommande d'utiliser une bibliothèque comme PETSc qui vous permet d'exécuter de nombreux algorithmes différents avec très peu de code utilisateur.