Hypergraph-Partitioning-Based Sparse Matrix Ordering

@inproceedings{citeulike:665922, abstract = {In this work we propose novel sparse matrix ordering approaches based on hypergraph partitioning. The significance of hypergraph-partitioning-based (HP-based) ordering is three-fold. First, almost all of the successful nested dissec- tion [6] tools [7, 9, 10] are based on multilevel graph partitioning tools [7, 8, 10] with some extra initial partitioning and refinement strategies specific to the solution of the Graph Partitioning by Vertex Separator (GPVS) problem. However, GPVS-based multilevel ordering has a flaw as will be discussed in the next section. Second, direct solutions of the systems in the form of ADAT x = b requires factorization of ADAT , where A is a sparse and possibly rectangular matrix, and D is a diagonal matrix. Here we present an approach for formulating GPVS problem as a Hypergraph Partitioning (HP) problem. Using that formulation coupled with hypergraphs ability to model unsymmetric matri- ces [4, 5], we propose a new method for finding a fill-reducing ordering of ADAT by finding a nested dissection of unsymmetric and possibly rectangular matrix A . Third, we generalize the proposed method to order any symmetric matrices.}, author = {Catalyurek, Umit V. and Aykanat, Cevdet }, booktitle = {Second International Workshop on Combinatorial Scientific Computing (CSC05)}, citeulike-article-id = {665922}, comment = {Abstract at http://www.cerfacs.fr/algor/CSC05/Abstracts/11\_Catalyurek\_Aykanat.pdf}, keywords = {hypergraph, matrix, partitioning, sparse}, month = {June}, posted-at = {2006-05-23 04:22:16}, priority = {5}, title = {Hypergraph-Partitioning-Based Sparse Matrix Ordering} }

TY - CONF ID - citeulike:665922 L3 - citeulike-article-id:665922 TI - Hypergraph-Partitioning-Based Sparse Matrix Ordering T2 - Second International Workshop on Combinatorial Scientific Computing (CSC05) N2 - In this work we propose novel sparse matrix ordering approaches based on hypergraph partitioning. The significance of hypergraph-partitioning-based (HP-based) ordering is three-fold. First, almost all of the successful nested dissec- tion [6] tools [7, 9, 10] are based on multilevel graph partitioning tools [7, 8, 10] with some extra initial partitioning and refinement strategies specific to the solution of the Graph Partitioning by Vertex Separator (GPVS) problem. However, GPVS-based multilevel ordering has a flaw as will be discussed in the next section. Second, direct solutions of the systems in the form of ADAT x = b requires factorization of ADAT , where A is a sparse and possibly rectangular matrix, and D is a diagonal matrix. Here we present an approach for formulating GPVS problem as a Hypergraph Partitioning (HP) problem. Using that formulation coupled with hypergraphs ability to model unsymmetric matri- ces [4, 5], we propose a new method for finding a fill-reducing ordering of ADAT by finding a nested dissection of unsymmetric and possibly rectangular matrix A . Third, we generalize the proposed method to order any symmetric matrices. KW - hypergraph KW - matrix KW - partitioning KW - sparse N1 - Abstract at http://www.cerfacs.fr/algor/CSC05/Abstracts/11_Catalyurek_Aykanat.pdf AU - Catalyurek, Umit AU - Aykanat, Cevdet ER -