Main Content

colamd

열 AMD(Approximate Minimum Degree) 치환

설명

예제

p = colamd(S)는 희소 행렬 S의 열에 대한 AMD(Approximate Minimum Degree) 치환 벡터를 반환합니다.

p = colamd(S,knobs)S의 행 또는 열이 무시되기 전까지 허용할 행과 열의 최대 요소 개수에 대한 임계값을 지정합니다.

[p,stats] = colamd(___)는 추가 출력값 stats에 행렬 S의 정렬 데이터와 유효성 데이터를 제공합니다.

예제

모두 축소

희소 행렬로 구성된 하웰-보잉(Harwell-Boeing) 컬렉션과 MATLAB® demos 디렉터리에 테스트 행렬 west0479가 포함되어 있습니다. 이는 웨스터버그(Westerberg)에 제시된 8단계 화학 증류탑 모델로부터 도출된 479 차수 행렬입니다. SPY 플롯은 이 8단계가 존재함을 보여줍니다. colamd 정렬은 이 구조를 재배열합니다.

load west0479
A = west0479;
p = colamd(A);

figure()
subplot(1,2,1), spy(A,4), title('A')
subplot(1,2,2), spy(A(:,p),4), title('A(:,p)')

Figure contains 2 axes objects. axes object 1 with title A, xlabel nz = 1887 contains a line object which displays its values using only markers. axes object 2 with title A(:,p), xlabel nz = 1887 contains a line object which displays its values using only markers.

원본 행렬의 LU 분해 SPY 플롯과 다시 정렬된 행렬의 LU 분해 SPY 플롯을 비교하면 최소 차수로 인해 시간과 저장 용량에 대한 요구 사항이 원래에 비해 2.8배 넘게 줄어든다는 것을 알 수 있습니다. 0이 아닌 요소의 개수가 각각 15918과 5920입니다.

figure()
subplot(1,2,1), spy(lu(A),4), title('lu(A)')
subplot(1,2,2), spy(lu(A(:,p)),4), title('lu(A(:,p))')

Figure contains 2 axes objects. axes object 1 with title lu(A), xlabel nz = 15918 contains a line object which displays its values using only markers. axes object 2 with title lu(A(:,p)), xlabel nz = 5920 contains a line object which displays its values using only markers.

입력 인수

모두 축소

희소 행렬. MATLAB® 내장 함수가 유효한 희소 행렬을 생성하는 경우에도 MATLAB C 또는 Fortran API를 사용하여 유효하지 않은 희소 행렬을 생성하고 colamd로 전달할 수 있습니다. 이런 이유로 colamdS가 유효한 희소 행렬인지 확인합니다.

  • 동일한 열에 행 인덱스가 2회 이상 나타난 경우에 colamd는 중복된 요소를 무시하고, 처리를 계속하고, stats(4:7)에서 중복된 요소에 대한 정보를 제공합니다.

  • 열에 있는 행 인덱스의 순서가 잘못된 경우에 colamd는 행렬 S 내부 복사본의 각 열을 정렬하고(입력 행렬 S를 수정하지는 않음), 처리를 계속하고, stats(4:7)에서 순서가 잘못된 요소에 대한 정보를 제공합니다.

  • S가 다른 어떤 방식으로도 유효하지 않은 경우 colamd는 더 이상 수행되지 않습니다. 오류 메시지가 출력되며, 출력 인수(p 또는 stats)는 반환되지 않습니다.

데이터형: double | logical
복소수 지원 여부:

행과 열 임계값으로, 벡터로 지정됩니다. knobs는 요소를 1~3개 가질 수 있습니다.

  • 요소가 max(16,knobs(1)*sqrt(size(S,2)))개를 초과하는 행은 무시됩니다.

  • 요소가 max(16,knobs(2)*sqrt(min(size(S))))개를 초과하는 열은 치환 인수 p의 마지막에 정렬됩니다.

  • knobs(1) 또는 knobs(2)가 0보다 작은 경우, 완전히 조밀한 행 또는 열만 각각 제거됩니다.

  • knobs(3)이 0이 아닌 경우, statsknobs가 출력됩니다.

예: p = colamd(S,[10 5])

출력 인수

모두 축소

치환 벡터로, 숫자형 벡터로 반환됩니다. 비대칭 행렬 S의 경우 S(:,p)S보다 더 희소한 LU 인수를 갖는 경우가 많습니다. 또한 S(:,p)'*S(:,p)의 촐레스키 분해(Cholesky Factorization)는 S'*S의 촐레스키 분해(Cholesky Factorization)보다 희소성이 큰 경향이 있습니다.

열 제거 트리 후위(Elimination Tree Post-ordering)가 뒤따라 옵니다.

정렬 정보로, 벡터로 반환됩니다. 다음과 같이 stats 벡터에는 수행된 정렬에 대한 정보와 희소 입력 행렬 S에 대한 정보가 포함됩니다.

stats(1)

colamd가 무시한 조밀한 행 또는 빈 행의 개수

stats(2)

colamd가 무시한 조밀한 열 또는 빈 열의 개수

stats(3)

colamd가 사용한 내부 데이터 구조에 수행된 가비지 컬렉션의 개수(대략적인 크기: 2.2*nnz(S) + 4*m + 7*n개의 정수)

stats(4)

0(행렬이 유효한 경우) 또는 1(행렬이 유효하지 않은 경우)

stats(5)

정렬되지 않았거나 중복된 요소를 포함하는 오른쪽 끝 열 인덱스 또는 (이러한 열 요소가 없는 경우) 0

stats(6)

stats(5)가 제공하는 열 인덱스에서 마지막으로 표시된 중복된 행 인덱스이거나 순서가 잘못된 행 인덱스 또는 (이러한 행 인덱스가 없는 경우) 0

stats(7)

중복되고 순서가 잘못된 행 인덱스의 개수

요소 stats(4:7)은 MATLAB C 또는 Fortran API를 사용하여 생성된 입력 행렬 S에만 연관됩니다. 이 경우 요소는 그러한 행렬의 형식이 유효하지 않은지 진단합니다. 자세한 내용은 S에 대한 설명을 참조하십시오.

참고 문헌

[1] Davis, Timothy A., John R. Gilbert, Stefan I. Larimore, and Esmond G. Ng. “Algorithm 836: COLAMD, a Column Approximate Minimum Degree Ordering Algorithm.” ACM Transactions on Mathematical Software 30, no. 3 (September 2004): 377–380. https://doi.org/10.1145/1024074.1024080.

확장 기능

버전 내역

R2006a 이전에 개발됨

참고 항목

| | | |