The double splitting iteration method for solving the large indefinite least squares problem

Resumo Técnico: O Método de Iteração de Dupla Divisão para Grandes Problemas de Mínimos Quadrados Indefinidos

Enunciado do Problema
O artigo aborda os desafios computacionais associados à resolução de problemas de mínimos quadrados indefinidos (ILS) em grande escala, formulados como a minimização da forma quadrática indefinida $(b - Ax)^T J (b - Ax)$, onde $A \in \mathbb{R}^{m \times n}$ é uma matriz esparsa de grande porte, $b \in \mathbb{R}^m$, e $J = \text{diag}(I_p, -I_q)$ é uma matriz de assinatura com $p+q=m$. Quando $pq > 0$, o problema leva a uma equação normal $A^T J A x = A^T J b$ envolvendo uma matriz Hessiana que não é definida positiva. Embora existam métodos diretos para problemas densos de pequena escala, esquemas iterativos são preferidos para sistemas de grande porte. Os solucionadores iterativos existentes mais avançados para este problema dependem predominantemente de estratégias de divisão única da matriz de coeficientes $A^T J A = M - N$, como os métodos baseados em Divisão (SP), Divisão Generalizada (GSP) e Implícito de Direção Alternada (ADI).

Metodologia
Os autores propõem um novo método de iteração de Dupla Divisão (DS). Diferentemente das abordagens tradicionais que decompõem a matriz de coeficientes em duas partes ($M - N$), este método utiliza uma decomposição em três partes:
$$A^T J A = P - R - S$$
onde $P$ é uma matriz não singular. Inspirados pela estrutura do método GSP, os autores definem matrizes específicas baseadas na partição $A = [A_1; A_2]$:

• $P = \alpha I + A_1^T A_1$ (Definida Positiva Simétrica, SPD)
• $R = A_2^T A_2$ (Simétrica)
• $S = \alpha I$ (Simétrica)
  onde $\alpha > 0$ é um parâmetro dado.

Esta decomposição leva a um esquema de iteração estacionária de dois passos:
$$x_{k+1} = P^{-1} R x_k + P^{-1} S x_{k-1} + P^{-1} A^T J b$$
Esta formulação incorpora informações das duas iterações anteriores ($x_k$ e $x_{k-1}$), distinguindo-se da natureza de um único passo dos métodos SP e GSP. A convergência deste esquema é analisada examinando o raio espectral $\rho(W)$ da matriz de iteração em bloco associada $W$. Os autores derivam uma equação quadrática escalar para os autovalores $\lambda$ de $W$ e aplicam um lema sobre as raízes de equações quadráticas para provar que $|\lambda| < 1$ para todo $\alpha > 0$.

Principais Contribuições

1. Novo Framework Iterativo: O artigo introduz uma estratégia concreta de dupla divisão adaptada especificamente para as equações normais que surgem de problemas ILS, oferecendo uma alternativa distinta aos paradigmas dominantes de divisão única.
2. Prova de Convergência Incondicional: Os autores fornecem uma análise espectral rigorosa demonstrando que o método de iteração DS proposto converge incondicionalmente para qualquer parâmetro positivo $\alpha$. Este resultado é contextualizado ao conectá-lo aos critérios de convergência existentes para matrizes hermitianas definidas positivas encontrados na literatura anterior.
3. Implementação Algorítmica: Um algoritmo detalhado (Algoritmo 2.1) é apresentado, delineando os passos computacionais, incluindo o uso da decomposição de Cholesky para inverter a matriz SPD $P$.

Resultados Numéricos
Dois experimentos numéricos foram conduzidos para avaliar o desempenho do método DS em comparação com os métodos SP, GSP e ADI:

• Exemplo 3.1 (Matrizes Densas): Utilizando matrizes densas de grande escala aleatórias, o método DS foi testado com dimensões variadas ($m$ até 54.000). Com um parâmetro ótimo $\alpha=1$, o método DS convergiu em exatamente 2 iterações. Embora SP e GSP também tenham convergido em 1 iteração, o método DS alcançou tempos de CPU significativamente menores (por exemplo, ~4,8s vs. ~75s para GSP em $m=51.000$).
• Exemplo 3.2 (Matrizes Esparsas): Utilizando matrizes derivadas de problemas de mínimos quadrados totais, o método DS foi testado com estruturas esparsas. Com um parâmetro ótimo $\alpha=10^{-4}$, o método DS novamente convergiu em 2 iterações. Ele superou consistentemente os métodos de divisão única no tempo computacional em todos os tamanhos testados (até $m=8.192$), demonstrando eficiência superior mesmo à medida que o tamanho do problema aumentava.

Significado e Alegações
O artigo alega que o paradigma de iteração de dupla divisão proposto oferece uma melhoria construtiva sobre as abordagens convencionais de divisão única. O significado principal reside na capacidade do método de alcançar maior velocidade de convergência (em termos de tempo de CPU) e robustez para problemas ILS de grande escala. Os autores enfatizam que, embora o método exija duas iterações anteriores, a incorporação dessa informação histórica permite uma redução substancial no custo computacional em comparação com os métodos de um único passo SP, GSP e ADI. O trabalho fornece referências metodológicas para pesquisas futuras sobre métodos iterativos baseados em dupla divisão e sugere extensões potenciais para seleção adaptativa de parâmetros e outros tipos de sistemas lineares indefinidos.