The shift-and-invert Arnoldi method for singular matrix pencils

Resumo Técnico: O Método de Arnoldi com Deslocamento e Inversão para Pencilas de Matrizes Singulares

Declaração do Problema
O artigo aborda o desafio de resolver problemas de autovalores generalizados esparsos e singulares de grande escala da forma $Ax = \lambda Bx$, onde o pencil de matrizes $A - \lambda B$ é singular (ou seja, $\det(A - \lambda B) \equiv 0$). Nesses casos, a definição clássica de autovalores falha porque qualquer escalar satisfaz a condição do determinante. As soluções significativas são os autovalores "regulares", definidos onde o posto de $A - \lambda_0 B$ cai abaixo do posto normal do pencil.

Embora métodos como o método da escada ou a decomposição QZ existam para problemas pequenos e densos, eles são computacionalmente proibitivos para sistemas esparsos de grande escala. Abordagens recentes de Hochstenbach, Mehl e Plestenjak propõem regularizar pencils singulares usando matrizes densas escolhidas aleatoriamente para separar autovalores verdadeiros de espúrios. No entanto, os autores argumentam que o uso de matrizes de regularização densas destrói a estrutura esparsa do problema original, levando a sobrecargas significativas de desempenho e memória para aplicações de grande escala. Além disso, solvers diretos esparsos existentes não suportam nativamente a remoção ou adição de linhas/colunas necessária para regularizar esses pencils sem desenvolvimento personalizado.

Metodologia
Os autores propõem uma estratégia determinística para regularizar pencils singulares, aproveitando a sequência de pivotação de uma fatoração LU esparsa. A metodologia central envolve as seguintes etapas:

1. Regularização via Pivotação LU: Em vez de matrizes densas aleatórias, o método utiliza uma fatoração LU esparsa da matriz deslocada $A - \sigma B$ (onde $\sigma$ é um deslocamento). Durante a fatoração, se um pivô zero (ou próximo de zero) for encontrado, o algoritmo adiciona uma linha e uma coluna à matriz para manter a fatoração.

   • Pencil Aumentado (AGEP): O processo constrói matrizes $F$ e $G$ de modo que o pencil aumentado $\begin{bmatrix} A & G \\ F^* & 0 \end{bmatrix} - \lambda \begin{bmatrix} B & 0 \\ 0 & 0 \end{bmatrix}$ se torne regular. As matrizes $F$ e $G$ são derivadas diretamente das matrizes de permutação e do processo de seleção de pivôs da fatoração LU.
   • Pencil Projetado (PGEP): Alternativamente, o método constrói um pencil projetado $G_\perp^* (A - \lambda B) F_\perp$ removendo as linhas e colunas correspondentes aos pivôs zero. $F_\perp$ e $G_\perp$ são derivados como a matriz identidade com linhas específicas removidas.

2. Detecção e Correção de Posto: A fatoração LU tenta naturalmente revelar o posto normal do pencil. Os autores observam que, devido a erros de arredondamento ou configurações inadequadas de tolerância, o posto detectado ($\hat{k}$) pode diferir do posto normal verdadeiro ($k$).

   • Se o posto detectado for muito baixo (ou seja, a tolerância for muito agressiva), um esquema de correção de posto é proposto. Isso envolve o uso de matrizes ortogonais aleatórias para aumentar as matrizes $F$ e $G$ detectadas à dimensão correta, seguido de uma atualização de baixo custo do complemento de Schur para resolver o sistema resultante.

3. Arnoldi com Deslocamento e Inversão: O problema regularizado (seja AGEP ou PGEP) é resolvido usando o método de Arnoldi bilateral com deslocamento e inversão. Os autores provam um teorema de equivalência mostrando que a fatoração de Arnoldi no pencil aumentado (com um vetor inicial específico e produto interno) produz os mesmos valores de Ritz e matriz de Hessenberg que o pencil projetado. Isso permite o uso da formulação projetada para evitar a construção explícita do sistema aumentado grande, mantendo as mesmas propriedades espectrais.

