Enlarged Krylov subspace conjugate gradient methods for reducing communication. (English) Zbl 1382.65086
Summary: In this paper we introduce a new approach for reducing communication in Krylov subspace methods that consists of enlarging the Krylov subspace by a maximum of \(t\) vectors per iteration, based on a domain decomposition of the graph of \(A\). The obtained enlarged Krylov subspace \(\mathcal K_{k,t}(A,r_0)\) is a superset of the Krylov subspace \(\mathcal{K}_k(A,r_0)\), \(\mathcal{K}_k(A,r_0) \subset \mathcal{K}_{k,t}(A,r_0)\). Thus, we search for the solution of the system \(Ax=b\) in \(\mathcal{K}_{k,t}(A,r_0)\) instead of \(\mathcal{K}_k(A,r_0)\). Moreover, we show in this paper that the enlarged Krylov projection subspace methods lead to faster convergence in terms of iterations and parallelizable algorithms with less communication, with respect to Krylov methods.
MSC:
| 65F10 | Iterative numerical methods for linear systems |
| 68W10 | Parallel algorithms in computer science |
References:
| [1] | A. Bhaya, P. Bliman, G. Niedu, and F. A. Pazos, {\it A cooperative conjugate gradient method for linear systems permitting multithread implementation of low complexity}, in Proceedings of the 51th IEEE Conference on Decision and Control, CDC 2012, Maui, HI, IEEE, Piscataway, 2012, pp. 638-643. · Zbl 06912483 |
| [2] | R. Bridson and C. Greif, {\it A multipreconditioned conjugate gradient algorithm}, SIAM J. Matrix Anal. Appl., 27 (2006), pp. 1056-1068. · Zbl 1104.65027 |
| [3] | A. Chapman and Y. Saad, {\it Deflated and augmented Krylov subspace techniques}, Numer. Linear Algebra Appl., 4 (1997), pp. 43-66. · Zbl 0889.65028 |
| [4] | A. T. Chronopoulos and W. Gear, {\it s-step iterative methods for symmetric linear systems}, J. Comput. Appl. Math., 25 (1989), pp. 153-168. · Zbl 0669.65021 |
| [5] | J. Demmel, L. Grigori, M. Hoemmen, and J. Langou, {\it Communication-optimal parallel and sequential QR and LU factorizations}, SIAM J. Sci. Comput., 34 (2012), pp. A206-A239. · Zbl 1241.65028 |
| [6] | J. Demmel, M. Heath, and H. van der Vorst, {\it Parallel numerical linear algebra}, Acta Numer., 2 (1993), pp. 111-197. · Zbl 0793.65011 |
| [7] | J. Erhel, {\it A parallel GMRES version for general sparse matrices}, Electron. Trans. Numer. Anal., 3 (1995), pp. 160-176. · Zbl 0860.65021 |
| [8] | R. Fletcher, {\it Conjugate gradient methods for indefinite systems}, in Numerical Analysis, G.A. Watson, ed., Lecture Notes in Math. 506, Springer, Berlin, 1976, pp. 73-89. · Zbl 0326.65033 |
| [9] | P. Ghysels, T. J. Ashby, K. Meerbergen, and W. Vanroose, {\it Hiding global communication latency in the GMRES algorithm on massively parallel machines}, SIAM J. Sci. Comput., 35 (2013), pp. C48-C71. · Zbl 1273.65050 |
| [10] | G. H. Golub and D. P. O’Leary, {\it Some history of the conjugate gradient and Lanczos algorithms:} 1948-1976, SIAM Rev., 31 (1989), pp. 50-102. · Zbl 0673.65017 |
| [11] | P. Gosselet, D. Rixen, F. Roux, and N. Spillane, {\it Simultaneous-FETI and Related Block Strategies: Robust Domain Decomposition Methods for Engineering Problems}, preprint, hal-01056928V1, 2014. |
| [12] | L. Grigori and S. Moufawad, {\it Communication Avoiding ILU0 Preconditioner}, SIAM J. Sci. Comput., 37 (2015), pp. C217-C246. · Zbl 1328.65076 |
| [13] | L. Grigori, S. Moufawad, and F. Nataf, {\it Enlarged Krylov Subspace Conjugate Gradient Methods for Reducing Communication}, preprint, hal-01065985, 2014. · Zbl 1382.65086 |
| [14] | L. Grigori, F. Nataf, and S. Yousef, {\it Robust Algebraic Schur Complement Preconditioners Based on Low Rank Corrections}, preprint, hal-01017448, 2014. |
| [15] | W. Gropp, {\it Update on Libraries for Blue Waters}, http://jointlab-pc.ncsa.illinois.edu/events/workshop3/pdf/presentations/Gropp-Update-on-Libraries.pdf. |
| [16] | T. Gu, X. Liu, Z. Mo, and X. Chi, {\it Multiple search direction conjugate gradient method I: Methods and their propositions}. Int. J. Comput. Math., 81 (2004), pp. 1133-1143. · Zbl 1059.65027 |
| [17] | F. Hecht, {\it New development in freefem++}, J. Numer. Math., 20 (2012), pp. 251-265. · Zbl 1266.68090 |
| [18] | M. R. Hestenes and E. Stiefel, {\it Methods of conjugate gradients for solving linear systems}, J. Res. Natl. Bur. Stand., 49 (1952), pp. 409-436. · Zbl 0048.09901 |
| [19] | M. Hoemmen, {\it Communication-Avoiding Krylov Subspace Methods}, Ph.D. thesis, EECS Department, University of California, Berkeley, CA, 2010. |
| [20] | G. Karypis and V. Kumar, {\it Metis 4.0: Unstructured Graph Partitioning and Sparse Matrix Ordering System}, Technical report, Department of Computer Science, University of Minnesota, Minneapolis, MN, 1998. |
| [21] | C. Lanczos, {\it Solution of systems of linear equations by minimized iterations}, J. Res. Natl. Bur. Stand, 49 (1952), pp. 33-53. |
| [22] | B. Lowery and J. Langou, {\it Stability Analysis of QR factorization in an Oblique Inner Product}. preprint, ArXiv:1401-5171, 2014. |
| [23] | M. Mohiyuddin, M. Hoemmen, J. Demmel, and K. Yelick, {\it Minimizing communication in sparse matrix solvers}, in Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis, SC 09, ACM, New York, 2009, pp. 1-12. |
| [24] | S. Moufawad, {\it Enlarged Krylov Subspace Methods and Preconditioners for Reducing Communication}, Ph.D. thesis, Université Pierre et Marie Curie, Paris, 2014. |
| [25] | D. P. O’Leary, {\it The block conjugate gradient algorithm and related methods}, Linear Algebra Appl., 29 (1980), pp. 293-322. · Zbl 0426.65011 |
| [26] | D. J. Rixen, {\it Substructuring and Dual Methods in Structural Analysis}, Ph.D. thesis, Université de Liège, Liège, Belgium, 1997. |
| [27] | M. Rozloznik, M. Tuma, A. Smoktunowicz, and J. Kopal, {\it Numerical stability of orthogonalization with a non-standard inner product}, BIT, 52 (2012), pp. 1035-1058. · Zbl 1259.65069 |
| [28] | Y. Saad, {\it Analysis of augmented Krylov subspace methods}, SIAM J. Matrix Anal. Appl., 18 (1997), pp. 435-449. · Zbl 0871.65026 |
| [29] | Y. Saad and M. H. Schultz, {\it GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems}, SIAM J. Sci. Stat. Comput., 7 (1986), pp. 856-869. · Zbl 0599.65018 |
| [30] | R. Thakur and W. Gropp, {\it Improving the performance of Collective Operations in MPICH}, in Proceedings of the 10th European PVM/MPI Users, 2003, Springer, New York, pp. 257-267. |
| [31] | H. A. Van der Vorst, {\it Bi-CGSTAB: A fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems}, SIAM J. Sci. Stat. Comput., 13 (1992), pp. 631-644. · Zbl 0761.65023 |
| [32] | J. Van Rosendale, {\it Minimizing inner product data dependencies in conjugate gradient iteration}, Techical report 172178, ICASE-NASA, 1983. |
| [33] | H. F. Walker, {\it Implementation of the GMRES method using Householder transformations}, SIAM J. Sci. Stat. Comput., 9 (1998), pp. 152-163. · Zbl 0698.65021 |
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.
