A class of low-rank short recurrences for nonsymmetric linear matrix equations

기술 요약: 비대칭 선형 행렬 방정식을 위한 저차단 짧은 재귀법의 한 계급

문제 제기
본 논문은 다음과 같은 형태의 대규모 다항항 선형 행렬 방정식의 수치 해법을 다룹니다:
$$A_1XB_1 + \dots + A_pXB_p = CD^T$$
여기서 $A_i \in \mathbb{R}^{n_A \times n_A}$와 $B_i \in \mathbb{R}^{n_B \times n_B}$는 크고 희소하며 비대칭인 행렬이며, $C$와 $D$는 낮은 랭크 $q \ll n_A, n_B$를 가진 긴(full-rank) 행렬입니다. 해 $X$는 일반적으로 직사각형입니다. 크로네커 곱을 사용하여 이 방정식을 표준 선형 시스템 $Ax=b$로 벡터화할 수 있지만, 결과적인 차원$n_A n_B$로 인해 메모리 제약으로 인해 전체 벡터 반복법이 실행 불가능해집니다. 저자들은$p > 2$인 경우 ($p=2$인 실베스터 방정식을 일반화한 경우) 와 해$X$가 저차단 근사를 허용하는 경우에 초점을 맞추고 있으며, 이는 이산화된 편미분 방정식 (PDE), 확률적 갤러킨 방법, 제어 시스템에서 흔히 발견되는 특성입니다.

방법론
저자들은 벡터 기반의 짧은 재귀법 (특히 최소 잔차법과 일반화 켤레 잔차법) 을 비대칭 행렬 설정으로 일반화하는 새로운 행렬 지향 반복법 계열을 제안합니다. 핵심 전략은 메모리 사용을 최소화하기 위해 반복 전반에 걸쳐 해와 잔차를 인수화된 저차단 형태로 유지하는 것입니다.

1. 짧은 재귀 공식화:
   문제를 벡터 시스템으로 변환하는 대신, 이 방법들은 저차단 보정을 사용하여 근사해 $X_k$를 직접 업데이트합니다:
   $$X_{k+1} = X_k + P^{(l)}_k \alpha_k (P^{(r)}_k)^T$$
   여기서 $P^{(l)}_k$와 $P^{(r)}_k$는 저차단 인수 행렬이며, $\alpha_k$는 국소 최소화 문제를 풀어서 결정된 작은 조밀 행렬입니다. 두 가지 구체적인 알고리즘이 유도됩니다:

   • ss–mr (부분공간 최소 잔차법): 벡터 MR 반복의 행렬 대응물로, 각 단계에서 잔차의 푸비니우스 노름을 최소화합니다.
   • ss–gcr(1) (부분공간 일반화 켤레 잔차법): 짧은 재귀 ($\ell=1$) 를 갖는 벡터 GCR 방법의 행렬 대응물로, 수렴을 가속화하기 위해 탐색 방향에 직교 조건을 부과합니다.

2. 국소 최적화:
   계수 행렬 $\alpha_k$ (그리고 ss–gcr(1) 의 업데이트 계수 $\beta_k$) 는 축소된 다항항 행렬 방정식을 풀어서 구합니다. 이는 현재 인수들이 span 하는 부분공간으로 연산자 $L$을 투영하는 것을 포함합니다. 랭크 크기에 따라 이러한 축소 시스템은 직접적인 촐레스키 분해 (작은 랭크의 경우) 또는 사전조건 켤레 기울기법 (PCG) (더 큰 랭크의 경우) 을 통해 해결됩니다.

3. 랭크 절단 및 무작위화:
   랭크 증가를 방지하고 메모리를 제어하기 위해 저자들은 저차단 절단 전략을 사용합니다. 특히, 큰 조밀 잔차 행렬을 명시적으로 형성하지 않고 잔차의 푸비니우스 노름을 계산하고 랭크를 절단하기 위해 무작위 스케칭 (무작위 부분표본 삼각함수 변환 사용) 을 도입합니다. 이를 통해 $n_A$ 또는 $n_B$ 차원이 전체 잔차를 저장하기에 너무 큰 경우에도 이 방법들을 처리할 수 있습니다.

