Diese Arbeit behandelt die effiziente Vorkonditionierung von Finite-Elemente-Matrizen unter Verwendung hierarchischer Matrizen.

Hierarchical matrix (H-matrix) techniques can be used to efficiently treat dense matrices. With an H-matrix, the storage requirements and performing all fundamental operations, namely matrix-vector multiplication, matrix-matrix multiplication and matrix inversion can be done in almost linear complexity. In this work, we tried to gain even further speedup for the H-matrix arithmetic by utilizing multiple processors. Our approach towards an H-matrix distribution relies on the splitting of the index set. The main results achieved in this work based on the index-wise H-distribution are: A highly scalable algorithm for the H-matrix truncation and matrix-vector multiplication, a scalable algorithm for the H-matrix matrix multiplication, a limited scalable algorithm for the H-matrix inversion for a large number of processors.

In dieser Arbeit entwickeln wir einen Löser für elliptische Randwertprobleme. Dazu diskretisieren wir ein Randwertproblem mittels der Methode der finiten Elemente und erhalten ein Gleichungssystem. Mittels Gebietszerlegungstechniken unterteilen wir das Gebiet der Differentialgleichung und können Teilprobleme des Randwertproblems definieren. Durch die Gebietszerlegung wird eine Hierarchie von Zerlegungen definiert, die wir mittels eines Gebietszerlegungsbaumes festhalten. Anhand dieses Baumes definieren wir nun einen Löser für das Randwertproblem. Dabei berechnen wir die verschiedenen Matrizen des Lösers durch den sogenannten HDD-Algorithmus (engl. hierarchical domain decomposition). Die meisten der zu erstellenden Matrizen sind dabei vollbesetzt, weshalb wir sie mittels Hierarchischer Matrizen approximieren. Mit Hilfe der Hierarchischen Matrizen können wir die Matrizen mit einem fast linearen Aufwand erstellen und speichern. Der Aufwand der Matrixoperationen ist ebenfalls fast linear. Damit wir die Hierarchischen Matrizen für den HDD-Algorithmus verwenden können, müssen wir die Technik der Hierarchischen Matrizen erweitern. Unter anderem führen wir eingeschränkte Clusterbäume, eingeschränkte Blockclusterbäume und die verallgemeinerte Addition für Hierarchische Matrizen ein. Zusätzlich führen wir eine neue Clusterbaum-Konstruktion ein, die auf den HDD-Algorithmus zugeschnitten ist. Die Kombination des HDD-Algorithmus mit Hierarchischen Matrizen liefert einen Löser, den wir mit einem fast linearen Aufwand berechnen können. Der Aufwand zur Berechnung einer Lösung sowie der Speicheraufwand ist ebenfalls fast linear. Des Weiteren geben wir noch einige Modifizierungen des HDD-Algorithmus für weitere Anwendungsmöglichkeiten an. Zusätzlich diskutieren wir die Möglichkeiten der Parallelisierung, denn durch die Verwendung der Gebietszerlegung wird das Randwertproblem in unabhängige Teilprobleme aufgeteilt, die sich sehr gut parallelisieren lassen. Wir schließen die Arbeit mit numerischen Tests ab, die die theoretischen Aussagen bestätigen.

Viele physikalische Probleme führen zu Randwertproblemen. Dabei gilt es die Lösung einer Dfferentialgleichung zu finden, so dass auf dem Rand vorgegebene Funktionswerte, die so genannten Randbedingungen, angenommen werden. Differentialgleichungen können nur in wenigen Spezialfällen analytisch gelöst werden. Man muss also auf numerische Verfahren zurückgreifen. Ein Problem aus der Praxis ist in der Regel von zu hoher Komplexität. Wir können daher nicht davon ausgehen ein Black-Box-Verfahren zu finden, welches jede Dfferentialgleichung innerhalb akzeptabler Zeit löst. Deshalb brauchen wir auf die Problemklassen zugeschnittene Verfahren, welche ihre speziellen Eigenschaften ausnutzen. Wir beschränken uns hier auf elliptische Randwertprobleme. Sie werden zu Integralgleichungen umformuliert, mittels Randelementmethode diskretisiert und damit in ein lineares Gleichungssystem überführt. Zur Behandlung des Gleichungssystems bedienen wir uns Hierarchischer Matrizen. Obwohl diese bereits effektive Hilfsmittel darstellen, wollen wir versuchen ihre Effzienz durch Verwendung gemeinsamer Basen weiter zu steigern. I

