Power iteration for matrices with power series entries

기술 요약: 멱급수 성분을 가진 행렬에 대한 거듭제곱 반복법(Power Iteration)

문제 정의
본 논문은 레비-치비타 체(Levi-Civita field) $\mathbb{C}$ 및 퓌조 급수체(Puiseux series field)와 같이 멱급수 성분을 가진 행렬의 고윳값(eigenvalues)과 고유벡터(eigenvectors)를 찾는 문제를 다룬다. 멱급수 상에서의 다항식 해를 구하는 문제는 대수 기하학 및 물리학(예: 해밀토니안 시스템, 전기 회로)에서 잘 연구된 문제이지만, 이러한 체 위에서의 행렬 고윳값 문제를 해결하는 것에 대해서는 연구가 제한적이었다. 특성 다항식의 근을 계산하는 것과 같은 기존 방식은 계산 비용이 많이 드는 것으로 설명된다. 저자들은 표준적인 복소 행렬에 대한 수치적 기법인 고전적인 거듭제곱 반복법(power iteration method)을, 표준적인 수렴 정의가 직접적으로 적용되지 않는 비아르키메데스 체(non-Archimedean fields)에 적응시키는 것을 목표로 한다.

방법론 및 이론적 프레임워크
본 방법론의 핵심은 레비-치비타 체($\mathbb{R}$ 및 $\mathbb{C}$)의 성질에 기초한다. 이 체는 비아르키메데스적이며, 코시 완비적(Cauchy-complete)이고, 실수 폐체(real-closed)이자(단, $\mathbb{C}$의 경우 대수적으로 닫힌 체) 순서 체이다. 저자들은 이 맥락에서 두 가지 유형의 수렴을 구분한다:

1. 강한 수렴(Strong Convergence): 순서 위상(order topology)에 대한 수렴.
2. 약한 수렴(Weak Convergence): 멱급수 표현에 있어 매우 중요한, 계수들의 통상적인 의미에서의 수렴.

저자들은 약한 수렴에 관한 몇 가지 보조 결과들을 확립하였으며, 여기에는 다음이 포함된다:

• "정규" 수열(좌측 유한 지지합을 갖는 수열)에 대한 덧셈 및 곱셈 하에서의 약한 수렴의 연속성.
• 특정 조건(예: $a[0] \neq 0$) 하에서 역수($1/a_k \to 1/a$) 및 제곱근($\sqrt{a_k} \to \sqrt{a}$)의 약한 수렴.
• 지지 집합의 유계 부분 집합 상에서의 계수의 균등 수렴에 기반한 약한 수렴 기준.

거듭제곱 반복 알고리즘
본 논문은 다음 조건 하에서 레비-치비타 체 $\mathbb{C}$ 상의 대각화 가능한 행렬에 대해 거듭제곱 반복법이 약하게 수렴함을 증명한다:

1. 행렬이 최대 유한한 성분을 가진다 (즉, 밸류에이션 $\lambda(a_{ij}) \geq 0$).
2. "복소 부분"(즉, $d^0$ 항의 계수, $\nu[0]$로 표기됨)의 절대값이 가장 큰 고윳값이 유일하게 존재한다.
3. 초기 벡터가 지배적 고유벡터의 방향으로 0이 아닌 성분을 가진다.

구체적으로, 만약 $\nu_1$이 $|\nu_1[0]| > |\nu_2[0]| \geq \dots$를 만족하는 지배적 고윳값이라면, 정규화된 벡터 시퀀스 $x_k / \|x_k\|$는 정규화된 지배적 고유벡터로 약하게 수렴한다. 또한, 레이리 몫(Rayleigh quotient) $u_k^* A u_k / \|u_k\|^2$는 지배적 고윳값으로 약하게 수렴한다.

처음에 "최대 유한" 조건을 만족하지 않거나 지배적 고윳값을 즉시 파악할 수 없는 행렬을 처리하기 위해, 저자들은 다음과 같은 스케일링 전략을 제안한다:

