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

Resumo Técnico: Análise de Convergência de um Solver de Autovalores Não Lineares Baseado em Aproximação Racional do Resolvente

Enunciado do Problema
O artigo aborda o desafio de resolver Problemas de Autovalores Não Lineares (NEPs) da forma $T(\lambda)v = 0$, onde $T$ é uma função matricial holomorfa. Os autores focam em uma classe específica de solvers de autovalores que computam autovalores identificando os polos de uma aproximação racional do resolvente $T^{-1}$. Embora essa abordagem, utilizando o algoritmo Adaptive Antoulas-Anderson (AAA) para aproximação racional, ofereça um framework flexível, ela sofre de duas limitações primárias:

1. Degradação da Precisão: Mesmo com aproximações racionais de alta precisão nos pontos de amostragem, os polos computados (autovalores) frequentemente carecem de alta precisão, particularmente para autovalores interiores ou com alta multiplicidade.
2. Detecção de Multiplicidade: Abordagens padrão usando vetores de sondagem escalares falham em detectar a multiplicidade dos autovalores, pois o resolvente escalar resultante exibe apenas polos simples, independentemente da multiplicidade algébrica subjacente.

Metodologia
A abordagem proposta constrói uma "função substituta" (surrogate function) $F(z)$ esboçando o resolvente com matrizes de sondagem aleatórias $\Omega_L$ e $\Omega_R$:
$$F(z) := \Omega_L^H T(z)^{-1} \Omega_R$$
O algoritmo procede em três estágios principais:

1. Sondagem em Bloco (Block Probing): Em vez de usar vetores escalares, o método emprega matrizes de sondagem $n \times b$. Esta modificação é projetada para preservar a informação espectral referente às multiplicidades dos autovalores e melhorar a robustez numérica.
2. Aproximação Racional: O algoritmo AAA (set-valued) é aplicado a $F(z)$ para gerar uma aproximação racional bari centrada $R(z)$.
3. Zooming In (Aproximação de Escala): Para lidar com domínios contendo muitos autovalores, o algoritmo subdivide recursivamente o domínio computacional $D$ em subdomínios menores. O procedimento de busca de polos é aplicado a essas regiões menores para reduzir o número de polos por aproximação, aumentando assim a precisão.

O passo final envolve encontrar os polos da aproximação racional $R(z)$ resolvendo um problema de autovalor generalizado derivado de sua forma bari centrada.

Principais Contribuições e Resultados Teóricos
O artigo fornece uma análise de convergência rigorosa abordando três questões fundamentais sobre a estabilidade e precisão deste método:

1. Recuperação Espectral via Sondagem em Bloco (Seção 2):

   • Os autores estabelecem que, se o tamanho do bloco $b$ for pelo menos a multiplicidade geométrica de um autovalor, a função substituta $F(z)$ retém toda a informação espectral essencial.
   • Teorema 2.3 demonstra que os valores singulares de $F(z)$ próximos a um autovalor $\lambda_i$ crescem em taxas determinadas pelas multiplicidades algébricas parciais, permitindo a recuperação da informação de multiplicidade.
   • Teorema 2.7 prova que a sondagem em bloco reduz significativamente a probabilidade de "perder" um autovalor devido ao processo de sketching (ou seja, as matrizes de coeficientes esboçadas tornarem-se zero), oferecendo um limite de anti-concentração mais forte do que a sondagem baseada em vetores.

2. Convergência de Polos e o Efeito do "Zooming In" (Seção 3):

   • Teorema 3.2 quantifica a convergência dos polos, mostrando que a precisão de um polo computado com multiplicidade $m$ é limitada a $O(u^{1/m})$ (onde $u$ é a precisão da máquina) se o domínio for grande. Isso explica a baixa precisão observada em abordagens ingênuas para autovalores de alta multiplicidade.
   • O artigo analisa a técnica de "zooming in", demonstrando que reduzir o diâmetro do domínio $\delta$ melhora linearmente a precisão dos autovalores computados, mitigando efetivamente a limitação $O(u^{1/m})$.
   • Teorema 3.4 fornece um resultado de convergência para domínios com múltiplos polos, mostrando que a precisão depende fortemente do número de polos dentro do domínio. Isso justifica teoricamente por que a partição do domínio (reduzindo o número de polos por subdomínio) leva a melhorias substanciais na precisão, especialmente quando combinado com a sondagem em bloco.

3. Estabilidade da Busca de Polos (Seção 4):

   • Os autores analisam a estabilidade backward e forward de encontrar as raízes da aproximação racional via um problema de autovalor generalizado.
   • Teorema 4.3 estabelece a estabilidade backward sob a condição de que o polo computado não esteja muito próximo de múltiplos pontos de suporte simultaneamente.
   • Teorema 4.4 caracteriza a estabilidade forward, confirmando que o melhor erro forward achievable é $O(u^{1/m})$ para um autovalor de multiplicidade $m$, consistente com solvers de autovalores densos clássicos.

Resultados
Experimentos numéricos validam os achados teóricos:

• Exemplo de Teste (Toy Example): Para uma matriz diagonal com autovalores distintos, a abordagem ingênua (sondagem escalar, domínio único) produz erros em torno de $10^{-14}$ a $10^{-13}$, com dígitos incorretos nas casas decimais menos significativas.
• Abordagem Melhorada: Aplicar sondagem em bloco (tamanho 2) e "zooming in" (subdivisão do domínio) recupera autovalores com pelo menos 15 dígitos de precisão.
• Problema Butterfly: Em um NEP complexo com 61 autovalores em um domínio específico, a combinação de sondagem em bloco e subdivisão de domínio reduz significamente o erro máximo em comparação ao uso de um único domínio grande, confirmando que separar clusters de polos melhora a precisão.

Significância
O artigo afirma fornecer a primeira análise teórica que explica as melhorias de precisão oferecidas pela sondagem em bloco e pelo "zooming in" para solvers de autovalores baseados em resolvente. Ele esclarece que:

• A sondagem em bloco é necessária não apenas para detectar multiplicidades, mas também para recuperar robustamente modos espectrais que poderiam ser perdidos devido ao sketching.
• A técnica de "zooming in" é teoricamente justificada como um método para melhorar linearmente a precisão ao reduzir a densidade de polos no domínio de aproximação, abordando diretamente a limitação de convergência identificada no Teorema 3.2.
• O método é estável em termos de backward e forward, desde que os pontos de amostragem sejam bem distribuídos e o problema de autovalor generalizado seja resolvido de forma estável.

Os autores observam que, embora a análise teórica esteja completa, a implementação de um procedimento de limpeza robusto para polos espúrios (Froissart doublets) permanece um desafio em aberto para trabalhos futuros.