Wie ist der aktuelle Stand der Polynom-Vorkonditionierer?

15

Ich frage mich, was mit Polynom-Vorkonditionierern passiert ist. Ich interessiere mich für sie, weil sie aus mathematischer Sicht vergleichsweise elegant erscheinen, aber soweit ich in Umfragen zu Krylov-Methoden gelesen habe, schneiden sie im Allgemeinen als Vorkonditionierer sehr schlecht ab. Nach den Worten von Saad und van der Host ist "das derzeitige Interesse an diesen Techniken so gut wie verschwunden" (hier) . Dennoch hat es in der jüngeren Vergangenheit Anwendungen für Multicore- und GPU-Berechnungen gegeben.

Kann mir jemand sagen oder eher erklären, in welchen Zusammenhängen diese Methoden noch existieren und wo man einen guten Überblick über den aktuellen Stand der Technik findet?

shuhalo
quelle
Ein kürzlich veröffentlichter Aufsatz über arxiv ( arxiv.org/pdf/1806.08020.pdf ) untersucht polynomiale Vorkonditionierer für Arnoldi. Insbesondere testen sie es auf eine Vielzahl von Problemen und erhalten eine gute Beschleunigung. Sie kommen zu dem Schluss, dass die Verringerung der Vektoroperationen aufgrund der Polynom-Vorkonditionierung "ein großes Potenzial für die kommunikationsvermeidende Eigenwertberechnung auf Hochleistungsrechnern bietet". Ich bin nicht einer der Autoren.
Amarney

Antworten:

12

Um eine vernünftige Leistung zu erzielen, benötigen Polynom-Vorkonditionierer ziemlich genaue Spektralschätzungen. Bei schlecht konditionierten elliptischen Problemen werden die kleinsten Eigenwerte normalerweise so getrennt, dass Methoden wie Chebyshev bei weitem nicht optimal sind. Die interessanteste Eigenschaft von Polynommethoden ist, dass sie keine inneren Produkte benötigen.

Es ist eigentlich ziemlich populär Polynom verwenden Glätter in Mehrgitter-. Der Hauptunterschied zu einem Vorkonditionierer besteht darin, dass der Glätter nur auf einen Teil des Spektrums abzielen soll . Ein Polynomglätter ist derzeit beispielsweise die Standardeinstellung im Multigrid von PETSc. Siehe auch Adams et al., Parallel Multigrid Smoother: Polynom versus Gauss-Seidel (2003) zum Vergleich.

Polynom-Vorkonditionierer können lediglich zur Reduzierung der Reduktionshäufigkeit eingesetzt werden. Obwohl sie für jede Matrix neu abgestimmt werden müssen, können die Einsparungen bei Hardware erheblich sein, bei der Verringerungen teuer sind (üblich bei großen Supercomputern). Siehe dazu McInnes, Smith, Zhang und Mills, Hierarchical and Nested Krylov Methods for Extreme-Scale Computing (2012) .

Jed Brown
quelle