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.

Im Folgenden finden sich einige Themenvorschläge für den Bachelorstudiengang Mathematik, den Masterstudiengang Mathematik, und den Bachelorstudiengang Informatik. Selbstverständlich können auch individuelle Themen vereinbart werden, die auf einer vertiefenden Vorlesung (z.B. "Iterative Verfahren für große Gleichungssysteme", "Numerical methods for partial differential equations", "Numerik nicht-lokaler Operatoren" oder "Numerik von Eigenwertproblemen") aufbauen.

 

Bachelorarbeit Mathematik

Padé-Approximation

Aus der Numerik-Grundvorlesung ist die Polynominterpolation bekannt, mit der sich beliebige hinreichend oft differenzierbare Funktionen approximieren lassen. Für Funktionen mit Singularitäten kann die Padé-Approximation von Interesse sein, bei der man statt eines Polynoms den Quotienten zweier Polynome verwendet. Im Rahmen einer Bachelorarbeit könnte man die Konstruktion solcher Approximationen und ihre Genauigkeit analysieren.

Block-Iterationsverfahren

In der Vorlesung "Iterative Verfahren für große Gleichungssysteme" werden Iterationsverfahren wie die Jacobi- oder die Gauß-Seidel-Iteration vorgestellt. Diese Verfahren können als Folge von Lösungsschritten für eindimensionale Gleichungssysteme interpretiert werden, beispielsweise bestimmt die Gauß-Seidel-Iteration der Reihe nach neue xi so, dass die i-te Zeile des Gleichungssystems gilt. Es liegt nahe, statt einzelner Unbekannter ganze Blöcke von Unbekannten zu behandeln, beispielsweise Zeilen oder Spalten eines Finite-Differenzen-Gitters. Unter gewissen Bedingungen kann diese Vorgehensweise erhebliche Vorteile bieten. Im Rahmen einer auf der Vorlesung aufbauenden Bachelorarbeit könnten Modellbeispiele analysiert werden, beispielsweise per Fourier-Analyse, um klassische Verfahren und ihre Blockvarianten zu vergleichen.

Nédélec-Basisfunktionen

In der Vorlesung "Numerical methods for partial differential equations" werden unter anderem auch Finite-Elemente-Verfahren analysiert. Manche partiellen Differentialgleichungen besitzen Eigenschaften, die sich ausnutzen lassen, wenn man geeignete Ansatzräume wählt. Ein Beispiel sind die Maxwell-Gleichungen der Elektrodynamik, bei denen elektrischen und magnetischen Potentialen eine besondere Rolle zukommt. Falls man die Maxwell-Gleichungen mit Hilfe der Nédélec-Basisfunktionen diskretisiert, lassen sich diese Potentiale besonders elegant berechnen. Im Rahmen einer auf der Vorlesung aufbauenden Bachelorarbeit könnte die Approximationseigenschaften der Nédélec-Basisfunktionen analysiert werden.

Jacobi-Iteration für Eigenwertprobleme

In der Vorlesung "Numerik von Eigenwertproblemen" wird bewiesen, dass die Jacobi-Iteration linear konvergiert, dass also in jedem Schritt der Fehler um einen Faktor reduziert wird. Mit etwas mehr Aufwand lässt sich zeigen, dass das Verfahren tatsächlich quadratisch konvergiert, falls die behandelte Matrix bereits "hinreichend nahe" an einer Diagonalmatrix liegt. Im Rahmen einer auf dieser Vorlesung aufbauenden Bachelorarbeit könnten diese stärkeren Konvergenzaussagen anhand geeigneter Literaturvorlagen bewiesen werden.

Approximation variabler Ordnung

In der Vorlesung "Numerik nicht-lokaler Operatoren" wird die Komplexität der H²-Matrix-Approximation eines einfachen eindimensionalen Modellproblems analysiert, das mittels Interpolation approximiert wird. Man kann beweisen, dass sich die Effizienz erheblich verbessern lässt, indem man die Interpolationsordnung abhängig von der Clustergröße wählt: Je größer der Cluster, desto höher die Ordnung. Im Rahmen einer auf dieser Vorlesung aufbauenden Bachelorarbeit könnte analysiert werden, wie sich der Speicherbedarf und die Komplexität bestimmter Algorithmen verändern, wenn mit variabler statt konstanter Ordnung gearbeitet wird.

