Geodesic
Preconditioners based on strong subgraphs
Electronic transactions on numerical analysis, Tome 40 (2013), pp. 225-248.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: 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.
Classification : 05C50, 05C70, 65F50
Keywords: sparse matrices, strong subgraphs, strong components, preconditioners 
@article{ETNA_2013__40__a14,
     author = {Duff, Iain S. and Kaya, Kamer},
     title = {Preconditioners based on strong subgraphs},
     journal = {Electronic transactions on numerical analysis},
     pages = {225--248},
     publisher = {mathdoc},
     volume = {40},
     year = {2013},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ETNA_2013__40__a14/}
}
TY  - JOUR
AU  - Duff, Iain S.
AU  - Kaya, Kamer
TI  - Preconditioners based on strong subgraphs
JO  - Electronic transactions on numerical analysis
PY  - 2013
SP  - 225
EP  - 248
VL  - 40
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ETNA_2013__40__a14/
LA  - en
ID  - ETNA_2013__40__a14
ER  - 
%0 Journal Article
%A Duff, Iain S.
%A Kaya, Kamer
%T Preconditioners based on strong subgraphs
%J Electronic transactions on numerical analysis
%D 2013
%P 225-248
%V 40
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ETNA_2013__40__a14/
%G en
%F ETNA_2013__40__a14
Duff, Iain S.; Kaya, Kamer. Preconditioners based on strong subgraphs. Electronic transactions on numerical analysis, Tome 40 (2013), pp. 225-248. http://geodesic.mathdoc.fr/item/ETNA_2013__40__a14/