Linear convergence of iterative contour integral-based eigensolvers for nonlinear eigenvalue problems

기술 요약: 비선형 고유값 문제에 대한 반복적 윤곽 적분 기반 고유값 솔버의 선형 수렴성

문제 정의
본 논문은 홀로모픽 행렬 함수 $T(\cdot)$에 대하여 $T(\lambda)u = 0$ 형태를 갖는 비선형 고유값 문제(Nonlinear Eigenvalue Problems, NEPs)를 해결하는 과제를 다룹니다. 윤곽 적분 기반 방법들은 주어진 영역 $D \subset \mathbb{C}$ 내의 모든 고유값을 신뢰성 있게 타겟팅할 수 있다는 점에서 매력적이지만, Beyn의 방법이나 비선형 Sakurai–Sugiura(SS) 방법과 같은 전통적인 접근 방식들은 내재적인 반복 정밀화 메커니즘이 부족합니다. 결과적으로, 이러한 방법들에서 높은 정확도를 달족하기 위해서는 이산화 오차를 줄이기 위해 quadrature node의 수를 늘려야 하며, 이는 반복적인 행렬 분해를 필요로 하기 때문에 막대한 계산 비용으로 이어집니다. 반면, NLFEAST 알고리즘은 윤곽 적분에 비선형 Rayleigh–Ritz 추출 단계를 결합하여 경험적으로 반복법처럼 동작하지만, 그 이론적 수렴 특성은 그동안 충분히 이해되지 않은 상태로 남아 있었습니다.

방법론 및 프레임워크
저자들은 기존의 방법들을 통합하고 수렴 분석을 용이하게 하는 반복적 윤곽 적분 기반 고유값 솔버(Algorithm 1)를 위한 일반적인 프레임워크를 제안합니다. 이 프레임워크는 반복당 두 단계의 교차 과정을 거칩니다:

1. 추출(Extraction): 부분 공간 $X^{(k)}$가 주어지면, Rayleigh–Ritz 절차를 사용하여 근사 고유쌍 $(\rho_i^{(k)}, x_i^{(k)})$을 추출합니다.
2. 필터링(Filtering): 새로운 부분 공간 $X^{(k+1)}$을 생성하기 위해 근사 고유벡터에 필터 연산자 $F_{it}(\rho_i^{(k)})$를 적용합니다. 이 필터는 스펙트럼 투영(spectral projector)의 윤곽 적분 표현으로부터 유도된 연속 연산자 $F_{ci}(\rho)$의 이산화된 근사치입니다.

연속 연산자 $F_{ci}(\rho)$는 다음과 같이 정의됩니다:
$$F_{ci}(\rho) := \frac{1}{2\pi i} \oint_{\partial D} \frac{1}{\xi - \rho} \left( I - T(\xi)^{-1}T(\rho) \right) d\xi$$
저자들은 Keldysh의 정리를 사용하여 이 연산자의 스펙트럼 특성을 규명하며, 이 연산자가 타겟 고유 공간 외부의 성분들을 제거하는 동시에 내부의 성분들은 보존함을 보여줍니다.

주요 기여 및 이론적 결과
본 논문의 주요 기여는 이 프레임워크에 대한 엄격한 수렴 이론을 확립한 것입니다:

