A multigrid method for multiprocessors (Q1821522)

Der Autor beschreibt ein modifiziertes Multigrid-Verfahren für lineare partielle Differentialgleichungen. Die Abänderung erlaubt die gleichzeitige Relaxation auf allen Gittern. Der Unterschied zur Standardmethode besteht darin, daß die rechten Seiten der Korrekturgleichungen für alle gröberen Gitter direkt aus den Residuen im feinsten Gitter abgeleitet werden. Außerdem wird aus den durch simultane Relaxation gewonnenen Korrekturen aller gröberen Gitter unmittelbar eine Korrektur für den Lösungsvektor im feinsten Gitter bestimmt. Der Autor zeigt, daß die Konvergenz schwächer ist als beim üblichen Verfahren. Er macht aber plausibel, daß der Verlust nicht zu groß ist. Unter anderem erwähnt er, daß die Anzahl der Zyklen weiterhin unabhängig von der Gitterweite ist. Es werden zwei Möglichkeiten zur Implementierung auf Parallelrechnern vorgestellt. In beiden Fällen wird ein globaler Speicher wegen der notwendigen Berechnung globaler Größen - anders als bei der Standardmethode - vorausgesetzt. Sicher läßt sich der Algorithmus aber auch auf Systeme mit verteilten Speichern abbilden, wenn auch mit Effizienzverlusten. Weiterhin sind beide Versionen in der angegebenen Form nicht für massiv parallele Systeme geeignet. Dies läßt sich allerdings durch die übliche Aufteilung der Gitter auf mehrere Prozessoren erreichen. Die als vollparallelisiert bezeichnete Implementierung ist wegen der notwendigen Synchronisationen nicht empfehlenswert. Dies zeigt sich bei den angegebenen Ergebnissen auf der CRAY XMP. Die zweite sogenannte teilweise parallelisierte Version ist deutlich besser. Auf der CRAY XMP- 48 wurde im günstigsten Fall ein Speedup von 2.9 gemessen. Der verbleibende Effizienzverlust liegt zu einem großen Teil in dem hohen Preis, den das benutzte Multitasking der CRAY XMP dem Benutzer abverlangt. Bei der Verwendung einfacher Synchronisationsmechanismen, die der Autor erwähnt, dürften die Ergebnisse deutlich besser werden.