Stabilizing randomized GMRES through flexible GMRES

기술적 요약: 유연한 GMRES 를 통한 무작위화 GMRES 의 안정화

문제 제기
본 논문은 무작위화 크릴로프 부분공간 방법을 사용하여 대규모 희소 선형 시스템 $Ax = b$를 해결하는 데 따른 과제를 다룹니다. 무작위화는 저랭크 행렬 근사 및 과결정 최소제곱 문제에 매우 효과적으로 입증되었으나, 일반적인 비대칭 선형 시스템에 적용하는 것은 더 어렵습니다. 과결정 시스템과 달리 일반적인 선형 시스템은 내재된 중복성이 부족하여, 모든 행렬 구성 요소의 섭동에 대해 해 벡터가 민감하게 반응합니다. 따라서 "문제를 스케치 (sketching)"하는 것보다 "알고리즘을 스케치"하는 것이 더 실현 가능합니다.

기존의 무작위화 크릴로프 솔버인 스케치된 GMRES(sGMRES) 는 스케칭 연산자 $S$를 사용하여 문제를 저차원 공간으로 투영함으로써 표준 GMRES 와 관련된 비싼 직교화 비용을 줄이려는 목표를 가집니다. 그러나 sGMRES 는 안정성 문제를 겪습니다. 구체적으로, 잘려진 Arnoldi 과정을 사용하여 비직교 크릴로프 기저를 생성할 때, 기저가 매우 조건이 나빠져 정지 (stagnation) 나 수치적 불안정성을 초래할 수 있습니다. sGMRES 를 재시작 (restarting) 하는 것은 일반적인 해결책이지만, 재시작 길이가 허용 불가능할 정도로 커야 수렴할 수 있는 어려운 문제의 경우 종종 수렴에 실패합니다.

방법론
저자들은 **유연한 GMRES(FGMRES)**를 외부 래퍼로 사용하여 **스케치된 GMRES(sGMRES)**를 안정화하는 하이브리드 접근법을 제안합니다. 핵심 방법론은 다음과 같은 구성 요소를 포함합니다:

1. 이론적 기반 (FGMRES 잔차 상한):
   저자들은 FGMRES 잔차에 대한 새로운 실용적인 상한을 유도합니다. 완전 직교화 방법 (Full Orthogonalization Method) 의 유연한 버전인 FFOM 을 도입함으로써, $m$번째 반복에서의 FGMRES 잔차 $\|r_m\|$는 이전 반복의 FFOM 잔차와 내부 전처리기 잔차의 곱으로 제한됨을 확립합니다:
   $$\|r_m\| \le \|r_{m-1}^{\text{FFOM}}\| \cdot \|r_m^{\text{precond}}\|$$
   이 상한은 내부 솔버 (전처리기) 가 잔차를 효과적으로 줄인다면, FGMRES 와 FFOM 잔차가 비교 가능하게 유지되는 한 외부 FGMRES 반복도 전역 잔차를 줄일 것임을 시사합니다. 이 이론적 결과는 내부 솔버가 불안정하더라도 FGMRES 를 사용하여 비감소 잔차 노름을 보장하는 것을 정당화합니다.

2. 알고리즘 구조 (FGMRES-sGMRES):
   제안된 알고리즘인 fastGMRES는 다음과 같이 작동합니다:

   • 외부 루프: FGMRES 반복을 실행합니다.
   • 내부 루프 (전처리기): 각 외부 반복 $j$에서, 전처리기 $M_j$는 $k$번의 sGMRES 반복을 통해 계산된 $Az = v_j$의 근사 해입니다.
   • sGMRES 구현: 내부 sGMRES 솔버는 잘려진 Arnoldi 과정 (마지막 $t$개의 벡터에 대해서만 직교화) 을 사용하여 크릴로프 기저 $B_k$를 구성합니다. 해 $z_j$는 $B_k$의 범위 내에서 스케치된 잔차 $\|S(v_j - Az)\|$를 최소화함으로써 구해집니다.
   • 정지 기준: 내부 sGMRES 루프는 세 가지 조건에 따라 종료됩니다:
     1. 메모리를 제어하기 위한 최대 반복 제한 $k_{\max}$ (예: 500).
     2. 심한 조건 불량을 방지하기 위한 스케치된 기저 $SAB_k$의 조건수 임계값 (예: $10^{15}$).
     3. 추정된 FGMRES 잔차 상한이 목표 허용 오차 이하로 떨어지는 것.

3. 파라미터화:
   이 방법은 최소한의 파라미터 튜닝을 요구합니다. 주요 파라미터는 Arnoldi 잘림 파라미터 $t$입니다. 저자들은 $t=0$(직교화 없는 순수 멱 기저) 에서 $t=5$까지를 조사합니다.

주요 기여

