The shift-and-invert Arnoldi method for singular matrix pencils

Technische Samenvatting: De Shift-and-Invert Arnoldi-methode voor singuliere matrixpencils

Probleemstelling
Het artikel behandelt de uitdaging om grote, schaars bezette singuliere gegeneraliseerde eigenwaardeproblemen op te lossen van de vorm $Ax = \lambda Bx$, waarbij de matrixpencil $A - \lambda B$ singulier is (d.w.z. $\det(A - \lambda B) \equiv 0$). In dergelijke gevallen faalt de klassieke definitie van eigenwaarden omdat elke scalair aan de determinantvoorwaarde voldoet. De zinvolle oplossingen zijn de "reguliere" eigenwaarden, gedefinieerd op de plaatsen waar de rang van $A - \lambda_0 B$ daalt onder de normale rang van de pencil.

Hoewel methoden zoals de trapmethode of QZ-decompositie bestaan voor kleine, dichte problemen, zijn ze computationeel onhaalbaar voor grote, schaars bezette systemen. Nieuwere benaderingen door Hochstenbach, Mehl en Plestenjak stellen voor om singuliere pencils te regulariseren met behulp van willekeurig gekozen dichte matrices om ware eigenwaarden te scheiden van schijnbare eigenwaarden. De auteurs betogen echter dat het gebruik van dichte regularisatiematrices de schaars bezette structuur van het oorspronkelijke probleem vernietigt, wat leidt tot aanzienlijke prestatie- en geheugenoverhead voor toepassingen op grote schaal. Bovendien ondersteunen bestaande schaars bezette directe oplossers de verwijdering of toevoeging van rijen/colommen die nodig is om deze pencils te regulariseren, niet op native wijze zonder aangepaste ontwikkeling.

Methodologie
De auteurs stellen een deterministische strategie voor om singuliere pencils te regulariseren door gebruik te maken van de pivotvolgorde van een schaars bezette LU-factorisatie. De kernmethodologie omvat de volgende stappen:

1. Regularisatie via LU-pivoting: In plaats van willekeurige dichte matrices, maakt de methode gebruik van een schaars bezette LU-factorisatie van de verschoven matrix $A - \sigma B$ (waarbij $\sigma$ een verschuiving is). Tijdens de factorisatie voegt het algoritme, indien een nul- (of bijna-nul) pivot wordt aangetroffen, een rij en kolom toe aan de matrix om de factorisatie te handhaven.

   • Geaugmenteerde pencil (AGEP): Het proces construeert matrices $F$ en $G$ zodat de geaugmenteerde pencil $\begin{bmatrix} A & G \\ F^* & 0 \end{bmatrix} - \lambda \begin{bmatrix} B & 0 \\ 0 & 0 \end{bmatrix}$ regulier wordt. De matrices $F$ en $G$ worden rechtstreeks afgeleid uit de permutatiematrices en het pivotselectieproces van de LU-factorisatie.
   • Geprojecteerde pencil (PGEP): Alternatief construeert de methode een geprojecteerde pencil $G_\perp^* (A - \lambda B) F_\perp$ door de rijen en kolommen die overeenkomen met de nul-pivots te verwijderen. $F_\perp$ en $G_\perp$ worden afgeleid als het eenheidsmatrix met specifieke rijen verwijderd.

2. Rangdetectie en correctie: De LU-factorisatie probeert op natuurlijke wijze de normale rang van de pencil te onthullen. De auteurs merken op dat door afrondingsfouten of ongeschikte tolerantie-instellingen de gedetecteerde rang ($\hat{k}$) kan verschillen van de ware normale rang ($k$).

   • Als de gedetecteerde rang te laag is (d.w.z. de tolerantie is te agressief), wordt een rangcorrectieschema voorgesteld. Dit houdt in dat willekeurige orthogonale matrices worden gebruikt om de gedetecteerde $F$ en $G$ aan te vullen tot de juiste dimensie, gevolgd door een goedkope Schur-complement-update om het resulterende systeem op te lossen.

3. Shift-and-Invert Arnoldi: Het geregulariseerde probleem (AGEP of PGEP) wordt opgelost met de tweezijdige shift-and-invert Arnoldi-methode. De auteurs bewijzen een equivalentiestelling die aantoont dat de Arnoldi-factorisatie op de geaugmenteerde pencil (met een specifiek startvector en inproduct) dezelfde Ritz-waarden en Hessenberg-matrix oplevert als de geprojecteerde pencil. Dit maakt het gebruik van de geprojecteerde formulering mogelijk om de expliciete constructie van het grote geaugmenteerde systeem te vermijden, terwijl dezelfde spectrale eigenschappen behouden blijven.