Diese Arbeit behandelt die effiziente Vorkonditionierung von Finite-Elemente-Matrizen unter Verwendung hierarchischer Matrizen.

In dieser Arbeit entwickeln wir einen Löser für elliptische Randwertprobleme. Dazu diskretisieren wir ein Randwertproblem mittels der Methode der finiten Elemente und erhalten ein Gleichungssystem. Mittels Gebietszerlegungstechniken unterteilen wir das Gebiet der Differentialgleichung und können Teilprobleme des Randwertproblems definieren. Durch die Gebietszerlegung wird eine Hierarchie von Zerlegungen definiert, die wir mittels eines Gebietszerlegungsbaumes festhalten. Anhand dieses Baumes definieren wir nun einen Löser für das Randwertproblem. Dabei berechnen wir die verschiedenen Matrizen des Lösers durch den sogenannten HDD-Algorithmus (engl. hierarchical domain decomposition). Die meisten der zu erstellenden Matrizen sind dabei vollbesetzt, weshalb wir sie mittels Hierarchischer Matrizen approximieren. Mit Hilfe der Hierarchischen Matrizen können wir die Matrizen mit einem fast linearen Aufwand erstellen und speichern. Der Aufwand der Matrixoperationen ist ebenfalls fast linear. Damit wir die Hierarchischen Matrizen für den HDD-Algorithmus verwenden können, müssen wir die Technik der Hierarchischen Matrizen erweitern. Unter anderem führen wir eingeschränkte Clusterbäume, eingeschränkte Blockclusterbäume und die verallgemeinerte Addition für Hierarchische Matrizen ein. Zusätzlich führen wir eine neue Clusterbaum-Konstruktion ein, die auf den HDD-Algorithmus zugeschnitten ist. Die Kombination des HDD-Algorithmus mit Hierarchischen Matrizen liefert einen Löser, den wir mit einem fast linearen Aufwand berechnen können. Der Aufwand zur Berechnung einer Lösung sowie der Speicheraufwand ist ebenfalls fast linear. Des Weiteren geben wir noch einige Modifizierungen des HDD-Algorithmus für weitere Anwendungsmöglichkeiten an. Zusätzlich diskutieren wir die Möglichkeiten der Parallelisierung, denn durch die Verwendung der Gebietszerlegung wird das Randwertproblem in unabhängige Teilprobleme aufgeteilt, die sich sehr gut parallelisieren lassen. Wir schließen die Arbeit mit numerischen Tests ab, die die theoretischen Aussagen bestätigen.

Hierarchical matrix (H-matrix) techniques can be used to efficiently treat dense matrices. With an H-matrix, the storage requirements and performing all fundamental operations, namely matrix-vector multiplication, matrix-matrix multiplication and matrix inversion can be done in almost linear complexity. In this work, we tried to gain even further speedup for the H-matrix arithmetic by utilizing multiple processors. Our approach towards an H-matrix distribution relies on the splitting of the index set. The main results achieved in this work based on the index-wise H-distribution are: A highly scalable algorithm for the H-matrix truncation and matrix-vector multiplication, a scalable algorithm for the H-matrix matrix multiplication, a limited scalable algorithm for the H-matrix inversion for a large number of processors.

