Main Content

etree

제거 트리(Elimination Tree)

설명

예제

p = etree(A)는 정사각 대칭 행렬(A에서 상삼각 행렬이 삼각 행렬이 됨)에 대한 제거 트리를 반환합니다.

예제

p = etree(A,type)은 제거 트리 유형을 지정합니다. 예를 들어, type"lo"인 경우 etreeA의 하부 삼각을 사용하여 정사각 대칭 행렬을 생성합니다.

[p,q] = etree(___)는 제거 트리의 후위 치환 q를 반환합니다. 위에 열거된 구문에 나와 있는 입력 인수를 조합하여 두 개의 출력값을 지정할 수 있습니다.

예제

모두 축소

0과 1로 구성된 7×7 삼중대각 행렬을 만듭니다.

A = diag(ones(1,7)) + diag(ones(1,6),1) + diag(ones(1,6),-1)
A = 7×7

     1     1     0     0     0     0     0
     1     1     1     0     0     0     0
     0     1     1     1     0     0     0
     0     0     1     1     1     0     0
     0     0     0     1     1     1     0
     0     0     0     0     1     1     1
     0     0     0     0     0     1     1

A의 제거 트리를 계산합니다. 제거 트리의 각 요소 p(i)는 노드 i의 부모를 나타냅니다. 노드 7이 트리의 루트이므로 p(7)은 0입니다.

p = etree(A)
p = 1×7

     2     3     4     5     6     7     0

0과 1로 구성된 6×6 블록 대각 행렬을 만듭니다.

a = ones(3);
b = zeros(3);
B = [a b; b a]
B = 6×6

     1     1     1     0     0     0
     1     1     1     0     0     0
     1     1     1     0     0     0
     0     0     0     1     1     1
     0     0     0     1     1     1
     0     0     0     1     1     1

B의 제거 트리를 계산합니다. etree는 인덱스 3과 6의 루트 노드로 표시된 두 개의 제거 트리가 있는 포레스트를 반환합니다.

r = etree(B)
r = 1×6

     2     3     0     5     6     0

bucky 희소 행렬의 서로 다른 제거 트리 두 개를 계산합니다. "lo" 제거 트리는 A의 하부 삼각을 사용하는 반면 "col" 제거 트리는 행렬 A'*A를 사용합니다.

A = bucky;
p1 = etree(A,"lo");
p2 = etree(A,"col");

treeplot을 사용하여 제거 트리를 플로팅합니다.

treeplot(p1)
title("Lower Triangle Elimination Tree")

Figure contains an axes object. The axes object with title Lower Triangle Elimination Tree, xlabel height = 58 contains 2 objects of type line. One or more of the lines displays its values using only markers

treeplot(p2)
title("Column Elimination Tree")

Figure contains an axes object. The axes object with title Column Elimination Tree, xlabel height = 58 contains 2 objects of type line. One or more of the lines displays its values using only markers

bucky 희소 행렬의 두 개의 치환에 대한 제거 트리를 계산합니다. symrcm을 사용하여 대칭적 컷힐-맥키(Cuthill-McKee) 역치환 정렬을 생성하고, symamd를 사용하여 대칭적 AMD(Approximate Minimum Degree) 정렬을 생성합니다.

A = bucky;
r = symrcm(A);
p1 = etree(A(r,r));
m = symamd(A);
p2 = etree(A(m,m));

treeplot을 사용하여 제거 트리를 플로팅합니다. 컷힐-맥키 역치환 제거 트리는 여러 노드로 구성된 하나의 선인 반면, 최소 차수 제거 트리는 여러 개의 서로소 가지를 가집니다.

treeplot(p1)
title("Reverse Cuthill-McKee Elimination Tree")

Figure contains an axes object. The axes object with title Reverse Cuthill-McKee Elimination Tree, xlabel height = 59 contains 2 objects of type line. One or more of the lines displays its values using only markers

treeplot(p2)
title("Minimum Degree Elimination Tree")

