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

Sintesi Tecnica: Analisi della Convergenza di un Eigensolver Nonlineare Basato sull'Approssimazione Razionale del Risolvente

Enunciato del Problema
Il documento affronta la sfida di risolvere Problemi di Autovalori Non lineari (NEP) della forma $T(\lambda)v = 0$, dove $T$ è una funzione matrice-valore oloforma. Gli autori si concentrano su una specifica classe di eigensolver che calcolano gli autovalori identificando i poli di un'approssimazione razionale del risolvente $T^{-1}$. Sebbene questo approccio, utilizzando l'algoritmo Adaptive Antoulas-Anderson (AAA) per l'approssimazione razionale, offra un framework flessibile, esso soffre di due limitazioni primarie:

1. Degradazione dell'Accuratezza: Anche con approssimazioni razionali ad alta precisione nei punti di campionamento, i poli calcolati (autovalori) spesso mancano di alta accuratezza, in particolare per gli autovalori interni o quelli con alta molteplicità.
2. Rilevamento della Molteplicità: Gli approcci standard che utilizzano vettori di sondaggio scalari non riescono a rilevare la molteplicità degli autovalori, poiché il risolvente scalare risultante presenta solo poli semplici indipendentemente dalla sottostante molteplicità algebrica.

Metodologia
L'approccio proposto costruisce una "funzione surrogata" $F(z)$ schematizzando il risolvente con matrici di sondaggio casuali $\Omega_L$ e $\Omega_R$:
$$F(z) := \Omega_L^H T(z)^{-1} \Omega_R$$
L'algoritmo procede in tre fasi principali:

1. Sondaggio a Blocchi (Block Probing): Invece di utilizzare vettori scalari, il metodo impiega matrici di sondaggio $n \times b$. Questa modifica è progettata per preservare le informazioni spettrali riguardanti le molteplicità degli autovalori e migliorare la robustezza numerica.
2. Approssimazione Razionale: L'algoritmo AAA (set-valued) viene applicato a $F(z)$ per generare un'approssimazione razionale baricentrica $R(z)$.
3. Zooming In (Ingrandimento): Per gestire domini contenenti molti autovalori, l'algoritmo suddivide ricorsivamente il dominio computazionale $D$ in sotto-domini più piccoli. La procedura di ricerca dei poli viene applicata a queste regioni più piccole per ridurre il numero di poli per approssimazione, migliorando così l'accuratezza.

Il passaggio finale consiste nel trovare i poli dell'approssimazione razionale $R(z)$ risolvendo un problema di autovalori generalizzato derivato dalla sua forma baricentrica.

Contributi Chiave e Risultati Teorici
Il documento fornisce un'analisi rigorosa della convergenza che affronta tre questioni fondamentali riguardanti la stabilità e l'accuratezza di questo metodo:

1. Recupero Spettrale tramite Sondaggio a Blocchi (Sezione 2):

   • Gli autori stabiliscono che se la dimensione del blocco $b$ è almeno pari alla molteplicità geometrica di un autovalore, la funzione surrogata $F(z)$ conserva tutte le informazioni spettrali essenziali.
   • Il Teorema 2.3 dimostra che i valori singolari di $F(z)$ vicino a un autovalore $\lambda_i$ esplodono a ritmi determinati dalle molteplicità algebriche parziali, permettendo il recupero delle informazioni sulla molteplicità.
   • Il Teorema 2.7 prova che il sondaggio a blocchi riduce significativamente la probabilità di "perdere" un autovalore a causa del processo di sketching (ovvero, che le matrici coefficienti schematizzate diventino nulle), offrendo un limite di anti-concentrazione più forte rispetto al sondaggio basato su vettori.

2. Convergenza dei Poli ed Effetto dello Zooming (Sezione 3):

   • Il Teorema 3.2 quantifica la convergenza dei poli, mostrando che l'accuratezza di un polo calcolato con molteplicità $m$ è limitata a $O(u^{1/m})$ (dove $u$ è la precisione di macchina) se il dominio è ampio. Questo spiega la scarsa accuratezza osservata negli approcci ingenui per autovalori ad alta molteplicità.
   • Il documento analizza la tecnica di "zooming in", dimostrando che la riduzione del diametro del dominio $\delta$ migliora linearmente l'accuratezza dei calcoli degli autovalori, mitigando efficacemente il limite $O(u^{1/m})$.
   • Il Teorema 3.4 fornisce un risultato di convergenza per domini con molteplicità di poli, mostrando che l'accuratezza dipende fortemente dal numero di poli all'interno del dominio. Ciò giustifica teoricamente perché la partizione del dominio (riducendo il numero di poli per sotto-dominio) porti a miglioramenti sostanziali dell'accuratezza, specialmente se combinata con il sondaggio a blocchi.

3. Stabilità della Ricerca dei Poli (Sezione 4):

   • Gli autori analizzano la stabilità backward (indietro) e forward (avanti) nel trovare le radici dell'approssimazione razionale tramite un problema di autovalori generalizzato.
   • Il Teorema 4.3 stabilisce la stabilità backward sotto la condizione che il polo calcolato non sia troppo vicino a più punti di supporto simultaneamente.
   • Il Teorema 4.4 caratterizza la stabilità forward, confermando che l'errore forward migliore ottenibile è $O(u^{1/m})$ per un autovalore di molteplicità $m$, coerentemente con i classici risolutori di autovalori densi.

Risultati
Gli esperimenti numerici validano i risultati teorici:

• Esempio Semplice (Toy Example): Per una matrice diagonale con autovalori distinti, l'approccio ingenuo (sondaggio scalare, dominio singolo) produce errori intorno a $10^{-14}$ - $10^{-13}$, con cifre errate nelle ultime posizioni meno significative.
• Approccio Migliorato: Applicando il sondaggio a blocchi (dimensione 2) e lo zooming in (suddivisione del dominio), si recuperano gli autovalori con almeno 15 cifre di accuratezza.
• Problema Butterfly: In un NEP complesso con 61 autovalori in un determinato dominio, la combinazione di sondaggio a blocchi e suddivisione del dominio riduce significativamente l'errore massimo rispetto all'uso di un singolo grande dominio, confermando che la separazione dei cluster di poli migliora l'accuratezza.

Significatività
Il documento sostiene di fornire la prima analisi teorica che spiega i miglioramenti di accuratezza offerti dal sondaggio a blocchi e dallo zooming in per gli eigensolver basati sul risolvente. Chiarisce che:

• Il sondaggio a blocchi è necessario non solo per rilevare le molteplicità, ma anche per recuperare robustamente i modi spettrali che potrebbero altrimenti andare perduti a causa dello sketching.
• La tecnica di "zooming in" è teoricamente giustificata come un metodo per migliorare linearmente l'accuratezza riducendo la densità dei poli nel dominio di approssimazione, affrontando direttamente il limite di convergenza identificato nel Teorema 3.2.
• Il metodo è stabile sia in senso backward che forward, a condizione che i punti di campionamento siano ben distribuiti e il problema di autovalori generalizzato sia risolto in modo stabile.

Gli autori osservano che, sebbene l'analisi teorica sia completa, l'implementazione di una procedura di pulizia robusta per i poli spuri (doppietti di Froissart) rimane una sfida aperta per il lavoro futuro.