Previous |  Up |  Next


Title: An adaptive $s$-step conjugate gradient algorithm with dynamic basis updating (English)
Author: Carson, Erin Claire
Language: English
Journal: Applications of Mathematics
ISSN: 0862-7940 (print)
ISSN: 1572-9109 (online)
Volume: 65
Issue: 2
Year: 2020
Pages: 123-151
Summary lang: English
Category: math
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ý (2018). 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. (English)
Keyword: conjugate gradient
Keyword: iterative method
Keyword: high-performance computing
MSC: 65F10
MSC: 65F50
MSC: 65Y05
MSC: 65Y20
idZBL: 07217102
idMR: MR4083461
DOI: 10.21136/AM.2020.0136-19
Date available: 2020-05-20T15:44:34Z
Last updated: 2020-08-14
Stable URL:
Reference: [1] Bai, Z., Hu, D., Reichel, L.: A Newton basis GMRES implementation.IMA J. Numer. Anal. 14 (1994), 563-581. Zbl 0818.65022, MR 1298533, 10.1093/imanum/14.4.563
Reference: [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).
Reference: [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. Zbl 1075.65041, MR 2137478, 10.1137/S0895479801384743
Reference: [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. Zbl 0796.65033, MR 1258973, 10.1007/s002110050016
Reference: [5] Calvetti, D., Reichel, L.: On the evaluation of polynomial coefficients.Numer. Algorithms 33 (2003), 153-161. Zbl 1035.65156, MR 2005559, 10.1023/A:1025555803588
Reference: [6] Carson, E. C.: Communication-Avoiding Krylov Subspace Methods in Theory and Practice.Ph.D. Thesis, University of California, Berkeley (2015). MR 3450264
Reference: [7] Carson, E. C.: The adaptive $s$-step conjugate gradient method.SIAM J. Matrix Anal. Appl. 39 (2018), 1318-1338. Zbl 1398.65044, MR 3846291, 10.1137/16M1107942
Reference: [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. Zbl 1302.65075, MR 3152736, 10.1137/120893057
Reference: [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. Zbl 1319.65024, MR 3357631, 10.1137/140990735
Reference: [10] Chronopoulos, A. T., Gear, C. W.: $s$-step iterative methods for symmetric linear systems.J. Comput. Appl. Math. 25 (1989), 153-168. Zbl 0669.65021, MR 0988055, 10.1016/0377-0427(89)90045-9
Reference: [11] Davis, T. A., Hu, Y.: The University of Florida sparse matrix collection.ACM Trans. Math. Softw. 38 (2011), Article No. 1, 25 pages. Zbl 1365.65123, MR 2865011, 10.1145/2049662.2049663
Reference: [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. MR 1204659
Reference: [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. Zbl 0842.65019, 10.1016/0168-9274(95)00079-A
Reference: [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. 10.1109/IPDPS.2008.4536305
Reference: [15] Dongarra, J., Beckman, P., Moore, T.: The international exascale software project roadmap.Int. J. High Perf. Comput. Appl. 25 (2011), 3-60. 10.1177/1094342010391989
Reference: [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. MR 3823058, 10.1177/1094342015593158
Reference: [17] Erhel, J.: A parallel GMRES version for general sparse matrices.ETNA, Electron. Trans. Numer. Anal. 3 (1995), 160-176. Zbl 0860.65021, MR 1368335
Reference: [18] Gautschi, W.: The condition of polynomials in power form.Math. Comput. 33 (1979), 343-352. Zbl 0399.41002, MR 0514830, 10.2307/2006047
Reference: [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. Zbl 1273.65050, MR 3033078, 10.1137/12086563X
Reference: [20] Ghysels, P., Vanroose, W.: Hiding global synchronization latency in the preconditioned conjugate gradient algorithm.Parallel Comput. 40 (2014), 224-238. MR 3225342, 10.1016/j.parco.2013.06.001
Reference: [21] Greenbaum, A.: Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences.Linear Algebra Appl. 113 (1989), 7-63. Zbl 0662.65032, MR 0978581, 10.1016/0024-3795(89)90285-1
Reference: [22] Greenbaum, A.: Estimating the attainable accuracy of recursively computed residual methods.SIAM J. Matrix Anal. Appl. 18 (1997), 535-551. Zbl 0873.65027, MR 1453539, 10.1137/S0895479895284944
Reference: [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. Zbl 0976.65030, MR 1779725, 10.1137/S0895479897331862
Reference: [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 {tgkolda/pubs/pubfiles/SAND2003-2927.pdf}.
Reference: [25] Hestenes, M. R., Stiefel, E.: Methods of conjugate gradients for solving linear systems.J. Res. Natl. Bur. Stand. 49 (1952), 409-436. Zbl 0048.09901, MR 0060307, 10.6028/jres.049.044
Reference: [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 7008035-note-householder-implementation-gmres-method. MR 0069574
Reference: [27] Hoemmen, M.: Communication-avoiding Krylov subspace methods.Ph.D. Thesis, University of California, Berkeley (2010). MR 2941535
Reference: [28] Imberti, D., Erhel, J.: Varying the $s$ in your $s$-step GMRES.ETNA, Electron. Trans. Numer. Anal. 47 (2017), 206-230. Zbl 1386.65108, MR 3747143, 10.1553/etna_vol47s206
Reference: [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. Zbl 0759.65008, 10.1080/00207169208804107
Reference: [30] Liesen, J., Strakoš, Z.: Krylov Subspace Methods. Principles and Analysis.Numerical Mathematics and Scientific Computation, Oxford University Press, Oxford (2013). Zbl 1263.65034, MR 3024841
Reference: [31] Manteuffel, T. A.: Adaptive procedure for estimating parameters for the nonsymmetric Tchebychev iteration.Numer. Math. 31 (1978), 183-208. Zbl 0413.65032, MR 0509674, 10.1007/BF01397475
Reference: [32] Meurant, G., Strakoš, Z.: The Lanczos and conjugate gradient algorithms in finite precision arithmetic.Acta Numerica 15 (2006), 471-542. Zbl 1113.65032, MR 2269746, 10.1017/S096249290626001X
Reference: [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. Zbl 07128072, MR 4027652, 10.1007/s11075-018-0634-8
Reference: [34] Philippe, B., Reichel, L.: On the generation of Krylov subspace bases.Appl. Numer. Math. 62 (2012), 1171-1186. Zbl 1253.65049, MR 2934761, 10.1016/j.apnum.2010.12.009
Reference: [35] Reichel, L.: Newton interpolation at Leja points.BIT 30 (1990), 332-346. Zbl 0702.65012, MR 1039671, 10.1007/BF02017352
Reference: [36] Saad, Y.: Iterative Methods for Sparse Linear Systems.SIAM Society for Industrial and Applied Mathematics, Philadelphia (2003). Zbl 1031.65046, MR 1990645, 10.1137/1.9780898718003
Reference: [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. Zbl 1048.65032, MR 2058070, 10.1137/S1064827502406415
Reference: [38] Sleijpen, G. L. G., Vorst, H. A. Van Der: Reliable updated residuals in hybrid Bi-CG methods.Computing 56 (1996), 141-163. Zbl 0842.65018, MR 1382009, 10.1007/BF02309342
Reference: [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. Zbl 0983.65039, MR 1785337, 10.1137/S1064827599353865
Reference: [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.
Reference: [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. 10.1109/ipdps.2014.119

Fulltext not available (moving wall 24 months)

Partner of
EuDML logo