H²-Arithmetik mit bekannten Clusterbasen

In der Vorlesung "Numerik nicht-lokaler Operatoren" wird die H-Matrix-Arithmetik eingehend behandelt, das Rechnen mit H²-Matrizen hingegen kommt nur am Rande vor, da die korrespondierenden Algorithmen erheblich komplexer sind. In einem Sonderfall ist die H²-Arithmetik allerdings recht einfach: Falls die Clusterbasen bereits bekannt sind, lässt sich ein Algorithmus optimaler Komplexität angeben, der die bestmögliche Approximation des Produkts zweier Matrizen bezüglich dieser Basen bestimmt. Im Rahmen einer auf dieser Vorlesung aufbauenden Bachelorarbeit könnte dieser Algorithmus implementiert und analysiert werden.

 

Masterarbeit Mathematik

Mehrgitter-Vorkonditionierer bei springenden Koeffizienten

In der Vorlesung "Iterative Verfahren für große Gleichungssysteme" wird das Mehrgitterverfahren als eigenständiges Lösungsverfahren behandelt. Man kann es aber auch als Vorkonditionierer verwenden, beispielsweise für das Verfahren der konjugierten Gradienten. Beispielsweise bei Differentialgleichung mit springenden Koeffizienten kann dieser Zugang erhebliche Vorteile bieten, weil sich beweisen lässt, dass die Sprünge zu einzelnen "Ausreißern" im Spektrum der vorkonditionierten Matrix führen und dass das Krylow-Verfahren in diesen Situationen schnell konvergiert, während das "reine" Mehrgitterverfahren sehr an Geschwindigkeit verliert.
Eine Masterarbeit zu diesem Thema könnte auf dem Forschungsartikel "Uniform convergent multigrid methods for elliptic problems with strongly discontinuous coefficients" von J. Xu und Y. Zhu aufbauen.

Eigenwert-Mehrgitterverfahren

In der Vorlesung "Iterative Verfahren für große Gleichungssysteme" wird das Mehrgitterverfahren für lineare Gleichungssysteme eingeführt. Man kann allerdings auch Mehrgitterverfahren für Eigenwertprobleme konstruieren: Mit Hilfe des Rayleigh-Quotienten können wir uns eine Näherung des Eigenwerts beschaffen, den Fehler ähnlich wie im linearen Fall glätten, und anschließend eine Grobgitterkorrektur einsetzen, um glatte Fehleranteile zu reduzieren. Dabei tritt die Komplikation auf, dass die Grobgitterprobleme singulär sind, schließlich liegt ein vollständiger Eigenraum im Kern der auftretenden Matrix. Dieses Problem lässt sich allerdings mit Hilfe geeigneter Projektionen in den Griff bekommen, so dass man ein sehr elegantes und schnelles Lösungsverfahren erhält.
Eine Masterarbeit zu diesem Thema könnte auf dem Forschungsartikel "On the computation of approximate eigenvalues and eigenfunctions of elliptic operators by means of a multi-grid method" von W. Hackbusch aufbauend einen Konvergenzbeweis führen.

Interpolation variabler Ordnung für Ableitungen

In der Vorlesung "Numerik nicht-lokaler Operatoren" werden H²-Matrix-Approximationen von Integraloperatoren konstruiert, indem die korrespondierende Kernfunktion durch ein Interpolationspolynom angenähert wird. Gelegentlich benötigen wir auch die Ableitungen dieser Kernfunktion, die sich einfach approximieren lassen, indem wir das Interpolationspolynom ableiten. Falls man die Effizienz der Approximation steigert, indem man die Interpolationsordnung abhängig von der Größe der Cluster wählt, entsteht das Problem, dass das Interpolationspolynom durch Hintereinanderausführung mehrerer Interpolationsoperatoren konstruiert wird, so dass die Fehleranalyse erheblich anspruchsvoller wird.
Eine Masterarbeit zu diesem Thema könnte auf dem Forschungsartikel "Approximation of integral operators by variable-order interpolation" von S. Börm, M. Löhndorf und J.M. Melenk aufbauend mit Hilfe funktionentheoretischer Techniken, insbesondere der Bernstein-Ellipsen, Fehlerabschätzungen für die Ableitungen beweisen.

