Ãœber den Einfluss von Kompressionen auf das paralle superkonvergente Multigrid Verfahren

Volker Schmidt, Leibniz Universität Hannover, bachelor thesis
08/2013

Das Multigrid Verfahren ist eines der performantesten Verfahren zum Lösen von Linearen Gleichungssystemen. Insbesondere für physikalische Probleme hat sich das das Multigrid Verfahren bewährt [1].

Für das Multigrid Verfahren existieren einige Parallelisierungsmöglichkeiten. Der Großteil setzt dabei jedoch an den Lösern für die linearen Gleichungssysteme an, die auch Smoother genannt werden. Ein ganz anderen Ansatz verfolgt das PSMG (parallele superkonvergente Multigrid) Verfahren [2]. Das Multigrid Verfahren versucht die Lösung im feinen Grid durch eine grobe Approximation des Fehlers auszugleichen und damit die Konvergenz zu beschleunigen. Für das Erstellen des groben Problems gibt es mehrere Möglichkeiten von denen üblicherweise eine gewählt wird. Im PSMG werden dahingegen alle Möglichkeiten gewählt und all diese werden parallel gelöst. Das PSMG Verfahren besitzt eine deutlich höhere Konvergenzrate als herkömmliche Verfahren jedoch erfordert sie auch einen größeren Kommunikationsoverhead.

Ziel dieser Arbeit soll es sein, den Poisson Solver einer Fluid Simulation, zum Berechnen des Druckausgleiches, mittels PSMG zu realisieren. Dabei soll untersucht werden, ob Kompressionsalgorithmen den Kommunikationsaufwand signifikant zu verringern können.

• [1] Trottenberg, Ulrich, Cornelius W. Oosterlee, and Anton Schuller. Multigrid. Academic press, 2000.
• [2] Frederickson, Paul O., and Oliver A. McBryan. Recent developments for the PSMG multiscale method. No. CU-CS-524-91. COLORADO UNIV AT BOULDER DEPT OF COMPUTER SCIENCE, 1991. 

Kontakt: Maximilian Klein