H2-Matrix-Arithmetik basierend auf Niedrigrangupdates

Reimer, Knut

Viele naturwissenschaftliche Phänomene lassen sich durch Differential- oder Integralgleichungen beschreiben. Bei typischen Diskretisierungen dieser Probleme entstehen große lineare Gleichungssysteme. Ein häufig verwendeter Ansatz zum Lösen dieser Gleichungssysteme sind iterative Verfahren, die schrittweise die näherungsweise Lösung verbessern. Dabei ist die Verbesserung, die in jedem Schritt erreicht wird, meistens von der Kondition der Systemmatrix abhängig. Deshalb werden zum effizienten Lösen solcher Probleme Vorkonditionierer verwendet, die die Inverse der Systemmatrix approximieren. An dieser Stelle setzt diese Arbeit an, die einen neuen Ansatz für eine approximative Arithmetik für H2-Matrizen vorstellt, mit der robuste Vorkonditionierer konstruiert werden können. Die H2-Matrizen verwenden hierarchische Partitionen der Indexmengen der Matrix, eine hierarchische Blockpartition der Matrix und faktorisierte Niedrigrang-Darstellungen für gewisse Blöcke. Damit erreichen H2-Matrizen einen Speicheraufwand in O(kn), wobei n die Matrix-Dimension und k den Rang der Niedrigrang-Darstellung beschreibt. Der Aufwand für die Matrix-Vektor-Multiplikation besitzt die gleiche Komplexität. Die hierarchische Blockpartition erlaubt es, arithmetische Operationen wie die Inversion oder die Cholesky-Zerlegung auf die Matrix-Matrix-Multiplikation für H2-Matrizen zurückzuführen. Dabei werden die gleichen Ansätze verwendet wie für H-Matrizen, die eine andere Niedrigrang-Darstellung nutzen und einen Speicheraufwand in O(kn log(n)) haben. Die in dieser Arbeit präsentierte Matrix-Matrix-Multiplikation für H2-Matrizen stellt eine Adaption des H-Algorithmus dar, der auf Niedrigrangupdates für H-Matrizen basiert. Die vorgestellten Niedrigrangupdates für H2-Matrizen verwenden eine Adaption eines Rekompression-Algorithmus für H2-Matrizen, die nur einen Teil der Matrix rekomprimiert. Wir untersuchen den Aufwand der Niedrigrangupdates und den entstehenden Approximationsfehler, der durch Fehlertoleranzen gesteuert werden kann. Mit Hilfe des Updates können wir die Arithmetik formulieren, deren Aufwand für Matrix-Produkt, Inversion und Cholesky-Zerlegung in O(k^2n log(n)) liegt. Damit sparen wir wie beim Speicheraufwand einen log(n)-Faktor im Vergleich zu den H-Matrizen ein. Zusätzlich stellen wir eine Variante für das Niedrigrangupdate und das Matrix-Produkt vor, die den Rechenaufwand für dreidimensionale Probleme deutlich reduziert. Als numerische Experimente betrachten wir elliptische partielle Differentialgleichungen und Integralgleichungen. Die Probleme lösen wir mit dem cg-Verfahren, das wir mit Hilfe der approximierten Cholesky-Zerlegung im H2-Matrix-Format vorkonditionieren. Dabei zeigt sich der Vorkonditionierer robust bezüglich der betrachteten Geometrien und für die Differentialgleichung bezüglich springender Koeffizienten.

Many processes in nature can be described by differential or integral equations. Typical discretisation schemes lead to large systems of linear equations. Often iterative solvers are used to improve the approximate solution of the system of equations. The improvement in every step depends on the condition of the system matrix. Thus preconditioners which approximate the inverse of the system matrix are applied to solve such problems efficiently. This study presents a new approach for an approximate arithmetic for H2-matrices which allows the construction of robust preconditioners. The H2-matrices use a hierarchical partition of the index sets of the matrix, a block partition of the matrix and factorized low rank representations for certain blocks. Thereby the H2-matrices have a storage requirement in O(kn) with matrix dimension n and rank k for the low rank representations. The matrix-vector multiplication has the same complexity. The hierarchical block partition allows to reduce arithmetic operations like inversion or the Cholesky decomposition to the matrix-matrix multiplication for H2-matrices. The techniques for the reduction are the same as for H-matrices that use another low rank representation and reach a storage requirement in O(kn log(n)). The matrix-matrix multiplication for H2-matrices presented in this study is an adaption of the H-matrix algorithms which are based on low rank updates for H-matrices. The presented low rank updates for H2-matrices are an adaption of a recompression algorithm for H2-matrices which recompresses only a part of the matrix. We will discuss the computing time and the resulting approximation error, which can be controlled by error tolerances. With the help of the updates we can define the arithmetic with computing time in O(k^2n log(n)) for the matrix-matrix multiplikations, the inversions and the Cholesky decompositions. In comparison to H-matrices, we save a factor log(n) for the storage requirement. In addition, we present a variant of the low rank update and the matrix-matrix multiplication which reduces the computing time for three dimensional problem essentially. Numerical experiments are carried out for elliptic partial differential equations and integral equations. We solve the problems with the preconditioned cg-method and use approximated Cholesky decompositions in the H2-matrix format as preconditioners. In the experiments, the preconditioners are robust in respect of the considered geometries and for the differential equation relating to jumping coefficients.

Quote

Citation style:

Reimer, Knut: H2-Matrix-Arithmetik basierend auf Niedrigrangupdates.

Rights

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

Export