The shift-and-invert Arnoldi method for singular matrix pencils

기술 요약: 특이 행렬 펜슬을 위한 시프트-인버트 아른홀디 방법

문제 제기
본 논문은 $Ax = \lambda Bx$ 형태의 대규모 희소 특이 일반 고유값 문제를 해결하는 과제를 다룹니다. 여기서 행렬 펜슬 $A - \lambda B$는 특이합니다 (즉, $\det(A - \lambda B) \equiv 0$). 이러한 경우, 임의의 스칼라가 행렬식 조건을 만족하므로 고전적인 고유값 정의는 실패합니다. 의미 있는 해는 "정규" 고유값이며, 이는 $A - \lambda_0 B$의 랭크가 펜슬의 정규 랭크보다 낮아지는 지점에서 정의됩니다.

작고 조밀한 문제를 위한 계단식 방법 (staircase method) 이나 QZ 분해와 같은 방법들이 존재하지만, 대규모 희소 시스템에는 계산 비용이 너무 많이 들어 실용적이지 않습니다. Hochstenbach, Mehl, Plestenjak 의 최근 접근법은 무작위로 선택된 조밀한 행렬을 사용하여 특이 펜슬을 정규화함으로써 진짜 고유값과 가짜 고유값을 분리하는 것을 제안합니다. 그러나 저자들은 조밀한 정규화 행렬을 사용하면 원래 문제의 희소성 구조가 파괴되어 대규모 응용 분야에서 성능 저하와 메모리 오버헤드가 크게 발생한다고 주장합니다. 또한, 기존 희소 직접 솔버는 이러한 펜슬을 정규화하는 데 필요한 행/열 제거 또는 추가를 커스텀 개발 없이 기본적으로 지원하지 않습니다.

방법론
저자들은 희소 LU 분해의 피벗팅 시퀀스를 활용하여 특이 펜슬을 정규화하는 결정론적 전략을 제안합니다. 핵심 방법론은 다음과 같은 단계들을 포함합니다:

1. LU 피벗팅을 통한 정규화: 무작위 조밀한 행렬 대신, 시프트된 행렬 $A - \sigma B$ (여기서 $\sigma$는 시프트) 의 희소 LU 분해를 사용합니다. 분해 과정에서 0(또는 0 에 가까운) 피벗이 발견되면, 알고리즘은 행렬에 행과 열을 추가하여 분해를 유지합니다.

   • 증강 펜슬 (AGEP): 이 과정은 행렬 $F$와 $G$를 구성하여 증강 펜슬 $\begin{bmatrix} A & G \\ F^* & 0 \end{bmatrix} - \lambda \begin{bmatrix} B & 0 \\ 0 & 0 \end{bmatrix}$이 정규이 되도록 합니다. 행렬 $F$와 $G$는 LU 분해의 치환 행렬과 피벗 선택 과정에서 직접 유도됩니다.
   • 투사된 펜슬 (PGEP): 또는, 0 피벗에 해당하는 행과 열을 제거하여 투사된 펜슬 $G_\perp^* (A - \lambda B) F_\perp$를 구성합니다. $F_\perp$와 $G_\perp$는 특정 행이 제거된 단위 행렬로 유도됩니다.

2. 랭크 감지 및 보정: LU 분해는 자연스럽게 펜슬의 정규 랭크를 드러내려고 시도합니다. 저자들은 반올림 오차나 부적절한 허용 오차 설정으로 인해 감지된 랭크 ($\hat{k}$) 가 실제 정규 랭크 ($k$) 와 다를 수 있다고 지적합니다.

   • 감지된 랭크가 너무 낮다면 (즉, 허용 오차가 너무 공격적이라면), 랭크 보정 기법이 제안됩니다. 이는 무작위 직교 행렬을 사용하여 감지된 $F$와 $G$를 올바른 차원으로 증강한 후, 결과 시스템의 해를 구하기 위해 저비용의 슈어 여분 (Schur complement) 업데이트를 수행하는 것을 포함합니다.

3. 시프트-인버트 아른홀디: 정규화된 문제 (AGEP 또는 PGEP) 는 양방향 시프트-인버트 아른홀디 방법을 사용하여 해결됩니다. 저자들은 특정 시작 벡터와 내적을 가진 증강 펜슬에 대한 아른홀디 분해가 투사된 펜슬과 동일한 리츠 값 (Ritz values) 과 헤센베르크 행렬을 산출한다는 동치 정리를 증명합니다. 이를 통해 명시적으로 대규모 증강 시스템을 구성하지 않으면서도 동일한 스펙트럼 속성을 유지하는 투사된 형식을 사용할 수 있습니다.

