희소 행렬 만들기

희소 행렬 만들기 (Creating Sparse Matrices)

희소 행렬을 만드는 방법은 여러 가지가 있어요. 상황에 따라 값을 처음부터 생성하는 함수를 쓰거나, 벡터로부터 조립하거나, 빈 행렬을 만든 뒤 채워 넣을 수 있답니다. Octave 매뉴얼 22.1.2절 내용을 정리해 볼게요.

출처: Creating Sparse Matrices

본문

희소 행렬을 만드는 방법은 크게 네 가지로 나눌 수 있어요.

함수에서 반환받기: 희소 행렬을 직접 돌려주는 함수가 여럿 있어요. speye, sprand, diag 등이 대표적이에요.

행렬이나 벡터로부터 생성: sparse 함수는 행 인덱스, 열 인덱스, 데이터를 나타내는 세 벡터로 희소 행렬을 만들어요. spconvert는 세 열짜리 행렬 형식을 써서 다른 프로그램에서 가져온 데이터를 쉽게 넣을 수 있게 해 줍니다.

만든 뒤 채우기: sparse나 spalloc로 빈 행렬을 만든 다음, 사용자가 값을 하나씩 채워 넣는 방식이에요.

사용자 바이너리 프로그램에서: oct-file 안에서 직접 희소 행렬을 만들 수도 있어요.

특정 희소 행렬을 돌려주는 기본 함수들은 여러 가지가 있어요. 예를 들어 희소 단위행렬은 자주 필요해서 전용 함수가 있답니다. speye (n) 또는 speye (r, c)로 n×n 또는 r×c 크기의 희소 단위행렬을 만들 수 있어요.

또 자주 쓰이는 희소 행렬로 무작위 원소를 가지는 행렬이 있어요. sprand와 sprandn은 각각 균등 분포와 정규 분포의 무작위 원소를 만듭니다. 호출 방식은 완전히 같아서 sprand (r, c, d)는 밀도 d만큼 채워진 r×c 희소 행렬을 만들어요.

희소 행렬을 직접 만드는 데 관심 있는 다른 함수로 diag와 이것을 일반화한 spdiags가 있어요. 대각선의 정의를 받아 그에 해당하는 희소 행렬을 만들죠. 예를 들어

s = diag (sparse (randn (1,n)), -1);

은 대각선 하나만 정의된 희소 (n+1)×(n+1) 행렬을 만들어요.

spdiags

B = spdiags (A)
[B, d] = spdiags (A)
B = spdiags (A, d)
A = spdiags (v, d, A)
A = spdiags (v, d, m, n)

diag 함수를 일반화한 함수예요. 입력 인자를 하나만 주면 A의 0이 아닌 대각선들 d를 추출해요. 인자를 두 개 주면 추출할 대각선이 벡터 d로 지정됩니다.

나머지 두 형태는 대각선을 교체해 입력 행렬을 수정해요. v의 열을 이용해 벡터 d가 나타내는 대각선을 교체하죠. 희소 행렬 A가 정의돼 있으면 그 행렬의 대각선이 교체되고, 아니면 m×n 행렬이 새로 만들어집니다.

d 값이 음수면 주대각선 아래의 대각선, 양수면 주대각선 위의 대각선을 나타내요.

예를 들어:

spdiags (reshape (1:12, 4, 3), [-1 0 1], 5, 4)
   ⇒  5 10  0  0
      1  6 11  0
      0  2  7 12
      0  0  3  8
      0  0  0  4

See also: diag.

speye

s = speye ()
s = speye (n)
s = speye (m, n)
s = speye ([m, n])

크기 m×n의 희소 단위행렬을 돌려줍니다. 인자 없이 호출하면 희소 스칼라값 1을 돌려주고, 스칼라 n 하나만 주면 N×N 정사각 단위행렬을 돌려줘요. 두 스칼라 (m, n)을 주거나 2-요소 벡터 [m, n]을 주면 m개 행과 n개 열을 가진 희소 M×N 단위행렬을 돌려줍니다.

Programming Note: 구현이 sparse (eye (...))보다 훨씬 효율적이에요. 전체 행렬을 만들지 않기 때문이죠.

See also: sparse, spdiags, eye.

spones

r = spones (S)

S의 0이 아닌 원소를 1로 교체해요. S와 같은 구조를 가진 희소 행렬을 만들죠.

See also: sparse, sprand, sprandn, sprandsym, spfun, spy.

sprand

s = sprand (m, n, d)
s = sprand (m, n, d, rc)
s = sprand (s)

균등 분포의 무작위 값을 가진 희소 행렬을 생성해요. 행렬 크기는 m×n, 값의 밀도는 d예요. d는 0과 1 사이여야 하고 값은 구간 (0, 1)에 균등 분포합니다.

