0이 아닌 요소

희소 행렬의 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 =

  (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
  (89,3)     -8.3694e-01
  (28,4)      1.3000e+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
    .
    .
    .

참고로, 처음에는 기본적으로 nnz가 nzmax와 동일한 값을 가집니다. 즉, 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

현재 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);

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.

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

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의 희소 형식을 원한다고 가정해 보겠습니다.

다음과 같이 행 첨자, 열 첨자, 값에 대한 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 =

   (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

희소 행렬 시각화하기

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

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

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

load west0479

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

spy(west0479)