4. 직사각형 문제: 이 방법은 직사각형 고유값 문제 ($A, B \in \mathbb{R}^{n \times m}$, $n \neq m$) 로 확장됩니다. 풀랭크 직사각형 문제의 경우, 기존 희소 솔버의 행 피벗팅을 사용하여 정사각형 정규 부분 문제를 직접 선택할 수 있습니다.

주요 기여

• 희소 정규화: 본 논문은 희소 LU 분해의 피벗팅 시퀀스에서 직접 $F, G, F_\perp, G_\perp$와 같은 희소 정규화 행렬을 생성하는 방법을 제시하여 원래 문제의 희소성을 보존합니다.
• 랭크 감지: 표준 희소 LU 분해 (부분, 룩, 또는 완전 피벗팅 사용) 가 종종 펜슬의 정규 랭크를 성공적으로 감지하여 정규화의 자동 구성을 용이하게 함을 보여줍니다.
• 랭크 보정: LU 분해가 정규 랭크를 과소평가할 경우 정규화를 보정하기 위한 구체적인 알고리즘이 제안되어, 불완전한 랭크 감지 상황에서도 방법이 견고하게 작동하도록 보장합니다.
• 이론적 동치: 아른홀디 방법의 맥락에서 증강 및 투사된 정규화 펜슬 간의 엄밀한 이론적 연결을 수립하여, 특정 조건 하에서 동일한 스펙트럼 근사를 산출함을 증명합니다.

결과
세 가지 유형의 문제에 대해 수치 실험이 수행되었습니다:

1. 유한 요소 모델 업데이트: 33 개의 자유도를 가진 트러스 구조 모델 (약 35,937 차원의 펜슬 생성). 제안된 방법 (RLU 피벗팅 사용) 은 랭크를 올바르게 식별하고 잔차를 $10^{-14}$ 수준으로 계산했습니다. 반면, 무작위화 접근법은 조건수가 훨씬 더 높게 ($10^3$ 대비 $10^6$) 나타났고 잔차도 더 컸습니다.
2. 이중 고유값 감지: 2D 라플라시안의 이산화와 관련된 매개변수 문제. LU 기반 방법은 랭크를 올바르게 결정하고 높은 정확도를 달성했습니다. 무작위화 접근법은 조밀한 행렬 구성이 필요하여 저장 공간과 계산 비용이 훨씬 더 많이 소요되었습니다.
3. 직사각형 비선형 고유값 문제: 비선형 고유값 문제에서 유도된 풀랭크 직사각형 문제. 희소 LU 접근법은 분해 및 투사에 대해 무작위 조밀 접근법보다 훨씬 빨랐습니다 (0.05 초 대 2.9 초) 그리고 더 적은 메모리 (204MB 대 98MB) 를 필요로 했습니다.

모든 경우, 희소 정규화 방법은 행렬의 희소성을 보존하여 시프트된 시스템에 대해 더 낮은 조건수를 제공하고 무작위 조밀 정규화보다 빠른 수렴을 이끌었습니다.

의의 및 주장
저자들은 이 작업을 완전한 최적화된 소프트웨어 솔루션이 아닌 개념으로 위치시키며, 현재 표준 소프트웨어 라이브러리에는 특이 행렬을 위한 견고한 희소 직접 솔버가 부족함을 인정합니다. 그러나 논문은 다음과 같이 주장합니다:

• 성능: 결정론적 피벗팅을 통한 희소성 보존은 고유값 솔버의 성능과 결과의 정확도 (더 나은 조건수를 통해) 모두에 유익합니다.
• 실현 가능성: 기존 희소 직접 솔버는 특히 풀랭크 직사각형 문제의 경우 새로운 복잡한 소프트웨어 인프라 없이도 이러한 문제를 해결하도록 적응될 수 있습니다.
• 견고성: 제안된 랭크 보정 기법은 LU 분해가 정규 랭크를 완벽하게 감지하지 못하더라도 방법이 작동하도록 보장합니다.

논문은 무작위화 접근법이 이론적으로 타당하지만, 고유값 감지를 위한 특이값 간의 간격이 충분하다면 결정론적 희소 LU 접근법이 대규모 특이 고유값 문제에 대한 실용적이고 효율적이며 정확한 대안이라고 결론지었습니다. 향후 연구로는 전역 최대 부피 피벗팅을 가진 솔버 탐색과 다중 매개변수 문제에서 크로네커 구조를 활용하는 것이 제안됩니다.