Figure contains an axes object. The axes object with title Minimum Degree Elimination Tree, xlabel height = 18 contains 2 objects of type line. One or more of the lines displays its values using only markers

spy를 사용하여 희소성 패턴을 플로팅합니다. 행렬의 제거 트리는 희소성 패턴에 따라 달라지므로 희소성 패턴이 다르면 제거 트리도 달라집니다.

spy(A(r,r))
title("Reverse Cuthill-McKee Sparsity Pattern")

Figure contains an axes object. The axes object with title Reverse Cuthill-McKee Sparsity Pattern, xlabel nz = 180 contains a line object which displays its values using only markers.

spy(A(m,m))
title("Minimum Degree Sparsity Pattern")

Figure contains an axes object. The axes object with title Minimum Degree Sparsity Pattern, xlabel nz = 180 contains a line object which displays its values using only markers.

입력 인수

모두 축소

입력 행렬. A는 비희소 행렬이거나 희소 행렬일 수 있습니다. 제거 트리 유형이 "sym" 또는 "lo"인 경우 A는 정사각 행렬이어야 합니다. etreeA의 희소성 구조를 사용하여 제거 트리를 계산합니다.

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

제거 트리 유형으로, "sym", "lo", "col" 또는 "row"로 지정됩니다. 이 인수를 사용하여 etree가 제거 트리를 계산하는 데 사용하는 행렬을 지정합니다.

  • type"sym"인 경우 etreeA의 상부 삼각을 사용하여 정사각 대칭 행렬을 생성하고 이 행렬의 제거 트리를 반환합니다.

  • type"lo"인 경우 etreeA의 하부 삼각을 사용하여 정사각 대칭 행렬을 생성하고 이 행렬의 제거 트리를 반환합니다.

  • type"col"인 경우 etree는 행렬 A'*A를 생성하고 이 행렬의 제거 트리, 즉 A의 열 제거 트리를 반환합니다.

  • type"row"인 경우 etree는 행렬 A*A'을 생성하고 이 행렬의 제거 트리, 즉 A의 행 제거 트리를 반환합니다.

출력 인수

모두 축소

제거 트리로, 숫자형 벡터로 반환됩니다. p(i)는 트리에서 노드 i의 부모를 나타내며, i가 루트인 경우에는 0입니다.

제거 트리 p의 후위 치환으로, 숫자형 벡터로 반환됩니다.

촐레스키 분해의 열을 직접 계산하는 경우 제거 트리의 후위 치환을 사용할 수 있습니다. 제거 트리 p의 노드 i와 부모 노드 j에 대해 촐레스키 분해에서 열 i는 열 j보다 먼저 완전히 계산되어야 합니다. p의 후위 치환은 이 요구 사항에 부합하게, 이러한 열들을 계산하는 순서를 지정합니다. 분해를 직접 계산하려면 chol을 사용하십시오.

세부 정보

모두 축소

제거 트리

제거 트리는 촐레스키 분해의 행 및 열 종속성을 캡처하고 동시에 수행할 수 있는 작업을 설명하는 데이터 구조체입니다. 제거 트리의 서로소 가지는 병렬로 계산될 수 있으므로 가지를 갖는 제거 트리가 있는 행렬의 분해는 더 빠르게 계산될 수 있습니다. 희소 행렬을 재정렬하여 필인(fill-in) 양을 변경하고 다른 제거 트리를 계산할 수 있습니다.

참고 문헌

[1] Chen, Yanqing, Timothy A. Davis, William W. Hager, and Sivasankaran Rajamanickam. “Algorithm 887: CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate.” ACM Transactions on Mathematical Software 35, no. 3 (October 2008): 1–14. https://doi.org/10.1145/1391989.1391995.

[2] Pothen, Alex, and Sivan Toledo. "Elimination Structures in Scientific Computing." In Handbook of Data Structures and Applications, edited by Dinesh P. Mehta and Sartaj Sahni, 945–965. New York: Chapman and Hall/CRC, 2017. https://doi.org/10.1201/9781315119335

확장 기능

버전 내역

R2006a 이전에 개발됨

참고 항목

| | |