Effiziente Approximation von Integraloperatoren mit Hilfe der Green'schen Darstellungsformel

Gördes, Jessica

In den Naturwissenschaften müssen immer wieder große vollbesetzte Matrizen behandelt werden. Die Approximation von Integraloperatoren mit einer Standard-Galerkin-Diskretisierung führt typischerweise genau auf solche Matrizen. Um die quadratische Komplexität zu vermeiden, die es braucht um eine vollbesetzte Matrix zu berechnen und zu speichern, sind bereits einige Ansätze eingeführt worden, inklusive hierarchischer Matrizen. Dieses kann erreicht werden, indem die Matrix partitioniert und in einer hierarchischen Repräsentation gespeichert wird, in der gewisse Matrixblöcke durch Niedrigrangmatrizen approximiert werden. Das analytische Herangehen besteht dabei in einer Approximation der Kernfunktion durch eine separierte Funktion, die dann auf eine Niedrigrangmatrix führt. Es gibt auch einen algebraischen Ansatz, der sich bestimmter Matrixeinträge bedient, um die Niedrigrangapproximation zu berechnen. In dieser Arbeit stelle ich eine neue Methode vor, um Niedrigrangmatrizen für hierarchischer Matrizen zu konstruieren. Ich bediene mich dabei des Beispiels von Integraloperatoren, um unsere Algorithmen einzuführen. Diese neue Methode baut eine entartete Kernfunktion auf, indem sie Quadratur auf die durch die Green'sche Formel dargestellte Kernfunktion anwendet. Dieses führt zu einem Algorithmus, für den exponentielle Konvergenz bewiesen wird. Obwohl die theoretischen Betrachtungen vielversprechend aussehen, kann der Algorithmus sich im dreidimensionalen Fall nicht gegenüber anderen gängigen Verfahren behaupten aufgrund der hohen lokalen Ränge, die dabei produziert werden. Das Verfahren kann aber noch weiter verbessert werden, indem diese analytische kernbasierte Methode mit der Kreuzapproximation kombiniert wird, um die hohen lokalen Ränge zu reduzieren. Mit einem zusätzlichen Interpolationsansatz ergibt sich ein sehr effizienter und zu gängigen Verfahren konkurrenzfähiger Algorithmus.

In the natural sciences there are often large densely populated matrices to be handled. Approximating integral operators by a standard Galerkin discretisation typically leads to this kind of matrices. To avoid the quadratic complexity it takes to compute and store a dense matrix, several approaches have been introduced including hierarchical matrices. This is achieved by partitioning the matrix in a hierarchical representation, where certain matrix blocks are approximated by low rank matrices. The analytic approach is to approximate the kernel function by a separable function which leads to a low rank matrix. There is also the algebraic approach that uses certain entries of the matrix itself to compute a low rank approximation. In this thesis I present a new method of low rank approximation to construct hierarchical matrices. I use the example of integral operators to introduce our algorithms. This new method builds a degenerated kernel function by using quadrature on the kernel function represented with Green's formula. It leads to an algorithm for which rigorous proofs yield exponential convergence. Although the theoretical results are very promising, the algorithm cannot compete with other currently used methods in the three-dimensional case due to high local ranks. The method can be further enhanced by combining this analytic kernel-based algorithm with cross approximation to reduce the local ranks. With an additional interpolation ansatz the resulting hybrid algorithm is very efficient and on a competitive basis with currently used methods.

Cite

Citation style:

Gördes, Jessica: Effiziente Approximation von Integraloperatoren mit Hilfe der Green'schen Darstellungsformel. 2013.

Rights

Use and reproduction:
No CC License (german copyright law applies)

Export