Successive overrelaxation (SOR) and related methods. (English) Zbl 0965.65052

Hadjidimos, A.

J. Comput. Appl. Math. 123, No. 1-2, 177-199 (2000).

This paper gives a comprehensive summary of the theory and practice of successive overrelaxation. After the general theory is outlined, the important cases of \((q,p-q)\)-cyclic consistently ordered matrices and block \(p\)-cyclic repartitioning are examined. Modified, symmetric and unsymmetric SOR methods, accelebrated overrelaxation, nonstationary, and higher-order methods are finally analyzed.

Reviewer: F.Szidarovszky (Tucson)

MSC:

65F10

Iterative numerical methods for linear systems

Keywords:

Jacobi method; Gauss-Seidel method; SOR method; successive overrelaxation; consistently ordered matrices; accelebrated overrelaxation

Software:

ITPACK

References:

[1]	Avdelas, G.; Hadjidimos, A., Optimum accelerated overrelaxation method in a special case, Math. comp., 36, 183-187, (1981) · Zbl 0463.65020
[2]	Avdelas, G.; Hadjidimos, A., Optimal 2-cyclic MSOR for “bowtie“ spectra and the “continuous” manteuffel algorithm, Linear algebra appl., 265, 29-54, (1997) · Zbl 0885.65035
[3]	Berman, A.; Plemmons, R.J., Nonnegative matrices in the mathematical sciences, (1994), SIAM Philadelphia, PA · Zbl 0815.15016
[4]	Buoni, J.J.; Neumann, M.; Varga, R.S., Theorems of stein – rosenberg type III, the singular case, Linear algebra appl., 42, 183-198, (1982) · Zbl 0487.65017
[5]	Buoni, J.J.; Varga, R.S., Theorems of stein – rosenberg type, (), 65-75 · Zbl 0412.65016
[6]	Buoni, J.J.; Varga, R.S., Theorems of stein – rosenberg type II, optimal paths of relaxation in the complex plane, (), 231-240
[7]	Chin, R.C.Y.; Manteuffel, T.A., An analysis of block successive overrelaxation for a class of matrices with complex spectra, SIAM J. numer. anal., 25, 564-585, (1988) · Zbl 0655.65060
[8]	L. Chong, D.-Y. Cai, Relationship between eigenvalues of Jacobi and SSOR iterative matrix with p-weak cyclic matrix J. Comput. Math. Coll. Univ. 1 (1985) 79-84 (in Chinese). · Zbl 0604.65014
[9]	Dancis, J., The optimal ω is not best for the SOR iteration method, Linear algebra appl., 154-156, 819-845, (1991) · Zbl 0731.65020
[10]	D’Sylva, E.; Miles, G.A., The S.S.O.R. iteration scheme for equations with σ1-orderings, Comput. J., 6, 271-273, (1963)
[11]	Eiermann, M.; Niethammer, W.; Ruttan, A., Optimal successive overrelaxation iterative methods for p-cyclic matrices, Numer. math., 57, 593-606, (1990) · Zbl 0708.65032
[12]	Eiermann, M.; Niethammer, W.; Varga, R.S., A study of semi-iterative methods for non-symmetric systems of linear equations, Numer. math., 47, 503-533, (1985) · Zbl 0585.65025
[13]	Eiermann, M.; Niethammer, W.; Varga, R.S., Acceleration of relaxation methods for non-Hermitian linear systems, SIAM J. matrix anal. appl., 13, 979-991, (1991) · Zbl 0757.65032
[14]	Eiermann, M.; Varga, R.S., Is the optimal ω best for the SOR iterative method? linear algebra appl., 182, 257-277, (1993) · Zbl 0773.65016
[15]	Eiermann, M.; Varga, R.S., Optimal semi-iterative methods applied to SOR in the mixed case, (), 47-73 · Zbl 0794.65027
[16]	Frankel, S.P., Convergence rates of iterative treatments of partial differential equations, Math. tables aids comput., 4, 65-75, (1950)
[17]	Galanis, S.; Hadjidimos, A., Best cyclic repartitioning for optimal SOR convergence, SIAM J. matrix anal. appl., 13, 102-120, (1992) · Zbl 0745.65022
[18]	Galanis, S.; Hadjidimos, A.; Noutsos, D., On the equivalence of the k-step iterative Euler methods and successive overrelaxation (SOR) methods for k-cyclic matrices, Math. comput. simulation, 30, 213-230, (1988) · Zbl 0659.65029
[19]	Galanis, S.; Hadjidimos, A.; Noutsos, D., Optimal p-cyclic SOR for complex spectra, Linear algebra appl., 263, 233-260, (1997) · Zbl 0885.65034
[20]	Galanis, S.; Hadjidimos, A.; Noutsos, D., A Young-Eidson’s type algorithm for complex p-cyclic SOR spectra, Linear algebra appl., 286, 87-106, (1999) · Zbl 0939.65043
[21]	Galanis, S.; Hadjidimos, A.; Noutsos, D.; Tzoumas, M., On the optimum relaxation factor associated with p-cyclic matrices, Linear algebra appl., 162-164, 433-445, (1992) · Zbl 0751.65020
[22]	Golub, G.H.; de Pillis, J., Toward an effective two-parameter method, (), 107-118
[23]	Greenbaum, A., Iterative methods for solving linear systems, (1997), SIAM Philadelphia, PA · Zbl 0883.65022
[24]	Hadjidimos, A., Accelerated overrelaxation method, Math. comp., 32, 149-157, (1978) · Zbl 0382.65015
[25]	Hadjidimos, A., The optimal solution to the problem of complex extrapolation of a first order scheme, Linear algebra appl., 62, 241-261, (1984) · Zbl 0567.65015
[26]	Hadjidimos, A., On the optimization of the classical iterative schemes for the solution of complex singular linear systems, SIAM J. algebra discrete methods, 6, 555-566, (1985) · Zbl 0582.65017
[27]	Hadjidimos, A., A survey of the iterative methods for the solution of linear systems by extrapolation, relaxation and other techniques, J. comput. appl. math., 20, 37-51, (1987) · Zbl 0635.65027
[28]	A. Hadjidimos, X.-Z. Li, R.S. Varga, Application of the Schur-Cohn theorem to precise convergence domains for the cyclic SOR iterative method, unpublished manuscript, 1985.
[29]	Hadjidimos, A.; Neumann, M., Precise domains of convergence for the block SSOR method associated with p-cyclic matrices, Bit, 29, 311-320, (1989) · Zbl 0677.65030
[30]	Hadjidimos, A.; Neumann, M., Convergence domains of the SSOR method for generalized consistently ordered matrices, J. comput. appl. math., 33, 35-52, (1990) · Zbl 0716.65027
[31]	Hadjidimos, A.; Neumann, M., Euclidean norm minimization of the SOR operators, SIAM J. matrix anal. appl., 19, 191-204, (1998) · Zbl 0915.65025
[32]	Hadjidimos, A.; Noutsos, D., The Young-eidson algorithm: applications and extensions, SIAM J. matrix anal. appl., 11, 620-631, (1990) · Zbl 0739.65028
[33]	Hadjidimos, A.; Noutsos, D., On a matrix identity connecting iteration operators associated with a p-cyclic matrix, Linear algebra appl., 182, 157-178, (1993) · Zbl 0777.65018
[34]	Hadjidimos, A.; Noutsos, D.; Tzoumas, M., Exact SOR convergence regions for a general class of p-cyclic matrices, Bit, 35, 469-487, (1995) · Zbl 0839.65035
[35]	Hadjidimos, A.; Noutsos, D.; Tzoumas, M., On the exact p-cyclic SSOR convergence domains, Linear algebra appl., 232, 213-236, (1996) · Zbl 0840.65020
[36]	Hadjidimos, A.; Noutsos, D.; Tzoumas, M., On the convergence domains of the p-cyclic SOR, J. comput. appl. math., 72, 63-83, (1996) · Zbl 0859.65025
[37]	Hadjidimos, A.; Noutsos, D.; Tzoumas, M., Towards the determination of the optimal p-cyclic SSOR, J. comput. appl. math., 90, 1-14, (1997) · Zbl 0934.65037
[38]	Hadjidimos, A.; Plemmons, R.J., Optimal p-cyclic SOR, Numer. math., 67, 475-490, (1994) · Zbl 0803.65032
[39]	Hadjidimos, A.; Psimarni, A.; Yeyios, A.K., On the convergence of the modified accelerated overrelaxation (MAOR) method, Applied numer. math., 10, 115-127, (1992) · Zbl 0754.65035
[40]	Hadjidimos, A.; Saridakis, Y.G., Modified successive overrelaxation (MSOR) and equivalent 2-step iterative methods for collocation matrices, J. comput. appl. math., 42, 375-393, (1992) · Zbl 0760.65031
[41]	Hadjidimos, A.; Yeyios, A., Symmetric accelerated overrelaxation (SAOR) method, Math. comput. simulation, XXIV, 72-76, (1982) · Zbl 0476.65022
[42]	Hadjidimos, A.; Yeyios, A., On some extensions of the accelerated overrelaxation (AOR) theory, Internat. J. math. math. sci., 5, 49-60, (1982) · Zbl 0497.65016
[43]	Hadjidimos, A.; Yeyios, A.K., Some recent results on the modified SOR theory, Linear algebra appl., 154-156, 5-21, (1991) · Zbl 0731.65019
[44]	Hageman, L.A.; Young, D.M., Applied iterative methods, (1981), Academic Press New York · Zbl 0459.65014
[45]	Henrici, P., Applied and computational complex analysis, (1974), Wiley New York
[46]	Kahan, W., Gauss – seidel methods of solving large systems of linear equations, doctoral thesis, (1958), University of Toronto Toronto, Canada
[47]	Kincaid, D.R., Norms of the successive overrelaxation method, Math. comp., 118, 345-357, (1972) · Zbl 0251.65026
[48]	Kincaid, D.R.; Respess, J.R.; Young, D.M.; Grimes, R.G., ITPACK 2C: a Fortran package for solving large sparse linear systems by adaptive accelerated iterative methods, ACM trans. math. software, 8, 302-322, (1992) · Zbl 0485.65025
[49]	Kincaid, D.R.; Young, D.M., The modified successive overrelaxation method with fixed parameters, Math. comp., 119, 705-717, (1972) · Zbl 0264.65029
[50]	Kjellberg, G., On the convergence of the successive over-relaxation applied to a class of linear systems of equations with complex eigenvalues, Ericsson technics Stockholm, 2, 245-258, (1958)
[51]	Kontovasilis, K.; Plemmons, R.J.; Stewart, W.J., Block cyclic SOR for Markov chains with p-cyclic infinitesimal generator, Linear algebra appl., 154-156, 145-223, (1991) · Zbl 0736.65094
[52]	Kredell, B., On complex successive overrelaxation, Bit, 2, 143-152, (1962) · Zbl 0112.07602
[53]	Kuznetsov, Y.A., Matrix iterative methods in subspaces, Proceedings of the international congress of mathematicians, warszawa, August 16-24, 1983, (1984), North Holland Amsterdam · Zbl 0569.65025
[54]	Li, X.; Varga, R.S., A note on the SSOR and USSOR iterative methods applied to p-cyclic matrices, Numer. math., 56, 109-121, (1989) · Zbl 0678.65021
[55]	Lynn, M.S., On the equivalence of SOR, SSOR and USSOR as applied to σ1-ordered systems of linear equations, Comput. J., 7, 72-75, (1964) · Zbl 0134.32705
[56]	Manteuffel, T.A., An iterative method for solving nonsymmetric linear systems with dynamic estimation of parameters, Utucsd-r-75, (1975), Department of Computer Science, University of Illinois Urbana, IL
[57]	Manteuffel, T.A., The tchebychev iteration for non-symmetric linear systems, Numer. math., 28, 307-327, (1977) · Zbl 0361.65024
[58]	Manteuffel, T.A., Adaptive procedure for estimating parameters for the non-symmetric tchebychev iteration, Numer. math., 31, 183-208, (1978) · Zbl 0413.65032
[59]	Manteuffel, T.A., Optimal parameters for linear second-degree stationary iterative methods, SIAM J. numer. anal., 19, 833-839, (1982) · Zbl 0486.65020
[60]	Markham, T.L.; Neumann, M.; Plemmons, R.J., Convergence of a direct-iterative method for large-scale least squares problems, Linear algebra appl., 69, 155-167, (1985) · Zbl 0576.65026
[61]	L.K. McDowell, Variable successive overrelaxation, Report No. 244, Department of Computer Sciences, University of Illinois, Urbana, IL.
[62]	Missirlis, N.M., Convergence theory of extrapolated iterative methods for a certain class of non-symmetric linear systems, Numer. math., 45, 447-458, (1984) · Zbl 0535.65016
[63]	Neumaier, A.; Varga, R.S., Exact convergence and divergence domains for the symmetric successive overrelaxation iterative (SSOR) method applied to H-matrices, Linear algebra appl., 58, 261-272, (1984) · Zbl 0569.65021
[64]	Nichols, N.K.; Fox, L., Generalized consistent ordering and the optimum successive over-relaxation factor, Numer. math., 13, 425-433, (1969) · Zbl 0172.42502
[65]	Niethammer, W., On different splittings and the associated iteration methods, SIAM J. numer. anal., 16, 186-200, (1979) · Zbl 0406.65011
[66]	Niethammer, W., Relaxation bei matrizen mit der eigenschaft “A”, Z. angew. math. mech., 44, T49-T52, (1964) · Zbl 0137.33001
[67]	Niethammer, W.; de Pillis, J.; Varga, R.S., Convergence of block iterative methods applied to sparse least squares problems, Linear algebra appl., 58, 327-341, (1984) · Zbl 0565.65019
[68]	Niethammer, W.; Varga, R.S., The analysis of k-step iterative methods for linear systems from summability theory, Numer. math., 41, 177-206, (1983) · Zbl 0487.65018
[69]	Noutsos, D., Optimal stretched parameters for the SOR iterative method, J. comput. appl. math., 48, 293-308, (1993) · Zbl 0797.65025
[70]	Noutsos, D., An operator relation of the USSOR and the Jacobi iteration matrices of a p-cyclic matrix, SIAM J. matrix. anal. appl., 17, 515-529, (1996) · Zbl 0855.65018
[71]	Opfer, G.; Schober, G., Richardson’s iterations for nonsymmetric matrices, Linear algebra appl., 58, 343-361, (1984) · Zbl 0565.65012
[72]	Pierce, D.J.; Hadjidimos, A.; Plemmons, R.J., Optimality relationships for p-cyclic SOR, Numer. math., 56, 635-643, (1990) · Zbl 0687.65034
[73]	Russell, D.B., On obtaining solutions to navier – stokes equations with automatic digital computers, (1963), Aeronautical Research Council Report R & M 3331 Engineering Laboratory Oxford
[74]	Saridakis, Y.G., Generalized consistent orderings and the accelerated overrelaxation method, Bit, 26, 369-376, (1986) · Zbl 0605.65017
[75]	Saridakis, Y.G., On the analysis of the unsymmetric overrelaxation method when applied to p-cyclic matrices, Numer. math., 49, 461-473, (1986) · Zbl 0579.65025
[76]	Sisler, M., Uber ein zweiparametrigen iterationsverfahrens, Apl. mat., 18, 325-332, (1973) · Zbl 0267.65024
[77]	Sisler, M., Uber die optimierung eines zweiparametrigen iterationsverfahrens, Apl. mat., 20, 126-142, (1975) · Zbl 0313.65028
[78]	Sisler, M., Bemerkungen zur optimierung eines zweiparametrigen iterationsverfahrens, Apl. mat., 21, 213-220, (1976) · Zbl 0339.65019
[79]	Southwell, R.V., Relaxation methods in theoretical physics, (1946), Clarendon Press Oxford · Zbl 0061.27706
[80]	Tall, D.O., Functions of a complex variable, (1970), Library of Mathematics, Routledge & Kegan Paul London · Zbl 0222.30001
[81]	Taylor, P.J., A generalisation of systematic relaxation methods for consistently ordered matrices, Numer. math., 13, 377-395, (1969) · Zbl 0257.65038
[82]	Varga, R.S., p-cyclic matrices: a generalization of the Young-frankel successive overrelaxation scheme, Pacific J. math., 9, 617-628, (1959) · Zbl 0088.09402
[83]	Varga, R.S., Matrix iterative analysis, (1962), Prentice-Hall Englewood Cliffs, NJ · Zbl 0133.08602
[84]	Varga, R.S., Extensions of the successive overrelaxation theory with applications to finite element approximations, (), 242-247
[85]	R.S. Varga, Personal communication (also, revision of [83], 1999).
[86]	Varga, R.S.; Niethammer, W.; Cai, D.Y., p-cyclic matrices and the symmetric successive overrelaxation method, Linear algebra appl., 58, 425-439, (1984) · Zbl 0569.65022
[87]	Verner, J.H.; Bernal, M.J.M., On generalizations of the theory of consistent orderings for successive overrelaxation methods, Numer. math., 12, 215-222, (1968) · Zbl 0172.18802
[88]	Wild, P.; Niethammer, W., Over and underrelaxation for linear systems with weakly cyclic Jacobi matrices of index p, Linear algebra appl., 91, 29-52, (1987) · Zbl 0624.65027
[89]	Wrigley, E.E., On accelerating the Jacobi method for solving simultaneous equations by Chebyshev extrapolation when the eigenvalues of the iteration matrix are complex, Comput. J., 6, 169-176, (1963) · Zbl 0131.14201
[90]	Young, D.M., Iterative methods for solving partial differential equations of elliptic type, doctoral thesis, (1950), Harvard University Cambridge, MA
[91]	Young, D.M., Iterative methods for solving partial differential equations of elliptic type, Trans. amer. math. soc., 76, 92-111, (1954) · Zbl 0055.35704
[92]	Young, D.M., Convergence properties of the symmetric and unsymmetric successive overrelaxation methods and related methods, Math. comp., 112, 793-807, (1970) · Zbl 0221.65060
[93]	Young, D.M., Iterative solution of large linear systems, (1971), Academic Press New York · Zbl 0204.48102
[94]	Young, D.M.; Eidson, H.E., On the determination of the optimum relaxation factor for the SOR method when the eigenvalues of the Jacobi matrix are complex, Report CNA-1, (1970), Center for Numerical Analysis, University of Texas Austin, TX
[95]	Young, D.M.; Kincaid, D.R., Norms of the successive overrelaxation method and related methods, Report TNN-94, (1969), Computation Center, University of Texas Austin, TX