4. 사전조건화:
   이 프레임워크는 연산자 $L = P - N$을 분할하여 사전조건화를 지원합니다. 저자들은 한 항 사전조건화 (단일 $A_i, B_i$ 쌍의 역행렬 계산) 와 두 항 사전조건화 (ADI 반복을 통해 실베스터 방정식을 근사적으로 해결) 에 대해 논의합니다. 사전조건화된 잔차는 다음 탐색 방향을 생성하는 데 사용됩니다.

주요 기여

• 비대칭 연산자로의 일반화: 본 논문은 이전에 대칭/양정치 연산자에 대해 확립된 짧은 재귀 행렬 방법을 일반적인 비대칭 경우로 확장합니다.
• 메모리 효율성: 짧은 재귀와 저차단 인수 표현 및 무작위 스케칭을 결합함으로써 $n_A n_B$ 길이의 전체 벡터를 저장하지 않으므로, 벡터화 접근법이 실패하는 문제에서도 실행 가능해집니다.
• 알고리즘 프레임워크: 다항항 방정식에 대해 계산 비용, 메모리, 수렴 특성을 균형 있게 맞추는 구체적인 알고리즘 (ss–mr 및 ss–gcr(1)) 의 유도.
• 확률적 갤러킨 적용: 이 방법들은 무작위 입력을 갖는 다라시 (Darcy) 흐름과 같은 도전적인 매개변수 PDE 문제에 적용되었으며, 확률적 갤러킨 혼합 유한 요소법 (SG-MFEM) 을 통해 이산화되어 많은 항을 가진 비대칭 행렬 방정식을 생성했습니다.

결과
수치 실험은 두 가지 벤치마크 문제에 대해 수행되었습니다:

1. 대류 - 확산 문제: 유한 차분법으로 이산화된 2D 정상 상태 대류 - 확산 방정식.
   • 새로운 방법들 (ss–mr 및 ss–gcr(1)) 은 최첨단 저차단 GMRES(lr-pgmres) 보다 CPU 시간 측면에서 현저히 빠르게 (종종 한 자릿수 이상) 수렴했습니다.
   • lr-pgmres 보다 훨씬 적은 메모리를 필요로 했습니다.
   • 크로네커 형태에 대한 벡터 기반 BiCGStab(2) 과 비교할 때, 행렬 방법들은 시간과 메모리 모두에서 압도적으로 우수했으며, 벡터 방법들은 더 큰 격자 크기에서 수렴하지 못하거나 메모리 부족으로 실패했습니다.
2. 확률적 다라시 흐름: 불확실한 투수성을 가진 매개변수 안장점 문제.
   • 이 방법들은 modest 한 메모리 자원을 사용하여 $10^9$ 개 이상의 자유도를 가진 문제를 성공적으로 해결했습니다.
   • 반복 횟수는 공간 메쉬 크기와 확률적 매개변수의 수에 독립적으로 유지되었습니다.
   • "느린 감쇠" 경우 (더 높은 랭크가 필요한 경우) 에는 ss–mr 이 $\beta_k$ 업데이트를 계산하지 않아 비용이 낮기 때문에 ss–gcr(1) 보다 CPU 시간에서 더 우수했으며, 두 방법 모두 메모리/시간 제약으로 인해 가장 큰 인스턴스에서 실패한 벡터 기반 MINRES 솔버보다 우수했습니다.

의의 및 주장
본 논문은 제안된 방법론이 해가 본질적으로 저차단인 설정에서 특히 대규모 비대칭 다항항 행렬 방정식을 해결하기 위한 강력하고 효율적인 대안을 제공한다고 주장합니다. 저자들은 그들의 접근법이 행렬 공식화의 이론적 이점 (구조 보존) 과 저차단 근사의 실용적 필요성 사이의 간극을 효과적으로 연결한다고 강조합니다.

의의는 크로네커 곱으로 인한 "차원의 저주"로 인해 표준 벡터 기반 반복 솔버로는 현재 해결 불가능한 문제들을 해결할 수 있는 능력에 있습니다. 무작위화 전략의 통합은 명시적인 행렬 형성 없이 잔차 노름을 계산하고 랭크를 절단할 수 있게 하는 핵심 요소로 강조됩니다. 저자들은 이 방법들이 효과적이지만, 그 성능은 좋은 사전조건자의 가용성과 해의 저차단 근사 가능성에 크게 의존한다고 지적합니다. 이 작업은 역사적으로 PDE 및 데이터 과학의 응용 분야에 비해 뒤처져 왔던 이러한 계급의 문제에 대한 알고리즘 개발의 한 걸음으로 제시됩니다.