Flexible GMRES converges in two phases

스테판 귤텔과 라우리 니만의 논문 "유연한 GMRES 는 두 단계로 수렴한다"에 대한 상세한 기술적 요약입니다.

1. 문제 제기

유연한 GMRES(FGMRES) 알고리즘은 가변적인 전구조건부 (variable preconditioning) 를 허용하는 대규모 선형 시스템 $Ax=b$를 위한 표준 반복 솔버입니다. 이러한 유연성은 전구조건부$M_j$자체가 반복 방법일 때 (예: 뉴턴 - 크릴로프 방법) 또는 행렬$A$ 가 행렬 - 벡터 곱을 통해서만 접근 가능한 경우에 특히 중요합니다.

그럼에도 불구하고 FGMRES 의 수렴 이론은 여전히 잘 이해되지 않고 있으며, 특히 내부 전구조건부의 잔차 허용오차 ($\mu$) 가 외부 FGMRES 루프의 수렴에 미치는 영향에 대해서는 더욱 그렇습니다.

• 간극: 기존 표준 GMRES 의 수렴 경계는 잔차의 다항식 표현에 의존하는데, 이는 가변적인 전구조건부 때문에 검색 공간이 표준 크릴로프 부분공간이 아니므로 FGMRES 에서는 성립하지 않습니다.
• 질문: FGMRES 는 전구조건부의 허용오차 $\mu$ 비율로 기하급수적으로 수렴하는가, 아니면 반복이 진행됨에 따라 수렴 거동이 변하는가? 이 방법이 정체 (stagnate) 될 수 있는가?

2. 방법론

저자들은 FGMRES 와 유연한 전체 직교화 방법 (FFOM) 간의 관계에 기반한 엄밀한 수렴 분석을 개발했습니다.

• 재귀적 경계 유도:

  • 저자들은 FGMRES 잔차 ($r^{FG}_m$) 와 FFOM 잔차 ($r^{FF}_{m-1}$) 를 전구조건부 잔차 ($r^P_m$) 와 결합하여 재귀적 관계를 수립했습니다.
  • $r^{FG}_m \perp \text{span}(AZ_m)$이라는 성질을 이용하여 다음 부등식을 유도했습니다:
    $$\|r^{FG}_m\| \leq \|r^{FF}_{m-1}\| \cdot \|r^P_m\|$$
  • 그들은 연속된 FGMRES 잔차의 비율과 관련된 기하학적 항등식을 통해 FFOM 과 FGMRES 잔차를 연관 짓고, 축소 계수 $\gamma_m$에 대한 재귀적 경계를 도출했습니다:
    $$\|r^{FG}_m\| \leq \gamma_m \|r^{FG}_{m-1}\|, \quad \text{여기서 } \gamma_m = \frac{\|r^P_m\|}{\sqrt{1 - \gamma_{m-1}^2}}$$

• 체비셰프 다항식을 통한 명시적 해:

  • 전구조건부 잔차에 대한 균일한 경계 $\|r^P_j\| \leq \mu$를 가정하고 축소 계수에 대한 재귀 관계를 분석했습니다.
  • 재귀 관계를 선형 시스템으로 변환함으로써, 축소 계수의 곱이 **제 2 종 체비셰프 다항식 ($U_m$)**과 관련됨을 확인했습니다.
  • 이를 통해 잔차 노름에 대한 폐형식 **사전적 상한 (a priori upper bound)**을 유도할 수 있었습니다.

• 최적성 (Sharpness) 구성:

  • 경계가 "최적 (sharp)"함을 증명하기 위해 (즉, 개선될 수 없음을 보이기 위해), 저자들은 구체적인 반례를 구성했습니다. 그들은 임의의 선형 시스템과 임의의 $\mu \leq 1/2$에 대해, FGMRES 잔차가 유도된 상한과 정확히 일치하는 전구조건부 시퀀스 (및 특정 행렬 $A$) 가 존재함을 보여주었습니다.

3. 주요 기여

A. 두 단계 수렴 거동

이 논문의 핵심 발견은 FGMRES 수렴이 전구조건부 허용오차 $\mu$에 의존하여 두 가지 뚜렷한 단계로 지배된다는 것입니다:

1. 1 단계 (초기 기하급수적 수렴):

   • 작은 반복 횟수 $m$에서 수렴률은 대략 $\mu$입니다.
   • $\|r^{FG}_m\| \approx \mu \|r^{FG}_{m-1}\|$.
   • 이 단계는 $\mu$가 작을 때 (예: $\mu \ll 0.5$) 지배적입니다.

2. 2 단계 (열화 또는 정체):

   • $m$이 증가함에 따라 수렴률은 $\mu$에서 새로운 점근적 속도 $\nu$로 열화됩니다.
   • 점근적 속도는 다음과 같습니다:
     $$\nu = \sin\left(\frac{1}{2} \arcsin(2\mu)\right)$$
   • $\mu \leq 0.5$인 경우: 속도 $\nu$는 $\mu$보다 약간 큽니다 (예: $\mu=0.1$이면 $\nu \approx 0.1005$). 매우 작은 $\mu$의 경우 속도는 실질적으로 일정하게 유지됩니다. 그러나 $\mu \to 0.5$로 갈수록 속도는 현저히 열화되어 $\nu \approx \sqrt{\mu}$에 접근합니다.
   • $\mu > 0.5$인 경우: 이 방법은 초기 감소 단계 후 정체되거나 붕괴될 수 있습니다. "정체 지수 (stalling index)" $m^*$ (정체 발생 전 반복 횟수) 는 $\mu$가 0.5 를 초과함에 따라 급격히 감소합니다.

