Cholesky factorization of matrices in parallel and ranking of graphs.

*(English)* Zbl 1128.68544
Wyrzykowski, Roman (ed.) et al., Parallel processing and applied mathematics. 5th international conference, PPAM 2003, Czȩstochowa, Poland, September 7–10, 2003. Revised papers. Berlin: Springer (ISBN 3-540-21946-3/pbk). Lecture Notes in Computer Science 3019, 985-992 (2004).

Summary: 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 an $O\left({m}^{2+d}\right)$ algorithm for edge ranking of graphs obtained by removing $O(logm)$ edges from a complete bipartite graph, where $d$ is a fixed number. Then we extend our results to complete $k$-partite graphs for any fixed $k>2$. In this way we give a new class of matrix factorization instances that can be optimally solved in polynomial time.

##### MSC:

68W10 | Parallel algorithms |

05C85 | Graph algorithms (graph theory) |

65F30 | Other matrix algorithms |