Scientific Computing

Abschlussarbeiten

Studentinnen und Studenten der Bachelor- und Master-Studiengänge Mathematik und Informatik, die ihre Abschlussarbeit in dem Themengebiet der Arbeitsgruppe schreiben möchten, sind uns herzlich willkommen. Während der Bearbeitung des Themas werden sie durch eine Mitarbeiterin oder einen Mitarbeiter betreut, Gespräche mit dem Arbeitsgruppenleiter können in der regelmäßig stattfindenden Sprechstunde stattfinden oder zu einem kurzfristig vereinbarten individuellen Termin. Beispiele für erfolgreich abgeschlossene Arbeiten finden sich in der Liste der Absolventinnen und Absolventen. Die Arbeiten müssen nach den Regeln guter wissenschaftlicher Praxis der Deutschen Forschungsgemeinschaft angefertigt werden.

Es folgen einige beispielhafte Themenvorschläge für

Auf Wunsch können auch gerne mit dem Arbeitsgruppenleiter individuelle Themen verabredet werden.

Bachelorarbeit Informatik

Approximation von Gravitationsfeldern auf einem verteilten Rechnersystem

Bei der Simulation der Gravitationskräfte innerhalb einer Galaxie müssen Wechselwirkungen zwischen Millionen von Sternen berechnet werden. Eine direkte Auswertung würde dabei zu einem Rechenaufwand führen, der die Kapazität auch der modernsten Großrechnersysteme sprengt. Deshalb kommen Approximationen zum Einsatz: Sterne werden hierarchisch zu Clustern zusammengefasst, die sich durch wenige Stellvertreter repräsentieren lassen. Mit diesem Ansatz lässt sich der Rechenaufwand erheblich reduzieren, bleibt aber immer noch zu hoch für einzelne Rechner.

Im Rahmen dieser Arbeit soll der Algorithmus deshalb auf ein verteiltes Rechnersystem übertragen werden. Dabei steht vor allem die Organisation des Datenaustauschs zwischen den beteiligten Rechnerknoten im Mittelpunkt, die mit Hilfe des Standards MPI realisiert werden soll.

Visualisierung der Wellengleichung

Die Simulation der Wellengleichung führt zunächst zu einer großen Anzahl von Zahlen, die die Positionen der einzelnen Gitterpunkte, deren Geschwindigkeiten und die auf sie wirkenden Kräfte beschreiben. Um diese Zahlen praktisch nutzbar zu machen, müssen sie geeignet visualisiert werden.

Im Rahmen dieser Arbeit soll auf Grundlage des Standards OpenGL ein Programm entwickelt werden, das die Simulationsergebnisse der Wellengleichung darstellt. Das Programm soll den aktuellen Standard verwenden, also nicht "Legacy OpenGL", so dass beispielsweise Vertex- und Fragment-Shader in der OpenGL Shading Language geschrieben werden müssen.

Paralleles Lösen von Tridiagonalsystemen

Bei der Simulation eindimensionaler Phänomene, beispielsweise bei der Berechnung der Grundschwingungen einer Gitarrensaite, treten häufig Tridiagonalmatrizen auf, also Matrizen, bei denen nur die Diagonale und die untere und obere Nebendiagonale von null verschiedene Koeffizienten aufweisen. Die Idee der "cyclic reduction" besteht darin, diese Matrizen so umzusortieren, dass nur noch eine Diagonalmatrix und eine neue Tridiagonalmatrix halber Größe übrig bleiben.

Im Rahmen dieser Arbeit soll untersucht werden, inwiefern sich dieser Algorithmus parallelisieren lässt. Dabei sollten im Idealfall sowohl Vektorisierung (SSE, AVX) und Multithreading (OpenMP) zum Einsatz kommen, um die Rechenleistung moderner Prozessoren möglichst gut auszunutzen.

Task-basierte Parallelisierung

