×

Block Gauss elimination followed by a classical iterative method for the solution of linear systems. (English) Zbl 1041.65032

The paper studies an approach for solving a system of linear equations \(Ax=b\) numerically which consists of two steps. Firstly, a preconditioner which consists of some steps of the Gaussian elimination is used which produces zero entries in the matrix. Secondly, a classical iterative scheme is applied to the preconditioned system with the matrix \(\tilde A\) or to a reduced system with the system matrix \(\tilde A_1\) where the columns of \(\tilde A\) with the zero entries and the corresponding rows are eliminated. This algorithm has been previously studied for one Gaussian elimination step and pointwise iterative methods.
In this paper, it is extended to more Gaussian elimination steps and blockwise iterative methods. The convergence of this algorithm is proven for nonsingular M-matrices \(A\), the block-Jacobi method, some block-Gauss-Seidel-type methods and block-successive overrelaxation-type methods applied to the systems with matrix \(\tilde A\) or \(\tilde A_1\), respectively, by bounding the spectral radii of the iteration matrices from above strictly by 1. The results are extended to nonsingular \(p\)-cyclic consistently ordered matrices. Their extensions to some types of singular matrices is discussed. For supporting the theoretical results, spectral radii of the iteration matrices for one particular M-matrix are presented.
Finally, a numerical example for a finite difference discretization of the Poisson equation is presented, where two of the studied methods are compared to preconditioned conjugated conjugate gradient (PCG) methods with an incomplete Cholesky preconditioner. If the mesh width becomes finer, PCG becomes more and more superior.

MSC:

65F10 Iterative numerical methods for linear systems
65N06 Finite difference methods for boundary value problems involving PDEs
35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation
65F35 Numerical computation of matrix norms, conditioning, scaling
65F05 Direct numerical methods for linear systems and matrix inversion
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] M. Alanelli, Elementary block elimination preconditioners for the numerical solution of nonsingular and singular linear systems, Master Dissertation, Department of Mathematics, University of Crete, GR-714 09 Heraklion, Greece, 2001 (in Greek).; M. Alanelli, Elementary block elimination preconditioners for the numerical solution of nonsingular and singular linear systems, Master Dissertation, Department of Mathematics, University of Crete, GR-714 09 Heraklion, Greece, 2001 (in Greek).
[2] M. Alanelli, A. Hadjidimos, Block Gauss elimination followed by a classical iterative method for the solution of linear systems, Preprint no. 02-1/2002, Department of Mathematics, University of Crete, GR-714 09 Heraklion, Greece, 2002.; M. Alanelli, A. Hadjidimos, Block Gauss elimination followed by a classical iterative method for the solution of linear systems, Preprint no. 02-1/2002, Department of Mathematics, University of Crete, GR-714 09 Heraklion, Greece, 2002. · Zbl 1041.65032
[3] Berman, A.; Plemmons, R. J., Nonnegative Matrices in the Mathematical Sciences, Classics in Applied Mathematics (1994), SIAM: SIAM Philadelphia · Zbl 0815.15016
[4] Eiermann, M.; Niethammer, W.; Ruttan, A., Optimal successive overrelaxation iterative methods for \(p\)-cyclic matrices, Numer. Math., 57, 593-606 (1990) · Zbl 0708.65032
[5] Fan, K., Note on \(M\)-matrices, Quart. J. Math. Oxford Ser., 11, 43-49 (1960) · Zbl 0104.01203
[6] Funderlic, R. E.; Plemmons, R. J., LU decomposition of \(M\)-matrices by elimination without pivoting, Linear Algebra Appl., 41, 99-110 (1981) · Zbl 0473.65011
[7] Galanis, S.; Hadjidimos, A., Best cyclic repartitioning for optimal overrelaxation convergence, SIAM J. Matrix Anal. Appl., 13, 1, 102-120 (1992) · Zbl 0745.65022
[8] Gunawardena, A. D.; Jain, S. K.; Snyder, L., Modified iterative methods for consistent linear systems, Linear Algebra Appl., 154-156, 123-143 (1991) · Zbl 0731.65016
[9] Hadjidimos, A., On the optimization of the classical iterative schemes for the solution of complex singular linear systems, SIAM J. Algebraic Discrete Methods, 6, 555-566 (1985) · Zbl 0582.65017
[10] Hadjidimos, A.; Noutsos, D.; Tzoumas, M., More on modifications and improvements of classical iterative schemes for \(Z\)-matrices, Linear Algebra Appl., 364, 253-279 (2003) · Zbl 1023.65022
[11] Hadjidimos, A.; Plemmons, R. J., Optimal \(p\)-cyclic SOR, Numer. Math., 67, 475-490 (1994) · Zbl 0803.65032
[12] Juncosa, M. L.; Mulliken, T. W., On the increase of convergence rates of relaxation procedures for elliptic partial differential equations, J. Assoc. Comput. Mach., 7, 29-36 (1960) · Zbl 0098.31502
[13] Kohno, T.; Kotakemori, H.; Niki, H.; Usui, M., Improving the Gauss-Seidel method for \(Z\)-matrices, Linear Algebra Appl., 267, 113-123 (1997) · Zbl 0886.65030
[14] Li, W.; Sun, W., Modified Gauss-Seidel type methods and Jacobi type methods for \(Z\)-matrices, Linear Algebra Appl., 317, 227-240 (2000) · Zbl 0966.65032
[15] Marek, I.; Szyld, D. B., Comparison theorems for weak splittings of bounded operators, Numer. Math., 58, 387-397 (1990) · Zbl 0694.65023
[16] Marek, I.; Szyld, D. B., Comparison theorems for the convergence factor for iterative methods for singular matrices, Linear Algebra Appl., 316, 67-88 (2000) · Zbl 0963.65036
[17] Marek, I.; Szyld, D. B., Comparison of convergence of general stationary iterative methods for singular matrices, SIAM J. Matrix Anal. Appl., 24, 68-77 (2002) · Zbl 1018.65041
[18] Markham, T. L.; Neumann, M.; Plemmons, R. J., Convergence of a direct-iterative method for large-scale least squares problem, Linear Algebra Appl., 69, 155-167 (1985) · Zbl 0576.65026
[19] Milaszewicz, J. P., A generalization of the Stein-Rosenberg theorem to banach spaces, Numer. Math., 34, 403-409 (1980) · Zbl 0426.47019
[20] Milaszewicz, J. P., On modified Jacobi linear operators, Linear Algebra Appl., 51, 127-136 (1983) · Zbl 0506.65014
[21] Milaszewicz, J. P., Improving Jacobi and Gauss-Seidel iterations, Linear Algebra Appl., 93, 161-170 (1987) · Zbl 0628.65022
[22] Neumann, M.; Plemmons, R. J., Convergent nonnegative matrices and iterative methods for consistent linear systems, Numer. Math., 31, 265-279 (1978) · Zbl 0372.65014
[23] D.J. Pierce, Parallel least squares computations and related material, Ph.D. Thesis, North Carolina State University, Raleigh, NC, 1987.; D.J. Pierce, Parallel least squares computations and related material, Ph.D. Thesis, North Carolina State University, Raleigh, NC, 1987.
[24] Pierce, D. J.; Hadjidimos, A.; Plemmons, R. J., Optimality relationships for p-cyclic SOR, Numer. Math., 56, 635-643 (1990) · Zbl 0687.65034
[25] F. Robert, Algorithmes tronqués de découpe linéaire, RAIRO, Revue de l’ AFCET, 1972, pp. 45-64.; F. Robert, Algorithmes tronqués de découpe linéaire, RAIRO, Revue de l’ AFCET, 1972, pp. 45-64.
[26] Robert, F., Autour du théorème de Stein-Rosenberg, Numer. Math., 27, 133-141 (1976) · Zbl 0361.65047
[27] Schneider, H., Theorems on \(M\)-splittings of a singular \(M\)-matrix which depend on graph structure, Linear Algebra Appl., 58, 407-424 (1984) · Zbl 0561.65020
[28] Varga, R. S., Matrix Iterative Analysis (1962), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ, (Also: 2nd Edition, Revised and Expanded, Springer, Berlin, 2000) · Zbl 0133.08602
[29] Woźnicki, Z., Nonnegative splitting theory, Jpn. J. Ind. Appl. Math., 11, 289-342 (1994) · Zbl 0805.65033
[30] Young, D. M., Iterative Solution of Large Linear Systems (1971), Academic Press: Academic Press New York · Zbl 0204.48102
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.