Best Cyclic Repartitioning for Optimal Successive Overrelaxation Convergence

Abstract

In this paper, the successive overrelaxation (SOR) method for the solution of a linear system whose matrix coefficient A is block p-cyclic consistently ordered is discussed. In recent works, many researchers considered some “natural” assumptions on the spectrum $\sigma (J_p )$ of the block Jacobi matrix $J_p $ associated with A and answered the following question: What is the repartitioning of A into a block q-cyclic form $(2\leqq q\leqq p)$ which yields the best optimal SOR method for the solution of the given system? In this paper, the same question is answered in the most general case considered so far, that is, under the assumption $\sigma (J_p^p ) \subset [ - \alpha ^p ,\beta ^p ] \subset \mathbb{R}\backslash \{ [1,\infty )\} ,\alpha ,\beta \geqq 0$. It is also shown that the results in all previous works are recovered as particular subcases of the case considered here.