Premium
A nested dissection approach for sparse matrix partitioning
Author(s) -
Boman Erik G.
Publication year - 2007
Publication title -
pamm
Language(s) - English
Resource type - Journals
ISSN - 1617-7061
DOI - 10.1002/pamm.200700703
Subject(s) - sparse matrix , computer science , matrix (chemical analysis) , row , partition (number theory) , row and column spaces , parallel computing , vertex (graph theory) , matrix multiplication , algorithm , dense graph , computation , sparse approximation , theoretical computer science , mathematics , graph , combinatorics , chemistry , physics , computational chemistry , chromatography , database , quantum mechanics , 1 planar graph , line graph , quantum , gaussian
We consider how to partition and distribute sparse matrices among processors to reduce communication cost in sparse matrix computations, in particular, sparse matrix‐vector multiplication. We consider 2d distributions, where the distribution is not constrained to just rows or columns. We present a new model and an algorithm based on vertex separators and nested dissection. Preliminary numerical results for sparse matrices from real applications indicate the new method performs consistently better than traditional 1d partitioning and is often also better than current 2d methods. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)