An extension of the I + S_max preconditioner for
the Gauss-Seidel method

ISNARDO ARENAS^*, PAUL CASTILLO, XUERONG YONG
University of Puerto Rico, Department of Mathematical Sciences, Mayagüez, Puerto Rico, 00681, US.

Abstract. A preconditioning technique based on the application of a fixed but arbitrary number of I +S_max steps is proposed. A reduction of the spectral radius of the Gauss-Seidel iteration matrix is theoretically analyzed for diagonally dominant Z-matrices. In particular, it is shown that after a finite number of steps this matrix reduces to null matrix. To illustrate the performance of the proposed technique numerical experiments on a wide variety of matrices are presented. Point and block versions of the preconditioner are numerically studied.
Keywords: Preconditioning, Gauss-Seidel method, regular splitting, point and block preconditioners.
MSC2010: XX00YY, AA99BB

Una extensión del precondicionador I + S_max para el
método de Gauss-Seidel

Resumen. Se propone una técnica de precondicionamiento para el método de Gauss-Seidel basada en la aplicación de una cantidad de pasos arbitrarios pero fijos del precondicionador I+S_max. Se analiza de manera teórica la reducción del radio espectral de la matriz de iteración del método de Gauss-Seidel para Z-matrices diagonalmente dominantes. En particular, se demuestra que después de un número finito de pasos esta matriz se reduce a una matriz nula. Para ilustrar la eficacia de la técnica propuesta se presentan experimentos numéricos para una amplia variedad de matrices. Se estudian numéricamente versiones puntuales y de bloques del precondicionador.
Palabras claves: Precondicionamiento, método Gauss-Seidel, descomposiciones regulares, precondicionadores de punto y bloque.

Texto Completo disponible en PDF

References

[1] Axelsson O., Iterative Solution Methods, Cambridge University Press, New York, 1994.

[2] Berman A. and Plemmons R.J., Nonnegative Matrices in the Mathematical Sciences, Classics in Applied Mathematics, 9, SIAM, 1994.

[3] Castillo P. and Sequeira F.A., "Computational aspects of the Local Discontinuous Galerkin method on unstructured grids in three dimensions", Mathematical and Computer Modelling 57 (2013), 2279-2288.

[4] Du J., Zheng B. and Wang L., "New iterative methods for solving linear systems", J. Appl. Anal. Comput. 1 (2011), no. 3, 351-360.

[5] Durlofsky L.J., "Accuracy of mixed and control volume finite element approximations to Darcy velocity and related quantities", Water Resources Research 30 (1994), no.4, 965-973.

[6] Gunawardena A.D., Jain S.K. and Snyder L., "Modified iterative methods for consistent linear systems", Linear Algebra Appl. 154-156 (1991), 123-143.

[7] Hadjidimos A., Noutsos D. and Tzoumas M., "More on modifications and improvements of classical iterative schemes for M-matrices", Linear Algebra Appl. 364 (2003), 253-279.

[8] Kohno T., Kotakemori H., Niki H. and Usui M., "Improving the modified Gauss-Seidel method for Z-matrices", Linear Algebra Appl. 267 (1997), 113-123.

[9] Kotakemori H., Harada K., Morimoto M. and Niki H., "A comparison theorem for the iterative method with preconditioner (I +S_max)", J. Comput. Appl. Math. 145 (2002), no. 2, 373-378.

[10] Kotakemori H., Niki H. and Okamoto N., "Accelerated iterative method for Z-matrices", J. Comput. Appl. Math. 75 (1996), no. 1, 87-97.

[11] Liu Q., Chen G. and Cai J., "Convergence analysis of the preconditioned Gauss-Seidel method for H-matrices", Comput. Math. Appl. 56 (2008), no. 8, 2048-2053.

[12] Milaszewicz J.P., "Improving Jacobi and Gauss-Seidel iterations", Linear Algebra Appl. 93 (1987), 161-170.

[13] Mokari-Bolhassan M.E. and Trick T.N., "A new iterative algorithm for the solutions of large scale systems", 28th Midwest Symposium on Circuits and Systems Louisville, Kentucky, 1985.

[14] Morimoto M., Harada K., Sakakihara M. and Sawami H., "The Gauss-Seidel iterative method with the preconditioning matrix (I + S + SM)", Japan J. Appl. Math. 21 (2004), 25-34.

[15] Niki H., Harada K., Morimoto M. and Sakakihara M., "The survey of preconditioners used for accelerating the rate of convergence in the Gauss-Seidel method", J. Comput. Applied. Math. 164-165 (2004), 587-600.

[16] Shao J.L., Huang T.Z. and Zhang G.F., "Linear system based approach for solving some related problems of M-matrices", Linear Algebra Appl. 432 (2010), 327-337.

[17] Shen H., Shao X., Huang Z. and Li C., "Preconditioned Gauss-Seidel iterative method for Z matrices linear systems", Bull. Korean. Math. Soc. 48 (2011), 303-314.

[18] Varga R.S., Matrix Iterative Analysis, Springer Series in Computational Mathematics, Springer, Berlin, 2000.

[19] Zheng B. and Miao S.X., "Two new modified Gauss-Seidel methods for linear systems with M-matrices", J. Comput. Appl. Math. 233 (2009), 922-930.

^*Corresponding author: E-mail: isnardo.arenas@upr.edu.
Received: 03 December 2012, Accepted: 23 March 2013.