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