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 $\mathbf{A}\mathbf{x} = \mathbf{b}$, where $\mathbf{A}$ is a large, nonsingular, real, $n \times n$ 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

< Back