Name
Title | ||
|---|---|---|
On Partitioning and Reordering Problems in a Hierarchically Parallel Hybrid Linear Solver |
Abstract | ||
|---|---|---|
PDSLin is a general-purpose algebraic parallel hybrid (direct/iterative) linear solver based on the Schur complement method. The most challenging step of the solver is the computation of a preconditioner based on the global Schur complement. Efficient parallel computation of the preconditioner gives rise to partitioning problems with sophisticated constraints and objectives. In this paper, we identify two such problems and propose hyper graph partitioning methods to address them. The first problem is to balance the work loads associated with different sub domains to compute the preconditioner. We first formulate an objective function and a set of constraints to model the preconditioner computation time. Then, to address these complex constraints, we propose a recursive hyper graph bisection method. The second problem is to improve the data locality during the parallel solution of a sparse triangular system with multiple sparse right-hand sides. We carefully analyze the objective function and show that it can be well approximated by a standard hyper graph partitioning method. Moreover, an ordering compatible with a post ordering of the sub domain elimination tree is shown to be very effective in preserving locality. To evaluate the two proposed methods in practice, we present experimental results using linear systems arising from some applications of our interest. First, we show that in comparison to a commonly-used nested graph dissection method, the proposed recursive hyper graph partitioning method reduces the preconditioner construction time, especially when the number of sub domains is moderate. This is the desired result since PDSLin is based on a two-level parallelization to keep the number of sub domains small by assigning multiple processors to each sub domain. We also show that our second proposed hyper graph method improves the data locality during the sparse triangular solution and reduces the solution time. Moreover, we show that partitioning time can be greatly reduced while maintaining its quality by removing quasi-dense rows from the solution vectors. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1109/IPDPSW.2013.170 | Parallel and Distributed Processing Symposium Workshops & PhD Forum |
Keywords | Field | DocType |
reordering problems,data locality,standard hyper graph,commonly-used nested graph dissection,proposed recursive hyper graph,hyper graph,objective function,parallel hybrid linear solver,sub domain,proposed hyper graph method,recursive hyper graph bisection,parallel processing,linear programming,algebra,sparse matrices,preconditioner,schur complement method,algorithm design and analysis,graph theory,linear system | Graph theory,Locality,Linear system,Preconditioner,Computer science,Parallel computing,Solver,Schur complement method,Graph partition,Schur complement | Conference |
ISBN | Citations | PageRank |
978-0-7695-4979-8 | 1 | 0.36 |
References | Authors | |
8 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ichitaro Yamazaki | 1 | 174 | 25.27 |
| Xiaoye S. Li | 2 | 1042 | 98.22 |
| Francois-Henry Rouet | 3 | 2 | 0.84 |
| Bora Ucar | 4 | 75 | 7.50 |