×

Preconditioners based on strong subgraphs. (English) Zbl 1286.05085

Summary: This paper proposes an approach for obtaining block diagonal and block triangular preconditioners that can be used for solving a linear system \(\mathbf{Ax} = \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.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
65F50 Computational methods for sparse matrices
PDFBibTeX XMLCite
Full Text: EMIS