Cholesky Factorization of Matrices in Parallel and Ranking of Graphs
Cholesky Factorization of Matrices in Parallel and Ranking of Graphs
复制标题
DOI：
10.1007/978-3-540-24669-5_127
复制
发表时间：
2003-09
影响因子：
3.7
通讯作者：
D. Dereniowski;M. Kubale
中科院分区：
文献类型：
--
作者：
D. Dereniowski;M. Kubale
顶点排序问题与求给定图的最小高度消去树问题密切相关。这意味着该问题在矩阵的并行Cholesky分解中有应用。我们描述了这个模型的图着色和矩阵分解之间的联系。我们还提出了一个多项式时间的算法，找到完全二部图的边排名。我们利用它设计了一个O（m2 + d）的边排序算法，该算法是从一个完全二部图中去掉O（logm）条边得到的，其中n是一个固定的数。然后，我们将我们的结果推广到完全k-部图的任何fixedk>2。通过这种方式，我们给出了一类新的矩阵因式分解实例，可以在多项式时间内最优求解。
The vertex ranking problem is closely related to the problem of finding the elimination tree of minimum height for a given graph. This implies that the problem has applications in the parallel Cholesky factorization of matrices. We describe the connection between this model of graph coloring and the matrix factorization. We also present a polynomial time algorithm for finding edge ranking of complete bipartite graphs. We use it to design anO(m2 + d) algorithm for edge ranking of graphs obtained by removingO(logm) edges from a complete bipartite graph, wheredis a fixed number. Then we extend our results to completek-partite graphs for any fixedk>2. In this way we give a new class of matrix factorization instances that can be optimally solved in polynomial time.