NR-SSOR right preconditioned RRGMRES for arbitrary singular systems and least squares problems

Resumo Técnico: RRGMRES com Pré-condicionamento à Direita NR-SSOR para Sistemas Não-Simétricos de Intervalo e Problemas de Mínimos Quadrados Retangulares de Posto Deficiente

Enunciado do Problema
O método de Gradiente de Mínimos Resíduos Generalizado (GMRES) é um solver iterativo de subespaço de Krylov padrão para sistemas lineares $Ax = b$. No entanto, quando $A$ é singular e o sistema é inconsistente (ou seja, $b \notin R(A)$), o GMRES é conhecido por falhar sem fornecer uma solução de mínimos quadrados (LS) a menos que $A$ seja simétrico de intervalo (EP), o que significa que $R(A) = R(A^T)$. Especificamente, se $R(A^T) \neq R(A)$ — uma condição que inclui casos onde o índice de $A$ é maior ou igual a 1 — existem vetores iniciais $x_0$ e termos independentes $b$ para os quais o GMRES falha. Além disso, mesmo quando $A$ é simétrico de intervalo, os subproblemas de mínimos quadrados resolvidos dentro do GMRES podem tornar-se perigosamente mal condicionados se $b \notin R(A)$.

Abordagens existentes, como o GMRES livre de falhas (breakdown-free), carecem de garantias teóricas de funcionamento sempre. Da mesma forma, embora o método AB-GMRES (aplicando GMRES a $ABz=b$) possa lidar com sistemas singulares, as escolhas padrão para o pré-condicionador $B$ (como $B=A^TC$ com iterações internas estacionárias) não garantem que $AB$ seja simétrico de intervalo para sistemas inconsistentes, o que pode levar à falha na busca de uma solução de LS.

Metodologia
Os autores propõem um método iterativo robusto combinando três componentes principais:

1. Pré-condicionamento à Direita com $B = CA^T$: Em vez de resolver $Ax=b$ diretamente, o método resolve um problema de mínimos quadrados transformado $\min_z \|b - ABz\|_2$ onde $B = CA^T$ e $C \in \mathbb{R}^{n \times n}$ é uma matriz simétrica definida positiva (SPD). Esta transformação garante que o produto $AB = ACA^T$ seja simétrico e simétrico de intervalo, independentemente de $A$ ser ou não simétrico de intervalo. Consequentemente, o método pode determinar uma solução de LS $x = CA^Tz$ sem falhas para qualquer $A$ singular e $b$.
2. RRGMRES (GMRES de Intervalo Restrito): Para abordar os problemas de mal condicionamento inerentes ao GMRES para sistemas inconsistentes, os autores empregam o RRGMRES em vez do GMRES padrão. O RRGMRES restringe o subespaço de busca ao alcance de $A$, proporcionando maior estabilidade para sistemas simétricos de intervalo inconsistentes. A análise teórica mostra que o menor valor singular da matriz de Hessenberg no RRGMRES é limitado inferiormente, uma propriedade não garantida no GMRES padrão.
3. Pré-condicionador NR-SSOR: O artigo introduz o uso do método Non-Symmetric SSOR (NR-SSOR) como um pré-condicionador de iteração interna à direita para construir a matriz $C$. Os autores provam que, se $A$ não possui colunas nulas e o parâmetro de relaxação $\omega$ satisfaz $0 < \omega < 2$, a matriz $C$ resultante (derivada da iteração NR-SSOR) é simétrica definida positiva (SPD). Esta garantia teórica valida o uso do NR-SSOR dentro do framework proposto tanto para sistemas singulares quadrados quanto para problemas de mínimos quadrados retangulares de posto deficiente ($A \in \mathbb{R}^{m \times n}$).

Principais Contribuições

• Justificativa Teórica: O artigo prova que, para o pré-condicionador à direita NR-SSOR $B = CA^T$, a matriz $C$ é SPD sob condições padrão ($A$ não possui colunas nulas, $0 < \omega < 2$). Isso garante que $AB$ seja simétrico de intervalo, permitindo que o método encontre robustamente soluções de LS para sistemas não-simétricos de intervalo e problemas retangulares.
• Robustez para Sistemas Inconsistentes: O RRGMRES pré-condicionado com NR-SSOR à direita é mostrado como capaz de determinar uma solução de mínimos quadrados para qualquer $b \in \mathbb{R}^m$ e $A$ singular, incluindo casos onde o índice de $A \ge 1$ e $R(A) \neq R(A^T)$.
• Extensão para Problemas Retangulares: O método é estendido com sucesso para problemas de mínimos quadrados retangulares subdeterminados e sobdeterminados, onde $A$ pode ser de posto deficiente.
• Comparação com MINRES-QLP: O artigo estabelece um framework de comparação com o MINRES-QLP, um método conhecido por lidar com sistemas simétricos singulares, observando que, enquanto o MINRES-QLP encontra soluções de norma mínima para sistemas consistentes, o método proposto oferece desempenho superior para sistemas inconsistentes.

Resultados Numéricos
Experimentos numéricos extensos foram conduzidos em:

1. Sistemas Inconsistentes GP: Matrizes com índice 1 onde $R(A) \cap N(A) = \{0\}$, mas $R(A) \neq R(A^T)$.
2. Sistemas Inconsistentes de Índice 2: Matrizes onde o índice é 2.
3. Problemas de Mínimos Quadrados Subdeterminados: Matrizes retangulares de grande escala (ex: Maragal, landmarkT, lp dfl001).

Os resultados demonstram que:

• Convergência: O GMRES padrão e o RRGMRES aplicados diretamente a $Ax=b$ frequentemente falham em convergir para uma solução de mínimos quadrados para estes sistemas inconsistentes e não-simétricos de intervalo.
• Superioridade do NR-SSOR: O RRGMRES pré-condicionado com NR-SSOR alcança consistentemente resíduos significativamente menores (frequentemente $10^{-10}$ a $10^{-15}$) em comparação com outros pré-condicionadores como $B = \{ \text{diag}(A^TA) \}^{-1}A^T$ ou $B = A^T$.
• Eficiência: O método proposto requer menos iterações e significativamente menos tempo de computação (até 87,9 vezes mais rápido em casos específicos subdeterminados) comparado a variantes não pré-condicionadas ou pré-condicionadas de forma diferente.
• Comparação com MINRES-QLP: Em cenários inconsistentes, o método proposto alcançou resíduos ordens de magnitude menores que o MINRES-QLP e atingiu esses mínimos em menos iterações.

Significância
O artigo afirma que o RRGMRES à direita pré-condicionado com NR-SSOR fornece uma solução teoricamente justificada e numericamente robusta para uma classe de problemas difíceis de álgebra linear: sistemas singulares, não-simétricos de intervalo e problemas de mínimos quadrados retangulares de posto deficiente. Ao provar a natureza SPD da matriz pré-condicionadora $C$ derivada do NR-SSOR, os autores garantem que o método evite as falhas associadas ao GMRES padrão em configurações inconsistentes. Os experimentos numéricos validam que esta abordagem não é apenas teoricamente sólida, mas também praticamente eficiente, superando métodos existentes como AB-GMRES com outros pré-condicionadores e o MINRES-QLP em termos de redução de resíduo e velocidade computacional para sistemas inconsistentes.