• 반복 정밀화를 위한 필요 조건: 저자들은 반복법이 수렴하기 위해서는 필터가 근사 고유벡터를 타겟 불변 부분 공간 $U_D$로 매핑해야 함을 입증합니다. 그들은 표준 이산화 방식(예: Beyn의 방법에서 사용되는 방식)이 이 조건을 충족하지 못함을 증명하는데, 이는 이산화된 펜실(pencil) $M_{1,N} - \xi M_{0,N}$이 quadrature가 정확하지 않는 한 정확한 NEP와 동일한 불변 부분 공간을 공유하지 않기 때문입니다. 이는 왜 Beyn의 방법이 반복만으로는 정확도를 개선할 수 없는지를 설명합니다.
• 선형 수렴을 위한 충분 조건 (Theorem 6): 단순 고유값(simple eigenvalues) 및 선형 독립인 고유벡터라는 완만한 가정 하에, 저자들은 필터 패밀리가 특정 점근적 오차 경계(즉, "부분 공간 외" 성분의 오차가 인자 $\gamma_N$에 의해 감소함)를 만족하면 알고리즘이 국소 선형 수렴을 보임을 증명합니다. 구체적으로, 계산된 부분 공간과 정확한 고유 공간 사이의 각도는 $\angle(X^{(k+1)}, U_D) = O(\gamma_N \angle(X^{(k)}, U_D))$와 같이 선형적으로 감소합니다.
• NLFEAST의 수렴성 (Theorem 7 & Corollary 8): 저자들은 이 이론을 NLFEAST 알고리즘에 적용합니다. NLFEAST에서 정의된 특정 필터 구조(지시 함수(indicator function)의 유리 근사와 잔차 역 반복(residual inverse iteration) 개념의 결합)를 활용하여, 저자들은 NLFEST가 선형 수렴을 위한 필요 조건을 만족함을 증명합니다. 수렴 속도는 quadrature node의 수 $N$에 따라 지수적으로 감소하는 quadrature 오차 $\gamma_N$에 달려 있습니다.

수치 결과
이론적 발견은 NLEVP 컬렉션의 9가지 도전적인 NEP와 특정 광학(photonic) 문제에 대한 광범한 수치 실험을 통해 검증되었습니다:

• 수렴 동작: 실험은 NLFEAST가 높은 정확도에 도달할 때까지 잔차가 꾸준히 감소하며 선형 수렴을 달성함을 확인시켜 줍니다. 이는 제한된 수의 quadrature node를 사용하더라도 가능합니다.
• Beyn의 방법과의 비교: 직접적인 비교에서, NLFEAST는 높은 정확도에 도달하는 데 필요한 계산 시간 측면에서 Beyn의 방법을 크게 능가합니다. Beyn의 방법은 정확도를 높이기 위해 $N$을 증가시켜야 하는 반면(따라서 행렬을 재분해해야 함), NLFEAST는 첫 번째 반복에서 계산된 행렬 $T(\xi_j)$의 LU 분해를 재사용하며, 이후 단계에서는 더 저렴한 삼각 행렬 풀이(triangular solves)에 의존합니다.
• 강건성: 본 방법은 서로 다른 고유값에 대응하는 고유벡터들이 선형 종속인 경우(예: 동일한 좌 또는 우 고유벡터를 공유하는 경우)에도 압축된 NEP에 대한 신뢰할 수 있는 솔버를 사용하는 한 강건함을 유지함을 보여줍니다.

의의 및 주장
본 논문은 NLFEAST의 선형 수렴에 대한 최초의 이론적 정당성을 제공하며, 왜 NLFEAST는 효과적인 반복법으로 작동하는 반면 다른 윤곽 적분 기반 접근 방식(Beyn의 방법 등)은 그렇지 못한지를 명확히 합니다. 저자들은 특정 방법들이 반복을 통한 수렴에 실패하는 이유를 설명합니다. 즉, 이러한 방법들은 quadrature 오차로 인해 부분 공간 다양체(subspace manifold) 내에 고정점(fixed point)을 갖지 못합니다.

이 연구의 의의는 높은 정확도의 NEPs를 달성하기 위해 quadrature node를 무한히 늘리는 과도한 비용 없이도 가능하다는 것을 입증한 데 있습니다. 대신, NLFEAST와 같이 반복 정밀화(iterative refinement)를 결합한 적절한 수의 노드를 사용하는 것이 충분합니다. 저자들은 이 프레임워크가 향상된 특성을 가진 새로운 반복적 비선형 고유값 솔버를 설계하는 경로를 열어준다고 결론짓지만, 동시에 수렴 조건을 만족하는 필터를 구축하는 것이 여전히 도전적인 과제이며 현재로서는 NLFEAST가 이 프레임워크에 부합하는 주요 사례임을 겸허히 언급합니다.