희소 행렬 액세스하기
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 = 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
나열을 중지할 수 있습니다.
참고로, 처음에는 기본적으로 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
(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.
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
의 희소 형식을 원한다고 가정해 보겠습니다.
다음과 같이 행 첨자, 열 첨자, 값에 대한 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
희소 행렬 시각화하기
희소 행렬 내에서 0이 아닌 요소의 분포를 확인하는 데 그래프 형식을 사용하는 것이 유용한 경우가 종종 있습니다. MATLAB spy
함수는 희소성 구조의 템플릿 보기를 생성하며, 여기서 그래프의 각 점은 0이 아닌 배열 요소의 위치를 나타냅니다.
예를 들면 다음과 같습니다.
하웰-보잉 컬렉션의 하나이자 제품에 탑재된 희소 행렬 west0479
를 불러옵니다.
load west0479
희소성 구조를 확인합니다.
spy(west0479)