On a computer implementation of the block Gauss--Seidel method

A. I. Zhdanov ; E. Yu. Bogdanova

Journal of Samara State Technical University, Ser. Physical and Mathematical Sciences, Tome 20 (2016) no. 4, pp. 730-738.

Résumé

This article focuses on the modification of the block option Gauss-Seidel method for normal systems of equations, which is a sufficiently effective method of solving generally overdetermined, systems of linear algebraic equations of high dimensionality. The main disadvantage of methods based on normal equations systems is the fact that the condition number of the normal system is equal to the square of the condition number of the original problem. This fact has a negative impact on the rate of convergence of iterative methods based on normal equations systems. To increase the speed of convergence of iterative methods based on normal equations systems, for solving ill-conditioned problems currently different preconditioners options are used that reduce the condition number of the original system of equations. However, universal preconditioner for all applications does not exist. One of the effective approaches that improve the speed of convergence of the iterative Gauss–Seidel method for normal systems of equations, is to use its version of the block. The disadvantage of the block Gauss–Seidel method for production systems is the fact that it is necessary to calculate the pseudoinverse matrix for each iteration. We know that finding the pseudoinverse is a difficult computational procedure. In this paper, we propose a procedure to replace the matrix pseudo-solutions to the problem of normal systems of equations by Cholesky. Normal equations arising at each iteration of Gauss–Seidel method, have a relatively low dimension compared to the original system. The results of numerical experimentation demonstrating the effectiveness of the proposed approach are given.

Détail

Mots-clés : normal equations
Keywords: block Gauss–Seidel method, Cholesky method, linear algebraic systems of large dimension.

Bibliographie

[1] Saad Y., “Basic Iterative Methods”, Iterative Methods for Sparse Liner Systems, SIAM, Philadelphia, PA, USA, 2003, 103–128 | DOI | MR

[2] Golub G. H., Van Loan C. F., Matrix Computations, Johns Hopkins Studies in Mathematical Sciences, Johns Hopkins University Press, Baltimore, London, 1996, xxvii+728 pp. | MR | Zbl

[3] Björck A., “Linear Least Squares Problems”, Numerical methods in matrix computations, Texts in Applied Mathematics, 59, Springer, Berlin, 2015, 211–430 | DOI

[4] Young D., Rheinboldt W., Iterative Solutions of Large Linear Systems, Academic Press, New York, 1971., 572 pp. | DOI | MR

[5] Ma A., Needell D., Ramdas A., “Convergence Properties of the Randomized Extended Gauss–Seidel and Kaczmarz Methods”, SIAM. J. Matrix Anal. Appl., 36:4 (2015), 1590–1604 | DOI | MR | Zbl

[6] Gill P. E., Murray W., Ponceleón D. B., Saunders M. A., “Preconditioners for Indefinite Systems Arising in Optimization”, SIAM. J. Matrix Anal. Appl., 13:1 (1992), 292–311 | DOI | MR | Zbl

[7] Benzi M., “Preconditioning Techniques for Large Linear Systems: A Survey”, Journal of Computational Physics, 182:2 (2002), 418–477 | DOI | MR | Zbl

[8] Benzi M., Tûma M., “A comparative study of sparse approximate inverse preconditioners”, Appl. Numer. Math., 1999, no. 30, 305–340 | DOI | MR | Zbl

[9] Bergamaschi L., Pini G., Sartoretto F., “Approximate inverse preconditioning in the parallel solution of sparse eigenproblems”, Numerical Linear Algebra with Applications, 7:3 (2000), 99–116 | 3.3.co;2-x class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[10] Benzi M., Joubert W. D., Mateescu G., “Numerical experiments with parallel orderings for ILU preconditioners”, Electronic Transactions on Numerical Analysis, 8 (1999), 88–114 | MR | Zbl

[11] Il'in V. P., “On the Kaczmarz iterative method and its generalizations”, J. Appl. Industr. Math., 2:3 (2008), 357–366 | DOI | MR | Zbl

[12] Gower R. M., Richtárik P., “Randomized Iterative Methods for Linear Systems”, SIAM. J. Matrix Anal. Appl., 36:4 (2015), 1660–1690 | DOI | MR | Zbl

[13] Strohmer T., Vershynin R., “A Randomized Kaczmarz Algorithm with Exponential Convergence”, J. Fourier Anal. Appl., 15:2 (2009), 262–278 | DOI | MR | Zbl

[14] Zhdanov A. I., Sidorov Y. V., “Parallel implementation of a randomized regularized Kaczmarz's algorithm”, Computer Optics, 39:4 (2015), 536–541 (In Russian) | DOI

[15] Horn R. A., Johnson C. R., Matrix Analysis, Cambridge University Press, Cambridge, 1989., xviii+643 pp. | DOI | MR

[16] Zhdanov A. I., Ivanov A. A., “Projection regularization algorithm for solving linear algebraic system of large dimension”, Vestn. Samar. Gos. Tekhn. Univ., Ser. Fiz.-Mat. Nauki [J. Samara State Tech. Univ., Ser. Phys. Math. Sci.], 2010, no. 21, 309–312 (In Russian) | DOI

[17] Malyshev A. N., Vvedenie v vychislitel'nuiu lineinuiu algebru [Introduction to computational linear algebra], Nauka, Novosibirsk, 1991, 229 pp. (In Russian)

[18] Gantmacher F. R., The theory of matrices, v. I and II, Chelsea, New York, 1959, x+374 pp.; ix+276 pp. | MR | MR

[19] Beklemishev D. V., Dopolnitel'nye glavy lineinoi algebry [Supplementary chapters in linear algebra], Nauka, Moscow, 1983, 336 pp. (In Russian) | MR