Efficient Nested Dissection for Multicore Architectures
| Dominique LaSalle and George Karypis |
| EuroPar, 2015 |
Download Paper  |
| Abstract Sparse matrices are common in scientific computing and machine learning. By storing and processing only the non-zero elements of a matrix containing mostly zeros, sparse matrix algorithms often reduce computation and storage requirements of operations by an order of complexity. The order of the rows and columns of the matrix can have a significant impact on the efficiency of sparse direct methods. For example, in a Cholesky decomposition, it is desirable to re-order the input matrix so as to reduce the number of non-zeros in the factors. One of the most effective methods for producing a good ordering nested dissection, where vertex separators are recursively found in the graph representation of the matrix and used to re-order the rows and columns. In this work we investigate the creation of vertex separators on shared memory parallel architectures and their use in nested dissection. We introduce a new effective scheme for refining a vertex separator in parallel, and a specialized parallel task scheduling scheme for the nested dissection problem. These algorithms have been implemented in the mt-Metis framework. Our experiments show that mt-Metis is 1.5× faster than ParMetis and PT- Scotch while producing orderings with 3.7% fewer non-zeros and 14.0% fewer operations. |
| Research topics: Graph partitioning | METIS | Parallel processing |