Volume 40, pp. 225-248, 2013.
Preconditioners based on strong subgraphs
Iain S. Duff and Kamer Kaya
Abstract
This paper proposes an approach for obtaining block diagonal and block
triangular preconditioners that can be used for solving a linear
system , where is a large,
nonsingular, real, sparse matrix. The proposed approach
uses Tarjan's algorithm for hierarchically decomposing a digraph into
its strong subgraphs.
To the best of our
knowledge, this is the first work that uses this algorithm
for preconditioning purposes. We describe the method, analyse its
performance, and compare it with preconditioners from the literature
such as ILUT
and XPABLO
and show that it is highly competitive with them in terms of both memory
and iteration count. In addition, our approach shares with XPABLO
the benefit of being able to exploit parallelism through a version that uses a
block diagonal preconditioner.
Full Text (PDF) [6 MB],
BibTeX
Key words
sparse matrices, strong subgraphs, strong components, preconditioners
AMS subject classifications
05C50, 05C70, 65F50