Ein eleganter Ansatz für die Parallelisierung größerer Rechenoperationen auf einem Shared-Memory-System beruht auf der Idee, die zu lösende Aufgabe in einzelne Teilaufgaben ("tasks") zu zerlegen und die Abhängigkeiten zwischen diesen Teilaufgaben zu analysieren, um möglichst viele von ihnen parallel ausführen zu können.

Im Rahmen dieser Arbeit soll ein Scheduler entwickelt werden, der Teilaufgaben unter Berücksichtigung ihrer Abhängigkeiten auf mehrere parallel laufende Threads verteilt. Als Anwendungsbeispiel kann die Berechnung der LR-Zerlegung einer Matrix dienen.

Integration einer Skriptsprache in ein wissenschaftliches Softwarepaket

Der Einsatz der in unserer Arbeitsgruppe entwickelten Open-Source-Programmbibliothek H2Lib erfordert derzeit Programmierkenntnisse in der Sprache C, die nicht unbedingt bei jedem potentiellen Anwender vorausgesetzt werden können. Die Einbindung einer Skriptsprache würde die Möglichkeit bieten, auch ohne Programmierkenntnisse immerhin einfachere Aufgaben mit der Bibliothek zu lösen.

Im Rahmen dieser Arbeit soll die Open-Source-Skriptsprache LUA in die Bibliothek H2Lib eingebunden werden. Dabei sollen die wichtigsten Variablentypen und Operationen der Bibliothek in der Skriptsprache zugänglich gemacht werden, so dass sich zumindest einfache Anwendungen wie das Aufstellen und Lösen eines Gleichungssystems auch ohne C-Kenntnisse umsetzen lassen.

Entwicklung von Schnittstellen für die Bibliothek H2Lib

Die in unserer Arbeitsgruppe entwickelte Programmbibliothek H2Lib ist aus Gründen der Portabilität und Effizienz in der Sprache C implementiert. Dadurch wird ihre Schnittstelle etwas unhandlich, beispielsweise existieren viele Funktionen, die im Prinzip dieselben Operationen für Matrizen in unterschiedlichen Darstellungen ausführen.

Im Rahmen dieser Arbeit sollen Schnittstellen in moderneren Programmiersprachen wie C++ oder Python entwickelt werden, die die Funktionen des H2Lib-Pakets in möglichst eleganter Form verfügbar machen, beispielsweise mit Hilfe überladener Funktionen oder objektorientierter Konzepte.

Bachelorarbeit Mathematik

Padé-Approximation

Die Auswertung glatter Funktionen in einem Rechner erfolgt häufig mit Hilfe der Interpolation: Die Funktion wird durch ein Polynom approximiert, das sich einfach und effizient auswerten lässt. Bei Funktionen mit Polstellen, beispielsweise dem Logarithmus oder dem Tangens, ist dieser Ansatz weniger attraktiv, da ein sehr hoher Polynomgrad erforderlich wird, um eine akzeptable Genauigkeit zu erreichen. In diesen Situationen kann die Padé-Approximation von Interesse sein, die eine gegebene Funktion durch den Quotienten zweier Polynome annähert. Polstellen der Funktion lassen sich dann durch Nullstellen des Nennerpolynoms wiedergeben.

Im Rahmen dieser Arbeit soll die grundlegende Theorie der Padé-Approximation kompakt dargestellt werden, also beispielsweise Fehlerabschätzungen und Algorithmen für die Konstruktion einer Approximation.

MinRes-Verfahren

Das Lösen eines linearen Gleichungssystems Ax=b mit einer symmetrischen Matrix A lässt sich als Minimierung der Funktion f(x)=|Ax-b|² auffassen. Diese Minimierung kann mit Hilfe eines Iterationsverfahrens erfolgen, das eine Folge von Näherungslösungen konstruiert. Wenn man die Symmetrie der Matrix A ausnutzt und geeignete Hilfsvektoren einsetzt, lässt sich ein Schritt der Iteration effizient durchführen. Das resultierende Verfahren trägt den Namen MinRes (für "Minimierung des Residuums").