4. Rechthoekige problemen: De methode wordt uitgebreid tot rechthoekige eigenwaardeproblemen ($A, B \in \mathbb{R}^{n \times m}$ met $n \neq m$). Voor vol-rang rechthoekige problemen kunnen bestaande schaars bezette oplossers met rij-pivoting direct worden gebruikt om een vierkante, reguliere sub-probleem te selecteren.

Belangrijkste bijdragen

• Schaars bezette regularisatie: Het artikel introduceert een methode om schaars bezette regularisatiematrices ($F, G, F_\perp, G_\perp$) rechtstreeks te genereren uit de pivotvolgorde van schaars bezette LU-factorisaties, waarbij de schaars bezette structuur van het oorspronkelijke probleem behouden blijft.
• Rangdetectie: Het toont aan dat standaard schaars bezette LU-factorisaties (met gebruik van partiële, rook- of volledige pivoting) vaak succesvol de normale rang van de pencil detecteren, wat de automatische constructie van de regularisatie faciliteert.
• Rangcorrectie: Een specifiek algoritme wordt voorgesteld om de regularisatie te corrigeren als de LU-factorisatie de normale rang onderschat, waardoor de methode robuust blijft zelfs bij imperfecte rangdetectie.
• Theoretische equivalentie: Het artikel vestigt een strikte theoretische link tussen de geaugmenteerde en geprojecteerde geregulariseerde pencils in de context van de Arnoldi-methode, en bewijst dat ze onder specifieke voorwaarden identieke spectrale benaderingen opleveren.

Resultaten
Numerieke experimenten werden uitgevoerd op drie soorten problemen:

1. Finite Element Model Updating: Een truss-structuurmodel met 33 vrijheidsgraden (wat resulteert in een pencil van dimensie ~35.937). De voorgestelde methode (met RLU-pivoting) identificeerde correct de rang en berekende eigenwaarden met residuen in de orde van $10^{-14}$. Daarentegen resulteerde de gerandomiseerde aanpak in conditienummers die orde van grootte hoger waren ($10^6$ versus $10^3$) en grotere residuen.
2. Detectie van dubbele eigenwaarden: Een parametrisch probleem dat de discretisatie van een 2D-Laplaciaan betreft. De op LU gebaseerde methode bepaalde correct de rang en behaalde hoge nauwkeurigheid. De gerandomiseerde aanpak vereiste het construeren van dichte matrices, wat leidde tot aanzienlijk hogere opslag- en rekenkosten.
3. Rechthoekig niet-lineair eigenwaardeprobleem: Een vol-rang rechthoekig probleem afgeleid van een niet-lineair eigenwaardeprobleem. De schaars bezette LU-benadering was aanzienlijk sneller (0,05s versus 2,9s voor factorisatie en projectie) en vereiste minder geheugen (98MB versus 204MB) in vergelijking met de gerandomiseerde dichte aanpak.

In alle gevallen behielden de schaars bezette regularisatiemethoden de schaars bezette structuur van de matrices, wat leidde tot lagere conditienummers voor de verschoven systemen en snellere convergentie in vergelijking met gerandomiseerde dichte regularisatie.

Betekenis en claims
De auteurs positioneren dit werk als een concept in plaats van een complete, geoptimaliseerde softwareoplossing, en erkennen dat robuuste schaars bezette directe oplossers voor singuliere matrices momenteel ontbreken in standaard softwarebibliotheken. Het artikel claimt echter dat:

• Prestaties: Het behoud van schaars bezette structuur door deterministische pivoting gunstig is voor zowel de prestaties van de eigenwaardeoplosser als de nauwkeurigheid van de resultaten (via betere conditionering).
• Haalbaarheid: Bestaande schaars bezette directe oplossers kunnen worden aangepast om deze problemen op te lossen, met name voor rechthoekige vol-rang gevallen, zonder dat nieuwe, complexe software-infrastructuur nodig is.
• Robuustheid: Het voorgestelde rangcorrectieschema zorgt ervoor dat de methode werkt, zelfs wanneer de LU-factorisatie de normale rang niet perfect detecteert.

Het artikel concludeert dat hoewel de gerandomiseerde aanpak theoretisch sound is, de deterministische schaars bezette LU-benadering een praktische, efficiënte en accurate alternatief biedt voor grote singuliere eigenwaardeproblemen, mits het gat tussen singuliere waarden voldoende is voor rangdetectie. Toekomstig werk wordt voorgesteld om oplossers met globale maximum-volume pivoting te verkennen en Kronecker-structuren in multiparameterproblemen te benutten.