dissect
嵌套剖分置换
说明
示例
输入参数
输出参量
算法
[1] 中介绍的嵌套剖分排序算法是一种多级图形分区算法,用于对稀疏矩阵进行减少填充量的排序。输入矩阵被视为图形的邻接矩阵。该算法通过折叠顶点和边来粗化图形,重排较小的图形,然后通过细化步骤对较小图形去粗,得到重排的原始图形。
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 中推出