H²-matrix preconditioners for integral and elliptic partial differential equations
Final Report Abstract
Es ist uns im Rahmen des Projekts gelungen, effiziente Algorithmen für die Konstruktion von Vorkonditionierern für Integralgleichungen und elliptische partielle Differentialgleichungen zu entwickeln. Unser Ansatz besteht darin, den Vorkonditionierer als approximative LR- oder Choles-ky-Zerlegung zu konstruieren, die sich mit Hilfe approximativer Matrix-Multiplikationen ausdrücken lasst, die wiederum mit Hilfe approximativer Niedrigrang-Updates dargestellt werden können. Diese Updates lassen sich mit Hilfe geeigneter Algorithmen in optimaler (namlich linearer) Komplexität ausführen, so dass sich für die Multiplikation und die Faktorisierung ein Rechenaufwand von Ό(nk log n) ergibt. Die so entstehenden Vorkonditionierer sind ähnlich robust wie ihre Vorbilder aus dem Bereich der hierarchischen Matrizen und lassen sich auch ähnlich flexibel einsetzen, benötigen aber erheblich weniger Speicherplatz. Durch die Entwicklung einer Variante des ursprünglich geplanten Algorithmus konnte der Zeitbedarf für das Aufstellen der Vorkonditionierer deutlich reduziert werden. Wir gehen davon aus, dass ein erst nach Ablaufen des Förderzeitraums entwickeltes neues Konzept die Rechenzeit weiter reduzieren könnte, hatten allerdings nicht mehr die Möglichkeit, diesen Ansatz weiter zu untersuchen.
Publications
- Computing the eigenvalues of symmetric H2-matrices by slicing the spectrum. Comp. Vis. Sci., 16(6):271–282 (2015)
P. Benner, S. Börm, T. Mach, K. Reimer
(See online at https://doi.org/10.1007/s00791-015-0238-y) - Efficient arithmetic operations for rank-structured matrices based on hierarchical low-rank updates. Comp. Vis. Sci., 16(6):247–258 (2015)
S. Börm, K. Reimer
(See online at https://doi.org/10.1007/s00791-015-0233-3)
