Main Content

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

amd

AMD(Approximate Minimum Degree) 치환

페이지 내 모두 축소

구문

P = amd(A)
P = amd(A,opts)

설명

P = amd(A)는 희소 행렬 C = A + A'의 AMD(Approximate Minimum Degree) 치환 벡터를 반환합니다. C(P,P) 또는 A(P,P)의 촐레스키 분해(Cholesky Factorization)는 C 또는 A의 촐레스키 분해(Cholesky Factorization)보다 희소성이 큰 경향이 있습니다. amd 함수는 symamd보다 더 빠르고 symamd보다 더 나은 정렬(Ordering)을 반환하는 경우가 많습니다. 행렬 A는 정사각 행렬이어야 합니다. A가 비희소 행렬(Full Matrix)인 경우 amd(A)는 amd(sparse(A))와 같습니다.

P = amd(A,opts)에는 재정렬(Reordering)을 위한 추가 옵션을 사용할 수 있습니다. opts 입력값은 아래에 나와 있는 2개의 필드가 있는 구조체입니다. 필요한 필드만 설정하면 됩니다.

  • dense — 조밀한 것으로 간주되는 수치를 나타내는 음이 아닌 스칼라 값입니다. A가 n×n인 경우 A + A'에서 항목이 max(16,(dense*sqrt(n)))개를 넘는 행과 열은 "조밀"한 것으로 간주되며 정렬(Ordering)할 때 무시됩니다. MATLAB®에서는 이러한 행과 열을 출력 치환 마지막에 넣습니다. 이 옵션을 사용하지 않을 경우 필드의 디폴트 값은 10.0입니다.

  • aggressive — 적극적인 흡수를 제어하는 스칼라 값입니다. 이 필드를 0이 아닌 값으로 설정하면 적극적인 흡수가 수행됩니다. 이는 이 옵션을 사용하지 않을 경우 디폴트 설정입니다.

MATLAB에서는 어셈블리 트리 후위(Assembly Tree Post-ordering)를 수행합니다. 어셈블리 트리 후위(Assembly Tree Post-ordering)는 일반적으로 제거 트리 후위(Elimination Tree Post-ordering)와 동일합니다. 하지만 근사 차수(Approximate Degree) 업데이트가 사용되고 "조밀한" 행과 열이 후위(Post-ordering)에 포함되지 않기 때문에 항상 동일한 것은 아닙니다. 후속 chol 연산에는 어셈블리 트리 후위(Assembly Tree Post-ordering)도 적합하지만, 정밀한 제거 트리 후위(Precise Elimination Tree Post-ordering)가 요구되는 경우에는 다음 코드를 사용합니다.

P = amd(S);
C = spones(S)+spones(S'); 
[ignore, Q] = etree(C(P,P));
P = P(Q);

S가 이미 대칭인 경우 두 번째 라인 C = spones(S)+spones(S')를 생략합니다.

예제

모두 축소

라이브 스크립트 열기

amd를 사용하여 행렬을 정렬하기 전과 후에 행렬의 촐레스키 인수를 구하여 희소성에 미치는 영향을 검토합니다.

바벨형 그래프 희소 행렬을 불러오고 희소 단위 행렬을 추가하여 양의 정부호 행렬이 되도록 합니다. 2개의 촐레스키 인수를 계산합니다. 하나는 원래 행렬의 촐레스키 인수이고 다른 하나는 원래 행렬을 amd로 전위한 것의 촐레스키 인수입니다.

load barbellgraph.mat
A = A+speye(size(A)); 
p = amd(A);
L = chol(A,'lower');
Lp = chol(A(p,p),'lower');

4개 행렬 모두의 희소성 패턴을 플로팅합니다. 전위된 행렬에서 구한 촐레스키 인수는 자연 정렬(Natural Ordering) 상태인 행렬의 인수에 비해 훨씬 더 희소성을 띕니다.

figure
subplot(2,2,1)
spy(A)
title('Original Matrix A')
subplot(2,2,2) 
spy(A(p,p))
title('AMD ordered A')
subplot(2,2,3) 
spy(L)
title('Cholesky factor of A')
subplot(2,2,4) 
spy(Lp)
title('Cholesky factor of AMD ordered A')

Figure contains 4 axes objects. Axes object 1 with title Original Matrix A contains an object of type line. Axes object 2 with title AMD ordered A contains an object of type line. Axes object 3 with title Cholesky factor of A contains an object of type line. Axes object 4 with title Cholesky factor of AMD ordered A contains an object of type line.

참고 문헌

[1] Amestoy, Patrick R., Timothy A. Davis, and Iain S. Duff. “Algorithm 837: AMD, an Approximate Minimum Degree Ordering Algorithm.” ACM Transactions on Mathematical Software 30, no. 3 (September 2004): 381–388. https://doi.org/10.1145/1024074.1024081.

확장 기능

참고 항목

| | | |