The open archive for STFC research publications

Full Record Details

DOI 10.5286/raltr.2016004
Persistent URL http://purl.org/net/epubs/work/24733312
Record Status Checked
Record Id 24733312
Title Nested dissection revisited
Abstract Nested dissection algorithms are widely used to order large sparse matrices with a symmetric sparsity pattern prior to using a sparse direct linear solver. In this report, we revisit nested dissection algorithms. In particular, level based methods and multilevel methods are examined, along with techniques for refining and improving the ordering. Our experience has led to the development of a new open source nested dissection-based ordering package SPRAL_ND. We report on the design of SPRAL_ND, the options that it offers and illustrate its performance using problems arising from a range of practical applications. Comparisons are made with the widely used MeTiS package. We find that while multilevel methods generally produce the best orderings in terms of the subsequent fill in the matrix factor and the ops needed to compute it, using a non-multilevel ordering that is significantly less expensive to compute can result in a reduction in the total solution time when used with a state-of-the-art parallel sparse direct solver.
Organisation STFC , SCI-COMP , SCI-COMP-CM
Funding Information
Related Research Object(s):
Licence Information: Creative Commons Attribution 3.0 Unported (CC BY 3.0)
Language English (EN)
Type Details URI(s) Local file(s) Year
Report RAL Technical Reports RAL-TR-2016-004. 2016. RAL-TR-2016-004.pdf 2016