Oct-File에서의 희소 행렬 만들기
Oct-File에서의 희소 행렬 만들기 (Creating Sparse Matrices in Oct-Files)
oct-file 안에서 희소 행렬을 만드는 방법은 크게 두 가지가 있어요. 행·열·값 벡터 세 개를 만들어 행렬을 구성하는 방법과, 알맞은 공간을 가진 희소 행렬을 먼저 만든 뒤 값을 채워 넣는 방법이죠. Appendix A.1.6.2절을 정리해 볼게요.
본문
희소 행렬을 만드는 데는 두 가지 유용한 전략이 있어요. 첫 번째는 행 인덱스, 열 인덱스, 데이터 값을 나타내는 벡터 세 개를 만들고 이들로부터 행렬을 만들는 것이고, 두 번째는 알맞은 공간의 희소 행렬을 만든 뒤 값을 채워 넣는 것이에요. 두 기법 모두 장점과 단점이 있습니다.
아래는 첫 번째 기법으로 작은 희소 행렬을 만드는 예시예요.
int nz, nr, nc;
nz = 4, nr = 3, nc = 4;
ColumnVector ridx (nz);
ColumnVector cidx (nz);
ColumnVector data (nz);
ridx(0) = 1; cidx(0) = 1; data(0) = 1;
ridx(1) = 2; cidx(1) = 2; data(1) = 2;
ridx(2) = 2; cidx(2) = 4; data(2) = 3;
ridx(3) = 3; cidx(3) = 4; data(3) = 4;
SparseMatrix sm (data, ridx, cidx, nr, nc);
이것은 Storage of Sparse Matrices 절에 주어진 행렬을 만들어요. 압축 행렬(compressed matrix) 형식은 행렬 자체를 만들 때는 사용되지 않고, 내부적으로만 사용된다는 점을 유의하세요.
Sparse Matrices 장에서 논의했듯이, 희소 행렬의 값은 증가하는 열 우선(column-major) 순서로 저장됩니다. 사용자가 전달하는 데이터가 이 요구를 반드시 지킬 필요는 없지만, 데이터를 미리 정렬하면 희소 행렬 생성이 크게 빨라져요.
이 기법의 단점은 데이터의 복사본 두 개가 잠시 존재한다는 점이에요. 메모리가 극도로 제약된 문제라면 희소 행렬을 만드는 데 이 기법이 최선이 아닐 수 있습니다.
대안은 먼저 원하는 수의 0이 아닌 원소를 가진 희소 행렬을 만든 다음, 나중에 그 원소들을 채우는 것이에요. 샘플 코드:
int nz, nr, nc;
nz = 4, nr = 3, nc = 4;
SparseMatrix sm (nr, nc, nz);
sm(0,0) = 1; sm(0,1) = 2; sm(1,3) = 3; sm(2,3) = 4;
이것은 이전과 같은 행렬을 만들어요. 역시 엄격히 필요하지는 않지만, 희소 행렬을 만들고 원소를 열 우선 순서로 추가하는 것이 훨씬 빠릅니다. 그 이유는 현재 알려진 원소 목록의 끝에 원소를 삽입하면 새 원소를 삽입하기 위해 행렬의 어떤 원소도 옮길 필요가 없기 때문이에요. 열 인덱스만 갱신하면 되죠.
이 방법으로 희소 행렬을 만들 때 주의할 점이 몇 가지 더 있어요. 첫째, 행렬에 실제로 삽입된 원소 수보다 더 적은 원소를 가진 희소 행렬을 만드는 것이 가능해요. 따라서
int nr, nc;
nr = 3, nc = 4;
SparseMatrix sm (nr, nc, 0);
sm(0,0) = 1; sm(0,1) = 2; sm(1,3) = 3; sm(2,3) = 4;
은 완전히 유효합니다. 다만 이것은 아주 나쁜 생각이에요. 희소 행렬에 새 원소가 추가될 때마다 행렬이 더 많은 공간을 요청하고 메모리를 재할당해야 하거든요. 이것은 비싼 연산으로, 이러한 방식의 희소 행렬 생성을 크게 느리게 만들어요. 초과 저장 공간을 가진 희소 행렬을 만드는 것도 가능해서, 이 예시에서 nz를 4보다 크게 하는 것도 유효합니다. 단점은 행렬이 엄격히 필요한 것보다 더 많은 메모리를 차지한다는 점이에요.
물론 행렬을 채우기 전에 0이 아닌 원소의 수를 항상 알 수 있는 건 아니에요. 이런 이유로 희소 행렬의 추가적인 미사용 저장 공간은 생성 후에 maybe_compress 함수로 제거할 수 있어요. 미사용 저장 공간을 해제하는 것 외에도 maybe_compress는 행렬에서 0 원소를 제거할 수도 있습니다. 행렬에서 0 원소를 제거하는 것은 maybe_compress 함수의 인자를 true로 설정해서 제어해요. 다만 0을 제거하는 비용은 높은데, 원소를 다시 정렬해야 하기 때문이에요. 가능하다면 처음부터 불필요한 0을 추가하지 않는 게 더 낫습니다. maybe_compress 사용 예시:
int nz, nr, nc;
nz = 6, nr = 3, nc = 4;
SparseMatrix sm1 (nr, nc, nz);
sm1(0,0) = 1; sm1(0,1) = 2; sm1(1,3) = 3; sm1(2,3) = 4;
sm1.maybe_compress (); // No zero elements were added
SparseMatrix sm2 (nr, nc, nz);
sm2(0,0) = 1; sm2(0,1) = 2; sm(0,2) = 0; sm(1,2) = 0;
sm1(1,3) = 3; sm1(2,3) = 4;
sm2.maybe_compress (true); // Zero elements were added
maybe_compress 함수는 행렬 생성을 느리게 하므로 가능하면 사용을 피해야 합니다.
세 번째 희소 행렬 생성 방법은 압축 행(compressed row) 형식의 데이터를 직접 다루는 것이에요. 이 고급 기법의 예시는 다음과 같아요.
octave_value arg;
...
int nz, nr, nc;
nz = 6, nr = 3, nc = 4; // Assume we know the max # nz
SparseMatrix sm (nr, nc, nz);
Matrix m = arg.matrix_value ();
int ii = 0;
sm.cidx (0) = 0;
for (int j = 1; j < nc; j++)
{
for (int i = 0; i < nr; i++)
{
double tmp = m(i,j);
if (tmp != 0.)
{
sm.data(ii) = tmp;
sm.ridx(ii) = i;
ii++;
}
}
sm.cidx(j+1) = ii;
}
sm.maybe_compress (); // If don't know a priori the final # of nz.
이것은 아마 희소 행렬을 만드는 가장 효율적인 방법일 거예요.
마지막으로, 처음에 만든 저장 공간의 양이 희소 행렬을 완전히 저장하기에 부족한 경우가 생길 수 있어요. 그래서 희소 메모리를 재할당하는 change_capacity 메서드가 존재합니다. 위 예시는 다음과 같이 수정되겠죠.
octave_value arg;
...
int nz, nr, nc;
nz = 6, nr = 3, nc = 4; // Guess the number of nz elements
SparseMatrix sm (nr, nc, nz);
Matrix m = arg.matrix_value ();
int ii = 0;
sm.cidx (0) = 0;
for (int j = 1; j < nc; j++)
{
for (int i = 0; i < nr; i++)
{
double tmp = m(i,j);
if (tmp != 0.)
{
if (ii == nz)
{
nz += 2; // Add 2 more elements
sm.change_capacity (nz);
}
sm.data(ii) = tmp;
sm.ridx(ii) = i;
ii++;
}
}
sm.cidx(j+1) = ii;
}
sm.maybe_compress (); // If don't know a priori the final # of nz.
희소 행렬의 0이 아닌 원소 수를 늘리거나 줄이는 것은 모두 비싼데, 메모리 재할당을 수반하기 때문이에요. 또한 행렬의 일부가(전체는 아니지만) 옛 복사본과 새 복사본으로 동시에 존재하기 때문에 추가 메모리가 필요해요. 따라서 가능하면 용량을 바꾸는 것을 피하세요.
더 알아보기
- octave-creating-sparse-matrices — 스크립트에서 희소 행렬 만들기
- octave-storage-of-sparse-matrices — 압축 열 저장 방식의 원리
- octave-external-code-interface — 외부 코드 인터페이스 개요