Preconditioning of iterative solvers using hierarchical matrices
Final Report Abstract
Im Laufe des Projekts wurde die Technik der hierarchischen Matrizen sowohl theoretisch wie auch algorithmisch weiterentwickelt. Die Existenz der Inversen und der LU-Zerlegung im hierarchischen Format wurde nachgewiesen. Sowohl die H-Inverse als auch die H-LU-Zerlegung können in nahezu linearer Zeit berechnet werden. Zudem konnte gezeigt werden, dass sich hierarchische Matrizen zum Einsatz in Quasi-Newton-Verfahren eignen. Ein bedeutender Schritt für die praktische Anwendbarkeit hierarchischer Matrizen ist, dass hierarchische Matrizen (ähnlich wie das algebraische Mehrgitterverfahren) nun auch rein algebraisch erzeugt werden können. Dadurch wurden sowohl die Effizienz als auch die Anwendbarkeit hierarchischer Matrizen signifikant verbessert. Das Gesamtziel der Entwicklung eines blackbox-artigen Vorkonditionierers mit linearer Komplexität wurde erreicht. Numerische Tests belegen, dass mit Hilfe dieses Vorkonditionierers auf Basis von hierarchischen Matrizen tatsächlich eine problemuna abh¨ngige Konvergenz und damit eine erhebliche Beschleunigung bei Problemen mit stark veränderlichen Koeffizienten erreicht wird.
Publications
- A Purely Algebraic Approach to Preconditioning based on Hierarchical LU Factorizations. Numerical Mathematics and Advanced Applications, Springer-Verlag, 135–142, 2008
M. Bebendorf and T. Fischer
- Hierarchical Matrices: A Means to Effciently Solve Elliptic Boundary Value Problems. Volume 63 of Lecture Notes in Computational Science and Engineering (LNCSE). Springer-Verlag, 2008. ISBN 978-3-540-77146-3
M. Bebendorf
- On the Purely Algebraic Data-Sparse Approximation of the Inverse and the Triangular Factors of Sparse Matrices. Technical report, Universiy of Leipzig, 2008
M. Bebendorf and T. Fischer
- Accelerating the Newton method by using a hierarchical matrices/AMG hybrid solution method. Technical report, University of Leipzig, 2009
F. van de Loo, T. Fischer, M. Bebendorf, and M. Schäfer
