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

기술 요약: 비-범위-대칭 시스템 및 계수 부족 직사각형 최소제곱 문제를 위한 NR-SSOR 우측 전처리된 RRGMRES

문제 정의
일반화 최소 잔차(GMRES)법은 선형 시스템 $Ax = b$를 위한 표준 크릴로프 부공간 반복 솔버이다. 그러나$A$가 특이 행렬(singular)이고 시스템이 일치하지 않는 경우(즉, $b \notin R(A)$), $A$가 범위-대칭(EP, 즉 $R(A) = R(A^T)$)이 아니라면 GMRES는 최소제곱(LS) 해를 제공하지 못한 채 중단(breakdown)되는 것으로 알려져 있다. 특히, $R(A^T) \neq R(A)$인 경우(이는 $A$의 지수(index)가 1 이상인 경우를 포함한다)에는 실패할 수 있는 초기 벡터 $x_0$와 우변 $b$가 존재한다. 또한, $A$가 범위-대칭이라 하더라도, GMRES 내에서 해결되는 최소제곱 부문제(subproblem)는 $b \notin R(A)$인 경우 매우 나쁜 조건수(ill-conditioned)를 가질 수 있다.

AB-GMRES와 같은 기존 접근 방식(AB$z=b$에 GMRES를 적용)은 특이 시스템을 처리할 수 있지만, 전처리기 $B$에 대한 표준적인 선택(예: 정적 내부 반복을 사용하는 $B=A^TC$)은 불일치하는 시스템에 대해 $AB$가 범위-대칭임을 보장하지 않으며, 이는 LS 해를 찾는 데 실패할 가능성을 초래할 수 있다.

방법론
저자들은 세 가지 핵심 구성 요소를 결합한 견고한 반복법을 제안한다:

1. $B = CA^T$를 이용한 우측 전처리: $Ax=b$를 직접 푸는 대신, 이 방법은$B = CA^T$(여기서$C \in \mathbb{R}^{n \times n}$은 대칭 양의 정부호(SPD) 행렬)인 변환된 최소제곱 문제 $\min_z \|b - ABz\|_2$를 해결한다. 이 변환은 $A$가 범위-대칭인지 여부와 관계없이 $AB = ACA^T$가 대칭이고 범위-대칭임을 보장한다. 결과적으로, 이 방법은 임의의 특이 행렬 $A$와 $b$에 대해 중단 없이 LS 해 $x = CA^Tz$를 결정할 수 있다.
2. RRGMRES (범위-제한 GMRES): 불일치하는 시스템에서 발생하는 조건수 악화 문제를 해결하기 위해, 저자들은 표준 GMRES 대신 RRGMRES를 사용한다. RRGMRES는 탐색 공간을 $A$의 범위(range)로 제한하여, 불일치하는 범위-대칭 시스템에 대해 더 높은 안정성을 제공한다. 이론적 분석에 따르면, RRGMRES의 헤센베르크 행렬의 최소 특이값은 하한값이 존재하며, 이는 표준 GMRES에서는 보장되지 않는 특성이다.
3. NR-SSOR 전처리기: 저자들은 행렬 $C$를 구축하기 위한 내부 반복 우측 전처리기로서 Non-Symmetric SSOR (NR-SSOR)의 사용을 도입한다. 저자들은 $A$가 영 열(zero column)을 갖지 않고 완화 매개변수 $\omega$가 $0 < \omega < 2$를 만족하면, NR-SSOR 반복으로부터 유도된 행렬 $C$가 대칭 양의 정부호(SPD)임을 증명하였다. 이 이론적 보증은 제안된 프레임워크 내에서 정방 특이 시스템과 직사각형 계수 부족 최소제곱 문제($A \in \mathbb{R}^{m \times n}$) 모두에 NR-SSOR을 사용하는 것을 정당화한다.

주요 기여

