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

Resumen Técnico: RRGMRES con Precondicionamiento Derecho NR-SSOR para Sistemas No Simétricos de Rango y Problemas de Mínimos Cuadrados Rectangulares de Rango Deficiente

Planteamiento del Problema
El método de Gradiente de Mínimos Residuales Generalizado (GMRES) es un solver iterativo de subespacio de Krylov estándar para sistemas lineales $Ax = b$. Sin embargo, cuando $A$ es singular y el sistema es inconsistente (es decir, $b \notin R(A)$), se sabe que GMRES falla sin proporcionar una solución de mínimos cuadrados (LS) a menos que $A$ sea simétrico de rango (EP), lo que significa que $R(A) = R(A^T)$. Específicamente, si $R(A^T) \neq R(A)$ —una condición que incluye casos donde el índice de $A$ es mayor o igual a 1— existen vectores iniciales $x_0$ y términos independientes $b$ para los cuales GMRES falla. Además, incluso cuando $A$ es simétrico de rango, los subproblemas de mínimos cuadrados resueltos dentro de GMRES pueden volverse peligrosamente mal condicionados si $b \notin R(A)$.

Los enfoques existentes, como el GMRES libre de colapsos (breakdown-free), carecen de garantías teóricas de funcionamiento siempre. Del mismo modo, aunque el método AB-GMRES (aplicando GMRES a $ABz=b$) puede manejar sistemas singulares, las elecciones estándar para el precondicionador $B$ (como $B=A^TC$ con iteraciones internas estacionarias) no garantizan que $AB$ sea simétrico de rango para sistemas inconsistentes, lo que podría conducir al fallo en la búsqueda de una solución de LS.

Metodología
Los autores proponen un método iterativo robusto que combina tres componentes clave:

1. Precondicionamiento Derecho con $B = CA^T$: En lugar de resolver $Ax=b$ directamente, el método resuelve un problema de mínimos cuadrados transformado $\min_z \|b - ABz\|_2$ donde $B = CA^T$ y $C \in \mathbb{R}^{n \times n}$ es una matriz simétrica definida positiva (SPD). Esta transformación asegura que el producto $AB = ACA^T$ sea simétrico y simétrico de rango, independientemente de si $A$ es simétrico de rango o no. En consecuencia, el método puede determinar una solución de LS $x = CA^Tz$ sin colapso para cualquier $A$ singular y $b$.
2. RRGMRES (GMRES de Rango Restringido): Para abordar los problemas de mal condicionamiento inherentes a GMRES en sistemas inconsistentes, los autores emplean RRGMRES en lugar de GMRES estándar. RRGMRES restringe el espacio de búsqueda al rango de $A$, proporcionando mayor estabilidad para sistemas simétricos de rango inconsistentes. El análisis teórico muestra que el valor singular más pequeño de la matriz de Hessenberg en RRGMRES está acotado inferiormente, una propiedad que no se garantiza en el GMRES estándar.
3. Precondicionador NR-SSOR: El artículo introduce el uso del método SSOR No Simétrico (NR-SSOR) como un precondicionador de iteración interna derecha para construir la matriz $C$. Los autores demuestran que si $A$ no tiene columnas nulas y el parámetro de relajación $\omega$ satisface $0 < \omega < 2$, la matriz $C$ resultante (derivada de la iteración NR-SSOR) es simétrica definida positiva. Esta garantía teórica valida el uso de NR-SSOR dentro del marco propuesto tanto para sistemas singulares cuadrados como para problemas de mínimos cuadrados rectangulares de rango deficiente ($A \in \mathbb{R}^{m \times n}$).

Contribuciones Clave

• Justificación Teórica: El artículo demuestra que para el precondicionador derecho NR-SSOR $B = CA^T$, la matriz $C$ es SPD bajo condiciones estándar ($A$ no tiene columnas nulas, $0 < \omega < 2$). Esto asegura que $AB$ sea simétrico de rango, permitiendo al método encontrar robustamente soluciones de LS para sistemas no simétricos de rango y problemas rectangulares.
• Robustez para Sistemas Inconsistentes: Se demuestra que el RRGMRES precondicionado por la derecha con NR-SSOR determina una solución de mínimos cuadrados para cualquier $b \in \mathbb{R}^m$ y $A$ singular, incluyendo casos donde el índice de $A \ge 1$ y $R(A) \neq R(A^T)$.
• Extensión a Problemas Rectangulares: El método se extiende exitosamente a problemas de mínimos cuadrados rectangulares subdeterminados y sobredeterminados, donde $A$ puede ser de rango deficiente.
• Comparación con MINRES-QLP: El artículo establece un marco de comparación con MINRES-QLP, un método conocido por manejar sistemas simétricos singulares, señalando que mientras MINRES-QLP encuentra soluciones de norma mínima para sistemas consistentes, el método propuesto ofrece un rendimiento superior para sistemas inconsistentes.

Resultados Numéricos
Se realizaron experimentos numéricos extensos sobre:

1. Sistemas Inconsistentes GP: Matrices con índice 1 donde $R(A) \cap N(A) = \{0\}$ pero $R(A) \neq R(A^T)$.
2. Sistemas Inconsistentes de Índice 2: Matrices donde el índice es 2.
3. Problemas de Mínimos Cuadrados Subdeterminados: Matrices rectangulares de gran escala (ej. Maragal, landmarkT, lp dfl001).

Los resultados demuestran que:

• Convergencia: El GMRES estándar y el RRGMRES aplicados directamente a $Ax=b$ a menudo fallan en converger a una solución de mínimos cuadrados para estos sistemas inconsistentes y no simétricos de rango.
• Superioridad de NR-SSOR: El RRGMRES precondicionado por la derecha con NR-SSOR logra consistentemente residuos significativamente más pequeños (a menudo $10^{-10}$ a $10^{-15}$) en comparación con otros precondicionadores como $B = \{ \text{diag}(A^TA) \}^{-1}A^T$ o $B = A^T$.
• Eficiencia: El método propuesto requiere menos iteraciones y significativamente menos tiempo de computación (hasta 87.9 veces más rápido en casos subdeterminados específicos) en comparación con variantes no precondicionadas o con diferentes precondicionadores.
• Comparación con MINRES-QLP: En escenarios inconsistentes, el método propuesto logró residuos órdenes de magnitud menores que MINRES-QLP y alcanzó estos mínimos en menos iteraciones.

Significancia
El artículo afirma que el RRGMRES precondicionado por la derecha con NR-SSOR proporciona una solución teóricamente justificada y numéricamente robusta para una clase de problemas de álgebra lineal difíciles: sistemas singulares, no simétricos de rango y problemas de mínimos cuadrados rectangulares de rango deficiente. Al demostrar la naturaleza SPD del precondicionador $C$ derivado de NR-SSOR, los autores aseguran que el método evita los colapsos asociados con el GMRES estándar en entornos inconsistentes. Los experimentos numéricos validan que este enfoque no solo es teóricamente sólido, sino también prácticamente eficiente, superando a métodos existentes como AB-GMRES con otros precondicionadores y a MINRES-QLP en términos de reducción de residuo y velocidad computacional para sistemas inconsistentes.