이 번역 페이지는 최신 내용을 담고 있지 않습니다. 최신 내용을 영문으로 보려면 여기를 클릭하십시오.
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')
를 생략합니다.
예제
참고 문헌
[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.