dissect

중첩 분할 치환

구문

p = dissect(A)

p = dissect(A,Name,Value)

설명

p = dissect(A)는 A의 희소성 구조의 중첩 분할을 사용하여 계산된 치환 벡터를 반환합니다.

p = dissect(A,Name,Value)는 하나 이상의 이름-값 쌍의 인수를 사용하여 추가 옵션을 지정합니다. 예를 들어, dissect(A,'NumIterations',15)는 중첩 분할 알고리즘에서 미세 조정 반복 횟수를 10 대신 15를 사용합니다.

예제

희소 행렬 열 재정렬하기

여러 메서드를 사용하여 희소 행렬을 재정렬하고 재정렬된 행렬의 LU 분해 시 발생된 필인(Fill-in)을 비교합니다.

west0479 행렬을 불러옵니다. 이 행렬은 켤레 고유값의 실수와 복소수 쌍을 포함한 실수 값의 479×479 희소 행렬입니다. 희소성 구조를 확인합니다.

load west0479.mat
A = west0479;
spy(A)

중첩 분할 정렬을 포함하여, 다양한 행렬 열의 치환을 계산합니다.

p1 = dissect(A);
p2 = amd(A);
p3 = symrcm(A);

다양한 정렬 메서드를 사용하여 A의 LU 분해로 얻은 희소성 구조를 비교합니다. dissect 함수는 가장 적은 양의 필인(Fill-in)을 발생시키는 재정렬을 생성합니다.

subplot(1,2,1)
spy(A)
title('Original Matrix')
subplot(1,2,2)
spy(lu(A))
title('LU Decomposition')

figure
subplot(1,2,1)
spy(A(p3,p3))
title('Reverse Cuthill-McKee')
subplot(1,2,2)
spy(lu(A(p3,p3)))
title('LU Decomposition')

figure
subplot(1,2,1)
spy(A(p2,p2))
title('Approximate Minimum Degree')
subplot(1,2,2)
spy(lu(A(p2,p2)))
title('LU Decomposition')

figure
subplot(1,2,1)
spy(A(p1,p1))
title('Nested Dissection')
subplot(1,2,2)
spy(lu(A(p1,p1)))
title('LU Decomposition')

조밀한 열 필터링하기

화살촉 행렬은 조밀한 열이 몇 개 안 되는 희소 행렬입니다. 재정렬된 행렬의 끝까지에서 조밀한 열을 필터링하려면 'MaxDegreeThreshold' 이름-값 쌍을 사용하십시오.

화살촉 희소 행렬을 만들고 희소성 패턴을 봅니다.

A = speye(100) + diag(ones(1,99),1) + diag(ones(1,98),2);
A(1:5,:) = ones(5,100);
A = A + A';
spy(A)

중첩 분할 정렬을 계산하고 0이 아닌 요소가 10개가 넘는 열을 필터링합니다.

p = dissect(A,'MaxDegreeThreshold',10);

재정렬된 행렬의 희소성 패턴을 봅니다. dissect는 조밀한 열을 재정렬된 행렬의 끝에 배치합니다.

spy(A(p,p))

입력 인수

A — 입력 행렬

정사각 행렬

입력 행렬로, 정사각 행렬로 지정됩니다. A는 비희소 행렬이거나 희소 행렬일 수 있습니다. A가 비대칭적이면 dissect는 이 행렬을 대칭화합니다.

데이터형: single | double | int8 | int16 | int32 | int64 | uint8 | uint16 | uint32 | uint64 | logical
복소수 지원 여부: 예

이름-값 인수

선택적 인수 쌍을 Name1=Value1,...,NameN=ValueN으로 지정합니다. 여기서 Name은 인수 이름이고 Value는 대응값입니다. 이름-값 인수는 다른 인수 뒤에 와야 하지만, 인수 쌍의 순서는 상관없습니다.

R2021a 이전 릴리스에서는 쉼표를 사용하여 각 이름과 값을 구분하고 Name을 따옴표로 묶으십시오.

예: p = dissect(A,'NumIterations',15,'NumSeparators',2)는 중첩 분할 알고리즘에 15회의 미세 조정 반복 횟수와 2개의 구분 기호를 사용합니다.

VertexWeights — 정점 가중치

벡터

정점 가중치로, 'VertexWeights'와 함께 벡터가 쉼표로 구분되어 지정됩니다. 각 정점에 가중치가 지정되도록 가중치로 구성된 벡터의 길이는 size(A,1)과 같아야 합니다. 그래프 정점(행렬 열)에 가중치가 지정되는 방식을 지정하려면 이 옵션을 사용하십시오. 이 옵션은 알고리즘이 파티션 간의 밸런스를 계산하는 방식에 영향을 줍니다.

기본적으로, 중첩 분할 알고리즘은 모든 정점에 균등하게 가중치를 지정합니다.

데이터형: single | double | int8 | int16 | int32 | int64 | uint8 | uint16 | uint32 | uint64

NumSeparators — 분리 개수

1 (디폴트 값) | 양의 정수

분리 개수로, 'NumSeparators'와 함께 양의 정수가 쉼표로 구분되어 지정됩니다. 각 분할 단계에서 그래프가 분리되어 만들어지는 파티션 개수를 지정하려면 이 옵션을 사용하십시오. 중첩 분할 알고리즘에서 분리 개수를 증가시키면 더 많은 실행 시간이 들지만 더 나은 치환 결과를 얻을 수 있습니다.