B. 최적 상한

저자들은 $m$단계에서의 잔차에 대한 다음과 같은 최적 상한을 유도했습니다 ($\mu \leq 1/2$ 가정):
$$\|r^{FG}_m\| \leq \|r_0\| \frac{\mu^{m/2}}{\sqrt{U_m\left(\frac{1}{2\mu}\right)}}$$
여기서 $U_m$은 제 2 종 체비셰프 다항식입니다.

• 이 경계는 **달성 가능 (attainable)**합니다: 저자들은 등식이 성립하는 선형 시스템과 전구조건부 시퀀스가 존재함을 증명했습니다.
• 이는 유도된 경계가 주어진 가정 하에서 FGMRES 에 대한 최악의 시나리오를 나타낸다는 것을 의미합니다.

C. 수렴 보장 조건

이 논문은 중요한 임계값을 확립했습니다: FGMRES 는 $\mu \leq 1/2$일 때만 정확한 해로 수렴이 보장됩니다 (정체 없이).

• $\mu > 1/2$인 경우, 이론적 경계는 정체를 허용하며, 저자들은 특정 시스템에서 실제로 정체가 발생할 수 있음을 보여주었습니다.

4. 결과 및 수치적 증명

이론적 발견은 MATLAB 을 통한 수치 실험으로 검증되었습니다:

1. 최적성 검증: 내부 GMRES(100) 전구조건부 ($\mu=0.5$) 를 가진 구성된 $2500 \times 2500$ 시스템에서 계산된 FGMRES 잔차가 이론적 상한과 정확히 일치하여 경계가 엄밀함을 확인했습니다.
2. 정체 예시: $\mu = 0.55$인 경우, 잔차는 초기에 감소했으나 6 회 반복 후 정체되어 예측된 "정체 지수"와 일치했습니다.
3. 실제 적용: 3 차원 푸아송 문제 (유한 요소 이산화) 에서의 대규모 희소 행렬에 대해, 새로운 경계는 FGMRES-GMRES 의 실제 수렴 거동을 밀접하게 추적하여 비구성 시스템에서도 실용적 관련성을 입증했습니다.

5. 중요성 및 함의

• 이론적 돌파구: 이는 가변적인 전구조건부 허용오차를 명시적으로 고려한 FGMRES 에 대한 최적이자 달성 가능한 상한을 제공하는 첫 번째 연구입니다. 좋은 내부 솔버에도 불구하고 FGMRES 가 때때로 기대보다 느리게 수렴하는 이유에 대한 수수께끼를 해결합니다.
• 튜닝을 위한 실용적 지침:
  • 전구조건부를 튜닝할 수 있는 경우 (예: 목표 잔차 $\mu$ 설정), 결과는 $\mu \leq 0.5$를 유지하는 것이 수렴 보장에 필수적임을 시사합니다.
  • 매우 엄격한 허용오차 ($\mu \ll 0.5$) 의 경우, 두 단계 거동은 미미하며 방법은 $\mu$ 속도로 기하급수적으로 수렴합니다.
  • 느슨한 허용오차 ($\mu \approx 0.5$) 의 경우, 사용자는 반복 횟수가 증가함에 따라 수렴 속도가 둔화될 것으로 예상해야 합니다.
• 재시작 GMRES 와의 비교: 논문은 재시작 GMRES 가 이론적 수렴 속도 $O(\mu^j)$를 가지지만, 내부 솔버가 축소된 우변을 보게 되는 축소 (deflation) 효과로 인해 FGMRES 가 실제로는 종종 더 우수하게 수행된다고 지적합니다. 그러나 $\mu$가 0.5 에 가까울 때 FGMRES 의 최악의 경우 경계는 재시작 GMRES 경계보다 엄격히 더 나쁘므로, 유연성과 최악의 경우 안정성 사이의 트레이드오프가 있음을 강조합니다.
• 한계: 분석은 $\|r^P_j\| \leq \mu$가 일정하다고 가정합니다. 저자들은 무작위 스키칭을 사용하는 "fastGMRES"와 같은 방법은 변동하는 $\mu$를 가질 수 있음을 인정하며, 이러한 경우로 분석을 확장하는 것은 여전히 열린 과제로 남아 있습니다.

요약하자면, 이 논문은 FGMRES 가 두 단계로 작동함을 증명하고, 엄밀한 수학적 경계와 수치적 증거를 바탕으로 보장된 수렴을 위한 엄격한 한계 ($\mu \leq 0.5$) 를 확립함으로써 FGMRES 수렴에 대한 결정론적 특성을 제공합니다.