Lanczos with compression for symmetric eigenvalue problems

Título: Lanczos com Compressão para Problemas de Autovalores Simétricos

Autores: Angelo A. Casulli, Daniel Kressner e Nian Shao.

1. Problema Abordado

O artigo foca no cálculo de alguns autovalores extremos (menores ou maiores) e seus respectivos autovetores de uma grande matriz simétrica $A$.

• Desafio Principal: Os métodos de subespaço de Krylov, como o método de Lanczos, exigem o armazenamento de uma base ortonormal $Q_m$ que cresce com o número de iterações. Em casos de convergência lenta, a memória pode ser esgotada antes de atingir a precisão desejada.
• Custo Computacional: Além do armazenamento, o custo de ortogonalização cresce quadraticamente com o tamanho da base ($O(m^2 n)$).
• Solução Atual: O padrão da indústria é o "reinício implícito" (Implicit Restarting), utilizado em métodos como o IRA (Implicitly Restarted Arnoldi) e o método de Krylov-Schur. Esses métodos utilizam filtragem polinomial para descartar partes indesejadas do espectro e reiniciar o processo com um vetor inicial atualizado. No entanto, a análise teórica de convergência para reinícios com "deslocamentos exatos" (exact shifts) é qualitativa e não fornece taxas de convergência específicas.

2. Metodologia Proposta: Lanczos com Compressão

Os autores propõem uma estratégia alternativa ao reinício, chamada Lanczos com Compressão (LC). Em vez de descartar informações e reiniciar, o método comprime o subespaço de Krylov mantendo a informação essencial.

Mecanismos Principais:

1. Decomposição Tipo-Krylov Generalizada:
   O método introduz uma decomposição mais geral que permite um termo de erro $F_m$:
   $$A Q_m = Q_m T_m + q_{m+1} b_m^T + F_m$$
   Diferente da decomposição de Krylov clássica (onde $F_m = 0$), esta estrutura permite que a compressão destrua a estrutura de Krylov estrita, mas mantenha a compatibilidade com passos subsequentes do método de Lanczos.

2. Compressão via Aproximação Racional:

   • O objetivo é projetar a base $Q_m$ em um subespaço de dimensão menor $\ell < m$ usando uma matriz ortonormal $V_\ell$.
   • A escolha de $V_\ell$ baseia-se na aproximação racional da função degrau $\chi_\tau(x)$ (que separa os autovalores desejados dos indesejados).
   • Utiliza-se uma função racional $r(x)$ (baseada no problema de Zolotarev) que é próxima de 1 para os autovalores de interesse e próxima de 0 para os demais.
   • O subespaço comprimido é construído combinando os autovetores de $T_m$ associados aos autovalores desejados e um Subespaço de Krylov Racional gerado por $r(T_m)$.

3. Reortogonalização com "Fill-in" (Preenchimento):

   • Um desafio crítico é manter a estabilidade numérica. A ortogonalidade padrão não é suficiente devido ao termo $F_m$.
   • Os autores propõem uma nova estratégia de reortogonalização com fill-in. Em vez de armazenar explicitamente a matriz $F_m$ (o que dobraria o custo de memória), o método permite que a estrutura tridiagonal de $T_m$ se torne cheia (fill-in) nas linhas e colunas correspondentes ao ponto de compressão.
   • Isso garante a estabilidade de retrocesso (backward stability) sem o custo extra de armazenamento de $F_m$.

4. Estratégia Adaptativa:
   O algoritmo seleciona automaticamente o grau da aproximação racional e o número de vetores a reter ($\ell$) para equilibrar o erro de compressão e o custo computacional, evitando gaps de autovalores muito pequenos que exigiriam graus polinomiais excessivos.

3. Contribuições Chave

• Novo Paradigma de Compressão: Substitui a filtragem polinomial (reinício) por compressão via aproximação racional, sacrificando a estrutura de Krylov estrita, mas preservando a informação espectral relevante.
• Análise Teórica de Convergência:
  • Demonstra que o erro introduzido pela compressão é limitado por $O(\text{tol}_{ra}^2)$, onde $\text{tol}_{ra}$ é a tolerância da aproximação racional.
  • Prova que a convergência dos valores de Ritz é negligenciavelmente afetada pela compressão em comparação com o Lanczos padrão.
  • Estabelece que a estabilidade de retrocesso é mantida, similar ao método de Krylov-Schur.
• Análise de Complexidade:
  • Para problemas com pequenos gaps relativos de autovalores, o método reduz o custo de ortogonalização. Enquanto o Lanczos padrão requer $O(n k^2 / \sqrt{\text{relgap}})$ operações, o método com compressão reduz isso para $O(n k^2 / \sqrt{\text{relgap}})$ com uma constante menor, pois a dimensão da base comprimida cresce apenas logaritmicamente com o inverso do gap.
• Algoritmo Eficiente: Apresenta o Algoritmo 2, que alterna ciclicamente entre expansão (passos de Lanczos) e compressão, utilizando apenas produtos matriz-vetor com $A$.

4. Resultados Numéricos

Os autores compararam o método proposto (LC) com o método de Krylov-Schur (KS), que é a base de funções como eigs no MATLAB e Julia.

• Problemas de Laplaciano (Domínio em L):
  • O método LC superou consistentemente o KS em termos de número de produtos matriz-vetor (matvecs).
  • A melhoria variou de 4% a 7% para diferentes tamanhos de matriz e tolerâncias, sendo essa vantagem robusta em relação à escolha do vetor inicial aleatório.
  • A aproximação do resíduo usada para verificar a convergência mostrou-se altamente confiável.
• Matrizes de Teoria do Funcional da Densidade (DFT):
  • Testes em matrizes de química computacional (ex: $H_2O$, $SiO_2$) mostraram que o LC frequentemente requer menos iterações que o KS.
  • Estagnação: Em casos com muitos autovalores (ex: 55 ou 86), observou-se estagnação na convergência devido a erros de arredondamento que afetam a estrutura de rank-1 do termo de erro. O estudo mostrou que a reortogonalização com "fill-in" é crucial para manter a estabilidade, enquanto métodos padrão (como Gram-Schmidt clássico) falhavam rapidamente após a primeira compressão.

5. Significado e Conclusão

O trabalho apresenta uma alternativa teoricamente fundamentada e numericamente superior ao reinício implícito padrão para problemas de autovalores simétricos grandes.

• Vantagem Principal: Redução do custo computacional e de memória, especialmente em problemas onde a convergência é lenta (pequenos gaps de autovalores).
• Impacto: Oferece garantias teóricas de convergência e estabilidade que faltam em métodos de reinício com deslocamentos exatos.
• Futuro: Os autores identificam a necessidade de superar a estagnação observada em casos de alta dimensionalidade e muitos autovalores, possivelmente refinando o tratamento do erro de arredondamento na estrutura da decomposição comprimida.

Em resumo, o "Lanczos com Compressão" é um método promissor que substitui a estratégia de "descartar e reiniciar" por uma de "comprimir e manter", oferecendo ganhos de eficiência em aplicações de grande escala.