Richtungsabhängige Interpolation für Ableitungen

In der Vorlesung "Numerik nicht-lokaler Operatoren" werden H²-Matrix-Approximation per Interpolation einer lokal glatten Kernfunktion konstruiert. Falls man diesen Ansatz auf hochfrequente Probleme anwenden möchte, steht man vor dem Problem, dass die Kernfunktion stark oszilliert, also keineswegs glatt ist. Ein Lösungsansatz besteht darin, die Kernfunktion in eine glatte Funktion und eine in eine gewisse Richtung laufende ebene Welle zu zerlegen und nur die glatte Funktion zu interpolieren.
Eine Masterarbeit zu diesem Thema könnte auf dem Forschungsartikel "Approximation of the high-frequency Helmholtz kernel by nested directional interpolation" von S. Börm und J.M. Melenk aufbauend mit Hilfe funktionentheoretischer Techniken, insbesondere holomorpher Fortsetzungen der Kernfunktion auf Bernstein-Ellipsen, Fehlerabschätzungen für die iterierte Interpolation und die Approximation von Ableitungen beweisen.

H²-Rekompression mit komprimierten Gewichten

In der Vorlesung "Numerik nicht-lokaler Operatoren" wird diskutiert, wie H²-Matrizen rekomprimiert, also mit effizienteren Basen ausgestattet, werden können. Dabei kommen Gewichtsmatrizen zum Einsatz, die die relative "Wichtigkeit" der ursprünglichen Basisvektoren ausdrücken, und diese Gewichtsmatrizen können bei hohen Genauigkeitsanforderungen mehr Speicher als die rekomprimierte H²-Matrix benötigen. Deshalb ist es von Interesse, die Gewichtsmatrizen zu approximieren, um ihren Speicherbedarf zu reduzieren.
Eine Masterarbeit zu diesem Thema könnte auf dem Forschungsartikel "Approximation of integral operators by H²-matrices with adaptive bases" von S. Börm aufbauend den Einfluss einer Approximation auf Rechenaufwand und Genauigkeit der resultierenden H²-Matrix untersuchen.

H²-Matrizen mit überlappenden Clustern

In der Vorlesung "Numerik nicht-lokaler Operatoren" wurden Clusterbäume eingeführt, mit deren Hilfe sich eine Matrix in Teilmatrizen zerlegen lässt, aus deren Approximation dann H- oder H²-Matrizen entstehen. Im Kontext partieller Differentialgleichungen ist eine Zerlegung in disjunkte Teilmatrizen problematisch, da nicht differenzierbar. Ein Ausweg besteht darin, überlappende Cluster in Kombination mit geeigneten Abschneidefunktionen zu verwenden. Dafür muss einerseits der Begriff des Clusterbaums erheblich verallgemeinert werden, andererseits müssen auch Algorithmen wie die H²-Kompression modifiziert werden.
Eine Masterarbeit zu diesem Thema könnte auf der ersten Hälfte des Forschungsartikels "BEM with linear complexity for the classical boundary integral operators" von S. Börm und S. Sauter aufbauend beispielsweise den H²-Kompressionsalgorithmus für überlappende Cluster verallgemeinern.

 

Bachelorarbeit Informatik

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.

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.

Verteilte Simulation der Wellengleichung

Das Leapfrog-Verfahren für die Simulation der Ausbreitung von Wellen wird beispielsweise in der Vorlesung "Numerische Programmierung" behandelt. Bei dreidimensionalen Berechnungen treten allerdings sehr viele Unbekannte auf, so dass unter Umständen ein einziger Computer nicht ausreichend viel Speicherplatz bietet. In diesem Fall kann es sinnvoll sein, die Berechnung auf mehrere Computer zu verteilen.

Im Rahmen dieser Arbeit soll die Simulation der dreidimensionalen Wellengleichung auf mehrere Computer verteilt werden, die mittels des MPI-Standards Daten austauschen. Nachdem eine einfache Version des Algorithmus implementiert wurde, können Verfeinerungen in Angriff genommen werden, beispielsweise die Bündelung mehrere Zeitschritte oder der Einsatz kollektiver Kommunikationsoperationen.