행렬 인자 하나로 호출하면 행렬 s가 0이 아닌 자리에 무작위 값을 채운 희소 행렬을 만들어요. 스칼라 네 번째 인자 rc로 호출하면 역조건수(reciprocal condition number) rc를 가진 무작위 희소 행렬을 생성합니다. rc가 벡터라면 생성될 행렬의 처음 몇 개 특이값을 지정해요 (length (rc) <= min (m, n)).

See also: sprandn, sprandsym, rand.

sprandn

s = sprandn (m, n, d)
s = sprandn (m, n, d, rc)
s = sprandn (s)

정규 분포의 무작위 값을 가진 희소 행렬을 생성해요. 크기는 m×n, 밀도는 d. d는 0과 1 사이여야 해요. 값은 평균 0, 분산 1의 정규 분포를 따릅니다.

행렬 인자 하나로 호출하면 그 행렬이 0이 아닌 자리에 무작위 값을 채운 희소 행렬을 만들어요. 스칼라 네 번째 인자 rc로 호출하면 역조건수 rc를 가진 희소 행렬을 생성하고, rc가 벡터면 처음 몇 개 특이값을 지정합니다.

See also: sprand, sprandsym, randn.

sprandsym

S = sprandsym (n, d)
S = sprandsym (s)

대칭 무작위 희소 행렬을 생성해요. 크기는 n×n, 밀도는 d (0과 1 사이). 값은 평균 0, 분산 1의 정규 분포를 따릅니다.

행렬 인자 하나로 호출하면 행렬 s의 하삼각 부분이 0이 아닌 자리에 무작위 값을 채운 희소 행렬을 만들어요.

See also: sprand, sprandn, spones, sparse.

