Shifted HSS solvers for the indefinite Helmholtz equation

1. Problemstellung

Das Paper adressiert die effiziente und skalierbare Lösung der indefiniten Helmholtz-Gleichung, die durch Finite-Elemente-Diskretisierung entsteht. Die Gleichung lautet:
$$(-\delta + ik)^2 u - \nabla^2 u = f$$
wobei $k$ die Wellenzahl und $\delta \ge 0$ ein Absorptionsparameter ist. Der Fokus liegt auf dem Fall, in dem $k \gg \delta$ (insbesondere $\delta = 0$), was zu einem stark indefiniten System führt.

Herausforderungen:

• Indefinitheit: Herkömmliche Multigrid-Verfahren mit Standard-Glättung (z. B. skalierte Jacobi-Iteration) versagen bei großen Wellenzahlen $k$, es sei denn, der Absorptionsparameter $\delta$ ist proportional zu $k$ ($\delta = O(k)$).
• Physikalische Realität: In vielen Anwendungen (z. B. Elektromagnetismus, Elastodynamik) ist $\delta$ jedoch klein oder null ($\delta = O(1)$).
• Zielkonflikt: Ein Verschiebungsoperator (Shift) mit $\hat{\delta} = O(k)$ ist für Multigrid geeignet, führt aber zu einer schlechten Konditionierung des ursprünglichen Problems, wenn er als Vorkonditionierer verwendet wird. Ein Shift mit $\hat{\delta} = O(1)$ ist für die Konditionierung gut, aber nicht für Multigrid lösbar.

2. Methodik

Die Autoren schlagen einen iterativen Lösungsansatz vor, der auf der Hermitian-Skew-Hermitian Splitting (HSS)-Iteration basiert, angewendet auf einen verschobenen Operator.

Kernidee:
Die Methode nutzt eine zweistufige Strategie, um den Zielkonflikt zwischen $\hat{\delta} = O(k)$ (für Multigrid) und $\hat{\delta} = O(1)$ (für die Konditionierung) zu lösen:

1. Verschiebung (Shift): Das ursprüngliche Problem ($\delta=0$) wird durch einen verschobenen Operator mit $\hat{\delta} = O(1)$ vorkonditioniert.
2. Innerer Iterationszyklus (HSS): Die Inversion des verschobenen Operators wird nicht exakt, sondern durch eine HSS-Iteration approximiert.
   • Der verschobene Operator wird in einen hermitischen und einen schief-hermitischen Teil zerlegt.
   • Um die Robustheit zu gewährleisten, wird die Anzahl der inneren HSS-Schritte proportional zur Wellenzahl gewählt: $O(k)$ Iterationen.
   • Innerhalb dieser HSS-Schritte wird der Operator (der nun effektiv $\hat{\delta} = O(k)$ entspricht) durch Multigrid mit Standard-Glättung und Transferoperatoren gelöst.

Formulierungen:
Das Verfahren wird für zwei Diskretisierungsansätze analysiert:

• Primalformulierung: Standard Finite-Elemente-Methode.
• Gemischte Formulierung (Mixed): Ein System erster Ordnung mit Variablen für Gradient und Lösung ($\sigma, u$), diskretisiert mit $DG_{p-1} \times CG_p$.

3. Wichtige Beiträge und Theoretische Ergebnisse

• Beweis der Robustheit:
  Die Autoren beweisen, dass die Anzahl der äußeren Iterationen (für das ursprüngliche Problem) unabhängig von $k$ und der Gitterauflösung ist, solange $O(k)$ innere HSS-Schritte durchgeführt werden. Dies wird durch die Analyse der Kontraktionsraten in einer speziellen Norm ($H_{primal}$ bzw. $H_{mixed}$) gezeigt.
• Überbrückung des Shift-Paradoxons:
  Durch die Kombination von $O(1)$-Shift (für die äußere Konditionierung) und $O(k)$-inneren HSS-Schritten (die effektiv einen $O(k)$-Shift nutzen) wird erreicht, dass Multigrid effizient eingesetzt werden kann, ohne die Konvergenz des äußeren Krylov-Verfahrens (z. B. GMRES) zu beeinträchtigen.
• Parallele Skalierbarkeit:
  Da die inneren HSS-Schritte mit Multigrid gelöst werden, das aus Standardkomponenten mit festen Stencil-Breiten besteht, ist der Algorithmus hochgradig parallelisierbar (z. B. via MPI/PETSc). Die Kommunikation (Halos) hat eine feste Tiefe, unabhängig von $k$.

4. Numerische Ergebnisse

Die Autoren validieren ihre Theorie mit umfangreichen numerischen Experimenten in 2D und 3D:

• Testfälle: Gleichmäßige Quellen (Uniform Source) und Box-Quellen (Box Source) auf dem Einheitsquadrat/Würfel.
• Konvergenzverhalten:
  • Bei Verwendung von $O(k)$ inneren HSS-Schritten ($\theta=1$) bleibt die Anzahl der äußeren Iterationen (Richardson oder FGMRES) konstant, wenn $k$ von 16 bis 1024 (2D) bzw. 20 bis 80 (3D) steigt.
  • Die gemessenen Kontraktionsraten der HSS-Iterationen stimmen exakt mit den theoretischen Schranken überein.
  • Bei zu wenigen inneren Schritten ($\theta < 1$) wächst die Anzahl der äußeren Iterationen mit $k$; bei zu vielen ($\theta > 1$) sinkt sie, aber der Gesamtaufwand steigt unnötig.
• Parallele Leistung (Weak Scaling):
  • Die Tests wurden auf dem Supercomputer ARCHER2 durchgeführt.
  • Die Wandzeit (Wallclock Time) skaliert linear mit $O(k)$, wie theoretisch vorhergesagt ($T \propto k$).
  • Dies gilt sowohl für Richardson-Iterationen als auch für FGMRES (wobei FGMRES die Gesamtiterationen signifikant reduziert).
  • Die Ergebnisse zeigen, dass das Verfahren auch in 3D robust ist, obwohl die Freiheitsgrade mit $O(k^{4.5})$ skalieren.

5. Bedeutung und Ausblick

Bedeutung:
Das Paper stellt einen Durchbruch dar, da es einen Solver für die indefinite Helmholtz-Gleichung bietet, der:

1. Skalierbar ist (funktioniert auf großen HPC-Systemen).
2. Robust gegenüber der Wellenzahl $k$ ist (keine Degradation der Konvergenz bei hohen Frequenzen).
3. Standardkomponenten nutzt (Multigrid mit Jacobi-Glättung), was die Implementierung vereinfacht und die Wartbarkeit erhöht.
4. Die „Pollution"-Effekte (die eine feinere Diskretisierung als $1/k$ erfordern) durch die $O(k)$-Skalierung der Rechenzeit kompensiert.

Ausblick:
Die Autoren planen, die Methode auf höhere Ordnungen der Diskretisierung, $H(\text{div})-L^2$-gemischte Formulierungen sowie auf harmonische Elastodynamik und Maxwell-Gleichungen zu erweitern.

Fazit:
Die vorgestellte „Shifted HSS"-Methode ist ein leistungsfähiger, theoretisch fundierter und praktisch bewährter Ansatz, der die Lücke zwischen der Notwendigkeit robuster Vorkonditionierung und der Effizienz von Multigrid-Solvern für hochfrequente Wellenprobleme schließt.