A General Theory of Optimal p-Cyclic SOR
APOSTOLOS HADJIDIMOS, Robert J. Plemmons · Purdue e-Pubs (Purdue University System) · 1992
The convergence theory of the Successive Overrelaxation (SOR) iterative method for the solution of nonsingular linear systems Ax = b, when the matrix A has a block p X P partitioned p-cyclic form, is well documented. However, when A is singular the corresponding theory is far behind that for the nonsingular case. Our purpose in this paper is to extend the p-cyclic SOR theory to consistent singular systems and to apply the results to the solution of large scale systems arising, e.g., in queueing network problems in Markov analysis. 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 transportation systems. For certain important classes of singular problems, we develop a convergence theory for p-cyclic SOR, and show how to repartition for optimal convergence. Results by Kontovasilis, Plemmons and Stewart on the new concept of convergence of SOR in an extended sense are rigorously analyzed and applied to the solution of periodic Markov chains with period p = 2. In addition, the use of p-cyclic SOR as a smoother for algebraic multigrid computations for queueing network problems is discussed. ·Department of Computer Science, Purdue University, West Lafayette, IN 47907. Research supported in part by the US Air Force under grant no. AFOSR-88-10243 and by NS F under grant no. CCR-86-19817. tDepartment of Mathematics and Computer Science, Wake Forest University, P.O. Box 7388, Winston-Salem, NC 27109. Research supported by the US Air Force under grant no. AFOSR-91-0163 and by NSF under grant no. CCR-92-01105.