Convergence analysis of a nonlinear eigensolver based on rational approximation of the resolvent

기술 요약: 분해수(Resolvent)의 유리 근사를 기반으로 한 비선형 고유값 솔버의 수렴 분석

문제 정의
본 논문은 홀로모픽(holomorphic) 행렬 함수 $T$에 대하여 $T(\lambda)v = 0$ 형태를 갖는 비선형 고유값 문제(Nonlinear Eigenvalue Problems, NEPs)를 해결하는 데 따르는 과제를 다룬다. 저자들은 분해수 $T^{-1}$의 유리 근사를 통해 고유값을 식별하는 특정 클래스의 고유값 솔버에 초점을 맞춘다. AAA(Adaptive Antoulas-Anderson) 알고리즘을 사용하여 유리 근사를 수행하는 이 방식은 유연한 프레임워크를 제공하지만, 다음과 같은 두 가지 주요 한계점을 가진다:

1. 정확도 저하: 샘플 지점에서 고정밀 유리 근사가 이루어지더라도, 계산된 극점(고유값)은 특히 내부 고유값이나 높은 중복도를 가진 고유값의 경우 높은 정확도를 확보하지 못하는 경우가 많다.
2. 중복도 탐지: 표준적인 스칼라 프로빙 벡터(probing vectors) 방식은 고유값의 중복도를 탐지하는 데 실패한다. 이는 결과적으로 도출된 스칼라 분해수가 기저의 대수적 중복도와 관계없이 단순 극점(simple poles)만을 나타내기 때문이다.

방법론
제안된 접근 방식은 무작위 프로빙 행렬 $\Omega_L$과 $\Omega_R$을 사용하여 분해수를 스케칭(sketching)함으로써 "대리 함수(surrogate function)" $F(z)$를 구성한다:
$$F(z) := \Omega_L^H T(z)^{-1} \Omega_R$$
알고리즘은 세 가지 주요 단계로 진행된다:

1. 블록 프로빙(Block Probing): 스칼라 벡터 대신 $n \times b$ 크기의 프로빙 행렬을 사용한다. 이러한 수정은 스펙트럼 정보에 관한 고유값의 중복도를 보존하고 수치적 강건성을 향상시키도록 설계되었다.
2. 유리 근사(Rational Approximation): (집합 값) AAA 알고리즘을 $F(z)$에 적용하여 바리센트릭(barycentric) 유리 근사 $R(z)$를 생성한다.
3. 줌인(Zooming In): 많은 고유값이 포함된 영역을 처리하기 위해, 알고리즘은 계산 영역 $D$를 더 작은 하위 영역으로 재귀적으로 세분화한다. 근사의 극점 수를 줄여 정확도를 높이기 위해 더 작은 영역에 대해 극점 찾기 절차를 적용한다.

최종 단계는 바리센트릭 형태로부터 유도된 일반화된 고유값 문제를 풀어 $R(z)$의 극점을 찾는 것이다.

주요 기여 및 이론적 결과
본 논문은 이 방법의 안정성과 정확도에 관한 세 가지 근본적인 질문을 다루는 엄밀한 수렴 분석을 제공한다:

1. 블록 프로빙을 통한 스펙트럼 회복 (섹션 2):

   • 저자들은 블록 크기 $b$가 고유값의 기하학적 중복도보다 크거나 같으면, 대리 함수 $F(z)$가 모든 필수적인 스펙트럼 정보를 유지함을 입증한다.
   • 정리 2.3은 $F(z)$의 특이값(singular values)이 고유값 $\lambda_i$ 근처에서 부분 대수적 중복도에 의해 결정되는 속도로 발산함을 보여주며, 이를 통해 중복도 정보를 회복할 수 있음을 나타낸다.
   • 정리 2.7은 블록 프로빙이 스케칭 과정(즉, 스케칭된 계수 행렬이 0이 되는 현상)으로 인해 고유값을 "놓칠" 확률을 크게 줄이며, 이는 벡터 기반 프로빙보다 더 강력한 반집중(anti-concentration) 경계를 제공함을 증명한다.

