Hypergraph Partitioning-Based Fill-Reducing Ordering for Symmetric Matrices
Hypergraph Partitioning-Based Fill-Reducing Ordering for Symmetric Matrices
复制标题
基于超图划分的对称矩阵填充减少排序
DOI：
--
复制
发表时间：
2011
影响因子：
3.1
通讯作者：
Enver Kayaaslan
中科院分区：
文献类型：
--
作者：
Ümit V. Çatalyürek;C. Aykanat;Enver Kayaaslan
线性系统$Mx=B$的直接求解器的典型第一步是对称矩阵$M$的重新排序以改进求解过程的执行时间和空间要求。在这项工作中，我们提出了一种新的嵌套解剖的排序方法，利用超图分区。我们的方法是基于制定的图分区顶点分离器（GPVS）的超图分区问题的问题。这种新的配方是免疫缺陷的GPVS在一个多层次的框架，从而使更好的排序。在矩阵方面，我们的方法依赖于输入$M$矩阵的结构因子分解的存在，其形式为$M=AA^T$（或$M= AD ^2A ^T $）。我们证明了矩形矩阵$A$的行网超图表示的划分导致矩阵$M$的标准图表示的GPVS。在没有这样的分解，我们还提出了简单的，但有效的结构分解技术的基础上找到一个边团覆盖的标准图表示矩阵$M$，因此适用于任何任意对称矩阵$M$。我们的实验评估表明，所提出的方法实现了更好的排序相比，最先进的基于图形的排序工具，即使是对称矩阵的结构$M=AA^T$分解不提供作为输入。对于来自线性规划问题的矩阵，我们的方法可以更快，更好地排序。
A typical first step of a direct solver for the linear system $Mx=b$ is reordering of the symmetric matrix $M$ to improve execution time and space requirements of the solution process. In this work, we propose a novel nested-dissection-based ordering approach that utilizes hypergraph partitioning. Our approach is based on the formulation of graph partitioning by vertex separator (GPVS) problem as a hypergraph partitioning problem. This new formulation is immune to deficiency of GPVS in a multilevel framework and hence enables better orderings. In matrix terms, our method relies on the existence of a structural factorization of the input $M$ matrix in the form of $M=AA^T$ (or $M=AD^2A^T$). We show that the partitioning of the row-net hypergraph representation of the rectangular matrix $A$ induces a GPVS of the standard graph representation of matrix $M$. In the absence of such factorization, we also propose simple, yet effective structural factorization techniques that are based on finding an edge clique cover of the standard graph representation of matrix $M$, and hence applicable to any arbitrary symmetric matrix $M$. Our experimental evaluation has shown that the proposed method achieves better ordering in comparison to state-of-the-art graph-based ordering tools even for symmetric matrices where structural $M=AA^T$ factorization is not provided as an input. For matrices coming from linear programming problems, our method enables even faster and better orderings.