This work addresses the question of the efficient numerical solution of time-domain boundary integral equations with retarded potentials arising in the problems of acoustic and electromagnetic scattering. The convolutional form of the time-domain boundary operators allows to discretize them with the help of Runge-Kutta convolution quadrature. This method combines Laplace-transform and time-stepping approaches and requires the explicit form of the fundamental solution only in the Laplace domain to be known. Recent numerical and analytical studies revealed excellent properties of Runge-Kutta convolution quadrature, e.g. high convergence order, stability, low dissipation and dispersion. As a model problem, we consider the wave scattering in three dimensions. The convolution quadrature discretization of the indirect formulation for the three-dimensional wave equation leads to the lower triangular Toeplitz system of equations. Each entry of this system is a boundary integral operator with a kernel defined by convolution quadrature. In this work we develop an efficient method of almost linear complexity for the solution of this system based on the existing recursive algorithm. The latter requires the construction of many discretizations of the Helmholtz boundary single layer operator for a wide range of complex wavenumbers. This leads to two main problems: the need to construct many dense matrices and to evaluate many singular and near-singular integrals. The first problem is overcome by the use of data-sparse techniques, namely, the high-frequency fast multipole method (HF FMM) and H-matrices. The applicability of both techniques for the discretization of the Helmholtz boundary single-layer operators with complex wavenumbers is analyzed. It is shown that the presence of decay can favorably affect the length of the fast multipole expansions and thus reduce the matrix-vector multiplication times. The performance of H-matrices and the HF FMM is compared for a range of complex wavenumbers, and the strategy to choose between two techniques is suggested. The second problem, namely, the assembly of many singular and nearly-singular integrals, is solved by the use of the Huygens principle. In this work we prove that kernels of the boundary integral operators $w_n^h(d)$ ($h$ is the time step and $t_n=nh$ is the time) exhibit exponential decay outside of the neighborhood of $d=nh$ (this is the consequence of the Huygens principle). The size of the support of these kernels for fixed $h$ increases with $n$ as $n^a,a<1$, where $a$ depends on the order of the Runge-Kutta method and is (typically) smaller for Runge-Kutta methods of higher order. Numerical experiments demonstrate that theoretically predicted values of $a$ are quite close to optimal. In the work it is shown how this property can be used in the recursive algorithm to construct only a few matrices with the near-field, while for the rest of the matrices the far-field only is assembled. The resulting method allows to solve the three-dimensional wave scattering problem with asymptotically almost linear complexity. The efficiency of the approach is confirmed by extensive numerical experiments.

This work addresses the question of the efficient numerical solution of time-domain boundary integral equations with retarded potentials arising in the problems of acoustic and electromagnetic scattering. The convolutional form of the time-domain boundary operators allows to discretize them with the help of Runge-Kutta convolution quadrature. This method combines Laplace-transform and time-stepping approaches and requires the explicit form of the fundamental solution only in the Laplace domain to be known. Recent numerical and analytical studies revealed excellent properties of Runge-Kutta convolution quadrature, e.g. high convergence order, stability, low dissipation and dispersion. As a model problem, we consider the wave scattering in three dimensions. The convolution quadrature discretization of the indirect formulation for the three-dimensional wave equation leads to the lower triangular Toeplitz system of equations. Each entry of this system is a boundary integral operator with a kernel defined by convolution quadrature. In this work we develop an efficient method of almost linear complexity for the solution of this system based on the existing recursive algorithm. The latter requires the construction of many discretizations of the Helmholtz boundary single layer operator for a wide range of complex wavenumbers. This leads to two main problems: the need to construct many dense matrices and to evaluate many singular and near-singular integrals. The first problem is overcome by the use of data-sparse techniques, namely, the high-frequency fast multipole method (HF FMM) and H-matrices. The applicability of both techniques for the discretization of the Helmholtz boundary single-layer operators with complex wavenumbers is analyzed. It is shown that the presence of decay can favorably affect the length of the fast multipole expansions and thus reduce the matrix-vector multiplication times. The performance of H-matrices and the HF FMM is compared for a range of complex wavenumbers, and the strategy to choose between two techniques is suggested. The second problem, namely, the assembly of many singular and nearly-singular integrals, is solved by the use of the Huygens principle. In this work we prove that kernels of the boundary integral operators $w_n^h(d)$ ($h$ is the time step and $t_n=nh$ is the time) exhibit exponential decay outside of the neighborhood of $d=nh$ (this is the consequence of the Huygens principle). The size of the support of these kernels for fixed $h$ increases with $n$ as $n^a,a<1$, where $a$ depends on the order of the Runge-Kutta method and is (typically) smaller for Runge-Kutta methods of higher order. Numerical experiments demonstrate that theoretically predicted values of $a$ are quite close to optimal. In the work it is shown how this property can be used in the recursive algorithm to construct only a few matrices with the near-field, while for the rest of the matrices the far-field only is assembled. The resulting method allows to solve the three-dimensional wave scattering problem with asymptotically almost linear complexity. The efficiency of the approach is confirmed by extensive numerical experiments.