Convergence analysis of a nonlinear eigensolver based on rational approximation of the resolvent

Technische Samenvatting: Convergentieanalyse van een Nietlineaire Eigensolver Gebaseerd op Rationale Approximatie van de Resolvent

Probleemstelling
Het artikel behandelt de uitdaging van het oplossen van Nietlineaire Eigenwaardeproblemen (NEP's) van de vorm $T(\lambda)v = 0$, waarbij $T$ een holomorfe matrix-waardige functie is. De auteurs richten zich op een specifieke klasse van eigenwaardesolvers die eigenwaarden berekenen door de polen te identificeren van een rationale approximatie van de resolvent $T^{-1}$. Hoewel deze aanpak, gebruikmakend van het Adaptive Antoulas-Anderson (AAA) algoritme voor rationale approximatie, een flexibel kader biedt, lijdt het onder twee primaire beperkingen:

1. Degradatie van Nauwkeurigheid: Zelfs met hoog-precieze rationale approximaties bij steunpunten, missen de berekende polen (eigenwaarden) vaak een hoge nauwkeurigheid, met name voor binnenliggende eigenwaarden of eigenwaarden met een hoge multipliciteit.
2. Detectie van Multipliciteit: Standaard benaderingen met scalaire probe-vectoren slagen er niet in de multipliciteit van eigenwaarden te detecteren, aangezien de resulterende scalaire resolvent slechts enkelvoudige polen vertoont, ongeacht de onderliggende algebraïsche multipliciteit.

Methodologie
De voorgestelde aanpak construeert een "surrogaatfunctie" $F(z)$ door de resolvent te schetsen met willekeurige probe-matrices $\Omega_L$ en $\Omega_R$:
$$F(z) := \Omega_L^H T(z)^{-1} \Omega_R$$
Het algoritme verloopt in drie hoofdfases:

1. Block Probing: In plaats van scalaire vectoren gebruikt de methode $n \times b$ probe-matrices. Deze modificatie is ontworgen om spectrale informatie betreffende de multipliciteit van eigenwaarden te behouden en de numerieke robuustheid te verbeteren.
2. Rationale Approximatie: Het (set-valued) AAA-algoritme wordt toegepast op $F(z)$ om een barycentrische rationale approximatie $R(z)$ te genereren.
3. Inzoomen (Zooming In): Om domeinen die veel eigenwaarden bevatten te behandelen, subdivideert het algoritme het computationele domein $D$ recursief in kleinere subdomeinen. De poolvindingsprocedure wordt toegepast op deze kleinere regio's om het aantal polen per approximatie te verminderen, wat de nauwkeurigheid verhoogt.

De laatste stap is het vinden van de polen van de rationale approximatie $R(z)$ door een generaaliseerd eigenwaardeprobleem op te lossen dat afgeleid is van de barycentrische vorm.

Belangrijkste Bijdragen en Theoretische Resultaten
Het artikel biedt een rigoureuze convergentieanalyse die drie fundamentele vragen adresseert met betrekking tot de stabiliteit en nauwkeurigheid van deze methode:

1. Spectrale Recovering via Block Probing (Sectie 2):

   • De auteurs stellen vast dat als de blokgrootte $b$ ten minste gelijk is aan de geometrische multipliciteit van een eigenwaarde, de surrogaatfunctie $F(z)$ alle essentiële spectrale informatie behoudt.
   • Theorem 2.3 demonstreert dat de singuliere waarden van $F(z)$ nabij een eigenwaarde $\lambda_i$ op een snelheid groeien die bepaald wordt door de partiële algebraïsche multipliciteiten, waardoor de recovery van multipliciteitsinformatie mogelijk is.
   • Theorem 2.7 bewijst dat block probing de waarschijnlijkheid aanzienlijk vermindert dat een eigenwaarde "gemist" wordt door het schetsingsproces (dat wil zeggen, dat de geschetste coëfficiëntmatrices nul worden), wat een sterkere anti-concentratie grens biedt dan vector-gebaseerde probing.

2. Convergentie van Polen en het Effect van Inzoomen (Sectie 3):

   • Theorem 3.2 kwantificeert de convergentie van polen en laat zien dat de nauwkeurigheid van een berekende pool met multipliciteit $m$ beperkt is tot $O(u^{1/m})$ (waarbij $u$ de machineprecisie is) als het domein groot is. Dit verklaart de slechte nauwkeurigheid die wordt waargenomen bij naïeve benaderingen voor eigenwaarden met een hoge multipliciteit.
   • Het artikel analyseert de "inzoom"-techniek en demonstreert dat het reduceren van de diameter van het domein $\delta$ de nauwkeurigheid van de berekende eigenwaarden lineair verbetert, wat de $O(u^{1/m})$ beperking effectief mitigeert.
   • Theorem 3.4 biedt een convergentieresultaat voor domeinen met meerdere polen, waarbij aantoont dat de nauwkeurigheid sterk afhangt van het aantal polen binnen het domein. Dit rechtvaardigt theoretisch waarom het partitioneren van het domein (het verminderen van het aantal polen per subdomein) leidt tot substantiële verbeteringen in nauwkeurigheid, vooral wanneer dit gecombineerd wordt met block probing.

3. Stabiliteit van Poolvinden (Sectie 4):

   • De auteurs analyseren de backward en forward stabiliteit van het vinden van de wortels van de rationale approximatie via een generaaliseerd eigenwaardeprobleem.
   • Theorem 4.3 stelt backward stabiliteit vast onder de voorwaarde dat de berekende pool niet te dicht bij meerdere steunpunten tegelijkertijd ligt.
   • Theorem 4.4 karakteriseert de forward stabiliteit en bevestigt dat de best haalbare forward error $O(u^{1/m})$ is voor een eigenwaarde met multipliciteit $m$, consistent met klassieke dense eigensolvers.

Resultaten
Numerieke experimenten valideren de theoretische bevindingen:

• Toy Example: Voor een diagonale matrix met verschillende eigenwaarden levert de naïeve aanpak (scalaire probing, enkel domein) fouten op rond $10^{-14}$ tot $10^{-13}$, met onjuiste cijfers in de minst significante plaatsen.
• Verbeterde Aanpak: Het toepassen van block probing (grootte 2) en inzoomen (subdivisie van het domein) herstelt eigenwaarden met ten minste 15 decimalen nauwkeurigheid.
• Butterfly Problem: In een complexe NEP met 61 eigenwaarden in een specifiek domein, vermindert de combinatie van block probing en domeinsubdivisie de maximale fout aanzienlijk vergeleken met het gebruik van een enkel groot domein, wat bevestigt dat het scheiden van poolclusters de nauwkeurigheid verbetert.

Significantie
Het artikel beweert de eerste theoretische analyse te bieden die de nauwkeurigheidsverbeteringen verklaart die worden geboden door block probing en inzoomen voor resolvent-gebaseerde eigensolvers. Het verheldert dat:

• Block probing noodzakelijk is, niet alleen voor het detecteren van multipliciteiten, maar ook voor het robuust herstellen van spectrale modi die anders verloren zouden kunnen gaan door schetsen.
• De "inzoom"-techniek theoretisch gerechtvaardigd is als een methode om de nauwkeurigheid lineair te verbeteren door de dichtheid van polen in het approximatiedomein te verminderen, wat direct de convergentiebeperkingen aanpakt die in Theorem 3.2 zijn geïdentificeerd.
• De methode backward en forward stabiel is, mits de steunpunten goed verdeeld zijn en het generale eigenwaardeprobleem stabiel wordt opgelost.

De auteurs merken op dat hoewel de theoretische analyse volledig is, de implementatie van een robuuste cleanup-procedure voor spookpolen (Froissart doublets) een openstaande uitdaging blijft voor toekomstig werk.