| 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:
|
2022-05-02 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/148106 |
| . |
| 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 http://www.sandia.gov/ {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 https://www.osti.gov/biblio/ 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 |
| . |