• 안정화 메커니즘: 본 논문은 sGMRES 를 FGMRES 외부 루프로 감싸는 것이 무작위화 솔버를 효과적으로 안정화함을 보여줍니다. 외부 루프는 재시작된 sGMRES 의 전형적인 정지 문제를 극복하고 비감소 잔차 노름을 보장합니다.
• 새로운 잔차 상한: $\|r_m\| \le \|r_{m-1}^{\text{FFOM}}\| \cdot \|r_m^{\text{precond}}\|$ 상한의 유도는 방법론의 견고성에 대한 이론적 정당성을 제공하며, 내부 솔버의 성능에 기반한 수렴 예측을 위한 실용적 도구를 제공합니다.
• 간단함과 견고성: 제안된 "fastGMRES" 방법은 매우 적은 사용자 입력을 요구합니다. 부분공간 크기와 제거된 (deflated) 벡터 수의 신중한 선택이 필요한 다른 제거 재시작 방법 (예: GMRES-SDR 또는 RGS-GMRES-MDR) 과 달리, fastGMRES 는 고정된 파라미터 ($t=0$ 또는 작은 $t$, 고정된 스케칭 차원) 로 견고하게 작동합니다.
• $t=0$를 통한 효율성: 저자들은 잘림 파라미터를 $t=0$(내부 루프에서 직교화 없음) 으로 설정하는 것이 종종 시간 대비 해 도출 성능을 최적화한다는 반직관적인 발견을 보고합니다. 특히 행렬 - 벡터 곱이 저렴한 문제에서 두드러집니다.

수치적 결과
저자들은 SuiteSparse Matrix Collection 및 기타 벤치마크의 여러 까다로운 문제에 대해 이 방법을 평가했습니다:

• vas stokes 1M: 재시작된 sGMRES 가 정지하는 어려운 문제입니다. FGMRES 로 안정화된 버전은 꾸준히 수렴합니다. 이 방법은 재시작된 sGMRES 를 크게 능가하며, 더 적은 파라미터 선택에도 불구하고 GMRES-SDR 및 RGS-GMRES-MDR 과 경쟁력을 가집니다.
• NACA12: 이 방법은 ILU 전처리 유무와 관계없이 견고하게 수렴합니다. 특히, 다른 방법들이 어려움을 겪거나 시간 초과가 발생하는 전처리 없는 경우에도 $t=0$가 여전히 가장 빠른 구성입니다.
• ML Geer: 대규모 문제 ($n \approx 150$만). 이 방법은 테스트된 모든 $t$에 대해 견고하게 수렴하지만, 외부 FGMRES 직교화 비용의 증가로 인해 $t=0$는 후속 반복에서 약간의 지연을 보입니다.
• 벤치마킹: 10 개의 문제에 대한 BiCGSTAB, GMRES, GMRES-DR, GMRES-SDR 과의 비교에서 fastGMRES 는 가장 신뢰할 수 있는 방법 중 하나입니다. 시간 제한 내에 수렴하지 못한 문제는 하나뿐이었으며 (이 경우 다른 모든 방법도 실패함), BiCGSTAB 은 두 개에서 실패했습니다. 신중하게 튜닝된 파라미터를 가진 GMRES-SDR 이 때때로 더 빠르지만, fastGMRES 는 파라미터 튜닝 없이도 비교 가능한 성능을 달성합니다.

의의 및 주장
본 논문은 FGMRES 와 sGMRES 의 결합이 효율성, 견고성, 사용 편의성을 균형 있게 갖춘 "실용적인 무작위화 솔버"를 제공한다고 주장합니다. 그 의의는 다음과 같습니다:

1. 신뢰성: 무작위화 또는 재시작된 크릴로프 방법에서 종종 손실되는 비감소 잔차 노름을 보장합니다.
2. 낮은 튜닝 오버헤드: 다른 고급 크릴로프 방법을 괴롭히는 제거 횟수나 재시작 길이와 같은 복잡한 파라미터 선택의 필요성을 제거합니다.
3. 계산 효율성: $t=0$의 놀라운 효과는 내부 루프에서 내적을 피하는 것이 특히 직교화를 위한 통신이 병목이 되는 병렬 컴퓨팅 및 혼합 정밀도 시나리오에서 매우 유익할 수 있음을 시사합니다.

저자들은 이 방법이 항상 최적 튜닝된 기존 솔버를 능가하는 것은 아니지만, 다양한 까다로운 선형 시스템 전반에 걸쳐 견고한 "설정 후 잊기 (set-and-forget)" 대안을 제공한다고 결론지었습니다. 향후 연구로는 매우 큰 반복 횟수에 대한 외부 루프의 직교화 비용을 완화하기 위해 다중 수준 FGMRES 구조를 탐구할 것을 제안합니다.