데이터형: single | double | int8 | int16 | int32 | int64 | uint8 | uint16 | uint32 | uint64

NumIterations — 미세 조정 반복 횟수

10 (디폴트 값) | 양의 정수

미세 조정 반복 횟수로, 'NumIterations'와 함께 양의 정수가 쉼표로 구분되어 지정됩니다. 미세 조정 반복 횟수가 많을수록 실행 시간은 증가하지만 치환 결과는 향상될 수 있습니다.

데이터형: single | double | int8 | int16 | int32 | int64 | uint8 | uint16 | uint32 | uint64

MaxImbalance — 파티션 불균형 임계값

1.2 (디폴트 값) | 스칼라

파티션 불균형 임계값으로, 'MaxImbalance'와 함께 1.001보다 크거나 같고 1.999보다 작거나 같은 0.001의 정수 배수인 스칼라 값이 쉼표로 구분되어 지정됩니다. 임계값이 높으면 알고리즘에서 부적합한 치환도 받아들일 수 있게 되어 실행 시간이 감소할 수 있습니다.

데이터형: single | double

MaxDegreeThreshold — 정점 차수의 임계값

0 (디폴트 값) | 음이 아닌 정수

정점 차수(Vertex Degree)의 임계값으로, 'MaxDegreeThreshold'와 함께 음이 아닌 정수가 쉼표로 구분되어 지정됩니다. 중첩 분할 알고리즘은 정렬 중 정점도가 threshold*(avg degree)/10보다 큰 정점은 무시합니다. dissect는 이렇게 무시된 정점을 치환 시 끝에 배치합니다. 이 알고리즘은 임계값보다 정점도가 큰 정점을 효과적으로 첫 번째 최상위 분리에 배치합니다. 때때로 밀접하게 연결된 정점을 필터링하면 정렬 속도와 정확성이 향상될 수 있습니다.

디폴트 값 0은 모든 정점이 정렬됨을 의미합니다.

데이터형: single | double | int8 | int16 | int32 | int64 | uint8 | uint16 | uint32 | uint64

출력 인수

p — 치환 벡터

벡터

치환 벡터로, 벡터로 반환됩니다. 인덱싱 표현식 A(p,p)를 사용하여 A의 열을 재정렬하려면 치환 벡터를 사용하십시오. 예를 들어, 촐레스키 분해(Cholesky Factorization) chol(A(p,p))는 A의 촐레스키 분해보다 희소성이 큰 경향이 있습니다.

알고리즘

[1]에서 설명된 중첩 분할 정렬 알고리즘은 희소 행렬의 필인(Fill-in) 감소 정렬을 생성하는 데 사용되는 다중 수준 그래프 분할 알고리즘입니다. 입력 행렬은 그래프의 인접 행렬로 취급됩니다. 알고리즘은 정점과 모서리를 축소하여 밀도를 줄이고, 작아진 그래프를 재정렬한 다음, 미세 조정 단계를 사용하여 작은 그래프의 밀도를 되돌려 원래 그래프의 재정렬을 도출합니다.

dissect에 대한 이름-값 쌍을 통해 알고리즘의 다양한 단계를 제어할 수 있습니다.

• 밀도 줄이기

  이 단계에서 알고리즘은 인접 정점 쌍을 함께 축소하여 원래 그래프에서 성공적으로 작은 그래프를 만듭니다. 'MaxDegreeThreshold'를 사용하여 작은 그래프를 마지막으로 정렬함으로써 밀접하게 연결된 그래프 정점(행렬에서 조밀 열)을 필터링할 수 있습니다.

• 분할

  그래프의 밀도가 감소된 후, 알고리즘은 작은 그래프를 완전히 재정렬합니다. 각 분할 단계에서 알고리즘은 그래프를 균등한 부분으로 분할하려 합니다. 'NumSeparators'는 그래프를 몇 부분으로 분할할지를 지정하고, 'VertexWeights'는 선택적으로 정점에 가중치를 지정하고, 'MaxImbalance'는 여러 파티션 간의 가중치 차이에 대한 임계값을 지정합니다.

• 미세 조정

  가장 작은 그래프가 재정렬된 후, 알고리즘은 투영을 통해 이전에 결합된 정점을 확장하여 그래프를 다시 원래 크기로 확대합니다. 각 투영 단계가 끝나면 미세 조정 단계가 수행되어 파티션 간에 정점을 이동하여 재정렬의 품질을 향상시킵니다. 'NumIterations'는 이 밀도 복구 단계에 사용되는 미세 조정 단계 수를 제어합니다.

참고 문헌

[1] Karypis, George and Vipin Kumar. "A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs." SIAM Journal on Scientific Computing. Vol. 20, Number 1, 1999, pp. 359–392.

확장 기능

스레드 기반 환경

MATLAB®의 backgroundPool을 사용해 백그라운드에서 코드를 실행하거나 Parallel Computing Toolbox™의 ThreadPool을 사용해 코드 실행 속도를 높일 수 있습니다.

이 함수는 스레드 기반 환경을 완전히 지원합니다. 자세한 내용은 스레드 기반 환경에서 MATLAB 함수 실행하기 항목을 참조하십시오.

버전 내역

R2017b에 개발됨

참고 항목

amd | colamd | symamd | symrcm | colperm

도움말 항목

• 치환과 재정렬(Reordering)