EXTENSIONS OF CERTAIN GRAPH-BASED ALGORITHMS FOR PRECONDITIONING ∗

Abstract. The original TPABLO algorithms are a collection of algorithms which compute a symmetric permutation of a linear system such that the permuted system has a relatively full block diagonal with relatively large nonzero entries. This block diagonal can then be used as a preconditioner. We propose and analyze three extensions of this approach: We incorporate a nonsymmetric permutation to obtain a large diagonal, we use a more general parametrization for TPABLO, and we use a block Gauss–Seidel preconditioner which can be implemented to have the same execution time as the corresponding block Jacobi preconditioner. Experiments are presented showing that for certain classes of matrices, the block Gauss–Seidel preconditioner used with the system permuted with the new algorithm can outperform the best ILUT preconditioners in a large set of experiments