A Study of the Influence of Sparse Matrices Reordering Algorithms on Krylov-Type Preconditioned Iterative Methods

Abstract

This work analyzes the influenc of matrices reordering algorithms on solving linear systems using non-stationary iterative methods GMRES and Conjugate Gradient, both with and without preconditioning. The algorithms referenced most often in the literature for the reordering of matrices are Reverse Cuthill-McKee (RCM), Gibbs-Poole-Stockmeyer (GPS), Nested Dissection (ND) and Spectral (ES). We analyze these algorithms and propose some modification comparing their solution qualities (minimizing bandwidth and minimizing envelope) and CPU times. Moreover, the linear systems associated with sparse matrices are solved via preconditioned Krylov-type iterative methods considering the incomplete LU factorization preconditioners. For the computational tests, we consider a set of structurally symmetric matrices that can come from various field of knowledge. We conclude that the reordering of matrices, in most cases, reduces the number of iterations in the iterative methods, but that reducing the CPU time depends on the size and conditioning of the matrix.