• 이론적 정당성: 본 논문은 NR-SSOR 우측 전처리기 $B = CA^T$에 대해, 표준 조건($A$가 영 열을 갖고 $0 < \omega < 2$) 하에서 행렬 $C$가 SPD임을 증명한다. 이는 $AB$가 범위-대칭임을 보장하여, 비-범위-대칭 시스템 및 직사각형 문제에 대해 이 방법이 LS 해를 견고하게 찾을 수 있도록 한다.
• 불일치 시스템에 대한 견고성: 제안된 NR-SSOR 우측 전처리된 RRGMRES는 임의의 $b \in \mathbb{R}^m$와 특이 행렬 $A$에 대해 최소제곱 해를 결정할 수 있음이 입증되었다. 여기에는 $A$의 지수가 1 이상이고 $R(A) \neq R(A^T)$인 경우도 포함된다.
• 직사각형 문제로의 확장: 제안된 방법은 계수 부족(rank-deficient)인 대규모 직사각형 최소제곱 문제(underdetermined 및 overdetermined)로 성공적으로 확장되었다.
• MINRES-QLP와의 비교: 본 논문은 특이 대칭 시스템을 처리하는 것으로 알려진 MINRES-QLP와의 비교 프레임워크를 설정하였으며, MINRES-QLP가 일치하는 시스템에서 최소 노름(min-norm) 해를 찾는 반면, 제안된 방법은 불일치하는 시스템에 대해 더 우수한 성능을 제공함을 언급하였다.

수치 결과
다음과 같은 대상에 대해 광범위한 수치 실험이 수행되었다:

1. GP 불일치 시스템: $R(A) \cap N(A) = \{0\}$이지만 $R(A) \neq R(A^T)$인 지수 1의 행렬들.
2. 지수 2 불일치 시스템: 지수가 2인 행렬들.
3. Underdetermined 최소제곱 문제: 대규모 직사각형 행렬 (예: Maragal, landmarkT, lp dfl001).

결과는 다음과 같이 보여준다:

• 수렴성: $Ax=b$에 직접 적용된 표준 GMRES 및 RRGMRES는 이러한 불일치하고 비-범위-대칭인 시스템에 대해 최소제곱 해로 수렴하지 못하는 경우가 많았다.
• NR-SSOR의 우수성: NR-SSOR 전처리된 RRGMRES는 다른 전처리기(예: $B = \{ \text{diag}(A^TA) \}^{-1}A^T$ 또는 $B = A^T$)와 비교하여 일관되게 현저히 작은 잔차(종종 $10^{-10}$에서 $10^{-15}$ 사이)를 달성하였다.
• 효율성: 제안된 방법은 미전처리 또는 다른 전처리 변형 방식에 비해 훨씬 적은 반복 횟수와 현저히 적은 계산 시간을 필요로 한다 (특정 underdetermined 사례에서 최대 87.9배 빠름).
• MINRES-QLP와의 비교: 불일치 시나리오에서, 제안된 방법은 MINRES-QLP보다 몇 자릿수 더 작은 잔차를 달ach성하였으며 더 적은 반복 횟수 내에 이 최솟값에 도달하였다.

의의
본 논문은 제안된 NR-SSOR 우측 전처리된 RRGMRES가 특이, 비-범위-대칭 시스템 및 계수 부족 직사각형 최소제곱 문제라는 어려운 선형 대수 문제 클래스에 대해 이론적으로 정당화되고 수치적으로 견고한 솔루션을 제공한다고 주장한다. NR-SSOR으로부터 유도된 전처리기 행렬 $C$의 SPD 성질을 증명함으로써, 저자들은 이 방법이 불일치하는 환경에서 발생하는 표준 GMRES의 중단 문제를 피할 수 있음을 보장한다. 수치 실험은 이 접근 방식이 이론적으로 타당할 뿐만 아니라, 불일치 시스템에 대해 잔차 감소 및 계산 속도 측면에서 기존의 AB-GMRES 및 MINRES-QLP를 능가하는 실용적인 효율성을 갖추었음을 검증한다.