Efficient nested dissection for multicore architectures

Dominique LaSalle, George Karypis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

21 Scopus citations


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 re-ordering is nested dissection, where vertex separators are recursively found in the graph representation of the matrix and are used to permute 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 while producing orderings with 3.7% fewer non-zeros and 14.0% fewer operations.

Original languageEnglish (US)
Title of host publicationEuro-Par 2015
Subtitle of host publicationParallel Processing - 21st International Conference on Parallel and Distributed Computing, Proceedings
EditorsJesper Larsson Traff, Sascha Hunold, Francesco Versaci
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783662480953
StatePublished - 2015
Event21st International Conference on Parallel and Distributed Computing, Euro-Par 2015 - Vienna, Austria
Duration: Aug 24 2015Aug 28 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other21st International Conference on Parallel and Distributed Computing, Euro-Par 2015

Bibliographical note

Funding Information:
This work was supported in part by NSF (IIS-0905220, OCI-1048018, CNS-1162405, IIS-1247632, IIP-1414153, IIS-1447788), Army Research Office (W911NF-14-1-0316), Intel Software and Services Group, and the Digital Technology Center at the University of Minnesota. Access to research and computing facilities was provided by the Digital Technology Center and the Minnesota Supercomputing Institute.

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2015.


Dive into the research topics of 'Efficient nested dissection for multicore architectures'. Together they form a unique fingerprint.

Cite this