An acceleration technique for the
Gauss-Seidel method applied to symmetric
linear systems

JESÚS CAJIGAS^{a, *}, ISNARDO ARENAS^b, PAUL CASTILLO^a

^a University of Puerto Rico, Department of Mathematical Sciences, Mayagüez, Puerto Rico 00681, US.
^b The University of Texas at Dallas, Department of Mathematical Sciences, Richardson, TX 75080-3021.

Abstract. A preconditioning technique to improve the convergence of the Gauss-Seidel method applied to symmetric linear systems while preserving symmetry is proposed. The preconditioner is of the form I + K and can be applied an arbitrary number of times. It is shown that under certain conditions the application of the preconditioner a finite number of steps reduces the matrix to a diagonal. A series of numerical experiments using matrices from spatial discretizations of partial differential equations demonstrates that both versions of the preconditioner, point and block version, exhibit lower iteration counts than its non-symmetric version.

Keywords: Preconditioning, Gauss-Seidel method, regular splitting.
MSC2010: 65F08, 65F10, 65F50.

Una técnica de aceleración para el método Gauss-Seidel aplicado a sistemas lineales simétricos

Resumen. Se propone una técnica de precondicionamiento para mejorar la convergencia del método Gauss-Seidel aplicado a sistemas lineales simétricos pero preservando simetría. El precondicionador es de la forma I + K y puede ser aplicado un número arbitrario de veces. Se demuestra que bajo ciertas condiciones la aplicación del precondicionador un número finito de pasos reduce la matriz del sistema precondicionado a una diagonal. Una serie de experimentos con matrices que provienen de la discretización de ecuaciones en derivadas parciales muestra que ambas versiones del precondicionador, por punto y por bloque, muestran un menor número de iteraciones en comparación con la versión que no preserva simetría.

Palabras Claves: Precondicionamiento, método de Gauss-Seidel, descomposiciones regulares.

Texto Completo disponible en PDF

Referencias

[1] Arenas I., Castillo P., and Yong X., "An extension of the I + S_max preconditioner for the Gauss-Seidel method", Rev. Integr. Temas Mat. 31 (2013), no. 1, 1-14.

[2] Castillo P., "Performance of discontinuous Galerkin methods for elliptic PDEs", SIAM J. Sci. Comput. 24 (2002), no. 2, 524-547.

[3] Castillo P., Cockburn B., Perugia I., and Schötzau D., "An a priori error analysis of the Local Discontinuous Galerkin method for elliptic problems", SIAM J. Numer. Anal., 38 (2000), no. 5, 1676-1706.

[4] Castillo P. and Sequeira F., "Computational aspects of the Local Discontinuous Galerkine method on unstructured grids in three dimensions", Math. Comput. Modelling 57 (2013), no. 9-10, 2279-2288.

[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] 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.

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

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

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

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

[11] 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. Appl. Math., 2004, no. 164-165, 587-600. Proceedings of the 10th International Congress on Computational and Applied Mathematics.

[12] 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), no. 1, 327-337.

[13] 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), no. 2, 303-314.

[14] Zheng B. andMiao 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: jesus.cajigas@upr.edu.
Received: 16 December 2013, Accepted: 20 March 2014.
To cite this article: J. Cajigas, I. Arenas, P. Castillo, An acceleration technique for the Gauss-Seidel method
applied to symmetric linear systems, Rev. Integr. Temas Mat. 32 (2014), no. 1, 91-100.