Sparse Cholesky Elimination Tree의 이해

수치 선형 대수학 분야에서 Cholesky factorization은 대칭 양의 정부호(symmetric positive-definite) 시스템을 해결하는 초석입니다. 그러나 대부분의 요소가 0인 희소 행렬(sparse matrices)을 다룰 때, 밀집(dense) factorization 알고리즘을 적용하는 것은 계산적으로 낭비이며 메모리 집약적입니다. 문제는 "fill-in"에 있습니다. 이는 원래 행렬 $A$의 0인 항목들이 결과로 나오는 하삼각 행렬 $L$에서 0이 아닌 항목으로 변하는 현상을 말합니다.

이를 관리하기 위해 엔지니어와 수학자들은 Elimination Tree를 사용합니다. 이 구조를 통해 fill-in이 어디에서 발생할지 정확히 예측할 수 있으며, 작업 의존성 그래프를 관리 가능한 트리 구조로 변환하여 최적의 작업 순서를 결정할 수 있습니다. 이 포스트에서는 right-looking Cholesky 알고리즘으로부터 elimination tree를 직접 도출하는 과정을 탐구합니다.

Cholesky의 메커니즘과 Fill-in 문제

Elimination tree를 이해하려면 먼저 dense right-looking Cholesky 알고리즘을 살펴보아야 합니다. 이 과정은 각 피벗 $k$에 대해 세 가지 주요 단계를 포함합니다:

  1. Pivot Factorization: 대각 요소 $L[k][k] = \sqrt{A[k][k]}$를 계산합니다.
  2. Column Scaling: 피벗 아래의 열을 스케일링합니다.
  3. Rank-1 Update: 후속 행렬을 업데이트합니다: $L[i][j] -= L[i][k] * L[j][k]$.

이 세 번째 단계인 rank-1 update가 fill-in을 유발합니다. 구체적으로, 만약 $L[i][k]$와 $L[j][k]$에 0이 아닌 항목이 있다면 ($k < j \le i$), 업데이트 과정에서 반드시 $L[i][j]$에 0이 아닌 항목이 생성되거나 수정됩니다.

Task DAG에서 Elimination Tree로

희소 행렬에 필요한 모든 연산을 매핑하면, 처음에는 작업 의존성의 유향 비순환 그래프(Directed Acyclic Graph, DAG)가 생성됩니다. 이 DAG는 필요한 모든 정보를 제공하지만, 종종 중복적입니다.

위에서 언급한 구조적 규칙($L[i][k] \neq 0$ 이고 $L[j][k] \neq 0 \implies L[i][j] \neq 0$) 때문에, 의존성 그래프의 많은 간선(edge)은 암시적입니다. 예를 들어, 열 0이 열 1에 의존하고, 열 1이 열 2에 의존한다면, 열 0이 열 2에 의존한다는 사실은 이미 포함되어 있습니다.

이러한 중복된 간선을 제거하면 DAG는 Column Elimination Tree로 축소됩니다. 이 트리는 $O(n)$ 데이터 구조로서 두 가지 중요한 정보를 제공합니다:

  1. Fill-in Prediction: $L$의 어떤 항목이 0이 아닌 항목이 될지 정확히 예측합니다.
  2. Task Scheduling: 열을 처리해야 하는 정확한 순서를 결정합니다.

Elimination Tree 구현

Symbolic Factorization

수치 계산을 수행하기 전에 "symbolic factorization"을 수행합니다. 이 단계에서는 elimination tree를 사용하여 실제 값을 계산하지 않고도 $L$을 위한 메모리를 미리 할당합니다. 알고리즘은 $A$의 행을 반복하며 elimination tree를 따라 올라가 모든 조상(ancestor)을 표시함으로써, L_col 구조체 내의 모든 잠재적인 fill-in 위치를 고려하도록 합니다.

Numeric Factorization

0이 아닌 패턴이 미리 계산되면, numeric factorization은 미리 할당된 인덱스를 반복하는 문제가 됩니다. Rank-1 update는 알려진 0이 아닌 항목에 대해서만 수행되므로, 계산의 내부 루프 동안 0을 확인하는 오버헤드를 피할 수 있습니다.

트리 계산하기

Elimination tree을 정의하는 것은 간단합니다: 열 $k$의 부모는 $L[j,k] \neq 0$을 만족하는 가장 작은 인덱스 $j > k$입니다.

$A$의 초기 0이 아닌 항목만을 사용하여 이를 효율적으로 계산하려면 증분 방식(incremental approach)을을 사용할 수 있습니다. 행 $r$을 증가하는 순서로 처리하고 ancestor 배열을을 유지하면서, 열 $c$에서 현재 행 $r$까지의 경로를를 통해 추적할 수 있습니다. 만약 경로가 종료된다면, 현재 행 $r$은 해당 경로의 마지막 노드의 부모가 됩니다. 이는 부모가 해당 열을 조상으로 필요로 하는 첫 번째 이후 행이 되도록 보장합니다.

결론

Elimination tree를 추상적인 그래프 이론이 아닌 right-looking Cholesky 알고리즘에 기반하여 설명함으로써, 선형 대수학적 관계와 소프트웨어 구현 사이의 관계가 명확해집니다. Elimination tree는 단순한 이론적 구조물이 아니라, 입력 행렬의 희소성을 활용하여 밀집 factorization의 이차 복잡도를 매우 효율적인 프로세스로 변환하는 실용적인 도구입니다.

Sources