대규모 과학 및 공학 계산의 중심에는 종종 선형 시스템 $Ax=b$를 푸는 문제가 자리 잡고 있다. 특히 유한요소해석(Finite Element Analysis), 전산 유체 역학(Computational Fluid Dynamics), 전자 회로 시뮬레이션(Circuit Simulation), 그리고 컴퓨터 그래픽스와 같은 분야에서는 편미분 방정식을 이산화(discretization)하는 과정에서 거대한 행렬 $A$가 필연적으로 등장한다.1 이러한 행렬들은 한 가지 공통적인 특징을 가지는데, 바로 대부분의 원소가 0이라는 점이다. 이러한 행렬을 희소 행렬(sparse matrix)이라 부른다. 저명한 수학자 제임스 윌킨슨(James Wilkinson)은 희소 행렬을 “0이 아닌 원소보다 0인 원소가 훨씬 많아서, 그 0들을 활용하는 것이 이득이 되는 행렬”이라고 실용적으로 정의했다.4
만약 이 거대한 희소 행렬을 모든 원소가 값을 가진다고 가정하는 밀집 행렬(dense matrix)로 취급한다면, 우리는 곧바로 계산 및 메모리의 한계에 부딪히게 된다. $n \times n$ 크기의 밀집 행렬을 다루는 표준적인 가우스 소거법은 $O(n^3)$의 계산 복잡도와 $O(n^2)$의 저장 공간을 요구한다.6 변수의 개수 $n$이 수백만을 넘나드는 현대의 문제에서 이는 사실상 불가능한 요구 조건이다. 따라서 희소 행렬의 ‘희소성’을 적극적으로 활용하는 특화된 알고리즘이 필수적이다.
이러한 문제들 중 상당수는 행렬 $A$가 대칭 양정치(Symmetric Positive-Definite, SPD)라는 특별한 성질을 가질 때 나타난다. SPD 행렬은 대칭성($A=A^T$)과 양의 정부호성($x^T A x > 0$ for all non-zero vectors $x$)을 동시에 만족하는 행렬을 의미한다.7 이러한 행렬은 물리 시스템의 에너지 최소화 문제, 통계학의 공분산 행렬, 그래프 이론의 라플라시안 행렬 등 다양한 분야에서 자연스럽게 발생하며, 매우 중요하고 유용한 수학적 특성을 지닌다.10
SPD 행렬을 위한 가장 효율적이고 안정적인 직접 해법 중 하나가 바로 촐레스키 분해(Cholesky factorization)이다. 이는 행렬 $A$를 하삼각행렬 $L$과 그 전치행렬 $L^T$의 곱, 즉 $A=LL^T$로 분해하는 방법으로, SPD 행렬에 대한 가우스 소거법의 특별한 형태로 볼 수 있다.13 밀집 행렬의 경우, 촐레스키 분해는 LU 분해에 비해 약 두 배 빠르며 수치적으로도 매우 안정적이다.
하지만 희소 행렬에 촐레스키 분해를 적용하는 순간, 우리는 ‘필인(fill-in)’이라는 근본적인 난관에 봉착한다. 필인이란, 원래 행렬 $A$에서는 0이었던 위치가 인수 $L$에서는 0이 아닌 값으로 채워지는 현상을 말한다.15 이 필인 현상은 희소성의 이점을 심각하게 훼손하며, 최악의 경우 인수 $L$이 거의 밀집 행렬에 가깝게 될 수도 있다. 놀랍게도, 필인의 양은 행렬의 행과 열을 어떤 순서로 처리하느냐에 따라 극적으로 달라진다. 예를 들어, 첫 번째 행과 열에만 비영 원소가 집중된 ‘화살표 행렬’은 원래 순서대로 분해하면 100% 필인이 발생하지만, 첫 행/열을 마지막으로 옮겨서 분해하면 필인이 전혀 발생하지 않는다.18
이러한 관찰은 희소 촐레스키 분해의 핵심 과제가 무엇인지를 명확히 보여준다. 그것은 단순히 수치 계산을 넘어, 필인을 최소화하는 최적의 처리 순서를 찾는 조합적 최적화 문제와 결합되어 있다는 점이다. 이 문제를 해결하기 위해 현대의 희소 직접 솔버(sparse direct solver)는 정교한 다단계 아키텍처를 채택한다 15:
$P$를 찾는다.$PAP^T$의 촐레스키 인수 $L_P$의 비영(non-zero) 구조를 수치 계산 없이 미리 예측한다.$L_P$의 값을 구한다.이러한 단계별 접근이 가능한 근본적인 이유는 촐레스키 분해의 탁월한 수치적 안정성 때문이다. 일반적인 LU 분해는 안정성을 위해 피벗팅(pivoting)이 필수적인데, 이는 계산 과정에서 행의 순서를 동적으로 바꾸므로 사전에 필인 구조를 예측하는 것을 거의 불가능하게 만든다. 반면, SPD 행렬에 대한 촐레스키 분해는 피벗팅 없이도 항상 안정적이라는 것이 증명되었다.8 이 결정적인 특성 덕분에, 필인 감소라는 조합적 문제와 수치 계산이라는 해석적 문제를 완전히 분리하여 순차적으로 처리하는 것이 가능해졌다. 이 ‘분리’의 원칙이야말로 오늘날의 고성능 희소 촐레스키 솔버를 지탱하는 아키텍처의 근간이다.
이 교재는 희소 촐레스키 분해의 이론적 기초부터 최첨단 알고리즘, 그리고 실제 응용에 이르기까지 모든 것을 심층적으로 탐구하는 것을 목표로 한다. 제1장에서는 밀집 행렬에 대한 표준 촐레스키 분해를 다루고, 제2장에서는 희소 행렬의 그래프 표현과 필인 현상의 본질을 파헤친다. 제3장에서는 필인 감소를 위한 핵심 기술인 재정렬 알고리즘들을 비교 분석하며, 제4장에서는 위에서 언급한 다단계 아키텍처를 상세히 설명한다. 마지막으로 제5장에서는 유한요소해석, 회로 시뮬레이션, 컴퓨터 그래픽스 등 주요 응용 분야에서 희소 촐레스키 분해가 어떻게 활용되고 발전해 왔는지 살펴볼 것이다.
희소 행렬의 복잡한 세계로 나아가기 전에, 먼저 밀집(dense) 행렬에 대한 표준 촐레스키 분해의 원리를 완벽히 이해하는 것이 필수적이다. 이 장에서는 대칭 양정치(SPD) 행렬에 대한 촐레스키 분해의 정의, 존재성 및 유일성을 수학적으로 증명하고, 알고리즘의 유도 과정과 그 특성을 분석한다. 이 기초는 이후 희소 행렬 분해에서 발생하는 도전 과제들을 이해하는 단단한 발판이 될 것이다.
촐레스키 분해는 대칭 양정치 행렬을 위한 매우 특별하고 우아한 행렬 분해 방법이다.
정의: $n \times n$ 크기의 에르미트 양정치(Hermitian positive-definite) 행렬 $A$에 대하여, $A = LL^*$를 만족하는 양수($>0$)의 대각 원소를 갖는 하삼각행렬(lower triangular matrix) $L$이 유일하게 존재하며, 이를 $A$의 촐레스키 분해라 한다. 여기서 $L^*$는 $L$의 켤레 전치(conjugate transpose)를 의미한다. 만약 $A$가 실수(real) 대칭 양정치 행렬이라면, 분해는 $A = LL^T$ 형태가 된다.9
존재성 증명: 촐레스키 분해의 존재는 수학적 귀납법을 통해 증명할 수 있다.7
기저 사례 (Base case): $n=1$일 때, $A = [\alpha_{11}]$이다. $A$가 양정치이므로 $\alpha_{11} > 0$이고 실수이다. 따라서 $L = [\sqrt{\alpha_{11}}]$로 두면 $A = LL^T$가 성립한다.
귀납 가정 (Inductive hypothesis): 크기가 $(n-1) \times (n-1)$인 모든 SPD 행렬에 대해 촐레스키 분해가 존재한다고 가정한다.
귀납 단계 (Inductive step): $n \times n$ SPD 행렬 $A$를 다음과 같이 블록 행렬로 분할한다.
\(A = \begin{pmatrix} \alpha_{11} & a_{21}^T \\ a_{21} & A_{22} \end{pmatrix}\)
여기서 $\alpha_{11}$은 스칼라, $a_{21}$은 $(n-1) \times 1$ 벡터, $A_{22}$는 $(n-1) \times (n-1)$ 행렬이다. $A$가 SPD이므로 $\alpha_{11} > 0$이다. 이제 $L$을 다음과 같은 형태로 찾고자 한다.
\(L = \begin{pmatrix} l_{11} & 0 \\ l_{21} & L_{22} \end{pmatrix}\)
$A = LL^T$로부터 다음 관계식을 얻는다.
\(\begin{pmatrix} \alpha_{11} & a_{21}^T \\ a_{21} & A_{22} \end{pmatrix} = \begin{pmatrix} l_{11}^2 & l_{11}l_{21}^T \\ l_{11}l_{21} & l_{21}l_{21}^T + L_{22}L_{22}^T \end{pmatrix}\)
이로부터 $l_{11} = \sqrt{\alpha_{11}}$ (양의 제곱근 선택) 그리고 $l_{21} = a_{21} / l_{11}$을 얻는다. 남은 부분은 $A_{22} = l_{21}l_{21}^T + L_{22}L_{22}^T$ 이므로, $L_{22}L_{22}^T = A_{22} - l_{21}l_{21}^T$ 이다.
여기서 핵심은 $A_{22}’ = A_{22} - l_{21}l_{21}^T$ (이를 슈어 보수(Schur complement)라 한다)가 여전히 $(n-1) \times (n-1)$ 크기의 SPD 행렬임을 보이는 것이다.7 이것이 증명되면, 귀납 가정에 의해
$A_{22}'$의 촐레스키 분해 $L_{22}$가 존재하게 되고, 따라서 $A$의 촐레스키 분해 $L$도 존재하게 된다.
유일성 증명: 만약 두 개의 촐레스키 분해 $A = L_1 L_1^T = L_2 L_2^T$가 존재한다고 가정하자. 여기서 $L_1, L_2$는 모두 양의 대각 원소를 갖는 하삼각행렬이다. $L_1, L_2$는 가역(invertible)이므로, $L_2^{-1}L_1 = L_2^T (L_1^T)^{-1} = (L_1^{-1}L_2)^T$를 얻을 수 있다. 좌변 $L_2^{-1}L_1$은 하삼각행렬이고, 우변 $(L_1^{-1}L_2)^T$는 상삼각행렬(upper triangular matrix)이다. 두 행렬이 같으려면 둘 다 대각 행렬(diagonal matrix) $D$이어야 한다. 즉, $L_2^{-1}L_1 = D$ 이고 $L_1 = L_2 D$ 이다. 이를 원래 식에 대입하면 $A = (L_2 D)(L_2 D)^T = L_2 D D^T L_2^T$가 된다. $A = L_2 L_2^T$이므로 $D D^T = I$ (단위행렬)가 성립해야 한다. $D$의 대각 원소를 $d_i$라 하면 $d_i^2 = 1$이므로 $d_i = \pm 1$이다. 하지만 $L_1$과 $L_2$의 대각 원소는 모두 양수여야 한다는 조건에 따라 $D$의 대각 원소도 모두 양수여야 하므로, $D=I$가 된다. 따라서 $L_1 = L_2$이며, 촐레스키 분해는 유일하다.23
반대로, 어떤 가역 행렬 $L$에 대해 $A=LL^T$로 표현될 수 있다면, $A$는 자명하게 대칭이며($A^T = (LL^T)^T = (L^T)^T L^T = LL^T = A$), 임의의 0이 아닌 벡터 $x$에 대해 $x^T A x = x^T L L^T x = (L^T x)^T (L^T x) = \|L^T x\|^2 > 0$이므로 양정치이다.8 이 성질 때문에 촐레스키 분해를 시도하는 것 자체가 행렬의 양정치성을 판별하는 효율적인 방법으로 사용될 수 있다.14
존재성 증명에서 사용된 블록 행렬 접근법은 촐레스키 분해 알고리즘을 직접적으로 유도하는 강력한 도구이다.7 위에서 보았듯이, $n \times n$ 행렬 $A$의 분해는 첫 번째 열/행을 계산하고, 남은 $(n-1) \times (n-1)$ 부분 행렬의 분해 문제로 축소된다.
이 재귀적인 과정을 반복적인 알고리즘으로 구현할 수 있다. 가장 일반적인 형태 중 하나는 행렬 $L$을 열(column) 단위로 계산해 나가는 방식이다. $A=LL^T$의 원소별 관계식 $A_{ij} = \sum_{k=1}^{j} L_{ik} L_{jk}$ (단, $i \ge j$)로부터 다음 계산식을 유도할 수 있다.23
$j=1, 2, \dots, n$ 에 대해:
$i = j+1, \dots, n$):
\(L_{ij} = \frac{1}{L_{jj}} \left( A_{ij} - \sum_{k=1}^{j-1} L_{ik} L_{jk} \right)\)
이 알고리즘은 $j$번째 열을 계산할 때 이전에 계산된 $1$부터 $j-1$번째 열의 정보만을 사용한다. 이와 같은 알고리즘을 Cholesky-Banachiewicz 알고리즘이라고도 부른다.7계산 복잡도: $n \times n$ 밀집 행렬에 대한 촐레스키 분해의 계산량을 분석해보자. 위 알고리즘의 내부 루프(summation)는 $j$번째 열을 계산할 때 약 $2(j-1)(n-j)$ 개의 부동소수점 연산(flops)을 수행하고, 제곱근과 나눗셈을 포함한다. 이를 모든 $j$에 대해 합하면 총 연산량은 약 $n^3/3$ flops가 된다. 이는 동일한 행렬에 대한 LU 분해에 필요한 연산량인 $2n^3/3$ flops의 정확히 절반이다.13 이 효율성은 촐레스키 분해가 SPD 시스템에 대한 선호되는 직접 해법인 주된 이유 중 하나이다.
수치 안정성: 촐레스키 분해의 가장 큰 장점 중 하나는 뛰어난 수치적 안정성이다. 양정치 행렬의 경우, 분해 과정에서 발생하는 모든 슈어 보수가 양정치를 유지하므로, 대각 원소 $L_{jj}$를 계산할 때 제곱근 안의 값이 항상 양수가 된다. 이 덕분에 가우스 소거법에서 안정성을 위해 필요한 피벗팅(pivoting, 행이나 열을 교환하는 작업)이 전혀 필요 없다.8 피벗팅이 없다는 것은 알고리즘 구현을 단순화할 뿐만 아니라, 희소 행렬을 다룰 때 필인 구조를 사전에 예측할 수 있게 하는 결정적인 역할을 한다.
계산된 인수 $\hat{L}$의 오차는 행렬의 조건수 $\kappa(A)$에 비례하여 $\| \hat{L} - L \| / \|L\| = O(\kappa(A)\epsilon_{\text{machine}})$로 나타날 수 있다. 여기서 $\epsilon_{\text{machine}}$은 기계 입실론이다. 하지만 분해된 인수의 곱 $\hat{L}\hat{L}^T$는 원래 행렬 $A$를 훨씬 더 정확하게 근사하며, 일반적으로 후방 안정성(backward stability)을 만족한다.13
촐레스키 분해 $A=LL^T$를 구했다면, 선형 시스템 $Ax=b$를 푸는 것은 두 개의 간단한 삼각 시스템을 푸는 문제로 귀결된다.9
원래 방정식 $Ax=b$는 $LL^T x = b$로 대체된다. 여기서 $y = L^T x$라고 치환하면, 문제는 다음 두 단계로 나뉜다 10:
전진 대입 (Forward Substitution): 하삼각 시스템 $Ly = b$를 풀어 중간 벡터 $y$를 구한다.
$y_1 = b_1 / L_{11}$
$y_i = (b_i - \sum_{j=1}^{i-1} L_{ij} y_j) / L_{ii}$ for $i=2, \dots, n$
후진 대입 (Backward Substitution): 상삼각 시스템 $L^T x = y$를 풀어 최종 해 $x$를 구한다.
$x_n = y_n / L_{nn}$
$x_i = (y_i - \sum_{j=i+1}^{n} L_{ji} x_j) / L_{ii}$ for $i=n-1, \dots, 1$
전진 대입과 후진 대입 각각은 약 $n^2$의 계산 복잡도를 가진다.14 따라서 분해 비용(
$O(n^3)$)에 비해 훨씬 저렴하다. 이는 동일한 행렬 $A$에 대해 여러 개의 다른 우변 벡터 $b$를 가지고 시스템을 풀어야 할 때 특히 효율적이다. 분해는 한 번만 수행하고, 각 $b$에 대해 저렴한 삼각 시스템 풀이만 반복하면 되기 때문이다.
표준 촐레스키 분해의 원리를 이해했다면, 이제 희소 행렬이라는 새로운 영역으로 들어설 준비가 되었다. 희소 행렬 분해는 단순히 0인 원소에 대한 연산을 건너뛰는 것 이상의 깊이를 가진다. 이 장에서는 희소 촐레스키 분해의 핵심 난제인 ‘필인(fill-in)’ 현상을 심층적으로 분석한다. 이를 위해 행렬의 비영 구조를 그래프로 변환하고, 분해 과정을 그래프 연산인 ‘제거 게임(elimination game)’으로 시각화하여 필인의 발생 원리를 직관적으로 이해할 것이다. 또한, 희소 행렬을 컴퓨터 메모리에 효율적으로 저장하고 처리하기 위한 필수 데이터 구조인 CSC(Compressed Sparse Column) 형식을 자세히 살펴본다.
희소 행렬의 구조적 특성을 분석하는 가장 강력한 도구는 그래프 이론이다. $n \times n$ 크기의 대칭 희소 행렬 $A$의 비영(non-zero) 구조는 인접 그래프(adjacency graph) $G(A)=(V, E)$로 완벽하게 표현될 수 있다.4
$V$: 그래프의 각 정점 $i \in V$ (여기서 $i=1, \dots, n$)는 행렬의 $i$번째 행과 $i$번째 열에 대응된다.$E$: 두 정점 $i$와 $j$ 사이에 간선 $(i, j) \in E$가 존재하는 것은 행렬의 비대각 원소 $A_{ij}$ (그리고 대칭성에 의해 $A_{ji}$)가 0이 아님을 의미한다 ($i \neq j$).대각 원소 $A_{ii}$는 항상 0보다 크다고 가정되므로 그래프에서는 보통 자기 자신을 가리키는 루프(loop)로 표현하지 않는다. 이 그래프 모델을 통해, 행렬의 대수적 연산은 그래프의 위상적(topological) 연산 문제로 변환될 수 있으며, 이는 필인 현상을 이해하고 제어하는 데 결정적인 역할을 한다.18
촐레스키 분해 과정에서 필인이 왜, 그리고 어떻게 발생하는지를 이해하기 위해 ‘제거 게임’이라는 그래프 모델을 도입한다.29 촐레스키 분해의
$k$번째 단계, 즉 $k$번째 변수를 소거하는 과정은 인접 그래프 $G(A)$에서 정점 $k$를 ‘제거(eliminating)’하는 과정과 동일하게 볼 수 있다.
제거 게임 규칙: 정점 $k$를 제거하는 과정은 다음과 같은 두 단계로 이루어진다.32
$k$에 인접한 모든 이웃 정점(neighbors)들을 서로 빠짐없이 연결하여 완전 그래프, 즉 클리크(clique)를 만든다. 이 과정에서 원래는 없었던 간선이 추가될 수 있는데, 이것이 바로 필인에 해당한다.$k$와 그에 연결된 모든 간선을 그래프에서 제거한다.이 과정을 모든 정점에 대해 순서대로 반복하면, 최종적으로 남는 간선들의 집합이 촐레스키 인수 $L$의 비영 구조를 나타내는 채워진 그래프(filled graph) $G^+(A)$를 형성한다.29
Fill Path Theorem: 어떤 간선 $(i, j)$가 필인으로 생성되는지를 예측하는 중요한 정리가 있다. 원래 그래프 $G(A)$에서 두 정점 $i$와 $j$ 사이에 경로가 존재하고, 그 경로를 구성하는 모든 중간 정점들이 $i$와 $j$보다 제거 순서에서 앞선다면, 채워진 그래프 $G^+(A)$에는 간선 $(i, j)$가 존재하게 된다. 즉, 필인이 발생한다.33 이는 필인이 국소적인 정보뿐만 아니라, 제거 순서에 따른 전역적인 경로 의존성에 의해 결정됨을 보여준다.
희소 행렬의 0이 아닌 원소들만 저장하기 위해 다양한 압축 형식이 개발되었다. 대표적으로 COO(Coordinate), CSR(Compressed Sparse Row), 그리고 CSC(Compressed Sparse Column) 형식이 있다.4 이 중 촐레스키 분해와 같은 열 지향적(column-oriented) 알고리즘에서는 CSC 형식이 특히 효율적이다.
CSC (Compressed Sparse Column) 형식: CSC 형식은 세 개의 1차원 배열을 사용하여 희소 행렬을 표현한다.36
data (또는 values): 0이 아닌 원소들의 값을 열 우선 순서(column-major order)로 저장한다.row_ind (또는 indices): data 배열에 저장된 각 원소의 행 인덱스(row index)를 저장한다.col_ptr (또는 indptr): 각 열이 data와 row_ind 배열에서 어디서 시작하는지를 가리키는 포인터 배열이다. 이 배열의 길이는 (열의 개수 + 1)이며, col_ptr[j]는 $j$번째 열의 첫 번째 비영 원소의 인덱스를, col_ptr[j+1] - col_ptr[j]는 $j$번째 열의 비영 원소 개수를 나타낸다.예를 들어, 촐레스키 분해 알고리즘은 특정 열을 계산하기 위해 그 열의 왼쪽에 있는 다른 열들의 정보를 참조한다. CSC 형식을 사용하면 특정 열에 해당하는 모든 비영 원소와 그 행 인덱스들을 메모리상에서 연속적으로 접근할 수 있다. 이는 캐시 효율성(cache efficiency)을 극대화하고 데이터 지역성(data locality)을 향상시켜 알고리즘의 실행 속도를 크게 높여준다.38
계산 비용의 재정의는 희소 촐레스키 분해의 성능을 이해하는 데 있어 매우 중요한 관점을 제공한다. 밀집 행렬의 분해 비용이 단순히 행렬 크기 $n$에 의해 결정되는 것과 달리, 희소 행렬의 분해 비용은 필인의 총 개수(nnz(L))만으로는 충분히 설명되지 않는다. 실제 계산량은 인수 $L$의 각 열에 있는 비영 원소 개수의 제곱의 합, 즉 $\sum_{j} |\text{col}_j(L)|^2$에 비례한다.20
이 공식은 두 가지 중요한 사실을 시사한다. 첫째, 더 희소한 인수 $L$이 일반적으로 더 적은 계산량을 필요로 한다. 둘째, 그리고 더 중요한 것은, 필인의 ‘분포’가 총량만큼이나 성능에 결정적인 영향을 미친다는 점이다. 예를 들어, 두 가지 다른 재정렬 방식이 동일한 총 필인 개수를 생성했다고 가정해보자. 한 방식은 필인을 모든 열에 비교적 고르게 분산시킨 반면, 다른 방식은 소수의 특정 열에 필인을 집중시켰다. 비용 공식을 적용하면, 소수의 ‘뚱뚱한’ 열(dense column)을 가진 두 번째 방식이 훨씬 더 큰 계산 비용을 초래하게 된다. 이는 $100^2 \times 1 + 1^2 \times 99$ 가 $10^2 \times 10$ 보다 훨씬 큰 것과 같은 이치이다. 따라서 좋은 재정렬 알고리즘의 목표는 단순히 nnz(L)을 최소화하는 것을 넘어, nnz(L)의 열별 분포를 최대한 균일하게 유지하여 이 제곱의 합을 최소화하는, 보다 정교한 최적화 문제를 푸는 것이다. 이 관점은 다음 장에서 다룰 최소 차수 알고리즘과 중첩 분할 알고리즘의 장단점을 비교하고 그 성능을 평가하는 핵심적인 기준이 된다.
| 특성 | 좌표 (COO) | 압축 희소 행 (CSR) | 압축 희소 열 (CSC) |
|---|---|---|---|
| 구조 | 3개의 배열: (row, col, data) |
3개의 배열: (data, indices, indptr) |
3개의 배열: (data, indices, indptr) |
| 행 슬라이싱 효율성 | 비효율적 | 매우 효율적 | 비효율적 |
| 열 슬라이싱 효율성 | 비효율적 | 비효율적 | 매우 효율적 |
| 행렬-벡터 곱 효율성 | 보통 | 매우 효율적 | 보통 |
| 구조 수정 용이성 | 매우 용이함 (새 원소 추가가 쉬움) | 어려움 (배열 재구성이 필요) | 어려움 (배열 재구성이 필요) |
| 주 사용처 | 희소 행렬을 처음 구성할 때 | 행 단위 접근이 잦은 알고리즘 (예: 반복법) | 열 단위 접근이 잦은 알고리즘 (예: 촐레스키 분해) |
이 표는 각 저장 형식의 장단점을 명확히 보여준다. COO는 행렬을 만들 때 유연하지만 연산에는 비효율적이다. CSR은 행 기반 연산에 최적화되어 있고, CSC는 열 기반 연산에 최적화되어 있다. 촐레스키 분해 알고리즘이 본질적으로 열 단위로 진행되기 때문에, CSC는 이 알고리즘을 위한 가장 자연스럽고 효율적인 데이터 구조이다.38
희소 촐레스키 분해의 성능은 필인(fill-in)의 양과 분포에 의해 결정되며, 이는 전적으로 행과 열의 처리 순서에 달려있다. 이 장은 희소 촐레스키 분해의 심장부라 할 수 있는 재정렬(reordering) 기법을 다룬다. 필인을 최소화하는 최적의 순서를 찾는 것은 NP-완전(NP-complete) 문제로 알려져 있어, 현실적으로는 효율적인 휴리스틱(heuristic) 알고리즘에 의존한다.30 여기서는 가장 대표적인 두 가지 휴리스틱 전략인 ‘최소 차수 알고리즘(Minimum Degree Algorithm)’과 ‘중첩 분할 알고리즘(Nested Dissection Algorithm)’을 심층적으로 비교 분석한다. 각 알고리즘의 작동 원리, 장단점, 그리고 성능 특성을 이해함으로써, 문제의 특성에 맞는 적절한 재정렬 전략을 선택하는 안목을 기를 수 있다.
재정렬의 수학적 표현은 순열 행렬(permutation matrix) $P$를 사용하는 것이다. 원래의 선형 시스템 $Ax=b$ 대신, 등가인 $(PAP^T)(P x) = P b$를 푼다. 여기서 순열 행렬 $P$를 $A$에 좌우로 곱하는 것은 $A$의 행과 열을 동일한 순서로 교환하는 것과 같으며, 이는 인접 그래프 $G(A)$의 정점 번호를 재부여하는 것과 동일한 효과를 가진다.18
중요한 점은 이러한 대칭적 순열 변환이 행렬의 핵심적인 대수적 성질을 보존한다는 것이다. $A$와 $PAP^T$는 동일한 고유값을 가지므로, $A$가 SPD이면 $PAP^T$도 SPD이다. 따라서 촐레스키 분해의 적용 가능성은 변하지 않는다.43 재정렬의 유일한 목표는 조합적인 최적화, 즉 $A$의 촐레스키 인수 $L$보다 $PAP^T$의 촐레스키 인수 $L_P$가 훨씬 더 희소하게(즉, 필인이 적게) 만들어주는 순열 $P$를 찾는 것이다.44
최소 차수(Minimum Degree, MD) 알고리즘은 가장 오래되고 널리 알려진 재정렬 휴리스틱 중 하나이다. 그 전략은 매우 직관적이고 탐욕적(greedy)이다.
$d$인 정점을 제거할 때 발생하는 필인의 상한은 $d(d-1)/2$이다. MD 알고리즘은 각 단계에서 이 상한을 최소화하는 국소적으로 최적인 선택을 반복하는 것이다.43중첩 분할(Nested Dissection, ND) 알고리즘은 MD와는 근본적으로 다른, 전역적인(global) 분할 정복(divide-and-conquer) 전략을 사용한다.
기본 아이디어: 그래프를 두 개 이상의 작은 부분 그래프로 나누는 작은 크기의 정점 분리자(vertex separator) $S$를 찾는다. 분리자 $S$를 제거하면 그래프는 서로 연결되지 않은 여러 개의 컴포넌트로 나뉜다.33
재귀적 과정:
$G$에서 정점 분리자 $S$를 찾는다.$G$는 분리된 부분 그래프들(예: $G_1, G_2$)과 분리자 $S$로 나뉜다.$G_1, G_2$ 각각에 대해 이 분할 과정을 재귀적으로 적용한다.원리: 이 순서를 따르면, 서로 다른 부분 그래프(예: $G_1, G_2$)에 속한 정점들 사이에는 직접적인 연결이 없으므로, 분해 과정에서 이들 사이에 필인이 발생하지 않는다. 필인은 각 부분 그래프 내부와 분리자 내부에서만 발생하도록 제한된다.33
성능: ND의 성능은 좋은 분리자를 얼마나 잘 찾느냐에 달려있다. 2D/3D 유한요소 메쉬와 같이 기하학적 구조를 가진 그래프들은 이론적으로 작은 크기의 분리자를 가짐이 증명되어 있다 (예: 평면 분리자 정리). 이러한 그래프에 대해 ND는 점근적으로 최적에 가까운 필인 및 연산량 상한을 보장한다.47 예를 들어,
$N$개의 정점을 가진 평면 그래프의 경우, 필인은 $O(N \log N)$, 연산량은 $O(N^{1.5})$로 알려져 있다.
MD와 ND는 서로 다른 철학을 바탕으로 하므로, 그 특성 또한 명확히 구분된다.
MD와 ND의 선택은 ‘탐욕적 휴리스틱’과 ‘분할 정복’이라는 컴퓨터 과학의 고전적인 패러다임 대결로 볼 수 있다. MD는 각 단계에서 가장 쉬워 보이는 문제(차수가 가장 낮은 노드)를 먼저 처리하는 빠른 ‘단기적 이익’ 추구 전략이다. 반면, ND는 비용이 많이 드는 분리자 탐색을 통해 문제를 독립적인 작은 문제들로 분해하여 ‘장기적 투자’를 하는 전략이다. 어떤 전략이 더 나은지는 문제의 근본적인 ‘구조’에 달려있다. 유한요소 메쉬와 같은 ‘기하학적’ 그래프는 작은 분리자를 갖는 경향이 있어 ND의 투자가 큰 보상으로 돌아온다.47 반면, 소셜 네트워크나 일부 회로망과 같은 ‘비기하학적’ 그래프는 좋은 분리자가 없을 수 있으며, 이 경우 ND의 비싼 투자 비용이 보상받지 못하고 오히려 빠른 MD가 더 실용적일 수 있다.42
이러한 상호 보완적인 특성 때문에, 대부분의 최신 고성능 솔버들은 하이브리드(hybrid) 전략을 채택한다. 즉, 상위 레벨에서는 ND를 사용하여 그래프를 큰 덩어리로 나누고, 재귀의 끝에 있는 작고 다루기 쉬운 부분 그래프들은 빠른 AMD로 처리한다. 이는 ND의 전역적 장점과 MD의 지역적 효율성을 결합하여, 이론과 실제 사이의 현명한 타협점을 찾는 것이다.51
| 특성 | 최소 차수(MD) 계열 | 중첩 분할(ND) 계열 |
|---|---|---|
| 기본 전략 | 지역적, 탐욕적 (Greedy) | 전역적, 분할 정복 (Divide-and-Conquer) |
| 재정렬 계산 비용 | 낮음 (일반적으로 매우 빠름) | 높음 (그래프 분할 비용이 큼) |
| 생성되는 필인 품질 | 좋음 (다양한 문제에 대해 안정적) | 매우 좋음 (특히 기하학적 문제에서 우수) |
| 병렬성 (제거 트리) | 낮음 (길고 불균형한 트리 생성 경향) | 높음 (넓고 균형 잡힌 트리 생성) |
| 강점 (유리한 문제) | 불규칙한 그래프, 빠른 재정렬이 중요할 때 | 기하학적 구조를 가진 그래프 (예: FEA 메쉬) |
| 약점 (불리한 문제) | 대규모 병렬 처리, 전역적 최적화가 필요할 때 | 좋은 분리자가 없는 그래프, 재정렬 비용이 부담될 때 |
| 대표 알고리즘 | AMD, MMD | METIS-based ND, Scotch-based ND |
이 표는 두 알고리즘 패밀리 간의 복잡한 트레이드오프를 한눈에 보여준다. 알고리즘 선택은 단순히 필인 감소율뿐만 아니라, 재정렬 시간, 그리고 후속 수치 분해 단계에서의 병렬성까지 고려해야 하는 다각적인 결정임을 알 수 있다.
재정렬을 통해 필인을 줄일 최적의 순서를 결정했다면, 이제 재정렬된 행렬을 실제로 분해할 차례이다. 이 장에서는 희소 촐레스키 분해의 전체 과정을 구성하는 세 가지 핵심 단계-심볼릭 분해, 수치적 분해, 삼각 시스템 풀이-를 상세히 설명한다. 먼저, 실제 수치 계산 없이 인수 $L$의 비영 구조를 예측하는 ‘심볼릭 분해’와 그 핵심 산출물인 ‘제거 트리’를 다룬다. 그 후, 예측된 구조를 기반으로 효율적으로 부동소수점 연산을 수행하는 ‘수치적 분해’ 단계를 설명하며, 이 과정에서 성능을 극대화하기 위한 초절점(supernode) 및 다중전선(multifrontal) 기법을 소개한다. 마지막으로, 분해된 인수를 사용하여 최종 해를 구하는 과정을 살펴본다.
심볼릭 분해는 수치 계산에 앞서 촐레스키 인수 $L$의 비영 구조(sparsity pattern)를 미리 파악하는 단계이다.15 이 단계는 오직 행렬의 비영 위치 정보(즉, 인접 그래프 구조)와 재정렬 순서에만 의존하며, 실제 수치 값은 사용하지 않는다.
심볼릭 분해의 장점:
$L$을 저장하는 데 필요한 메모리 양을 정확히 계산하고, 수치 분해 단계가 시작되기 전에 필요한 데이터 구조를 미리 할당할 수 있다. 이는 동적 메모리 할당으로 인한 오버헤드를 없애고 예측 가능한 실행을 가능하게 한다.54핵심 산출물: 제거 트리 (Elimination Tree, etree)
심볼릭 분해 과정에서 가장 중요하게 생성되는 데이터 구조가 바로 제거 트리이다.
정의: 제거 트리는 채워진 그래프 $G^+(A)$의 스패닝 트리(spanning tree)로, 각 정점(열) $j$의 부모는 인수 $L$의 $j$번째 열에서 대각 원소 바로 아래에 있는 첫 번째 비영 원소의 행 인덱스 $i$로 정의된다. 즉, parent[j] = min{i > j | L(i,j)!= 0} 이다.29 만약
$j$열에 대각 원소 외에 비영 원소가 없다면, $j$는 트리의 루트(root)가 된다.
역할과 의미: 제거 트리는 단순한 데이터 구조를 넘어, 전체 희소 촐레스키 분해 과정의 ‘계산 흐름도’ 역할을 한다. 이 트리는 열들 간의 계산 의존성을 완벽하게 나타낸다. 만약 $L_{ij} \neq 0$ (단, $i>j$) 이라면, 이는 제거 트리에서 정점 $j$가 정점 $i$의 자손(descendant)임을 의미한다.29 이는
$j$열의 계산 결과가 $i$열을 계산하는 데 필요하다는 것을 뜻한다. 이 의존성 구조는 병렬성, 데이터 지역성, 그리고 고성능 알고리즘의 기반을 형성한다.
구축: 중요한 점은 제거 트리를 구축하기 위해 채워진 그래프 $G^+(A)$나 인수 $L$을 실제로 계산할 필요가 없다는 것이다. 원래 그래프 $G(A)$와 재정렬 순서만으로 $O(|A|)$ 또는 그에 준하는 매우 효율적인 시간 복잡도로 제거 트리를 구축하는 알고리즘들이 존재한다.29
수치적 분해는 심볼릭 분해에서 결정된 $L$의 구조 내에서, 실제 부동소수점 값들을 계산하는, 전체 과정에서 가장 계산 비용이 높은 단계이다.15 다양한 알고리즘 형태가 존재하지만, 크게 세 가지로 분류할 수 있다.
$L$의 $k$번째 열을 계산하기 위해, $k$열에 영향을 주는 모든 왼쪽의 열들($j<k$)의 정보를 가져와서 $k$열을 업데이트한 후, 최종적으로 $k$열을 분해한다. 이는 데이터가 필요한 시점에 가져오는 방식이며, CSC 저장 형식에 매우 자연스럽게 부합한다.21$k$번째 열의 분해를 완료한 후, 이 열이 앞으로 영향을 미칠 모든 오른쪽의 열들($j>k$)에 업데이트를 미리 전파하는 방식이다.$L$의 일부가 되고, 나머지 업데이트 정보는 부모 노드의 전선 행렬로 전달된다. 이 방식은 임시 저장 공간을 추가로 요구하지만, 계산의 대부분을 고도로 최적화된 밀집 행렬 연산(BLAS-3)으로 구성하여 현대 컴퓨터 아키텍처에서 최고의 성능을 이끌어낼 수 있다.2성능 가속화 기법: 초절점 (Supernodes)
수치 분해의 성능을 극대화하기 위한 핵심적인 최적화 기법은 초절점(supernode)의 활용이다.
제거 트리는 단순한 데이터 구조를 넘어, 희소 촐레스키 분해의 모든 후속 단계(수치 분해, 병렬화, 성능 최적화)를 지배하는 중심적인 ‘청사진’이다. 서로 다른 서브트리(subtree)에 속한 노드들은 서로 계산 의존성이 없으므로 동시에 처리할 수 있으며, 이는 병렬 희소 직접 솔버의 기본 원리가 된다.56 초절점 기법 역시 이 트리에서 특정 패턴(유사한 비영 구조를 가진 노드들의 체인)을 찾아내어 계산을 ‘블록화’하고, 하드웨어 성능을 최대한 끌어내는 정교한 최적화 기법이다.15
수치 분해가 완료되어 재정렬된 행렬 $PAP^T$의 인수 $L_P$를 얻었다면, 마지막으로 선형 시스템을 푸는 단계가 남았다. 이 과정은 재정렬된 변수 순서에 맞춰 진행된다.
원래 시스템 $Ax=b$는 $P(Ax) = Pb$ 이고, $A=P^T L_P L_P^T P$ 이므로, $P(P^T L_P L_P^T P)x = Pb$ 가 된다. $PP^T=I$ 이므로, 풀어야 할 시스템은 $L_P L_P^T (Px) = Pb$ 이다. 여기서 $x' = Px$ 로 치환하면, 다음 과정을 거친다 60:
$b' = Pb$ 를 계산한다.$L_P y = b'$ 를 풀어 중간 벡터 $y$를 구한다.$L_P^T x' = y$ 를 풀어 재정렬된 해 벡터 $x'$를 구한다.$x = P^T x'$ 를 계산한다.이 삼각 시스템 풀이 단계는 분해 단계에 비해 계산 비용이 훨씬 저렴하며($O(\text{nnz}(L_P))$), 희소성을 활용하여 효율적으로 수행된다.
희소 촐레스키 분해는 단순한 학문적 호기심의 산물이 아니다. 이 기술의 발전은 실제 공학 및 과학 분야에서 발생하는 구체적이고 까다로운 문제들을 해결하려는 노력의 결과물이다. 이 장에서는 유한요소해석, 전자 회로 시뮬레이션, 컴퓨터 그래픽스라는 세 가지 대표적인 응용 분야를 통해, 각 분야의 문제 특성이 어떻게 희소 행렬의 구조와 알고리즘의 발전에 영향을 미쳤는지 심층적으로 분석한다. 이를 통해 이론적 지식이 실제 문제 해결에 어떻게 적용되고 진화해 왔는지에 대한 깊은 통찰을 얻을 수 있다.
문제 배경: 유한요소해석은 구조물의 응력 해석, 열 전달, 유체 흐름 등 연속적인 물리 현상을 다루는 편미분 방정식을 풀기 위한 강력한 수치 기법이다. FEA는 복잡한 형상의 도메인을 삼각형이나 사각형 같은 작은 유한 요소(finite element)들의 집합으로 나누고, 각 요소 내에서 해를 단순한 다항식으로 근사한다. 이 과정을 통해 편미분 방정식은 거대한 대수 방정식 시스템 $K u = f$로 변환된다.1
행렬 특성: 여기서 $K$는 강성 행렬(stiffness matrix)이라 불리며, 다음과 같은 특징을 가진다.
$K$는 매우 희소하다.알고리즘 영향: FEA 문제의 기하학적 특성은 중첩 분할(ND) 알고리즘의 발전을 촉진했다. 2D나 3D 메쉬는 작은 크기의 정점 분리자를 쉽게 찾을 수 있는 구조를 가지고 있어, ND가 필인을 효과적으로 줄이는 데 매우 성공적임이 이론적으로나 실험적으로 입증되었다.47 또한, 동일한 메쉬에 대해 하중 조건(
$f$)만 바꿔 여러 번 해석하는 경우가 많아, 심볼릭 분해와 수치 분해 단계를 분리하는 아키텍처가 매우 효과적이다.20 대규모 병렬 처리가 필수적인 현대의 FEA에서는 초절점(supernodal) 기법과 결합된 병렬 ND 기반 솔버가 표준으로 자리 잡고 있다.59
알고리즘 영향: 회로 행렬의 불규칙성은 전역적 분할에 기반한 ND보다 지역적 휴리스틱인 최소 차수(MD) 계열 알고리즘을 더 선호하게 만들었다. KLU와 같은 회로 시뮬레이션 전용 솔버는 행렬을 블록 삼각 형태(Block Triangular Form, BTF)로 분해하는 전처리 기법과 MD를 결합하여 회로 행렬의 특성을 효과적으로 활용한다.62 또한, 과도 해석에서는 회로의 토폴로지(비영 구조)는 고정된 채 소자의 동작점(수치 값)만 계속 변하므로, 심볼릭 분해와 수치 분해를 분리하는 아키텍처가 성능에 결정적인 역할을 한다.3
문제 배경: 컴퓨터 그래픽스 분야에서는 탄성체의 변형, 옷감이나 머리카락의 움직임, 유체 시뮬레이션, 기하학적 메쉬 편집 등 다양한 물리 기반 시뮬레이션을 수행한다. 이러한 시뮬레이션은 안정적인 시간 적분을 위해 암시적 방법(implicit method)을 사용하는 경우가 많으며, 이 과정에서 매 시간 단계마다 거대한 희소 선형 시스템을 풀어야 한다.63
행렬 특성 및 도전 과제: 동적 희소성 (Dynamic Sparsity): 그래픽스 응용 분야의 가장 큰 특징은 행렬의 비영 구조가 고정되어 있지 않고 시간에 따라 변한다는 점이다.
물체 간의 접촉(contact)이 발생하거나 떨어질 때,
메쉬가 찢어지거나 파괴(fracture)될 때,
또는 메쉬 품질을 유지하기 위해 국소적으로 재구성(remeshing)할 때,
행렬의 비영 패턴이 동적으로 변화한다.63
알고리즘 영향: 이러한 동적 희소성은 전통적인 희소 촐레스키 파이프라인에 심각한 도전 과제를 제기한다. 매 프레임마다 비용이 많이 드는 전체 재정렬 및 심볼릭 분해를 다시 수행하는 것은 엄청난 계산 낭비이다. 이 문제를 해결하기 위해 희소 촐레스키 분해의 최신 연구 분야가 탄생했다.
$A_{new} = A_{old} + vv^T$)와 같이 작은 변화가 생겼을 때, 기존의 인수 $L$을 처음부터 다시 계산하지 않고 효율적으로 수정하는 기법이다. 이는 변화의 영향을 받는 $L$의 일부 열만 선택적으로 재계산한다.40이 사례들은 희소 촐레스키 분해 기술의 발전이 순수한 수학적 탐구가 아니라, 각 응용 분야가 제기하는 구체적이고 까다로운 ‘요구사항’과 ‘병목 현상’을 해결하는 과정에서 이루어졌음을 명확히 보여준다. FEA의 ‘규칙성’은 ND 알고리즘의 이론적 토대를 제공했고, 회로 시뮬레이션의 ‘불규칙성’과 ‘반복성’은 하이브리드 재정렬과 심볼릭/수치 분리 아키텍처를 공고히 했으며, 컴퓨터 그래픽스의 ‘동적 변화’는 업데이트 및 적응형 재사용과 같은 최첨단 기법의 등장을 이끌었다. 이처럼 희소 촐레스키 분해는 다양한 응용 분야와의 상호작용을 통해 끊임없이 진화하는, 살아있는 문제 해결 지향적인 분야이다.
이론적 지식을 실제 코드로 구현하고 활용하는 것은 이론을 완전히 이해하는 데 필수적인 과정이다. 이 부록은 Python의 과학 계산 라이브러리인 SciPy와 scikit-sparse를 사용하여 희소 촐레스키 분해의 전체 과정을 단계별로 시연하고, 산업 표준으로 여겨지는 CHOLMOD와 같은 고성능 라이브러리의 역할과 사용법을 간략히 소개하여 이론과 실제 구현 사이의 간극을 메우는 것을 목표로 한다.
고수준 과학 계산 환경에서는 희소 촐레스키 분해의 복잡한 단계들이 잘 추상화되어 있어 사용자가 편리하게 이용할 수 있다. 여기서는 Python을 기반으로 한 예시를 보인다.
희소 행렬 생성: scipy.sparse 모듈은 다양한 희소 행렬 형식을 지원한다. 촐레스키 분해에 효율적인 CSC 형식을 사용하여 예제 SPD 행렬을 생성할 수 있다.37
import numpy as np
from scipy.sparse import csc_matrix, csr_matrix, triu, diags
# 예제 5x5 SPD 희소 행렬 생성
# (실제 응용에서는 유한요소법 등으로 생성됨)
row = np.array()
col = np.array()
data = np.array([10, -2, 11, -3, 15, -1, 16, -2, -3, 12], dtype=float)
# 대칭성을 위해 상삼각/하삼각 부분을 모두 포함
A_coo = csr_matrix((data, (row, col)), shape=(5, 5))
A_upper = triu(A_coo)
A = A_upper + A_upper.T - diags(A_upper.diagonal())
A_csc = A.tocsc()
print("Original Sparse Matrix (CSC format):")
print(A_csc)
재정렬, 심볼릭 및 수치 분해: 고성능 라이브러리에서는 재정렬, 심볼릭 분해, 수치 분해가 하나의 함수 호출로 통합되어 있다. scikit-sparse 라이브러리는 CHOLMOD의 강력한 기능을 Python에서 사용할 수 있도록 래핑(wrapping)한다. cholesky 함수는 내부적으로 최적의 재정렬(기본적으로 AMD)을 수행하고, 심볼릭 분석을 거쳐 수치 분해까지 완료한 Factor 객체를 반환한다.40
from sksparse.cholmod import cholesky
# A_csc는 CSC 형식의 희소 SPD 행렬
# cholesky 함수가 재정렬, 심볼릭, 수치 분해를 모두 수행
try:
factor = cholesky(A_csc)
print("\nCholesky factorization successful.")
except Exception as e:
print(f"\nCholesky factorization failed: {e}")
# 이 경우 행렬이 SPD가 아닐 수 있음
이 factor 객체는 분해된 인수 $L_P$와 순열 정보 $P$를 모두 내포하고 있다.
삼각 시스템 풀이: 분해된 factor 객체를 함수처럼 사용하여 선형 시스템 $Ax=b$를 매우 효율적으로 풀 수 있다. factor(b) 호출은 내부적으로 순열 적용, 전진 대입, 후진 대입, 역순열 적용을 모두 처리해준다.40
# 우변 벡터 b 생성
b = np.array([1, 2, 3, 4, 5])
# factor 객체를 사용하여 Ax=b 풀이
x = factor(b)
print("\nSolution vector x:")
print(x)
# 검증: A @ x 가 b와 유사한지 확인
print("\nVerification (A @ x):")
print(A_csc @ x)
직접 희소 촐레스키 분해의 모든 단계를 저수준으로 구현하는 것은 매우 복잡하고 어려운 작업이다. 다행히도, 수십 년간의 연구 결과가 집약된 고도로 최적화된 오픈소스 라이브러리들이 존재하며, 대부분의 과학 계산 소프트웨어는 이들을 기반으로 한다.
$LL^T$ 및 $LDL^T$)에 특화되어 있다.40 CHOLMOD의 주요 특징은 다음과 같다.
이러한 고성능 라이브러리들은 MATLAB, R(Matrix 패키지), Python(scikit-sparse), Julia 등 많은 고수준 과학 계산 환경의 희소 행렬 연산 엔진으로 사용된다.40 이는 사용자가 복잡한 저수준 구현의 세부 사항에 신경 쓰지 않고도, 자신의 응용 문제에 집중하면서 최적화된 희소 직접 솔버의 성능을 최대한 활용할 수 있게 해준다. 따라서 희소 촐레스키 분해를 실제로 사용하고자 한다면, 이러한 검증된 라이브러리를 활용하는 것이 가장 현명한 접근 방식이다.
| Cholesky Factorization | Advanced Matrix Computations Class Notes - Fiveable, accessed July 24, 2025, https://library.fiveable.me/advanced-matrix-computations/unit-2/cholesky-factorization/study-guide/mJZImJ7Ld5v7jWFW |
| Comparison of Nested Dissection | Download Table - ResearchGate, accessed July 24, 2025, https://www.researchgate.net/figure/Comparison-of-Nested-Dissection_tbl4_281452673 |
| Hybridizing Nested Dissection and Halo Approximate Minimum Degree for Efficient Sparse Matrix Ordering. | Request PDF - ResearchGate, accessed July 24, 2025, https://www.researchgate.net/publication/220104624_Hybridizing_Nested_Dissection_and_Halo_Approximate_Minimum_Degree_for_Efficient_Sparse_Matrix_Ordering |