• 행렬 성분을 최소 밸류에이션 $q_0$만큼 이동시켜 $A' = d^{-q_0}A$인 행렬을 생성한다.
• "복소 부분" 행렬 $\pi(A')$(즉, $0$-차 계수들의 행렬)을 분석한다.
• 만약 $\pi(A')$가 지배적 고윳값을 가진다면, 원래 행렬의 지배적 고윳값과 고유벡터를 찾기 위해 스케일링된 행렬에 거듭제곱 반복법을 적용할 수 있다.

이 접근법은 레비-치비타 체의 부분체인 퓌조 급수체로 확장되어, 퓌조 급수 성분을 가진 행렬에도 적용될 수 있다.

주요 결과

• 정리 5.5: (무한히 크거나 작은 성분을 가질 수 있는) 대각화 가능한 행렬 $A$가 스케일링되어 그 "복소 부분" 행렬이 엄격하게 지배적인 고윳값을 가질 수 있다면, 거듭제곱 반복법이 가장 큰 모듈러스 고윳값과 그에 대응하는 고유벡터를 성공적으로 찾아낸다는 것을 확립한다.
• 따름정리 5.7: 이 방법이 퓌조 급수체 상의 대각화 가능한 행렬에 적용되어, 동일한 체 내에서 결과를 산출함을 확인한다.
• 수렴 증명: 본 논문은 레비-치비타 체에서의 수열의 정규성과 대수적 연산의 연속성을 활용하여, 벡터 시퀀스와 레이리 몫의 약한 수렴에 대한 엄밀한 증명을 제공한다.

구현 및 실험 결과
저자들은 알고리즘을 Python으로 구현하였다. 이들은 퓌조 급수체 $\mathbb{R}\{\{t\}\}$ 상의 차수가 21인 다항식의 동반 행렬(companion matrix)에 대해 방법을 테스트하였다.

• 복잡도: 동반 행렬의 경우, 시간 복잡도는 $O(n d_t \log(d_t))$로 추정되며 ($n$은 행렬 차원, $d_t$는 성분 내 변수 $t$의 최대 차수), 임의의 행렬의 경우 $O(n^2 d_t \log(d_t))$이다.
• 성능: 특정 테스트 케이스(차수 21 다항식)에서, 알고리즘은 100회의 반복을 통해 가장 큰 근(약 $100 + t + \dots$로 근사됨)에 수렴하였다. 오차는 유의미하게 감소하여 대부분의 성분에 대해 $10^{-12}$에서 $10^{-14}$의 크기에 도달하였다. 실행 시간은 100회 반복에 대해 Lenovo p50에서 약 135초가 소요되었다.
• 관찰 사항: 저자들은 수정된 버전의 알고리즘을 통해 성능을 크게 향상시킬 수 있다고 언급하였다. 또한 나머지 벡터들을 찾거나 모든 벡터를 동시에 찾기 위한 보완 도구로서 역 벡터 반복법(inverse vector iteration), 부분 공간 반복법(subspace iteration), 그리고 QR 알고리즘의 구현을 언급하였다.

의의 및 주장
본 논문은 멱급수 성분을 가진 행렬을 위해 특별히 설계된 최초의 거듭제곱 반복 알고리즘을 제공한다고 주장한다. 저자들은 이 방법이 이론적으로 흥미로울 뿐만 아니라, 다변수 다항식의 근을 찾기 위한 추가적인 수치적 접근법 개발의 문을 열어준다고 상정한다. 이러한 새로운 접근법들이 특성 다항식의 근을 계산하는 데 의존하는 기존 방식들에 비해 더 나은 안정성과 효율성을 제공할 수 있음을 시사한다. 이 연구는 멱급수가 흔히 사용되는 대수 기하학과 수치 선형 대수 사이의 간극을 메우며, 근본적인 반복법을 비아르키메데스 체에 적응시킨다.