Scharfe a priori Konvergenzabschätzungen für Krylovraum-basierte Eigenlöser

• Antragsteller: Professor Dr. Klaus Neymeyr
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung von 2021 bis 2025
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 463329614

• Erstellungsjahr: 2023

Zusammenfassung der Projektergebnisse

Lineare Gleichungssysteme und Matrixeigenwertprobleme lassen sich mit Iterationsverfahren in Krylovräumen effizient lösen. Die Aktualität solcher Methoden wird beispielhaft durch Anwendungen für das spektrale Clustering in der Datenanalyse oder durch Self- Consistent-Field-Iterationen in der quantenmechanischen Dichtefunktionaltheorie belegt. Grundprinzip ist die Lösung eines hochdimensionalen Problems mittels einer Folge approximativer Lösungen aus adaptiv verbesserten Unterräumen kleinerer Dimensionen. Die Einfachheit der Verfahrenskonstruktion steht einer hohen Komplexität der Beschreibung ihres Konvergenzverhaltens gegenüber. In diesem Projekt wurden Krylovraum-basierte Verfahren für die numerische Lösung hermitescher Eigenwertprobleme mit Blockiterationen, Neustarts und Vorkonditionierung hinsichtlich ihrer Konvergenz analysiert. Dabei wurden die folgenden Resultate erzielt. (i) Für Krylovraum-basierte Verfahren ohne Vorkonditionierung oder mit einer Vorkonditionierung mittels exakter Inverser wurde eine von abstrakten Unterraumiterationen ausgehende Analyse weiterentwickelt. Es werden bestehende Majorization-Ansätze mittels biorthogonaler Hilfsvektoren erweitert, um Approximationsfehler der Unterraumiterierten oder Ritzwerte durch tupelweise Konvergenzfaktoren beschreiben zu können. Die resultierenden Abschätzungen lassen sich auf verschiedene Eigenlöser sowie Filterungen anwenden. Die Spezialisierung für Block-Krylovräume beziehungsweise das Block-Lanczos-Verfahren verbessert bekannte Abschätzungen, welche skalare Konvergenzfaktoren verwenden. (ii) Nachteile winkelabhängiger Ritzwert-Abschätzungen bei Neustarts wurden durch winkelfreie Varianten überwunden. Bei der Herleitung werden begleitende Unterraumiterationen konstruiert und entsprechende Zwischenabschätzungen rekursiv kombiniert. Das ermöglicht unter anderem Mehrschritt-Abschätzungen für neugestartete Versionen des Block-Lanczos-Verfahrens. (iii) Für vorkonditionierte Gradientenverfahren mit impliziter Deflation wurden neue Abschätzungen unter schwächeren Voraussetzungen hergeleitet und ferner auf blockweise Versionen verallgemeinert. Besonders von Bedeutung ist eine für Deflation modifizierte Interpretation der Vorkonditionierung, welche zukünftig zur Analyse weiterentwickelter Verfahren mit impliziter Deflation erneut eingesetzt werden kann. (iv) Zur Analyse der Cluster-Robustheit für blockweise vorkonditionierte Gradientenverfahren wurden für feste Schrittweiten entwickelte Ansätze auf optimale Schrittweiten erweitert. Bestehende Resultate ließen sich dadurch bezogen auf flexible Anwendbarkeit und einfache Konvergenzfaktoren verbessern.

Projektbezogene Publikationen (Auswahl)

• Convergence analysis of a block preconditioned steepest descent eigensolver with implicit deflation. Numerical Linear Algebra with Applications, 30(5).
  Zhou, Ming; Bai, Zhaojun; Cai, Yunfeng & Neymeyr, Klaus
  
• Convergence rates of individual Ritz values in block preconditioned gradient-type eigensolvers. ETNA -Electronic Transactions on Numerical Analysis, 58, 597-620.
  Zhou, Ming & Neymeyr, Klaus
  
• Sharp Majorization-Type Cluster Robust Bounds for Block Filters and Eigensolvers. SIAM Journal on Matrix Analysis and Applications, 44(4), 1852-1878.
  Zhou, Ming; Argentati, Merico; Knyazev, Andrew V. & Neymeyr, Klaus
  
• Angle‐Free Cluster‐Robust Ritz Value Bounds for Restarted Block Eigensolvers. Numerical Linear Algebra with Applications, 32(1).
  Zhou, Ming; Knyazev, Andrew & Neymeyr, Klaus