희소 행렬의 저장 방식
희소 행렬의 저장 방식 (Storage of Sparse Matrices)
사용자가 희소 행렬이 실제로 어떻게 저장되는지 꼭 이해해야 하는 건 아니에요. 다만 이 원리를 알면 희소 행렬의 크기를 가늠하는 데 큰 도움이 되고, 자신만의 oct-file을 만들고 싶은 분이라면 저장 기법을 이해하는 게 필수랍니다. Octave 매뉴얼 22.1.1절을 정리해 볼게요.
본문
희소 행렬 데이터를 저장하는 방법은 아주 많아요. 모든 방법이 공통적으로 추구하는 건, 풀고자 하는 특정 문제 계열에 대한 사전 지식을 활용해 복잡도와 저장 공간을 줄이는 거예요. 희소 행렬 저장에 쓰이는 기법들에 대한 좋은 요약은 Saad의 문헌에서 찾을 수 있어요 (Footnote 8).
전체(full) 행렬에서는 행렬 원소가 메모리에서 어디에 놓이는지만 봐도 그 원소가 행렬 안에서 어느 위치인지 알 수 있어요. 하지만 희소 행렬은 그렇지 않아요. 그래서 행렬의 0이 아닌 원소들의 위치도 함께 저장해야 합니다.
가장 직관적인 방법은 행렬 원소를 삼중항(triplet)으로 저장하는 거예요. 두 원소는 배열 속의 위치(행과 열), 나머지 하나는 데이터 자체죠. 개념적으로 이해하기 쉬우지만 필요한 것보다 더 많은 저장 공간을 써요.
Octave에서 쓰는 저장 기법은 **압축 열 형식(compressed column format)**이에요. Yale 형식과 비슷합니다 (Footnote 9). 이 형식에서는 각 원소의 행 위치와 데이터를 앞서처럼 저장해요. 그런데 같은 열의 모든 원소가 컴퓨터 메모리에서 서로 인접하게 저장된다고 가정하면, 각 원소의 위치 대신 각 열에 있는 0이 아닌 원소의 개수만 저장하면 돼요. 따라서 행렬이 열 개수보다 0이 아닌 원소를 더 많이 가질 때 메모리 사용량 관점에서 이득이 생깁니다.
실제로 열 인덱스는 열 개수보다 원소 하나를 더 많이 가지며, 첫 원소는 항상 0이에요. 이렇게 하면 처음이나 마지막 열을 위한 특별한 case가 필요 없어져 코드가 단순해지는 이점이 있어요. C로 이를 보여주는 짧은 예시는 다음과 같아요.
for (j = 0; j < nc; j++)
for (i = cidx(j); i < cidx(j+1); i++)
printf ("nonzero element (%i,%i) is %d\n",
ridx(i), j, data(i));
이해를 돕기 위해 예시 행렬에 어떻게 적용되는지 살펴볼게요. 다음 행렬을 봐 주세요.
1 2 0 0
0 0 0 3
0 0 0 4
이 행렬의 0이 아닌 원소는
(1, 1) ⇒ 1
(1, 2) ⇒ 2
(2, 4) ⇒ 3
(3, 4) ⇒ 4
이것은 각각 열 인덱싱, 행 인덱싱, 데이터를 나타내는 세 벡터 cidx, ridx, data로 저장됩니다. 위 행렬에 대한 세 벡터의 내용은
cidx = [0, 1, 2, 2, 4]
ridx = [0, 0, 1, 2]
data = [1, 2, 3, 4]
여기서 주의할 점은 이 표현이 첫 번째 행과 열이 0부터 시작한다고 가정하는 반면, Octave 자체의 행·열 인덱싱은 1부터 시작한다는 거예요. 따라서 i번째 열의 원소 개수는 cidx (i + 1) - cidx (i)로 주어집니다.
Octave는 압축 열 형식을 사용하지만, 압축 행 형식도 얼마든지 가능하다는 점을 알아 두세요. 다만 희소 행렬과 전체 행렬이 섞여 있는 혼합 연산의 맥락에서는, 희소 행렬의 원소가 전체 행렬과 같은 순서로 놓이는 게 말이 돼요. Octave는 전체 행렬을 열 우선(column major) 순서로 저장하므로, 희소 행렬도 같은 방식으로 저장됩니다.
Octave가 쓰는 희소 행렬 저장에 대한 추가 제약은, 각 행의 원소가 행 인덱스의 증가 순서로 저장돼야 한다는 거예요. 이는 특정 연산을 더 빠르게 만들지만, 희소 행렬을 만들 때 원소를 정렬해야 하는 필요성을 부과해요. 원소가 정렬되어 있지 않으면 두 희소 행렬을 연결하는 같은 연산이 더 쉽고 빨라질 수 있지만, 다른 곳에서는 복잡성과 속도 문제를 더합니다.
Footnotes
(8) Y. Saad "SPARSKIT: A basic toolkit for sparse matrix computation", 1994, https://www-users.cs.umn.edu/~saad/software/SPARSKIT/paper.ps
(9) https://en.wikipedia.org/wiki/Sparse_matrix#Yale_format
더 알아보기
- octave-sparse-matrices — 희소 행렬 개념과 챕터 구성
- octave-creating-sparse-matrices — 희소 행렬 만들기 함수들
- octave-sparse-linear-algebra — 희소 행렬의 선형대수 솔버