The Impact of Hardware Gather/Scatter on Sparse Gaussian Elimination

Recent vector supercomputers provide vector memory access to "randomly" indexed vectors, whereas early vector supercomputers required contiguously or regularly indexed vectors. This additional capability, known as "hardware gather/scatter," can be used to great effect in general...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on scientific and statistical computing 1988-03, Vol.9 (2), p.304-311
Main Authors: Lewis, John G., Simon, Horst D.
Format: Article
Language:English
Subjects:
Algorithms
Computers
Sparsity
Supercomputers
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Recent vector supercomputers provide vector memory access to "randomly" indexed vectors, whereas early vector supercomputers required contiguously or regularly indexed vectors. This additional capability, known as "hardware gather/scatter," can be used to great effect in general sparse Gaussian elimination. In this note we present some examples that show the impact of this change in hardware on the choice of algorithms for sparse Gaussian elimination. Common folk wisdom holds that general sparse Gaussian elimination algorithms do not perform well on vector computers. Our numerical results demonstrate that hardware gather/scatter allows general sparse elimination algorithms to outperform algorithms based on a band, envelope, or block structure on such computers.
ISSN:0196-5204
1064-8275
2168-3417
1095-7197
DOI:10.1137/0909019