Im Rahmen dieser Arbeit sollen das MinRes-Verfahren hergeleitet und grundlegende Aussagen zu seiner Konvergenz bewiesen werden.

Extrapolationsverfahren für gewöhnliche Differentialgleichungen

Bei der Behandlung gewöhnlicher Differentialgleichungen können Extrapolationstechniken eingesetzt werden, um die mit einem einfachen Verfahren berechneten Näherungslösungen erheblich zu verbessern. Mit diesem Ansatz lassen sich theoretisch beliebig hohe Konsistenzordnungen mit relativ geringem Implementationsaufwand erreichen.

Im Rahmen dieser Arbeit soll die Theorie der Extrapolationsverfahren für gewöhnliche Differentialgleichungen dargestellt werden. Ein zentrales Resultat ist dabei der Nachweis des Existenz einer asymptotischen Entwicklung der Lösung der Gleichung in Abhängigkeit von der Schrittweite. Als Beispiel kann die Simulation eines Räuber-Beute-Modells durch die Lotka-Volterra-Gleichung dienen.

Schnelle Auswertung der Gravitationskräfte in einem Vielkörpersystem

Bei der Simulation von Vielkörpersystemen, beispielsweise von Galaxien oder komplizierten Molekülen, stellt die schnelle Auswertung der nicht-lokalen Wechselwirkungen zwischen den beteiligten Körpern eine Herausforderung dar, denn ein naiver Ansatz würde bei n Körpern mindestens Rechenoperationen erfordern. Die Auswertung lässt sich erheblich beschleunigen, indem man Wechselwirkungen zwischen weit voneinander entfernten Clustern von Körpern durch Einführung virtueller Körper approximiert. Für die Auswertung der approximierten Kräfte genügen dann O(n log n) Operationen, so dass auch sehr große Systeme effizient behandelt werden können.

Im Rahmen dieser Arbeit soll ein Algorithmus entwickelt werden, der die in einem Vielkörpersystem wirkenden Kräfte effizient approximiert. Dabei wird das Gravitationsgesetz durch Interpolation angenähert, so dass ein Verfahren entsteht, dessen Genauigkeit sich einfach über die Interpolationsordnung steuern lässt.

Masterarbeit Informatik

Simulation eines Vielkörpersystems auf einem verteilten Rechner

Für die Simulation des Verhaltens eines Galaxie müssen die gravitationellen Wechselwirkungen zwischen sämtlichen in ihm enthaltenen Sonnen berechnet werden. Der dabei auftretende Rechenaufwand lässt sich für n Sonnen mit Hilfe geeigneter Approximationstechniken auf O(n) reduzieren. Ein einzelner Prozessor wird in der Regel immer noch zu lange für die Durchführung der Berechnung benötigen, so dass sich die Frage stellt, ob sich die Arbeit auf mehrere Prozessoren verteilen lässt.

Im Rahmen dieser Arbeit soll ein Programm entwickelt werden, das den bei der Approximation der Gravitationskräfte auftretenden Rechenaufwand auf mehrere Knoten eines Cluster-Systems verteilt. Grundlage der Implementierung soll dabei der Standard MPI sein, der Funktionen für die Synchronisation und den Datenaustausch zwischen den einzelnen Knoten definiert. Die für die Approximation erforderlichen Funktionen stellt die in der Arbeitsgruppe entwickelte Programmbibliothek H2Lib zur Verfügung. Für Testläufe können ein (sehr) kleiner Cluster der Arbeitsgruppe und der rzcluster des Rechenzentrums genutzt werden.

Finite-Elemente-Simulation auf einer Grafikkarte

