Formulation of a Preconditioned Algorithm for the Conjugate Gradient Squared Method in Accordance with Its Logical Structure

Shoji Itoh¹, Masaaki Sugihara²

¹Division of Science, School of Science and Engineering, Tokyo Denki University, Saitama, Japan.
²Department of Physics and Mathematics, College of Science and Engineering, Aoyama Gakuin University, Kanagawa, Japan.

DOI: 10.4236/am.2015.68131                

Abstract

In this paper, we propose an improved preconditioned algorithm for the conjugate gradient squared method (improved PCGS) for the solution of linear equations. Further, the logical structures underlying the formation of this preconditioned algorithm are demonstrated via a number of theorems. This improved PCGS algorithm retains some mathematical properties that are associated with the CGS derivation from the bi-conjugate gradient method under a non-preconditioned system. A series of numerical comparisons with the conventional PCGS illustrate the enhanced effectiveness of our improved scheme with a variety of preconditioners. This logical structure underlying the formation of the improved PCGS brings a spillover effect from various bi-Lanczos-type algorithms with minimal residual operations, because these algorithms were constructed by adopting the idea behind the derivation of CGS. These bi-Lanczos-type algorithms are very important because they are often adopted to solve the systems of linear equations that arise from large-scale numerical simulations.

Keywords

Linear Systems, Krylov Subspace Method, Bi-Lanczos Algorithm, Preconditioned System, PCGS

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Sonneveld, P. (1989) CGS, A Fast Lanczos-Type Solver for Nonsymmetric Linear Systems. SIAM Journal on Scienti fic and Statistical Computing, 10, 36-52. http://dx.doi.org/10.1137/0910004
[2]	Fletcher, R. (1976) Conjugate Gradient Methods for Indefinite Systems. In: Watson, G., Ed., Numerical Analysis Dundee 1975, Lecture Notes in Mathematics, Vol. 506, Springer-Verlag, Berlin, New York, 73-89.
[3]	Lanczos, C. (1952) Solution of Systems of Linear Equations by Minimized Iterations. Journal of Research of the National Bureau of Standards, 49, 33-53. http://dx.doi.org/10.6028/jres.049.006
[4]	Van der Vorst, H.A. (1992) Bi-CGSTAB: A Fast and Smoothly Converging Variant of Bi-CG for the Solution of Nonsymmetric Linear Systems. SIAM Journal on Scientific and Statistical Computing, 13, 631-644. http://dx.doi.org/10.1137/0913035
[5]	Zhang, S.-L. (1997) GPBi-CG: Generalized Product-Type Methods Based on Bi-CG for Solving Nonsymmetric Linear Systems. SIAM Journal on Scientific Computing, 18, 537-551. http://dx.doi.org/10.1137/s1064827592236313
[6]	Itoh, S. and Sugihara, M. (2010) Systematic Performance Evaluation of Linear Solvers Using Quality Control Techniques. In: Naono, K., Teranishi, K., Cavazos, J. and Suda, R., Eds., Software Automatic Tuning: From Concepts to State-of-the-Art Results, Springer, 135-152.
[7]	Itoh, S. and Sugihara, M. (2013) Preconditioned Algorithm of the CGS Method Focusing on Its Deriving Process. Transactions of the Japan SIAM, 23, 253-286. (in Japanese)
[8]	Hestenes, M.R. and Stiefel, E. (1952) Methods of Conjugate Gradients for Solving Linear Systems. Journal of Research of the National Bureau of Standards, 49, 409-435. http://dx.doi.org/10.6028/jres.049.044
[9]	Barrett, R., Berry, M., Chan, T.F., Demmel, J., Donato, J., Dongarra, J., et al. (1994) Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. SIAM. http://dx.doi.org/10.1137/1.9781611971538
[10]	Van der Vorst, H.A. (2003) Iterative Krylov Methods for Large Linear Systems. Cambridge University Press, Cambridge. http://dx.doi.org/10.1017/CBO9780511615115
[11]	Meurant, G. (2005) Computer Solution of Large Linear Systems. Elsevier, Amsterdam.
[12]	Davis, T.A. The University of Florida Sparse Matrix Collection. http://www.cise.ufl.edu/research/sparse/matrices/
[13]	Matrix Market Project. http://math.nist.gov/MatrixMarket/
[14]	SSI Project, Lis. http://www.ssisc.org/lis/