Poolpermutatiemethoden voor het eigenwaardeprobleem - Rationale QR algoritmen

Het matrix eigenwaardeprobleem is vaak voorkomend in wetenschappelijk
rekenen. Alhoewel de probleemstelling eenvoudig is, zijn de beste numerieke
algoritmes verre van voor de hand liggend.

Het berekenen van alle eigenwaarden van een kleine tot middelgrote matrix is
tegenwoordig een routine taak voor een impliciet QR algoritme dat gebruik
maakt van een bulge chasing techniek. Voor grote, ijle eigenwaardeproblemen
worden vaak projectiemethodes gebruikt om een deelverzameling van de
eigenwaarden te berekenen. Krylov deelruimtemethodes zijn waarschijnlijk
bij de meest gebruikte methodes binnen deze klasse.

Het convergentiegedrag van zowel het klassieke impliciet QR algoritme als van
Krylov deelruimtemethodes wordt bepaald door veeltermen. Het leeuwendeel
van deze thesis houdt zich bezig met QR-type methodes waarvoor het
convergentiegedrag bepaald wordt door meer algemene rationale functies.
Het eerste numerieke schema dat we voorstellen is de rationale QZ methode
voor veralgemeende eigenwaardeproblemen. De methode maakt gebruik van
een poolpermutatietechniek voor Hessenberg matrix paren. We formuleren een
impliciete Q stelling voor Hessenberg matrix paren die een motivering geeft voor
de poolpermutatie aanpak vermits ze aantoont dat de rationale QZ iteraties
uniek zijn. Rationale Krylov theorie stelt ons in staat om te bewijzen dat de
rationale QZ methode impliciet een deelruimte-iteratie uitvoert die versneld
wordt door rationale functies. Numerieke experimenten tonen aan dat de
rationale QZ methode leidt tot een significante vermindering van het rekenwerk
in vergelijking met de klassieke QZ methode. Verder formuleren we ook een
nieuw algoritme om een matrix paar te reduceren tot Hessenbergvorm en tonen
we dat een goede keuze van polen kan leiden tot voortijdige middendeflaties
tijdens de reductiefase.

Het daaropvolgende hoofdstuk past recente ontwikkelingen voor het QR
algoritme aan voor de rationale QZ methode. Dit resulteert in een multishift,
multipool rationale QZ methode met dicht op elkaar gepakte shifts en
polen. Bovendien maken we gebruik van aggressieve voortijdige deflatie om
geconvergeerde eigenwaarden te detecteren vooraleer klassieke deflatie criteria ze
kunnen detecteren. Onze implementatie van het algoritme is publiek beschikbaar
gemaakt en de numerieke testen tonen aan dat het LAPACK kan overtreffen
op vlak van nauwkeurigheid, snelheid en empirische tijdscomplexiteit.

Verder stellen we een rationale QR methode voor als een specificatie van de
rationale QZ methode die het standaard eigenwaardeprobleem op efficiënte wijze
behandelt. Deze methode past een poolpermutatie-algoritme toe op Hessenberg,
unitaire Hessenberg matrix paren en vereist slechts O(n) opslagruimte voor de
unitaire matrix. Dit halveert de opslagruimte en de rekenkost in vergelijking
met de rationale QZ methode.

Tweezijdige poolpermutatie-algoritmes voor tridiagonale matrix paren worden
bestudeerd in het voorlaatste hoofdstuk. Dit resulteert in het rationale LR
algoritme voor niet-symmetrische paren en het rationale TT T voor symmetrische,
diagonaliseerbare paren. Deze algoritmes hebben een verminderde rekenkost van
O(n 2 ) dankzij de tridiagonale structuur maar ze maken gebruik van niet-unitaire
equivalentie transformaties waardoor numerieke stabiliteit niet gegarandeerd
kan worden. We voorzien optimaliteitsvoorwaarden voor de niet-unitaire
transformaties. Numerieke experimenten geven veelbelovende resultaten maar
tonen ook dat numerieke stabiliteit in dit geval niet triviaal is.

Het laatste hoofdstuk van de thesis gaat over de welbekende rationale
Krylov methode for grootschalige eigenwaardeproblemen. We tonen aan hoe
benaderende eigenwaarden, verkregen met behulp van de rationale Krylov
methode, met de rationale QZ methode berekend kunnen worden. Verder testen
we ook de poolpermutatietechniek om op een efficiënte manier de rationale
Krylov methode te filteren en herstarten.