희소행렬

1. 개요[편집]

100만 x 100만 행렬인데 0이 99.999%라고? 그럼 0을 굳이 저장할 이유가 있나?

희소행렬(sparse matrix)은 성분의 대부분이 0이고 0이 아닌 성분(nonzero)이 극소수인 행렬을 말한다. 반대로 대부분의 성분이 0이 아닌 행렬은 밀집행렬(dense matrix)이라 부른다. 엄밀한 경계선은 없지만, 통상 0이 아닌 성분의 개수가 $O(n)$ 수준(행당 상수 개)이면 희소하다고 본다. 전산유체역학·구조해석·회로 해석(SPICE) 등 격자나 그래프 위에서 정의되는 거의 모든 시뮬레이션의 계수행렬이 극도로 희소하다.¹

희소성이 왜 축복인가 하면, 유한요소법이나 유한체적법에서 각 미지수는 이웃한 소수의 미지수하고만 연결되기 때문이다. 100만 개 격자점이 있어도 한 점은 고작 이웃 몇 개와만 방정식을 공유한다. 그러니 행렬의 각 행에는 0이 아닌 값이 몇 개뿐이고, 나머지 100만 개 가까이는 전부 0이다. 이 0들을 곧이곧대로 다 저장했다간 메모리가 순식간에 폭발하므로, 0이 아닌 값만 골라 저장하는 특수 자료구조가 필수다.

2. 왜 특수 저장이 필요한가[편집]

밀집 형식으로 $n \times n$ 행렬을 저장하면 $n^2$개의 실수가 필요하다. $n = 10^6$이면 $10^{12}$개, 배정밀도로 8 TB다. 개인 워크스테이션은커녕 웬만한 서버도 감당 못 한다.

반면 행당 0이 아닌 성분이 평균 7개뿐인 희소행렬이라면 실제 값은 700만 개, 약 56 MB로 충분하다. 8 TB 대 56 MB. 이 압도적 차이가 희소 저장의 존재 이유다. 게다가 저장뿐 아니라 연산도 이득이다. 행렬-벡터 곱을 밀집으로 하면 $O(n^2)$이지만, 희소 형식이면 0이 아닌 성분 개수에 비례해 $O(n)$으로 끝난다. 이 값싼 행렬-벡터 곱이 바로 반복법과 크리로프 부분공간법이 대규모 문제에서 위력을 발휘하는 근본 이유다.

3. 저장 형식[편집]

희소행렬 저장 형식은 여러 가지가 있지만, 실무의 양대 국룰은 CSR과 CSC다.

COO(Coordinate list, 좌표 형식)는 가장 직관적이다. 0이 아닌 성분마다 (행 인덱스, 열 인덱스, 값) 세 쌍을 그냥 나열한다. 만들기는 쉽지만 연산 효율이 나빠서, 주로 행렬을 조립할 때 임시로 쓰고 CSR/CSC로 변환한다.

CSR(Compressed Sparse Row, 압축 행 저장)은 가장 널리 쓰이는 형식이다. 세 개의 배열로 구성된다.

• values: 0이 아닌 값들을 행 우선(row-major) 순서로 나열
• col_indices: 각 값의 열 인덱스
• row_pointers: 각 행이 values에서 어디부터 시작하는지 가리키는 길이 $n+1$ 포인터

CSR의 강점은 행 단위 접근과 행렬-벡터 곱이 빠르다는 것이다. $i$번째 행의 성분들은 row_pointers[i]부터 row_pointers[i+1] 직전까지 연속으로 놓여 있어 캐시 효율이 좋다.

CSC(Compressed Sparse Column, 압축 열 저장)는 CSR을 열 기준으로 뒤집은 형식이다. 열 단위 접근과 전치 연산에 유리해서 LU 분해 기반 희소 직접 솔버나 최적화 라이브러리(예: SuiteSparse)가 선호한다. MATLAB의 내부 희소행렬은 CSC로 저장된다.

