Wie kann man eine Multigrid-Methode zur Lösung eines linearen Gleichungssystems parallelisieren?

So wie ich es verstehe, löst die Multigrid-Methode ein lineares System, indem sie eine gröbere Version desselben Problems löst (dort durch Eliminieren von Niederfrequenzfehlern) und dann zurück zum feinen Gitter projiziert, um die Hochfrequenzfehler zu glätten. Bei großen Systemen kann ich sehen, wie eine iterative Methode auf jeder Gitterebene parallel implementiert werden kann. Skaliert dieser Ansatz gut parallel? Gibt es eine andere Quelle der Parallelität im Algorithmus, die parallel genutzt werden kann?

Parallele geometrische Multigrids lassen sich problemlos auf strukturierten Gittern implementieren. Algebraisches und unstrukturiertes Multigrid sind technischer. In dieser Antwort finden Sie Links zu Implementierungen.

$V$$\log_{c} N$$N$$c$$2^d$$3^d$$d$$\log_2 \log_c N$. Ich habe noch keine Demonstration auf realer Hardware gesehen, bei der die erhöhte Parallelität die schlechteren Konstanten und die verringerte Robustheit additiver Methoden rechtfertigt.

$\mathcal O (N/P)$

In der Praxis erreichen grobe Gitter schnell die starke Skalierbarkeitsgrenze (ab der das Hinzufügen weiterer Prozesse die Laufzeit erhöht), sodass sie sich auf immer kleineren MPI-Kommunikatoren befinden sollten. Dies fügt der Implementierung eine leichte Komplexität hinzu. Bei Problemen, bei denen die Grobebenen zu strukturiert sind, um weiter zu vergröbern, kann die Lösung der Grobebenen zu einem Engpass werden.

Zum Testen verschiedener paralleler Multigrid-Methoden empfehle ich die Verwendung einer Bibliothek wie PETSc, mit der Sie viele verschiedene Algorithmen mit sehr wenig Benutzercode ausführen können.