4. Problemas Retangulares: O método é estendido para problemas de autovalores retangulares ($A, B \in \mathbb{R}^{n \times m}$ com $n \neq m$). Para problemas retangulares de posto completo, solvers esparsos existentes com pivotação de linhas podem ser usados diretamente para selecionar um subproblema quadrado e regular.

Principais Contribuições

• Regularização Esparsa: O artigo introduz um método para gerar matrizes de regularização esparsas ($F, G, F_\perp, G_\perp$) diretamente da sequência de pivotação de fatorações LU esparsas, preservando a esparsidade do problema original.
• Detecção de Posto: Demonstra que fatorações LU esparsas padrão (usando pivotação parcial, de rook ou completa) frequentemente detectam com sucesso o posto normal do pencil, facilitando a construção automática da regularização.
• Correção de Posto: Um algoritmo específico é proposto para corrigir a regularização se a fatoração LU subestimar o posto normal, garantindo que o método permaneça robusto mesmo com detecção de posto imperfeita.
• Equivalência Teórica: O artigo estabelece um vínculo teórico rigoroso entre os pencils regularizados aumentados e projetados no contexto do método de Arnoldi, provando que eles produzem aproximações espectrais idênticas sob condições específicas.

Resultados
Experimentos numéricos foram conduzidos em três tipos de problemas:

1. Atualização de Modelo por Elementos Finitos: Um modelo de estrutura de treliça com 33 graus de liberdade (resultando em um pencil de dimensão ~35.937). O método proposto (usando pivotação RLU) identificou corretamente o posto e calculou autovalores com resíduos na ordem de $10^{-14}$. Em contraste, a abordagem aleatória resultou em números de condição ordens de magnitude maiores ($10^6$ vs $10^3$) e resíduos maiores.
2. Detecção de Autovalor Duplo: Um problema paramétrico envolvendo a discretização de um Laplaciano 2D. O método baseado em LU determinou corretamente o posto e alcançou alta precisão. A abordagem aleatória exigiu a construção de matrizes densas, levando a custos de armazenamento e computação significativamente maiores.
3. Problema de Autovalor Não Linear Retangular: Um problema retangular de posto completo derivado de um problema de autovalor não linear. A abordagem LU esparsa foi significativamente mais rápida (0,05s vs 2,9s para fatoração e projeção) e exigiu menos memória (98MB vs 204MB) em comparação com a abordagem densa aleatória.

Em todos os casos, os métodos de regularização esparsa preservaram a esparsidade das matrizes, levando a números de condição mais baixos para os sistemas deslocados e convergência mais rápida em comparação com a regularização densa aleatória.

Significado e Alegações
Os autores posicionam este trabalho como um conceito e não como uma solução de software completa e otimizada, reconhecendo que solvers diretos esparsos robustos para matrizes singulares estão atualmente ausentes nas bibliotecas de software padrão. No entanto, o artigo afirma que:

• Desempenho: Preservar a esparsidade através de pivotação determinística é benéfico tanto para o desempenho do solver de autovalores quanto para a precisão dos resultados (via melhor condicionamento).
• Viabilidade: Solvers diretos esparsos existentes podem ser adaptados para resolver esses problemas, particularmente para casos retangulares de posto completo, sem necessidade de nova infraestrutura de software complexa.
• Robustez: O esquema de correção de posto proposto garante que o método funcione mesmo quando a fatoração LU falha em detectar perfeitamente o posto normal.

O artigo conclui que, embora a abordagem aleatória seja teoricamente sólida, a abordagem determinística LU esparsa oferece uma alternativa prática, eficiente e precisa para problemas de autovalores singulares de grande escala, desde que o intervalo entre os valores singulares seja suficiente para a detecção de posto. Trabalhos futuros são sugeridos para explorar solvers com pivotação de volume máximo global e explorar estruturas de Kronecker em problemas multiparamétricos.