6.18 희소 행렬과 효율적 저장 구조

1. 희소 행렬의 개념

희소 행렬(sparse matrix)은 대부분의 성분이 0이고 비0 성분의 수가 전체 성분 수에 비해 매우 적은 행렬을 가리킨다. 정확한 임계 비율에 대한 보편적 정의는 없으나, 일반적으로 비0 성분의 수가 $O(n)$ 또는 $O(n \log n)$ 수준이며 전체 성분 수 $n^2$ 에 비해 무시할 수 있을 때 희소하다고 한다. 그 반대 개념인 밀집 행렬(dense matrix)은 대부분의 성분이 비0이다.

희소성의 의의는 단순히 저장 공간의 절약에 그치지 않는다. 적절한 저장 구조와 알고리즘을 결합하면 행렬-벡터 곱, 선형계 풀이, 분해 등의 핵심 연산을 비0 성분의 수에 비례하는 시간으로 수행할 수 있어, 대규모 문제의 실시간 처리가 가능해진다.

2. 희소성의 정량적 척도

행렬 $A \in \mathbb{R}^{m \times n}$ 의 비0 성분의 수를 $\text{nnz}(A)$ 로 표기하면 희소도(sparsity)는 다음과 같이 정의된다.

$\text{sparsity}(A) = 1 - \frac{\text{nnz}(A)}{mn}$

희소도가 1에 가까울수록 행렬은 더 희소하다. 밀도(density)는 $1 - \text{sparsity}(A)$ 로 정의된다.

희소 행렬 저장 형식

희소 행렬의 저장 형식은 사용 목적에 따라 다양하게 설계되어 있으며, 각 형식은 저장 효율과 특정 연산의 효율성 사이의 절충을 반영한다.

COO 형식 (좌표 형식)

좌표 형식(coordinate format)은 비0 성분을 (행 지표, 열 지표, 값)의 삼중쌍으로 저장한다.

$\text{row} = [i_1, i_2, \ldots, i_k], \quad \text{col} = [j_1, j_2, \ldots, j_k], \quad \text{val} = [v_1, v_2, \ldots, v_k]$

저장 공간은 $3 \cdot \text{nnz}(A)$ 이며, 행렬을 동적으로 구성할 때 새로운 성분을 추가하기 쉽다는 장점이 있다. 그러나 행렬-벡터 곱의 효율은 떨어지며, 일반적으로 행렬 구성 단계에서 임시 형식으로 사용된 뒤 다른 형식으로 변환된다.

2.1 CSR 형식 (압축 행 저장)

압축 행 저장(compressed sparse row) 형식은 행 단위로 비0 성분을 정렬하고 다음의 세 배열로 저장한다.

$\text{val}$ : 비0 성분의 값을 행 우선 순서로 나열한 배열, 길이 $\text{nnz}(A)$
$\text{col\_idx}$ : 각 비0 성분의 열 지표 배열, 길이 $\text{nnz}(A)$
$\text{row\_ptr}$ : 각 행이 시작되는 $\text{val}$ 배열의 위치, 길이 $m + 1$

총 저장 공간은 $2 \cdot \text{nnz}(A) + m + 1$ 이다. CSR 형식은 행렬-벡터 곱 $\mathbf{y} = A\mathbf{x}$ 를 다음과 같이 효율적으로 수행할 수 있게 한다.

$y_i = \sum_{k = \text{row\_ptr}[i]}^{\text{row\_ptr}[i+1] - 1} \text{val}[k] \cdot x[\text{col\_idx}[k]]$

각 행의 비0 성분에 대해서만 연산이 수행되므로 총 연산량은 $O(\text{nnz}(A))$ 이다. CSR은 가장 보편적인 저장 형식이며, 대부분의 희소 선형대수 라이브러리가 기본으로 채택한다.

CSC 형식 (압축 열 저장)

압축 열 저장(compressed sparse column) 형식은 CSR의 열 우선 변형이며, 열 단위 접근이 빈번한 경우에 사용된다. 자코비안의 열 단위 접근, 전치 행렬과 벡터의 곱 $A^\top \mathbf{x}$ 등에 유리하다.

DIA 형식 (대각 저장)

대각 저장(diagonal format)은 비0 성분이 소수의 대각선에 집중된 행렬에 적합한 형식이다. 각 대각선의 값과 그 오프셋을 별도로 저장한다. 유한 차분법의 행렬, 1차원 합성곱 행렬 등에 효과적이다.

ELL 형식

ELLPACK 형식은 각 행이 일정한 비0 성분 수를 가지거나 그에 가까운 경우에 사용된다. $m \times K$ 형태의 두 배열( $K$ 는 행당 비0 성분 수의 최댓값)을 사용하여 저장하며, GPU에서의 병렬 연산에 유리한 메모리 접근 패턴을 제공한다.

블록 희소 형식

대각선 또는 작은 영역에 밀집된 비0 블록이 산재하는 행렬에는 블록 CSR(BSR)과 같은 블록 단위 저장 형식이 사용된다. 유한 요소법 행렬과 다물체 동역학 시스템의 행렬이 대표적인 예이다.

희소 행렬 연산의 시간 복잡도

