Acceleration of Relaxation Methods for Non-Hermitian Linear Systems

Let A = I - B ∈ Cn,n, with diag$(B) = 0$, denote a nonsingular non-Hermitian matrix. To iteratively solve the linear system A x = b, two splittings of A, together with induced relaxation methods, have been recently investigated in [W. Niethammer and R. S. Varga, Results in Math., 16 (1989), pp. 308–320]. The Hermitian splitting of A is defined by A = Mʰ - Nʰ, where Mʰ : = ( A + A^ * )/2 is the Hermitian part of A. The skew-Hermitian splitting of A is similarly defined by A = Mˢ - Nˢ with Mˢ : = I + ( A - A^ *)/2. This paper considers k-step iterative methods to accelerate the relaxation schemes (involving a relaxation factor ω) that are generated by these two splittings. The primary interest is not to determine the optimal relaxation factor ω that minimizes the spectral radius of the associated iteration operator. Rather, a value of ω is sought such that the resulting relaxation method can be most efficiently accelerated by a k-step method. For the Hermitian splitting, the choice ω = 1 (together with a suitable Chebyshev acceleration) turns out to be optimal in this sense. For the skew-Hermitian splitting, a hybrid scheme is proposed that is nearly optimal. As another application of this latter hybrid procedure, the block Jacobi method arising from a model equation for a convection-diffusion problem is analyzed.