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

Probleemstelling

Het artikel richt zich op het oplossen van indefinite least squares (ILS) problemen, gedefinieerd als:
$$\min_{x \in \mathbb{R}^n} (b - Ax)^T H_{p,q} (b - Ax)$$
waarbij $A$ een grote, dunbevolkte (sparse) matrix is en $H_{p,q}$ een signatuurmatrix is met $p$ positieve en $q$ negatieve eigenwaarden ($p+q=m$). In tegenstelling tot standaard least squares-problemen (waar $p=0$ of $q=0$), is de kwadratische vorm hier indefinit, wat leidt tot een Hessian-matrix die niet per se positief definiet is.

De normale vergelijkingen voor dit probleem kunnen worden herschreven als een niet-singulair lineair systeem van $3 \times 3$ blokken:
$$\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}$$
waarbij $P = A_1^T A_1$.

Het centrale probleem bij het oplossen van dit systeem met iteratieve methoden (zoals GMRES) is dat de blokken $P$ vaak slecht geconditioneerd zijn. Bestaande block-splitting preconditioners (zoals MBS1, MBS2, MBS3 en BUT) vereisen het exact oplossen van lineaire systemen met $P$ als interne stap. Bij slecht geconditioneerde $P$ leidt dit tot cumulatieve fouten en falen van de externe GMRES-iteraties.

Methodologie

De auteurs introduceren inexacte versies van bestaande block-splitting preconditioners, genaamd IBS (Inexact Block-Splitting).

1. Benadering van de Matrix $P$:
   In plaats van de oorspronkelijke matrix $P = A_1^T A_1$ te gebruiken, wordt deze vervangen door een goed geconditioneerde, symmetrisch positief definiete (SPD) benadering $\hat{P}$. De auteurs kiezen specifiek voor:
   $$\hat{P} = \alpha I + P$$
   waarbij $\alpha = 1/\|A_1\|_2$. Deze verschuiving verbetert de conditiegetal van de matrix aanzienlijk.

2. Nieuwe Splijtingen:
   Op basis van $\hat{P}$ worden vier nieuwe splijtingen gedefinieerd ($M_1 - N_1$ tot $M_4 - N_4$), die corresponderen met de preconditioners IBS1, IBS2, IBS3 en IBS4.

   • IBS1 & IBS3: Gebaseerd op de oorspronkelijke MBS1 en MBS3 structuren.
   • IBS2 & IBS4: Gebaseerd op MBS2 en de Block Upper Triangular (BUT) methode.

3. Implementatie:
   Het toepassen van deze preconditioners vereist het oplossen van systemen met $\hat{P}$. Omdat $\hat{P}$ goed geconditioneerd is, kunnen deze "interne" systemen efficiënt en inexact worden opgelost met een beperkt aantal iteraties van de Conjugate Gradient (CG) methode. Dit maakt de methode geschikt voor Flexible GMRES (FGMRES).

Belangrijkste Bijdragen en Theoretische Analyse

• Convergentievoorwaarden: De auteurs bewijzen dat de stationaire iteratieve methoden die corresponderen met de IBS-preconditioners convergeren naar de unieke oplossing onder specifieke voorwaarden (bijv. dat $2\hat{P} - P - A_2^T A_2$ SPD is).
• Spectrale Eigenschappen: Een cruciale theoretische bevinding is dat onder de convergentievoorwaarden, alle eigenwaarden van de gepreconditioneerde matrix $\mathcal{M}^{-1}\mathcal{A}$ binnen een cirkel liggen met middelpunt $(1,0)$ en straal $1$.
  • Dit betekent dat de eigenwaarden sterk geclusterd zijn rondom 1.
  • Voor IBS2 en IBS4 liggen alle eigenwaarden zelfs in het positieve reële interval $(0, 2)$.
• Theoretische Boventer op Iteraties: Op basis van de analyse van de eigenparen en het minimale polynoom, leiden de auteurs af dat de GMRES-methode (in exacte rekenkunde) garandeert dat de oplossing wordt gevonden in maximaal $n + q + 1$ iteraties. Dit is een sterke theoretische onderbouwing voor de snelheid van convergentie.
• Robuustheid: De methode is ontworpen om robuust te zijn tegenover slecht geconditioneerde matrices, een veelvoorkomend probleem in praktische ILS-toepassingen.

Resultaten (Numerieke Experimenten)

De auteurs testen de IBS-preconditioners op drie sets van problemen en vergelijken ze met recente methoden (BS2 en BUT):

1. Stabiliteitsanalyse van vliegtuigen (TOLS-matrices):

   • De IBS-methoden (met name IBS2 en IBS4) presteerden aanzienlijk beter dan BS2 en BUT in termen van het aantal iteraties (IT) en CPU-tijd.
   • Terwijl BS2 en BUT soms faalden of duizenden iteraties nodig hadden, convergeerden de IBS-methoden binnen 30-40 iteraties.

2. Olie-reservoir simulatie (SHERMAN-matrices):

   • Bij deze uitdagende problemen met hoge conditiegetallen bleek dat BS2 en BUT weliswaar het lineaire systeem (3) konden oplossen (kleine residuen), maar geen accurate oplossing vonden voor het oorspronkelijke ILS-probleem (grote relatieve fouten, ERR $\approx$ 1).
   • De IBS-methoden leverden zowel snelle convergentie als zeer nauwkeurige oplossingen (ERR in de orde van $10^{-9}$).

3. Zwaar slecht geconditioneerde Hilbert-matrices:

   • Bij extreem slecht geconditioneerde problemen (Hilbert-matrices) faalden de concurrenten (BS2, BUT) volledig (niet-convergentie binnen 2000 iteraties).
   • Alle IBS-methoden bleven stabiel en efficiënt, waarbij IBS2 en IBS4 opnieuw de beste prestaties leverden.

Significantie

Dit artikel biedt een praktische en theoretisch onderbouwde oplossing voor een klassiek probleem in numerieke lineaire algebra: het oplossen van grote, indefiniete least squares-systemen.

• Efficiëntie: Door de interne systemen inexact op te lossen met een goed geconditioneerde benadering, wordt de rekentijd drastisch verkort zonder de nauwkeurigheid te verliezen.
• Robuustheid: De methode is superieur bij problemen waar traditionele preconditioners falen vanwege slechte conditionering.
• Toepasbaarheid: De techniek is direct toepasbaar in toepassingen zoals totale least squares (TLS), robuuste optimalisatie en $H_\infty$-smoothing, waar dergelijke indefiniete systemen veel voorkomen.

Kortom, de voorgestelde IBS-preconditioners vormen een krachtig alternatief voor bestaande technieken, vooral voor grote, schaarse en slecht geconditioneerde problemen.