연산	밀집 행렬	희소 행렬 (CSR)
행렬-벡터 곱 $A\mathbf{x}$	$O(mn)$	$O(\text{nnz}(A))$
행렬 덧셈 $A + B$	$O(mn)$	$O(\text{nnz}(A) + \text{nnz}(B))$
행렬 곱셈 $AB$	$O(mnp)$	출력 비0 수에 의존
전치 $A^\top$	$O(mn)$	$O(\text{nnz}(A) + n)$

희소 행렬 곱셈의 출력 행렬 $AB$ 는 일반적으로 입력보다 더 밀집할 수 있으므로, 곱셈의 결과 희소도는 사전에 정확히 예측되지 않는다. 이를 채움 발생(fill-in)이라 한다.

희소 행렬의 분해와 채움 발생

희소 선형계의 직접 풀이에서는 LU 분해, 촐레스키 분해, QR 분해 등이 사용되며, 이때 원래 0이었던 위치가 분해 과정에서 비0이 되는 채움 발생이 가장 큰 효율 저하 요인이다. 채움 발생을 최소화하기 위해 다음의 전략이 사용된다.

전략 1 (최소 차수 순서, AMD). 각 단계에서 가장 적은 채움을 발생시키는 행/열을 선택한다.

전략 2 (네스티드 분할, METIS). 그래프 분할에 기반하여 행렬을 재배열한다.

전략 3 (역방향 커트힐-맥키, Reverse Cuthill-McKee). 대역폭(bandwidth)을 줄이는 순열을 적용한다.

이러한 재배열은 분해 후 채움 비0의 수를 결정적으로 줄이며, 대규모 희소 선형계 풀이의 핵심 기술이다.

반복법과 희소 행렬

대규모 희소 행렬에 대해서는 직접 분해보다 반복법이 더 효율적인 경우가 많다. 켤레 기울기법(conjugate gradient), GMRES, BiCGSTAB과 같은 크릴로프 부분 공간 방법은 행렬을 직접 변형하지 않고 행렬-벡터 곱만 사용하므로, 희소성을 그대로 유지한다. 각 반복의 비용은 $O(\text{nnz}(A))$ 이며, 적절한 전처리(preconditioning)와 결합하면 큰 시스템도 효율적으로 풀 수 있다.

로봇공학에서의 응용

그래프 SLAM의 정보 행렬

그래프 SLAM에서 자세 변수와 지도 변수를 노드로 하고 측정값을 간선으로 하는 인수 그래프(factor graph)는 매우 희소한 정보 행렬을 만든다. 각 측정값은 관련된 두 노드 사이의 항만 비0으로 만들기 때문이다. 수만 개의 자세와 수십만 개의 측정값을 포함하는 SLAM 문제도 희소 분해와 적절한 변수 순서화를 통해 효율적으로 풀린다.

모델 예측 제어의 KKT 행렬

이산 시간 모델 예측 제어에서 예측 구간 $N$ 에 걸친 최적화 문제는 블록 띠 구조(block-banded structure)를 가지는 대규모 KKT 시스템을 만든다. 이 구조를 활용하여 $O(N)$ 의 복잡도로 시스템을 풀 수 있는 리카치 재귀 또는 띠 분해가 사용된다.

다물체 동역학의 질량 행렬

트리 구조 다관절 로봇의 관절 공간 관성 행렬은 일반적으로 밀집하지만, 작업 공간 동역학과 제약 조건이 결합된 형태에서는 희소 블록 구조가 나타난다. 폐연쇄 메커니즘과 유연체 동역학의 시스템은 더욱 강한 희소성을 가진다.

유한 요소 해석

로봇의 유연 부재 해석, 접촉 역학의 강체-유연체 결합 모델 등에 사용되는 유한 요소 강성 행렬은 지역적 결합만을 가지므로 매우 희소하다. 이는 토플리츠 또는 블록 띠 형태의 행렬로 저장 및 처리된다.

카메라 번들 조정

다시점 기하학에서 카메라 자세와 3차원 점을 동시에 추정하는 번들 조정(bundle adjustment) 문제는 카메라-점 사이의 관측 관계만 비0으로 가지는 희소 자코비안을 만든다. 이 자코비안의 정규 방정식 행렬은 카메라 블록과 점 블록으로 분할된 화살촉(arrowhead) 구조를 가지며, 슈어 보수 기법을 통해 효율적으로 풀린다.

제어 할당과 액추에이터 매핑

다수의 액추에이터를 가진 로봇에서 제어 할당 행렬은 각 액추에이터가 특정 자유도에만 영향을 주는 구조 때문에 희소하다. 이러한 구조는 실시간 제어 할당 알고리즘의 효율적 구현을 가능하게 한다.

참고문헌

Davis, T. A. (2006). Direct Methods for Sparse Linear Systems. SIAM.
Saad, Y. (2003). Iterative Methods for Sparse Linear Systems (2nd ed.). SIAM.
Golub, G. H., & Van Loan, C. F. (2013). Matrix Computations (4th ed.). Johns Hopkins University Press.
Dellaert, F., & Kaess, M. (2017). Factor Graphs for Robot Perception. Foundations and Trends in Robotics, 6(1-2), 1-139.

Version: 1.0