Comparison theorems for splittings of M-matrices in (block) Hessenberg form

Some variants of the (block) Gauss–Seidel iteration for the solution of linear systems with M-matrices in (block) Hessenberg form are discussed. Comparison results for the asymptotic convergence rate of some regular splittings are derived: in particular, we prove that for a lower-Hessenberg M-matrix ρ(PGS) ≥ ρ(PS) ≥ ρ(PAGS) , where PGS, PS, PAGS are the iteration matrices of the Gauss–Seidel, staircase, and anti-Gauss–Seidel method. This is a result that does not seem to follow from classical comparison results, as these splittings are not directly comparable. It is shown that the concept of stair partitioning provides a powerful tool for the design of new variants that are suited for parallel computation.