Bilkent University
Department of Computer Engineering
MS Thesis Presentation
Graph- and Hypergraph-Based Based Matrix Reordering Towards a Scalable Sparse Direct and Iterative Linear Solver
Mustafa Gündoğan
MS Student
Computer Engineering Department
Bilkent University
Given a linear system of equations of the form Ax = f, where A is large and sparse, it is known that hybrid solvers that contain both direct and iterative components are promising in terms of robustness and scalability on parallel computing platforms. DDPS, a state-of-the-art hybrid solver, which uses the generalized form parallel DS factorization is the focus of this work. The generalized DS factorization of the system involves reordering A to extract a block diagonal submatrix D, so that A = D + R where R contains the remaining off-diagonal entries, then, multiplying both sides of the system with D^-1. Resulting multiplied system contains a smaller reduced system of equations whose size is determined by number of columns that contains nonzero entries in off-diagonal blocks of the reordered system. The solution of the original system, Ax = f, can be constructed from the solution of this reduced system. After DS factorization, solution to the Ax = f reduces to a sequence of steps that are very amenable to parallel execution. In general, the scalability of this factorization scheme depends on decreasing the solution time of the reduced system. The solution time of the reduced system greatly depends on the size and the number of nonzeros of the reduced system.
Two different reordering strategies are investigated for a successful DS factorization preconditioning scheme: Reordering via graph partitioning (GP), and reordering via hypergraph partitioning (HP). In the GP scheme, the standard graph representation on matrix A is used.In the HP scheme, the column-net hypergraph model of matrix A is used.
The experimental performance comparison of the proposed GP and HP schemes for preconditioning with DS factorization are studied by using multi-level graph and hypergraph partitioning tools MeTiS and PaToH. Experiments are performed on 173 sparse linear systems from UFL Sparse Matrix Collection. To test the robustness and scalability of the preconditioned solver algorithm various configurations of DDPS are investigated in the experiments. Results obtanied from these experiments indicate that usage of both HP and GP schemes as a partitioner improves the performance of DDPS algorithm. HP scheme performs better than GP scheme in both minimizing the size of reduced system and reducing the solution time of the overall sparse linear system in most of the selected sparse linear systems. Nearly in 80% of linear systems used in the experiments, HP scheme considerably performs better than GP scheme.
DATE: 22 August, 2013, Thursday@ 14:00
PLACE: EA-502