2. 극점의 수렴 및 줌인의 효과 (섹션 3):

   • 정리 3.2는 극점의 수렴을 정량화하며, 중복도 $m$을 가진 계산된 극점의 정확도는 영역이 클 경우 $O(u^{1/m})$(여기서 $u$는 머신 정밀도)로 제한됨을 보여준다. 이는 왜 단순한 접근 방식이 고중복도 고유값에 대해 낮은 정확도를 보이는지를 설명한다.
   • 저자들은 "줌인" 기술을 분석하여, 영역의 지름 $\delta$를 줄이는 것이 계산된 고유값의 정확도를 선형적으로 개선하여 $O(u^{1/m})$의 한계를 효과적으로 완화함을 입증한다.
   • 정리 3.4는 여러 개의 극점이 존재하는 영역에 대한 수렴 결과를 제공하며, 정확도가 영역 내의 극점 수에 크게 의존함을 보여준다. 이는 영역을 분할하는 것(하위 영역당 극점 수를 줄이는 것)이 특히 블록 프로빙과 결래될 때 상당한 정확도 향상을 가져온다는 것을 이론적으로 정당화한다.

3. 극점 찾기의 안정성 (섹션 4):

   • 저자들은 바리센트릭 형태로부터 유도된 일반화된 고유값 문제를 통해 유리 근사의 근을 찾는 과정의 후방 안정성(backward stability)과 전방 안정성(forward stability)을 분석한다.
   • 정리 4.3은 계산된 극점이 동시에 너무 많은 중복 지점(support points)에 가깝지 않다는 조건 하에 후방 안정성을 확립한다.
   • 정리 4.4는 전방 안정성을 규명하며, 중복도 $m$인 고유값에 대해 달성 가능한 최선의 전방 오차는 $O(u^{1/m})$임을 확인하여, 이는 고전적인 밀집(dense) 고유값 솔버와 일치한다.

결과
수치 실험은 이론적 발견을 검증한다:

• Toy Example: 고유값이 서로 다른 대각 행렬에 대해, 단순한 접근 방식(스칼라 프로빙, 단일 영역)은 $10^{-14}$에서 $10^{-13}$ 정도의 오차를 보이며, 최하위 자리수에서 잘못된 숫자를 산출한다.
• 개선된 접근 방식: 블록 프로빙(크기 2)과 줌인(영역 세분화)을 적용하면 최소 15자리의 정확도로 고유값을 회복한다.
• Butterfly Problem: 특정 영역 내에 61개의 고유값이 존재하는 복잡한 NEP에서, 블록 프로빙과 영역 세분화의 결합은 단일 큰 영역을 사용할 때보다 최대 오차를 유의미하게 감소시켜, 극점 클러스터를 분리하는 것이 정확도 향상에 도움이 됨을 확인시켜 준다.

의의
본 논문은 분해수 기반 고유값 솔버에서 블록 프로빙과 줌인이 제공하는 정확도 향상을 설명하는 첫 번째 이론적 분석이라고 주장한다. 이는 다음을 명확히 한다:

• 블록 프로빙은 중복도를 탐지하기 위해서뿐만 아니라, 스케칭 과정에서 손실될 수 있는 스펙트럼 모드를 견고하게 회복하기 위해서도 필요하다.
• "줌인" 기술은 근사의 극점 밀도를 줄임으로써 정확도를 선형적으로 개선하는 방법으로서 이론적으로 정당화되며, 이는 정리 3.2에서 식별된 수렴 한계를 직접적으로 해결한다.
• 샘플링 지점이 잘 분포되어 있고 일반화된 고유값 문제가 안정적으로 풀린다면, 이 방법은 후방 및 전방 안정성을 갖는다.

저자들은 이론적 분석은 완료되었으나, 가짜 극점(Froissart doublets)을 제거하기 위한 견고한 클린업(cleanup) 절차 구현은 향후 연구 과제로 남아 있다고 언급하였다.