dissect
중첩 분할 치환
설명
예제
입력 인수
출력 인수
알고리즘
[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.
확장 기능
버전 내역
R2017b에 개발됨