ePubs
The open archive for STFC research publications
Home
About ePubs
Content Policies
News
Help
Privacy/Cookies
Suggest an Enhancement
Contact ePubs
Full Record Details
Persistent URL
http://purl.org/net/epubs/work/65525
Record Status
Checked
Record Id
65525
Title
Compressed threshold pivoting for sparse symmetric indefinite systems
Contributors
JD Hogg (STFC Rutherford Appleton Lab.)
,
JA Scott (STFC Rutherford Appleton Lab.)
Abstract
A key technique for controlling numerical stability in sparse direct solvers is threshold partial pivoting. When selecting a pivot, the entire candidate pivot column below the diagonal must be up-to-date and must be scanned. If the factorization is parallelized across a large number of cores, communication latencies can be the dominant computational cost. In this paper, we propose two alternative pivoting strategies for sparse symmetric indefinite matrices that significantly reduce communication by compressing the necessary data into a small matrix that can be used to select pivots. Once pivots have been chosen, they can be applied in a communication-efficient fashion. For an nxp submatrix on P processors, we show our methods perform a factorization using O(log P)messages instead of the O(p log P) for threshold partial pivoting. The additional costs in terms of operations and communication bandwidth are relatively small. A stability proof is given and numerical results using a range of symmetric indefinite matrices arising from practical problems are used to demonstrate the practical robustness. Timing results on large random examples illustrate the potential speedup on current multicore machines.
Organisation
STFC
,
SCI-COMP
Keywords
Funding Information
Related Research Object(s):
Licence Information:
Language
English (EN)
Type
Details
URI(s)
Local file(s)
Year
Report
RAL Preprints
RAL-P-2013-007. 2013.
RAL-P-2013-007.pdf
2013
Showing record 1 of 1
Recent Additions
Browse Organisations
Browse Journals/Series
Login to add & manage publications and access information for OA publishing
Username:
Password:
Useful Links
Chadwick & RAL Libraries
SHERPA FACT
SHERPA RoMEO
SHERPA JULIET
Journal Checker Tool
Google Scholar