Block cyclic SOR for Markov chains with \(p\)-cyclic infinitesimal generator (Q1176521)

A new application of p-cyclic iterations, for arbitrary \(p\geq 2\), is introduced. The authors are interested in using block successive overrelaxation (SOR) to compute the stationary probability distribution of an irreducible Markov chain with infinitesimal generator that is \(p\)- cyclic. It is shown that the speed up parameter \(\omega\) may be chosen in a way such that the operator in the usual block decomposition method violates the conditions for semiconvergence. SOR ``converges'' to a vector that has subvectors parallel to the corresponding subvectors of the stationary probability vector. Necessary and sufficient conditions for convergence in this extended version are derived. They are applied to find the exact convergence intervals for the case where the \(p\)-th power of the block Jacobi matrix has nonnegative eigenvalues only. The optimal \(\omega\)-values are determined as well. In addition to the ``usual'' optimal \(\omega\) in the interval \((1,p/(p-1))\), other \(\omega\)-values that yield convergence in the extended case are found for the same optimal convergence rate. The paper contains numerical tests indicating that perturbations of \(\omega\) around the optimal value affect the convergence rate much less if these new optimal values are used.