×

zbMATH — the first resource for mathematics

An adaptive \(s\)-step conjugate gradient algorithm with dynamic basis updating. (English) Zbl 07217102
Summary: The adaptive \(s\)-step CG algorithm is a solver for sparse symmetric positive definite linear systems designed to reduce the synchronization cost per iteration while still achieving a user-specified accuracy requirement. In this work, we improve the adaptive \(s\)-step conjugate gradient algorithm by the use of iteratively updated estimates of the largest and smallest Ritz values, which give approximations of the largest and smallest eigenvalues of \(A\), using a technique due to G. Meurant and P. Tichý [Numer. Algorithms 82, No. 3, 937–968 (2019; Zbl 1436.65033)]. The Ritz value estimates are used to dynamically update parameters for constructing Newton or Chebyshev polynomials so that the conditioning of the \(s\)-step bases can be continuously improved throughout the iterations. These estimates are also used to automatically set a variable related to the ratio of the sizes of the error and residual, which was previously treated as an input parameter. We show through numerical experiments that in many cases the new algorithm improves upon the previous adaptive \(s\)-step approach both in terms of numerical behavior and reduction in number of synchronizations.
MSC:
65F10 Iterative numerical methods for linear systems
65F50 Computational methods for sparse matrices
65Y05 Parallel numerical computation
65Y20 Complexity and performance of numerical algorithms
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bai, Z.; Hu, D.; Reichel, L., A Newton basis GMRES implementation, IMA J. Numer. Anal. 14 (1994), 563-581
[2] Bouras, A.; Frayssé, V., A Relaxation Strategy for Inexact Matrix-Vector Products for Krylov Methods, CERFACS Technical Report TR/PA/00/15, CERFACS, Toulouse (2000)
[3] Bouras, A.; Frayssé, V., Inexact matrix-vector products in Krylov methods for solving linear systems: A relaxation strategy, SIAM J. Matrix Anal. Appl. 26 (2005), 660-678
[4] Calvetti, D.; Golub, G. H.; Reichel, L., An adaptive Chebyshev iterative method for nonsymmetric linear systems based on modified moments, Numer. Math. 67 (1994), 21-40
[5] Calvetti, D.; Reichel, L., On the evaluation of polynomial coefficients, Numer. Algorithms 33 (2003), 153-161
[6] Carson, E. C., Communication-Avoiding Krylov Subspace Methods in Theory and Practice, Ph.D. Thesis, University of California, Berkeley (2015)
[7] Carson, E. C., The adaptive \(s\)-step conjugate gradient method, SIAM J. Matrix Anal. Appl. 39 (2018), 1318-1338
[8] Carson, E.; Demmel, J., A residual replacement strategy for improving the maximum attainable accuracy of \(s\)-step Krylov subspace methods, SIAM J. Matrix Anal. Appl. 35 (2014), 22-43
[9] Carson, E.; Demmel, J. W., Accuracy of the \(s\)-step Lanczos method for the symmetric eigenproblem in finite precision, SIAM J. Matrix Anal. Appl. 36 (2015), 793-819
[10] Chronopoulos, A. T.; Gear, C. W., \(s\)-step iterative methods for symmetric linear systems, J. Comput. Appl. Math. 25 (1989), 153-168
[11] Davis, T. A.; Hu, Y., The University of Florida sparse matrix collection, ACM Trans. Math. Softw. 38 (2011), Article No. 1, 25 pages
[12] Sturler, E. de, A parallel variant of GMRES \((m)\), IMACS’91: Proceedings of the 13th IMACS World Congress on Computation and Applied Mathematics Criterion Press, Dublin (1991), 602-683
[13] Sturler, E. de; Vorst, H. A. van der, Reducing the effect of global communication in GMRES \((m)\) and CG on parallel distributed memory computers, Appl. Numer. Math. 18 (1995), 441-459
[14] Demmel, J.; Hoemmen, M.; Mohiyuddin, M.; Yelick, K., Avoiding communication in sparse matrix computations, IEEE International Symposium on Parallel and Distributed Processing IEEE, Miami (2008), 1-12
[15] Dongarra, J.; Beckman, P.; Moore, T., The international exascale software project roadmap, Int. J. High Perf. Comput. Appl. 25 (2011), 3-60
[16] Dongarra, J.; Heroux, M. A.; Luszczek, P., High-performance conjugate-gradient benchmark: A new metric for ranking high-performance computing systems, Int. J. High Perf. Comput. Appl. 30 (2016), 3-10
[17] Erhel, J., A parallel GMRES version for general sparse matrices, ETNA, Electron. Trans. Numer. Anal. 3 (1995), 160-176
[18] Gautschi, W., The condition of polynomials in power form, Math. Comput. 33 (1979), 343-352
[19] Ghysels, P.; Ashby, T. J.; Meerbergen, K.; Vanroose, W., Hiding global communication latency in the GMRES algorithm on massively parallel machines, SIAM J. Sci. Comput. 35 (2013), C48-C71
[20] Ghysels, P.; Vanroose, W., Hiding global synchronization latency in the preconditioned conjugate gradient algorithm, Parallel Comput. 40 (2014), 224-238
[21] Greenbaum, A., Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences, Linear Algebra Appl. 113 (1989), 7-63
[22] Greenbaum, A., Estimating the attainable accuracy of recursively computed residual methods, SIAM J. Matrix Anal. Appl. 18 (1997), 535-551
[23] Gutknecht, M. H.; Strakoš, Z., Accuracy of two three-term and three two-term recurrences for Krylov space solvers, SIAM J. Matrix Anal. Appl. 22 (2000), 213-229
[24] M. Heroux, R. Bartlett, V. H. R. Hoekstra, J. Hu, T. Kolda, R. Lehoucq, K. Long; R. Pawlowski; E. Phipps; A. Salinger; H. Thornquist; R. Tuminaro; J. Willenbring; A. Williams, An Overview of Trilinos, Technical Report SAND2003-2927, Sandia National Laboratories, Albuquerque (2003), 1-42 Available at http://www.sandia.gov/ tgkolda/pubs/pubfiles/SAND2003-2927.pdf
[25] Hestenes, M. R.; Stiefel, E., Methods of conjugate gradients for solving linear systems, J. Res. Natl. Bur. Stand. 49 (1952), 409-436
[26] Hindmarsh, A. C.; Walker, H., Note on a Householder Implementation of the GMRES Method, Technical Report UCID-20899, Lawrence Livermore National Laboratory, Logan (1986), Available at https://www.osti.gov/biblio/ 7008035-note-householder-implementation-gmres-method
[27] Hoemmen, M., Communication-avoiding Krylov subspace methods, Ph.D. Thesis, University of California, Berkeley (2010)
[28] Imberti, D.; Erhel, J., Varying the \(s\) in your \(s\)-step GMRES, ETNA, Electron. Trans. Numer. Anal. 47 (2017), 206-230
[29] Joubert, W. D.; Carey, G. F., Parallelizable restarted iterative methods for nonsymmetric linear systems. I: Theory, Int. J. Comput. Math. 44 (1992), 243-267
[30] Liesen, J.; Strakoš, Z., Krylov Subspace Methods. Principles and Analysis, Numerical Mathematics and Scientific Computation, Oxford University Press, Oxford (2013)
[31] Manteuffel, T. A., Adaptive procedure for estimating parameters for the nonsymmetric Tchebychev iteration, Numer. Math. 31 (1978), 183-208
[32] Meurant, G.; Strakoš, Z., The Lanczos and conjugate gradient algorithms in finite precision arithmetic, Acta Numerica 15 (2006), 471-542
[33] Meurant, G.; Tichý, P., Approximating the extreme Ritz values and upper bounds for the \(A\)-norm of the error in CG, Numer. Algorithms 82 (2019), 937-968
[34] Philippe, B.; Reichel, L., On the generation of Krylov subspace bases, Appl. Numer. Math. 62 (2012), 1171-1186
[35] Reichel, L., Newton interpolation at Leja points, BIT 30 (1990), 332-346
[36] Saad, Y., Iterative Methods for Sparse Linear Systems, SIAM Society for Industrial and Applied Mathematics, Philadelphia (2003)
[37] Simoncini, V.; Szyld, D. B., Theory of inexact Krylov subspace methods and applications to scientific computing, SIAM J. Sci. Comput. 25 (2003), 454-477
[38] Sleijpen, G. L. G.; Vorst, H. A. Van Der, Reliable updated residuals in hybrid Bi-CG methods, Computing 56 (1996), 141-163
[39] Vorst, H. A. Van Der; Ye, Q., Residual replacement strategies for Krylov subspace iterative methods for the convergence of true residuals, SIAM J. Sci. Comput. 22 (2000), 835-852
[40] Rosendale, J. Van, Minimizing inner product data dependencies in conjugate gradient iteration, International Conference on Parallel Processing, ICPP’83 IEEE Computer Society, Los Alamitos (1983), 44-46
[41] Williams, S.; Lijewski, M.; Almgren, A.; Straalen, B. Van; Carson, E.; Knight, N.; Demmel, J., \(s\)-step Krylov subspace methods as bottom solvers for geometric multigrid, 28th IEEE International Parallel and Distributed Processing Symposium IEEE Computer Society, Los Alamitos (2014), 1149-1158
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.