The double splitting iteration method for solving the large indefinite least squares problem

Technischer Überblick: Das Verfahren der doppelten Aufspaltungsiteration für große indefinite Least-Squares-Probleme

Problemstellung
Der Beitrag behandelt die rechnerischen Herausforderungen beim Lösen großer indefiniter Least-Squares-Probleme (ILS), die als Minimierung der indefiniten quadratischen Form $(b - Ax)^T J (b - Ax)$ formuliert sind, wobei $A \in \mathbb{R}^{m \times n}$ eine große dünnbesetzte Matrix ist, $b \in \mathbb{R}^m$ und $J = \text{diag}(I_p, -I_q)$ eine Signaturmatrix mit $p+q=m$ darstellt. Für $pq > 0$ führt das Problem auf eine Normalgleichung $A^T J A x = A^T J b$, die eine Hesse-Matrix beinhaltet, die nicht positiv definit ist. Während direkte Methoden für kleine, dichtbesetzte Probleme existieren, werden für große Systeme iterative Verfahren bevorzugt. Bestehende hochmoderne iterative Löser für dieses Problem stützen sich überwiegend auf Strategien der einfachen Aufspaltung der Koeffizientenmatrix $A^T J A = M - N$, wie etwa die auf Aufspaltung basierenden (SP), die verallgemeinerten SP (GSP) und die Alternating Direction Implicit (ADI)-Methoden.

Methodik
Die Autoren schlagen ein neuartiges Verfahren der doppelten Aufspaltung (DS) als Iterationsmethode vor. Im Gegensatz zu traditionellen Ansätzen, die die Koeffizientenmatrix in zwei Teile zerlegen ($M - N$), nutzt diese Methode eine Zerlegung in drei Teile:
$$A^T J A = P - R - S$$
wobei $P$ eine nichtsinguläre Matrix ist. Inspiriert durch die Struktur der GSP-Methode definieren die Autoren spezifische Matrizen basierend auf der Partitionierung $A = [A_1; A_2]$:

• $P = \alpha I + A_1^T A_1$ (Symmetrisch Positiv Definit, SPD)
• $R = A_2^T A_2$ (Symmetrisch)
• $S = \alpha I$ (Symmetrisch)
  wobei $\alpha > 0$ ein gegebener Parameter ist.

Diese Zerlegung führt zu einem zweistufigen stationären Iterationsschema:
$$x_{k+1} = P^{-1} R x_k + P^{-1} S x_{k-1} + P^{-1} A^T J b$$
Diese Formulierung integriert Informationen aus den beiden vorherigen Iterierten ($x_k$ und $x_{k-1}$), was sie vom einstufigen Charakter der SP- und GSP-Methoden unterscheidet. Die Konvergenz dieses Schemas wird durch Untersuchung des Spektralradius $\rho(W)$ der zugehörigen blockweisen Iterationsmatrix $W$ analysiert. Die Autoren leiten eine skalare quadratische Gleichung für die Eigenwerte $\lambda$ von $W$ her und wenden ein Lemma bezüglich der Nullstellen quadratischer Gleichungen an, um zu beweisen, dass $|\lambda| < 1$ für alle $\alpha > 0$ gilt.

Hauptbeiträge

1. Neues iteratives Rahmenwerk: Der Beitrag stellt eine konkrete Strategie der doppelten Aufspaltung vor, die speziell für die aus ILS-Problemen resultierenden Normalgleichungen entwickelt wurde und eine deutliche Alternative zu den vorherrschenden Paradigmen der einfachen Aufspaltung bietet.
2. Bedingungsloser Konvergenzbeweis: Die Autoren liefern eine rigorose spektrale Analyse, die zeigt, dass die vorgeschlagene DS-Iterationsmethode für jeden positiven Parameter $\alpha$ bedingungslos konvergiert. Dieses Ergebnis wird weiter kontextualisiert, indem es mit bestehenden Konvergenzkriterien für hermitesche positiv definite Matrizen aus der früheren Literatur in Verbindung gebracht wird.
3. Algorithmische Implementierung: Ein detaillierter Algorithmus (Algorithmus 2.1) wird vorgestellt, der die Rechenschritte umreißt, einschließlich der Verwendung der Cholesky-Zerlegung zur Invertierung der SPD-Matrix $P$.

Numerische Ergebnisse
Zwei numerische Experimente wurden durchgeführt, um die Leistungsfähigkeit der DS-Methode im Vergleich zu den SP-, GSP- und ADI-Methoden zu bewerten:

• Beispiel 3.1 (Dichtbesetzte Matrizen): Unter Verwendung zufälliger großer, dichtbesetzter Matrizen wurde die DS-Methode mit variierenden Dimensionen getestet ($m$ bis zu 54.000). Mit einem optimalen Parameter $\alpha=1$ konvergierte die DS-Methode in genau 2 Iterationen. Während SP und GSP ebenfalls in 1 Iteration konvergierten, erreichte die DS-Methode signifikant niedrigere CPU-Zeiten (z. B. ~4,8 s vs. ~75 s für GSP bei $m=51.000$).
• Beispiel 3.2 (Dünnbesetzte Matrizen): Unter Verwendung von Matrizen, die aus Total-Least-Squares-Problemen abgeleitet wurden, wurde die DS-Methode mit dünnbesetzten Strukturen getestet. Mit einem optimalen Parameter $\alpha=10^{-4}$ konvergierte die DS-Methode erneut in 2 Iterationen. Sie übertraf die Methoden der einfachen Aufspaltung in der Rechenzeit bei allen getesteten Größen (bis zu $m=8.192$) konsistent und zeigte eine überlegene Effizienz, selbst wenn die Problemgröße zunahm.

Bedeutung und Behauptungen
Der Beitrag behauptet, dass das vorgeschlagene Paradigma der doppelten Aufspaltungsiteration eine konstruktive Verbesserung gegenüber konventionellen Ansätzen der einfachen Aufspaltung darstellt. Die primäre Bedeutung liegt in der Fähigkeit der Methode, eine schnellere Konvergenzgeschwindigkeit (in Bezug auf die CPU-Zeit) und Robustheit für große ILS-Probleme zu erreichen. Die Autoren betonen, dass die Methode zwar zwei vorherige Iterierte erfordert, die Einbeziehung dieser historischen Informationen jedoch eine erhebliche Reduzierung der Rechenkosten im Vergleich zu den einstufigen SP-, GSP- und ADI-Methoden ermöglicht. Die Arbeit liefert methodische Referenzen für zukünftige Forschungen zu auf doppelten Aufspaltungen basierenden iterativen Methoden und deutet potenzielle Erweiterungen auf adaptive Parameterauswahl und andere Arten indefiniter linearer Systeme an.