Main Content

희소 행렬 액세스하기

0이 아닌 요소

희소 행렬의 0이 아닌 요소에 대한 개괄적 정보를 제공하는 여러 가지 명령이 있습니다.

  • nnz는 희소 행렬에 포함된 0이 아닌 요소의 개수를 반환합니다.

  • nonzeros는 희소 행렬에서 0이 아닌 요소를 모두 포함하는 열 벡터를 반환합니다.

  • nzmax는 희소 행렬에서 0이 아닌 항목에 할당된 저장소 공간의 크기를 반환합니다.

이 중 일부를 사용해 보려면 하웰-보잉(Harwell-Boeing) 컬렉션의 하나이자 제품에 탑재된 희소 행렬 west0479를 불러오십시오.

load west0479
whos
  Name            Size             Bytes  Class     Attributes

  west0479      479x479            34032  double    sparse   

이 행렬은 8단계 화학 증류탑을 모델링합니다.

다음 명령을 시도해 봅니다.

nnz(west0479)
ans =

        1887
format short e
west0479
west0479 =

  479×479 sparse double matrix (1887 nonzeros)

  (25,1)      1.0000e+00
  (31,1)     -3.7648e-02
  (87,1)     -3.4424e-01
  (26,2)      1.0000e+00
  (31,2)     -2.4523e-02
  (88,2)     -3.7371e-01
  (27,3)      1.0000e+00
  (31,3)     -3.6613e-02
     .
     .
     .
nonzeros(west0479)
ans =

   1.0000e+00
  -3.7648e-02
  -3.4424e-01
   1.0000e+00
  -2.4523e-02
  -3.7371e-01
   1.0000e+00
  -3.6613e-02
  -8.3694e-01
   1.3000e+02
    .
    .
    .

참고

Ctrl+C를 사용하여 언제든지 nonzeros 나열을 중지할 수 있습니다.

참고로, 처음에는 기본적으로 nnznzmax와 동일한 값을 가집니다. 즉, 0이 아닌 요소의 개수가 0이 아닌 요소에 할당된 저장소 위치의 개수와 동일합니다. 그러나, 추가 배열 요소를 0으로 처리해도 MATLAB®은 메모리를 동적으로 해제하지 않습니다. 일부 행렬 요소의 값을 0으로 변경하면 nzmax의 값이 아니라 nnz의 값이 변경됩니다.

그러나, 0이 아닌 요소를 원하는 만큼 행렬에 추가할 수 있으며 nzmax의 원래 값에 제약을 받지 않습니다.

인덱스와 값

비희소 행렬(Full Matrix)이나 희소 행렬에 상관없이 모든 행렬에 대해 find 함수는 0이 아닌 요소의 인덱스와 값을 반환합니다. 구문은 다음과 같습니다.

[i,j,s] = find(S);

find는 벡터 i에 0이 아닌 값의 행 인덱스, 벡터 j에 열 인덱스, 벡터 s에 0이 아닌 값 자체를 반환합니다. 아래 예제에서는 find를 사용하여 희소 행렬에서 0이 아닌 요소의 인덱스와 값을 찾습니다. sparse 함수는 find 출력값과 함께, 행렬의 크기를 사용하여 행렬을 다시 만듭니다.

S1 = west0479;
[i,j,s] = find(S1);
[m,n] = size(S1);
S2 = sparse(i,j,s,m,n);

희소 행렬 연산에서 인덱싱하기

희소 행렬은 압축된 희소 열 형식으로 저장되기 때문에, 희소 행렬의 요소를 참조하는데 드는 노력은 비희소 행렬의 요소를 참조하는데 드는 노력과 다릅니다. 이러한 비용은 희소 행렬에서 몇 개의 요소만 변경해야 할 경우 무시할 수 있는 정도이므로, 이런 경우 다음과 같이 일반 배열 인덱싱을 사용하여 값을 재할당할 수 있습니다.

B = speye(4);
[i,j,s] = find(B);
[i,j,s]
ans =

     1     1     1
     2     2     1
     3     3     1
     4     4     1
B(3,1) = 42;
[i,j,s] = find(B);
[i,j,s]
ans =

     1     1     1
     3     1    42
     2     2     1
     3     3     1
     4     4     1
(3,1)의 값이 42인 새 행렬을 저장하기 위해 MATLAB은 추가 행을 0이 아닌 요소 값 벡터와 첨자 벡터에 삽입한 후 (3,1) 다음에 있는 모든 행렬 값을 밀어 이동시킵니다.

현재 MATLAB상에서 행렬에 허용되는 최대 요소 개수인 2^48-1을 초과하는 경우, 선형 인덱싱을 사용하여 큰 희소 행렬의 요소를 액세스하거나 할당하려고 하면 작업이 실패합니다.