형식	구성	강점	주 사용처
COO	행·열·값 삼중쌍	조립·수정 쉬움	임시 조립
CSR	값·열인덱스·행포인터	행 접근, 행렬-벡터 곱	반복법 솔버
CSC	값·행인덱스·열포인터	열 접근, 전치	직접 솔버, 최적화

이 밖에 대각 위주 행렬을 위한 DIA, 블록 구조를 살린 BSR, GPU에서 각광받는 ELL/SELL 등 하드웨어와 패턴에 맞춘 형식이 수십 가지 존재한다.² GPU 컴퓨팅에서는 워프 단위 접근 효율 때문에 CSR을 그대로 쓰기보다 변형 형식을 쓰는 경우가 많다.

4. 채움현상[편집]

희소행렬의 최대 골칫거리는 LU 분해나 가우스 소거법으로 직접 풀 때 발생하는 채움현상(fill-in)이다. 소거 과정에서 원래 0이던 자리에 0이 아닌 값이 새로 생겨나는 현상으로, 방치하면 성긴 행렬이 분해 후엔 거의 밀집 행렬이 되어버린다. 애써 아낀 메모리가 도로 폭발하는 셈.

채움현상의 양은 소거 순서에 크게 좌우된다. 그래서 희소 직접 솔버는 분해 전에 행과 열을 재배열(reordering)해 채움을 최소화한다. 대표적인 순서화 기법은 다음과 같다.

• 최소 차수(Minimum Degree, AMD): 그래프에서 연결이 가장 적은 정점부터 소거
• 중첩 분할(Nested Dissection): 그래프를 재귀적으로 반씩 갈라 분할정복

다만 채움을 아무리 줄여도 3차원 대규모 문제에서는 한계가 있어, 결국 채움현상 자체가 없는 반복법과 다중격자법으로 넘어가는 경우가 많다. 반복법은 행렬-벡터 곱만 쓰므로 원래 희소성을 조금도 훼손하지 않는다.

5. 응용과 라이브러리[편집]

희소행렬은 시뮬레이션의 뼈대다. 유한요소법의 강성행렬, 전산유체역학의 압력 방정식 계수행렬, 반도체 소자 시뮬레이션의 자코비안, 심지어 구글의 페이지랭크 계산까지 전부 희소행렬 위에서 돈다.

실무에서 이걸 손으로 짤 일은 거의 없다. Python의 SciPy(scipy.sparse), Intel MKL, SuiteSparse(UMFPACK·CHOLMOD), PETSc, Eigen 등 잘 다듬어진 라이브러리가 저장 형식 변환부터 전처리기, 솔버까지 다 제공한다.³ 엔지니어가 할 일은 적절한 형식과 솔버를 고르는 안목을 기르는 것이다.

6. 관련 문서[편집]

• 반복법
• LU 분해 · 가우스 소거법
• 전처리기
• 크리로프 부분공간법
• 다중격자법
• 강성행렬
• 수치해석
• GPU 컴퓨팅 · 병렬 컴퓨팅

7. Footnotes[편집]

1. 회로 시뮬레이터 SPICE의 계수행렬이 대표적이다. 수십만 개 소자가 있어도 각 노드는 몇 개 소자하고만 연결되므로, 행렬은 눈물겹게 성기다. 애초에 희소행렬 이론의 상당 부분이 회로 해석에서 발전했다. ↩

2. “어떤 저장 형식이 최고냐”는 질문에는 정답이 없다. 행렬의 0 분포 패턴, 쓸 연산, 돌릴 하드웨어에 따라 최적 형식이 다 다르다. 그래서 고성능 라이브러리는 형식 변환 함수를 잔뜩 제공하고, 사용자는 벤치마크를 돌려 제일 빠른 걸 고른다. 결국 또 일단 돌려보는 것이다. ↩

3. SuiteSparse를 만든 팀 데이비스(Tim Davis)는 이 분야의 전설이다. MATLAB의 백슬래시 연산자 \가 희소행렬을 만나면 뒤에서 그의 코드가 돌아간다. 전 세계 공대생이 무심코 친 A\b 한 줄이 사실은 수십 년 축적된 희소 솔버의 집약체인 것이다. ↩