Main Content

이 번역 페이지는 최신 내용을 담고 있지 않습니다. 최신 내용을 영문으로 보려면 여기를 클릭하십시오.

colamd

열 AMD(Approximate Minimum Degree) 치환

구문

p = colamd(S)

설명

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

knobs는 요소를 2개 가진 벡터입니다. S가 m×n인 경우 항목이 (knobs(1))*n개를 초과하는 행은 무시됩니다. 항목이 (knobs(2))*m개를 초과하는 열은 정렬 전에 제거되고, 출력 치환 p의 마지막에 정렬됩니다. knobs 파라미터가 없는 경우 knobs(1) = knobs(2) = spparms('wh_frac')입니다.

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)

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

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

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

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

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

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

예제

모두 축소

희소 행렬의 하웰-보잉(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)')

원본 행렬의 LU 분해 SPY 플롯과 다시 정렬된 행렬의 LU 분해 SPY 플롯을 비교하면 최소 차수가 시간 및 저장 용량에 대한 요구 사항을 원래의 1/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))')

참고 문헌

[1] The authors of the code for colamd are Stefan I. Larimore and Timothy A. Davis. The algorithm was developed in collaboration with John Gilbert, Xerox PARC, and Esmond Ng, Oak Ridge National Laboratory. Sparse Matrix Algorithms Research: http://faculty.cse.tamu.edu/davis/research.html

참고 항목

| | | |

R2006a 이전에 개발됨