S = spalloc(2^30,2^30,2);
S(end) = 1
Maximum variable size allowed by the program is exceeded.

선형 인덱스가 intmax보다 큰 요소에 액세스하려면 다음과 같이 배열 인덱싱을 사용하십시오.

S(2^30,2^30) = 1
S =

         (1073741824,1073741824)              1

단일 요소를 변경하기 위해 희소 행렬의 요소를 참조하는데 드는 시간은 무시할 수 있는 양이지만, 루프의 경우에는 이러한 시간 문제가 심각하며 큰 행렬의 경우 속도가 상당히 느려질 수 있습니다. 이런 이유로, 많은 희소 행렬 요소를 변경해야 하는 경우 루프를 사용하는 대신 연산을 벡터화하는 것이 가장 좋습니다. 예를 들어, 다음과 같은 희소 단위 행렬이 있다고 가정해 보겠습니다.

n = 10000;
A = 4*speye(n);
루프 내에서 A의 요소를 변경하는 작업은 이와 유사한 벡터화 연산보다 더 시간이 소요됩니다.
tic
A(1:n-1,n) = -1; 
A(n,1:n-1) = -1; 
toc
Elapsed time is 0.003344 seconds.
tic
for k = 1:n-1
  C(k,n) = -1; 
  C(n,k) = -1; 
end
toc
Elapsed time is 0.448069 seconds.
MATLAB이 압축된 희소 열 형식으로 희소 행렬을 저장하므로 루프를 통과할 때마다 A에 포함된 여러 항목을 이동시켜야 합니다.

마찬가지로, 희소 행렬에 사용할 메모리를 사전할당한 후 요소별로 채우면 희소 배열의 요소를 참조할 때 상당한 양의 오버헤드가 발생하게 됩니다.

S1 = spalloc(1000,1000,100000);
tic;
for n = 1:100000
    i = ceil(1000*rand(1,1));
    j = ceil(1000*rand(1,1));
    S1(i,j) = rand(1,1);
end
toc
Elapsed time is 2.577527 seconds.

인덱스와 값으로 구성된 벡터를 생성하면 희소 배열의 요소를 참조할 필요가 없으며, 따라서 속도가 상당히 빨라집니다.

i = ceil(1000*rand(100000,1));
j = ceil(1000*rand(100000,1));
v = zeros(size(i));
for n = 1:100000
    v(n) = rand(1,1);
end

tic;
S2 = sparse(i,j,v,1000,1000);
toc
Elapsed time is 0.017676 seconds.

이런 이유로, sparse 함수나 spdiags 함수와 같은 생성 함수를 사용하여 모든 희소 행렬을 한꺼번에 생성하는 것이 가장 좋습니다.

예를 들어, 좌표 행렬 C의 희소 형식을 원한다고 가정해 보겠습니다.

C=(4000104001004010101014114)

다음과 같이 행 첨자, 열 첨자, 값에 대한 3요소 쌍을 사용하여 sparse 함수로 직접 5열 행렬을 생성합니다.

i = [1 5 2 5 3 5 4 5 1 2 3 4 5]';
j = [1 1 2 2 3 3 4 4 5 5 5 5 5]';
s = [4 1 4 1 4 1 4 1 -1 -1 -1 -1 4]';
C = sparse(i,j,s)
C =

  5×5 sparse double matrix (13 nonzeros)

   (1,1)        4
   (5,1)        1
   (2,2)        4
   (5,2)        1
   (3,3)        4
   (5,3)        1
   (4,4)        4
   (5,4)        1
   (1,5)       -1
   (2,5)       -1
   (3,5)       -1
   (4,5)       -1
   (5,5)        4
출력되는 값의 순서는 열 기준으로 저장된 상태를 반영합니다. MATLAB이 희소 행렬을 저장하는 방법에 대한 자세한 내용은 Sparse Matrices In MATLAB: Design and Implementation(SIAM Journal on Matrix Analysis and Applications, 13:1, 333–356 (1992))(저자: John R. Gilbert, Cleve Moler, Robert Schreiber)을 참조하십시오.

희소 행렬 시각화하기

희소 행렬 내에서 0이 아닌 요소의 분포를 확인하는 데 그래프 형식을 사용하는 것이 유용한 경우가 종종 있습니다. MATLAB spy 함수는 희소성 구조의 템플릿 보기를 생성하며, 여기서 그래프의 각 점은 0이 아닌 배열 요소의 위치를 나타냅니다.

예를 들면 다음과 같습니다.

하웰-보잉 컬렉션의 하나이자 제품에 탑재된 희소 행렬 west0479를 불러옵니다.

load west0479

희소성 구조를 확인합니다.

spy(west0479)

Figure contains an axes object. The axes object with xlabel nz = 1887 contains a line object which displays its values using only markers.

참고 항목

관련 항목