Finite-Elemente-Berechnungen spielen beispielsweise bei der Untersuchung strukturmechanischer Phänomene eine Rolle, etwa bei der Simulation der Statik eines Gebäudes oder der Deformation einer Karosserie bei einem virtuellen Crashtest. Sie beruhen auf der Idee, den zu simulierenden Körper in eine Anzahl einfacher Stücke, die finiten Elemente, zu zerlegen und eine mathematische Beschreibung des komplexen Gesamtsystems aus einfachen Gleichungen für die einzelnen finiten Elemente zusammenzusetzen. Bei einer typischen Implementierung wird das Gesamtsystem vollständig aufgestellt und im Speicher gehalten, so dass sehr viel Speicher benötigt wird, auf dem nur relativ wenige Rechenoperationen durchgeführt werden. Damit sind derartige Implementierungen schlecht für den Einsatz auf Grafikkarten geeignet, bei denen relativ wenig und vergleichsweise langsamer Speicher einer sehr hohen Rechenleistung gegenüber steht.

Im Rahmen dieser Arbeit soll ein alternativer Ansatz erprobt werden, bei dem das System nie vollständig aufgestellt wird. Stattdessen wird direkt mit den finiten Elementen gearbeitet, die zwar einen höheren Rechenaufwand erfordern, aber eine geringere Speicherbandbreite. Das Ziel ist es, eine Implementierung auf einer Grafikkarte zu entwickeln, die deren hohe Rechenleistung möglichst gut nutzt.

Masterarbeit Mathematik

Simulation der elastischen Deformation eines Festkörpers

Ein klassisches Anwendungsgebiet numerischer Simulationsverfahren ist die Festkörpermechanik, insbesondere die Behandlung elastischer Deformationen. Ausgehend von einer Referenzkonfiguration des Festkörpers werden dabei die Verschiebungen berechnet, mit denen er auf externe Kräfte reagiert. Mathematisch lässt sich das System durch eine Minimierungsaufgabe beschreiben: Der Körper versucht, die wirkenden Spannungen möglichst gering zu halten.

Im Rahmen dieser Arbeit sollen aus physikalischen Grundannahmen die Differentialgleichungen der klassischen Elastizitätstheorie hergeleitet werden. In linearisierter Form, beispielsweise in Gestalt der Lamé-Gleichung, können diese Gleichungen dann mit numerischen Standard-Verfahren behandelt werden, um zu einer Simulation eines Festkörpers auf Grundlage der in der Arbeitsgruppe entwickelten Programmbibliothek SimpleFEM zu gelangen.

Effiziente Verfahren für Streuprobleme

In vielen Anwendungen (Radar, Sonar, WLAN-Ausleuchtung) ist man daran interessiert, zu berechnen, wie Wellen an Hindernissen gestreut werden. Mathematisch lässt sich diese Fragestellung als eine Helmholtz-Gleichung formulieren, die eintreffende und reflektierte Wellen zueinander in Beziehung setzt. Sie lässt sich in eine Randintegralformulierung überführen, bei der lediglich auf den reflektierenden Oberflächen gerechnet werden muss, nicht im gesamten Volumen. Um die Randintegralgleichung effizient lösen zu können, muss die ihr zugrunde liegende Kernfunktion approximiert werden.

Im Rahmen dieser Arbeit soll eine moderne Approximationstechnik für die Kernfunktion der Helmholtz-Gleichung untersucht werden. Sie beruht auf der Idee, die Kernfunktion als Produkt einer glatten Kernfunktion und einer ebenen Welle darzustellen. Die glatte Kernfunktion lässt sich gut approximieren, beispielsweise durch Taylor-Entwicklung oder Interpolation. Die ebene Welle kann direkt ausgewertet werden. Das Ziel der Arbeit wäre es, Fehlerabschätzungen für die so konstruierte Approximation herzuleiten und ihre Genauigkeit in praktischen Experimenten auf Grundlage der in der Arbeitsgruppe entwickelten Programmbibliothek H2Lib zu erforschen.