Inexact versions of several block-splitting preconditioners for indefinite least squares problems

Titel

Inexakte Versionen mehrerer Block-Splitting-Vorkonditionierer für Probleme der indefiniten Least-Squares-Optimierung

1. Problemstellung

Das Paper befasst sich mit der numerischen Lösung von indefiniten Least-Squares-Problemen (ILS) der Form:
$$\min_{x \in \mathbb{R}^n} (b - Ax)^T H_{p,q} (b - Ax)$$
wobei $A \in \mathbb{R}^{m \times n}$ eine große, dünnbesetzte Matrix ist und $H_{p,q}$ eine Signaturmatrix mit $p$ positiven und $q$ negativen Einträgen auf der Diagonalen darstellt ($p+q=m$). Im Gegensatz zu klassischen Least-Squares-Problemen (wo $p=0$ oder $q=0$) ist die quadratische Form hier indefinit, was die Lösung erschwert.

Die Normalgleichungen dieses Problems führen zu einem linearen System, das oft ineffizient gelöst wird. Ein gängiger Ansatz ist die Umformulierung in ein nicht-singuläres lineares Block-System der Größe $3 \times 3$:
$$\mathcal{A} \begin{pmatrix} \delta_1 \\ x \\ \delta_2 \end{pmatrix} = \begin{pmatrix} I & A_1 & 0 \\ 0 & P & A_2^T \\ 0 & A_2 & I \end{pmatrix} \begin{pmatrix} \delta_1 \\ x \\ \delta_2 \end{pmatrix} = \begin{pmatrix} b_1 \\ A_1^T b_1 \\ b_2 \end{pmatrix}$$
Hierbei ist $P = A_1^T A_1$.

Herausforderung:
Bestehende Block-Splitting-Vorkonditionierer (wie $M_{BS1}$ bis $M_{BS4}$) erfordern die exakte Lösung innerer linearer Systeme mit der Matrix $P$. Da $P$ oft schlecht konditioniert ist (insbesondere wenn $A_1$ schlecht konditioniert ist), führt die exakte Lösung dieser inneren Systeme zu hohem Rechenaufwand oder numerischen Fehlern, die die Konvergenz des äußeren GMRES-Verfahrens beeinträchtigen.

2. Methodik

Die Autoren schlagen inexakte Block-Splitting-Vorkonditionierer (IBS) vor, um das Problem der schlechten Konditionierung von $P$ zu umgehen.

• Idee: Die Matrix $P$ in den Vorkonditionierern wird durch eine gut konditionierte, symmetrisch positiv definite (SPD) Näherung $\hat{P}$ ersetzt.
• Konstruktion von $\hat{P}$: Es wird gewählt als $\hat{P} = \alpha I + P$, wobei $\alpha > 0$ ein Parameter ist (empfohlen: $\alpha = 1/\|A_1\|_2$). Dies verbessert die Konditionszahl erheblich.
• Die neuen Vorkonditionierer: Basierend auf diesem Ansatz werden vier Varianten definiert ($M_1, M_2, M_3, M_4$), die den ursprünglichen Block-Splitting-Strukturen ($M_{BS1}$ bis $M_{BUT}$) entsprechen, aber $\hat{P}$ statt $P$ enthalten.
• Implementierung: Die Anwendung dieser Vorkonditionierer erfordert das Lösen von Systemen mit $\hat{P}$. Da $\hat{P}$ gut konditioniert und SPD ist, können diese inneren Systeme effizient und inexakt (z. B. mit wenigen Schritten des konjugierten Gradienten-Verfahrens, CG) gelöst werden. Dies ermöglicht den Einsatz von Flexible GMRES (FGMRES).

3. Theoretische Analyse und Beiträge

Das Paper liefert eine umfassende theoretische Analyse der vorgeschlagenen Methoden:

1. Konvergenz stationärer Iterationsverfahren:
   Es werden hinreichende Bedingungen hergeleitet, unter denen die stationären Iterationsverfahren, die durch die IBS-Splitting-Strukturen induziert werden, konvergieren.

   • Für IBS1 und IBS3: Konvergenz, wenn $2\hat{P} - P - A_2^T A_2$ und $\hat{P} - A_2^T A_2$ SPD sind.
   • Für IBS2 und IBS4: Konvergenz, wenn $2\hat{P} - P + A_2^T A_2$ SPD ist.
   • Ein Korollar zeigt, dass wenn $\hat{P} - P$ SPD ist (was durch die Wahl $\hat{P} = \alpha I + P$ garantiert ist), alle Methoden konvergieren.

2. Spektrale Eigenschaften (Eigenwertverteilung):
   Unter den Konvergenzbedingungen werden die Eigenwerte der vorkonditionierten Matrizen $M_i^{-1}\mathcal{A}$ analysiert.

   • Spektrale Clusterung: Alle Eigenwerte liegen innerhalb eines Kreises mit Mittelpunkt $(1, 0)$ und Radius $1$.
   • Eigenvektoren: Die Struktur der Eigenpaare wird detailliert untersucht. Es wird gezeigt, dass die Eigenwerte 1 eine hohe geometrische Vielfachheit haben und die restlichen Eigenwerte in einem positiven reellen Intervall $(0, 2)$ liegen (für IBS2 und IBS4).

3. Theoretische Obergrenze für GMRES:
   Basierend auf der Analyse des Minimalpolynoms wird bewiesen, dass der Grad des Minimalpolynoms für alle IBS-Vorkonditionierer höchstens $n + q + 1$ beträgt.

   • Konsequenz: Das GMRES-Verfahren konvergiert theoretisch in maximal $n + q + 1$ Schritten (bei exakter Arithmetik). Dies ist eine starke theoretische Begründung für die Effizienz.

4. Numerische Ergebnisse

Die Autoren testen die IBS-Vorkonditionierer (IBS1 bis IBS4) im Vergleich zu bestehenden Methoden (BS2 und BUT) an drei Testreihen:

• Beispiel 1 (TOLS-Matrizen): Probleme aus der Flugstabilitätsanalyse.
  • Ergebnis: Alle IBS-Methoden sind deutlich schneller (weniger Iterationen, weniger CPU-Zeit) als BS2 und BUT. IBS2 und IBS4 schneiden am besten ab.
• Beispiel 2 (SHERMAN-Matrizen): Probleme aus der Ölfeldsimulation (schlecht konditioniert).
  • Ergebnis: Während BS2 und BUT zwar das lineare System lösen (kleiner Residuen), liefern sie falsche Lösungen für das ursprüngliche ILS-Problem (großer Fehler ERR $\approx 1$). Die IBS-Methoden liefern sowohl konvergente lineare Systeme als auch korrekte Lösungen mit hoher Genauigkeit.
• Beispiel 3 (Hilbert-Matrizen): Extrem schlecht konditionierte Probleme.
  • Ergebnis: BS2 und BUT scheitern bei großen Problemen (keine Konvergenz innerhalb 2000 Iterationen). Alle IBS-Methoden lösen die Probleme effizient und robust. IBS4 ist hier leicht am schnellsten.

5. Bedeutung und Fazit

Das Paper stellt einen signifikanten Fortschritt in der numerischen linearen Algebra für indefinite Least-Squares-Probleme dar:

• Robustheit: Durch die Ersetzung von $P$ durch $\hat{P}$ werden die Vorkonditionierer unempfindlich gegenüber der schlechten Konditionierung von $A_1$.
• Effizienz: Die Kombination aus inexakten inneren Lösern und der spektralen Clusterung der Eigenwerte führt zu einer drastischen Reduktion der Iterationszahlen und Rechenzeit.
• Theoretische Fundierung: Die Herleitung einer Obergrenze für die GMRES-Iterationen und die detaillierte Eigenwertanalyse geben dem Ansatz eine solide theoretische Basis.
• Praktische Relevanz: Die Methode ist besonders für große, dünnbesetzte und schlecht konditionierte Probleme geeignet, bei denen herkömmliche direkte Methoden oder andere Vorkonditionierer versagen.

Zusammenfassend bieten die vorgeschlagenen IBS-Vorkonditionierer eine überlegene Alternative zu bestehenden Block-Splitting-Methoden, die sowohl theoretisch fundiert als auch numerisch hocheffizient ist.