사용자가 희소 행렬을 만들 때 권장되는 방법은 데이터의 행 인덱스와 열 인덱스를 담은 벡터 두 개, 그리고 저장할 데이터를 담은 같은 크기의 벡터 하나를 만드는 거예요. 예를 들어

  ri = ci = d = [];
  for j = 1:c
    ri = [ri; randperm(r,n)'];
    ci = [ci; j*ones(n,1)];
    d = [d; rand(n,1)];
  endfor
  s = sparse (ri, ci, d, r, c);

은 열마다 n (<r)개의 무작위 원소가 분포된 r×c 희소 행렬을 만들어요. 벡터 원소는 특별한 순서로 정렬할 필요가 없어요. Octave가 저장하기 전에 정렬을 하거든요. 다만 미리 정렬해 두면 희소 행렬을 더 빨리 만들 수 있어요.

spconvert 함수는 3열 또는 4열짜리 실수 행렬을 받아요. 처음 두 열은 각각 행과 열 인덱스, 세 번째와 네 번째 열은 희소 행렬의 실수부와 허수부를 나타내죠. 행렬에는 0 원소를 넣을 수 있고 원소 순서는 아무렇게나 돼 있어도 돼요. 0 원소를 추가하는 건 희소 행렬의 크기를 정의하는 편리한 방법이에요. 예를 들어:

s = spconvert ([1 2 3 4; 1 3 4 4; 1 2 3 0]')
⇒  Compressed Column Sparse (rows=4, cols=4, nnz=3)
      (1 , 1) -> 1
      (2 , 3) -> 2
      (3 , 4) -> 3

행렬을 만들고 채우는 예시를 보면

k = 5;
nz = r * k;
s = spalloc (r, c, nz)
for j = 1:c
  idx = randperm (r);
  s (:, j) = [zeros(r - k, 1); ...
        rand(k, 1)] (idx);
endfor

여기서 주의할 점은 Octave의 할당 함수가 루프를 돌 때마다 희소 행렬이 쓰는 메모리를 재할당한다는 거예요. 그래서 spalloc 함수는 nz 인자를 무시하고 메모리를 미리 할당하지 않습니다. 따라서 위와 같은 구조를 쓰는 코드는 가능한 한 벡터화해서 할당 횟수와 메모리 할당 횟수를 줄이는 게 아주 중요해요.

full

FM = full (SM)

희소, 대각, 치환 행렬이나 range에서 전체 저장 행렬을 돌려줍니다.

See also: sparse, issparse.

spalloc

s = spalloc (m, n, nz)

최대 nz개의 0이 아닌 원소를 위한 공간이 미리 할당된 m×n 희소 행렬을 만들어요. 인덱스 할당을 반복해 행렬을 점진적으로 만들 때 유용합니다. spalloc 이후의 인덱스 할당은 다음 단순한 형태 중 하나라면 미리 할당된 메모리를 재사용해요.

  • s(I:J) = x
  • s(:,I:J) = x
  • s(K:L,I:J) = x

그리고 다음 조건이 충족돼야 해요:

  • 할당이 nnz (S)를 줄이지 않아야 한다.
  • 할당 후 nnz (S)가 nz를 넘지 않아야 한다.
  • 인덱스가 범위를 벗어나지 않아야 한다.

데이터의 일부 이동은 여전히 일어날 수 있지만, 대체로 이런 조건에서는 할당이 메모리와 시간 면에서 더 효율적이에요. 특히 연결된 열 블록으로 미리 할당된 희소 행렬을 효율적으로 만들 수 있답니다.

특정 행렬에 미리 할당된 메모리 양은 nzmax 함수로 조회할 수 있어요.

Programming Note: Octave는 nz가 0이어도 항상 값 하나만큼의 메모리를 예약합니다.

See also: nzmax, sparse.

sparse

S = sparse (A)
S = sparse (m, n)
S = sparse (i, j, sv)
S = sparse (i, j, sv, m, n)
S = sparse (i, j, sv, m, n, "unique")
S = sparse (i, j, sv, m, n, nzmax)

전체 행렬 A 또는 행·열·값 삼중항으로부터 희소 행렬을 만들어요.

A가 전체 행렬이면 그 과정에서 0 값을 모두 제거한 희소 행렬 표현으로 변환해요. 행렬 A는 logical 또는 double 타입이어야 합니다.

m(행)과 n(열) 두 입력을 지정하면 지정한 차원의 빈 희소 행렬을 만들어요.

정수 인덱스 벡터 i와 j, 그리고 실수 또는 복소수 값의 1×nnz 벡터 sv가 주어지면 전체 차원 m과 n을 가진 희소 행렬 S(i(k),j(k)) = sv(k)를 구성해요. i, j, sv 중 어느 것이 스칼라이건 공통 크기로 확장됩니다.

m이나 n이 지정되지 않으면 그 값은 벡터 i와 j의 최대 인덱스로부터 정해져요: m = max (i), n = max (j).

Note: 같은 i, j 인덱스에 여러 값이 지정되면 S의 해당 값은 그 자리에 반복된 값들의 합이 돼요. 최솟값을 취하는 것처럼 다른 동작을 원하면 accumarray를 참고하세요.

"unique" 옵션이 주어지고 같은 i, j 인덱스에 값이 두 개 이상이면 마지막에 지정된 값만 사용해요. 완전성을 위해 "sum" 옵션도 줄 수 있는데, 기본 동작이 반복 위치의 값을 합하는 것이므로 무시돼요.

sparse (m, n)은 빈 m×n 희소 행렬을 만들고 sparse ([], [], [], m, n)과 같아요.

선택적인 마지막 인자는 희소 배열에 nzmax개 값의 공간을 예약해요. 최종 0이 아닌 값 개수가 초기 구성에 쓰인 sv의 값 개수보다 많을 것으로 예상될 때 유용합니다. 자세한 내용은 spalloc을 참고하세요.

Example 1 (전체 행렬을 희소 행렬로 바꿔 메모리를 아끼기):

x = full (diag (1:1000));
sizeof (x)
⇒   8000000
s = sparse (x);
sizeof (xs)
⇒   24008

Example 2 (반복 인덱스에서 합하기):

i = [1 1 2]; j = [1 1 2]; sv = [3 4 5];
sparse (i, j, sv, 3, 4)
⇒ 
   Compressed Column Sparse (rows = 3, cols = 4, nnz = 2 [17%])

     (1, 1) ->  7
     (2, 2) ->  5

Example 3 ("unique" 옵션):

i = [1 1 2]; j = [1 1 2]; sv = [3 4 5];
sparse (i, j, sv, 3, 4, "unique")
⇒ 
   Compressed Column Sparse (rows = 3, cols = 4, nnz = 2 [17%])

     (1, 1) ->  4
     (2, 2) ->  5

See also: full, accumarray, spalloc, spdiags, speye, spones, sprand, sprandn, sprandsym, spconvert, spfun.

spconvert

x = spconvert (m)

다른 프로그램이 쉽게 만드는 단순한 희소 행렬 형식을 Octave의 내부 희소 형식으로 변환해요. 입력 m은 희소 행렬 원소의 행, 열, 실수부, 허수부를 담은 3열 또는 4열짜리 실수 행렬이에요. 실수부와 허수부가 모두 0인 원소는 특정 행렬 크기를 강제하는 데 쓸 수 있어요.

See also: sparse.

위에서 본 메모리 재할당 문제는 oct-file에서는 피할 수 있어요. 다만 oct-file에서 희소 행렬을 만드는 건 여기서 다룰 수 없을 만큼 복잡해요. 전체 설명은 External Code Interface 장을 참고하세요.

더 알아보기

  • octave-sparse-matrices — 희소 행렬 개념과 챕터 구성
  • octave-storage-of-sparse-matrices — 압축 열 저장 방식의 원리
  • octave-sparse-linear-algebra — 희소 행렬의 선형대수 솔버