An adaptive s -step conjugate gradient algorithm with dynamic basis updating

Erin Claire Carson

Applications of Mathematics (2020)

  • Volume: 65, Issue: 2, page 123-151
  • ISSN: 0862-7940

Abstract

top
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.

How to cite

top

Carson, Erin Claire. "An adaptive $s$-step conjugate gradient algorithm with dynamic basis updating." Applications of Mathematics 65.2 (2020): 123-151. <http://eudml.org/doc/297391>.

@article{Carson2020,
abstract = {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.},
author = {Carson, Erin Claire},
journal = {Applications of Mathematics},
keywords = {conjugate gradient; iterative method; high-performance computing},
language = {eng},
number = {2},
pages = {123-151},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {An adaptive $s$-step conjugate gradient algorithm with dynamic basis updating},
url = {http://eudml.org/doc/297391},
volume = {65},
year = {2020},
}

TY - JOUR
AU - Carson, Erin Claire
TI - An adaptive $s$-step conjugate gradient algorithm with dynamic basis updating
JO - Applications of Mathematics
PY - 2020
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 65
IS - 2
SP - 123
EP - 151
AB - 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.
LA - eng
KW - conjugate gradient; iterative method; high-performance computing
UR - http://eudml.org/doc/297391
ER -

References

top
  1. Bai, Z., Hu, D., Reichel, L., 10.1093/imanum/14.4.563, IMA J. Numer. Anal. 14 (1994), 563-581. (1994) Zbl0818.65022MR1298533DOI10.1093/imanum/14.4.563
  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). (2000) 
  3. Bouras, A., Frayssé, V., 10.1137/S0895479801384743, SIAM J. Matrix Anal. Appl. 26 (2005), 660-678. (2005) Zbl1075.65041MR2137478DOI10.1137/S0895479801384743
  4. Calvetti, D., Golub, G. H., Reichel, L., 10.1007/s002110050016, Numer. Math. 67 (1994), 21-40. (1994) Zbl0796.65033MR1258973DOI10.1007/s002110050016
  5. Calvetti, D., Reichel, L., 10.1023/A:1025555803588, Numer. Algorithms 33 (2003), 153-161. (2003) Zbl1035.65156MR2005559DOI10.1023/A:1025555803588
  6. Carson, E. C., Communication-Avoiding Krylov Subspace Methods in Theory and Practice, Ph.D. Thesis, University of California, Berkeley (2015). (2015) MR3450264
  7. Carson, E. C., 10.1137/16M1107942, SIAM J. Matrix Anal. Appl. 39 (2018), 1318-1338. (2018) Zbl1398.65044MR3846291DOI10.1137/16M1107942
  8. Carson, E., Demmel, J., 10.1137/120893057, SIAM J. Matrix Anal. Appl. 35 (2014), 22-43. (2014) Zbl1302.65075MR3152736DOI10.1137/120893057
  9. Carson, E., Demmel, J. W., 10.1137/140990735, SIAM J. Matrix Anal. Appl. 36 (2015), 793-819. (2015) Zbl1319.65024MR3357631DOI10.1137/140990735
  10. Chronopoulos, A. T., Gear, C. W., 10.1016/0377-0427(89)90045-9, J. Comput. Appl. Math. 25 (1989), 153-168. (1989) Zbl0669.65021MR0988055DOI10.1016/0377-0427(89)90045-9
  11. Davis, T. A., Hu, Y., 10.1145/2049662.2049663, ACM Trans. Math. Softw. 38 (2011), Article No. 1, 25 pages. (2011) Zbl1365.65123MR2865011DOI10.1145/2049662.2049663
  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. (1991) MR1204659
  13. Sturler, E. de, Vorst, H. A. van der, 10.1016/0168-9274(95)00079-A, Appl. Numer. Math. 18 (1995), 441-459. (1995) Zbl0842.65019DOI10.1016/0168-9274(95)00079-A
  14. Demmel, J., Hoemmen, M., Mohiyuddin, M., Yelick, K., 10.1109/IPDPS.2008.4536305, IEEE International Symposium on Parallel and Distributed Processing IEEE, Miami (2008), 1-12. (2008) DOI10.1109/IPDPS.2008.4536305
  15. Dongarra, J., Beckman, P., Moore, T., 10.1177/1094342010391989, Int. J. High Perf. Comput. Appl. 25 (2011), 3-60. (2011) DOI10.1177/1094342010391989
  16. Dongarra, J., Heroux, M. A., Luszczek, P., 10.1177/1094342015593158, Int. J. High Perf. Comput. Appl. 30 (2016), 3-10. (2016) MR3823058DOI10.1177/1094342015593158
  17. Erhel, J., A parallel GMRES version for general sparse matrices, ETNA, Electron. Trans. Numer. Anal. 3 (1995), 160-176. (1995) Zbl0860.65021MR1368335
  18. Gautschi, W., 10.2307/2006047, Math. Comput. 33 (1979), 343-352. (1979) Zbl0399.41002MR0514830DOI10.2307/2006047
  19. Ghysels, P., Ashby, T. J., Meerbergen, K., Vanroose, W., 10.1137/12086563X, SIAM J. Sci. Comput. 35 (2013), C48--C71. (2013) Zbl1273.65050MR3033078DOI10.1137/12086563X
  20. Ghysels, P., Vanroose, W., 10.1016/j.parco.2013.06.001, Parallel Comput. 40 (2014), 224-238. (2014) MR3225342DOI10.1016/j.parco.2013.06.001
  21. Greenbaum, A., 10.1016/0024-3795(89)90285-1, Linear Algebra Appl. 113 (1989), 7-63. (1989) Zbl0662.65032MR0978581DOI10.1016/0024-3795(89)90285-1
  22. Greenbaum, A., 10.1137/S0895479895284944, SIAM J. Matrix Anal. Appl. 18 (1997), 535-551. (1997) Zbl0873.65027MR1453539DOI10.1137/S0895479895284944
  23. Gutknecht, M. H., Strakoš, Z., 10.1137/S0895479897331862, SIAM J. Matrix Anal. Appl. 22 (2000), 213-229. (2000) Zbl0976.65030MR1779725DOI10.1137/S0895479897331862
  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}. (2003) 
  25. Hestenes, M. R., Stiefel, E., 10.6028/jres.049.044, J. Res. Natl. Bur. Stand. 49 (1952), 409-436. (1952) Zbl0048.09901MR0060307DOI10.6028/jres.049.044
  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. (1986) MR0069574
  27. Hoemmen, M., Communication-avoiding Krylov subspace methods, Ph.D. Thesis, University of California, Berkeley (2010). (2010) MR2941535
  28. Imberti, D., Erhel, J., 10.1553/etna_vol47s206, ETNA, Electron. Trans. Numer. Anal. 47 (2017), 206-230. (2017) Zbl1386.65108MR3747143DOI10.1553/etna_vol47s206
  29. Joubert, W. D., Carey, G. F., 10.1080/00207169208804107, Int. J. Comput. Math. 44 (1992), 243-267. (1992) Zbl0759.65008DOI10.1080/00207169208804107
  30. Liesen, J., Strakoš, Z., Krylov Subspace Methods. Principles and Analysis, Numerical Mathematics and Scientific Computation, Oxford University Press, Oxford (2013). (2013) Zbl1263.65034MR3024841
  31. Manteuffel, T. A., 10.1007/BF01397475, Numer. Math. 31 (1978), 183-208. (1978) Zbl0413.65032MR0509674DOI10.1007/BF01397475
  32. Meurant, G., Strakoš, Z., 10.1017/S096249290626001X, Acta Numerica 15 (2006), 471-542. (2006) Zbl1113.65032MR2269746DOI10.1017/S096249290626001X
  33. Meurant, G., Tichý, P., 10.1007/s11075-018-0634-8, Numer. Algorithms 82 (2019), 937-968. (2019) Zbl07128072MR4027652DOI10.1007/s11075-018-0634-8
  34. Philippe, B., Reichel, L., 10.1016/j.apnum.2010.12.009, Appl. Numer. Math. 62 (2012), 1171-1186. (2012) Zbl1253.65049MR2934761DOI10.1016/j.apnum.2010.12.009
  35. Reichel, L., 10.1007/BF02017352, BIT 30 (1990), 332-346. (1990) Zbl0702.65012MR1039671DOI10.1007/BF02017352
  36. Saad, Y., 10.1137/1.9780898718003, SIAM Society for Industrial and Applied Mathematics, Philadelphia (2003). (2003) Zbl1031.65046MR1990645DOI10.1137/1.9780898718003
  37. Simoncini, V., Szyld, D. B., 10.1137/S1064827502406415, SIAM J. Sci. Comput. 25 (2003), 454-477. (2003) Zbl1048.65032MR2058070DOI10.1137/S1064827502406415
  38. Sleijpen, G. L. G., Vorst, H. A. Van Der, 10.1007/BF02309342, Computing 56 (1996), 141-163. (1996) Zbl0842.65018MR1382009DOI10.1007/BF02309342
  39. Vorst, H. A. Van Der, Ye, Q., 10.1137/S1064827599353865, SIAM J. Sci. Comput. 22 (2000), 835-852. (2000) Zbl0983.65039MR1785337DOI10.1137/S1064827599353865
  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. (1983) 
  41. Williams, S., Lijewski, M., Almgren, A., Straalen, B. Van, Carson, E., Knight, N., Demmel, J., 10.1109/ipdps.2014.119, 28th IEEE International Parallel and Distributed Processing Symposium IEEE Computer Society, Los Alamitos (2014), 1149-1158. (2014) DOI10.1109/ipdps.2014.119

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.