OPTIMAL P-CYCLIC SOR

Our purpose in this paper is to extend p-cyclic SOR theory to consiste nt singular systems and to apply the results to the solution of large scale systems arising, e.g., in queueing network problems in Markov an alysis. Markov chains and queueing models lead to structured singular linear systems and are playing an increasing role in the understanding of complex phenomena arising in computer, communication and transport ation systems. For certain important classes of singular problems, we develop a convergence theory for p-cyclic SOR, and show how to reparti tion for optimal convergence. Results by Kontovasilis, Plemmons and St ewart on the concept of convergence of SOR in an extended sense are ri gorously analyzed and applied to the solution of periodic Markov chain s with period p = 2.