Abstract
The GMRES method is used to solve sparse, non-symmetric systems of linear equations arising from many scientific applications. The solver performance within a single node is memory bound, due to the low arithmetic intensity of its computational kernels. To reduce the amount of data movement, and thus, to improve performance, we investigated the effect of using a mix of single and double precision while retaining double-precision accuracy. Previous efforts have explored reduced precision in the preconditioner, but the use of reduced precision in the solver itself has received limited attention. We found that GMRES only needs double precision in computing the residual and updating the approximate solution to achieve double-precision accuracy, although it must restart after each improvement of single-precision accuracy. This finding holds for the tested orthogonalization schemes: Modified Gram-Schmidt (MGS) and Classical Gram-Schmidt with Re-orthogonalization (CGSR). Furthermore, our mixed-precision GMRES, when restarted at least once, performed 19% and 24% faster on average than double-precision GMRES for MGS and CGSR, respectively. Our implementation uses generic programming techniques to ease the burden of coding implementations for different data types. Our use of the Kokkos library allowed us to exploit parallelism and optimize data management. Additionally, KokkosKernels was used when producing performance results. In conclusion, using a mix of single and double precision in GMRES can improve performance while retaining double-precision accuracy.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Anzt, H., Heuveline, V., Rocker, B.: Mixed precision iterative refinement methods for linear systems: convergence analysis based on Krylov subspace methods. In: Jónasson, K. (ed.) PARA 2010. LNCS, vol. 7134, pp. 237–247. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-28145-7_24
Arnoldi, W.E.: The principle of minimized iteration in the solution of the matrix eigenvalue problem. Quart. Appl. Math. 9, 17–29 (1951). https://doi.org/10.1090/qam/42792
Baboulin, M., et al.: Accelerating scientific computations with mixed precision algorithms. CoRR abs/0808.2794 (2008). https://doi.org/10.1016/j.cpc.2008.11.005
Baker, A.H.: On improving the performance of the linear solver restarted GMRES, Ph.D. thesis. University of Colorado (2003)
Baker, A.H., Jessup, E.R., Manteuffel, T.: A technique for accelerating the convergence of restarted GMRES. SIAM J. Matrix Anal. Appl. 26(4), 962–984 (2005). https://doi.org/10.1137/S0895479803422014
Buttari, A., Dongarra, J., Langou, J., Langou, J., Luszczek, P., Kurzak, J.: Mixed precision iterative refinement techniques for the solution of dense linear systems. Int. J. High Perform. Comput. Appl. 21(4), 457–466 (2007). https://doi.org/10.1177/1094342007084026
Carson, E., Higham, N.J.: A new analysis of iterative refinement and its application to accurate solution of ill-conditioned sparse linear systems. SIAM J. Sci. Comput. 39(6), A2834–A2856 (2017). https://doi.org/10.1137/17M1122918
Davis, T.A., Hu, Y.: The University of Florida sparse matrix collection. ACM Trans. Math. Softw. 38(1), 25 (2011). https://doi.org/10.1145/2049662.2049663
Edwards, H.C., Trott, C.R., Sunderland, D.: Kokkos: enabling manycore performance portability through polymorphic memory access patterns. J. Parallel Distr. Comput. 74(12), 3202–3216 (2014). https://doi.org/10.1016/j.jpdc.2014.07.003
Giraud, L., Haidar, A., Watson, L.T.: Mixed-precision preconditioners in parallel domain decomposition solvers. In: Langer, U., Discacciati, M., Keyes, D.E., Widlund, O.B., Zulehner, W. (eds.) Domain Decomposition Methods in Science and Engineering XVII. LNCSE, vol. 60. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-75199-1_44
Giraud, L., Langou, J., Rozloznik, M.: The loss of orthogonality in the Gram-Schmidt orthogonalization process. Comput. Math. Appl. 50(7), 1069–1075 (2005). https://doi.org/10.1016/j.camwa.2005.08.009
Gratton, S., Simon, E., Titley-Peloquin, D., Toint, P.: Exploiting variable precision in GMRES. SIAM J. Sci. Comput. (2020, to appear)
Greenbaum, A., Rozložník, M., Strakoš, Z.: Numerical behaviour of the modified Gram-Schmidt GMRES implementation. Bit. Numer. Math. 37(3), 706–719 (1997). https://doi.org/10.1007/BF02510248
Grützmacher, T., Anzt, H.: A modular precision format for decoupling arithmetic format and storage format. In: Revised Selected Papers, Turin, Italy, pp. 434–443 (2018). https://doi.org/10.1007/978-3-030-10549-5_34
Gustafson, J.L., Yonemoto, I.T.: Beating floating point at its own game: posit arithmetic. Supercomput. Front. Innov. 4(2), 71–86 (2017). https://doi.org/10.14529/jsfi170206
Liang, X., et al.: Error-controlled lossy compression optimized for high compression ratios of scientific datasets. In: 2018 IEEE International Conference on Big Data (Big Data), pp. 438–447. IEEE (2018). https://doi.org/10.1109/BigData.2018.8622520
Lindstrom, P.: Fixed-rate compressed floating-point arrays. IEEE Trans. Vis. Comput. Graph. 20(12), 2674–2683 (2014). https://doi.org/10.1109/TVCG.2014.2346458
Paige, C.C.: A useful form of unitary matrix obtained from any sequence of unit 2-norm n-vectors. SIAM J. Matrix Anal. Appl. 31(2), 565–583 (2009). https://doi.org/10.1137/080725167
Paige, C.C., Rozlozník, M., Strakos, Z.: Modified Gram-Schmidt (MGS), least squares, and backward stability of MGS-GMRES. SIAM J. Matrix Anal. Appl. 28(1), 264–284 (2006). https://doi.org/10.1137/050630416
Paige, C.C., Strakos, Z.: Residual and backward error bounds in minimum residual Krylov subspace methods. SIAM J. Sci. Comput. 23(6), 1898–1923 (2001). https://doi.org/10.1137/S1064827500381239
Saad, Y.: Iterative Methods for Sparse Linear Systems, 2nd edn. SIAM Press, Philadelphia (2003)
Saad, Y., Schultz, M.H.: GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Stat. Comput. 7(3), 856–869 (1986). https://doi.org/10.1137/0907058
Van der Vorst, H.A., Vuik, C.: The superlinear convergence behaviour of GMRES. J. Comput. Appl. Math. 48(3), 327–341 (1993). https://doi.org/10.1016/0377-0427(93)90028-A
Wilkinson, J.H.: Rounding Errors in Algebraic Processes. Prentice-Hall, Princeton (1963)
Acknowledgments
This material is based upon work supported by the University of Tennessee grant MSE E01-1315-038 as Interdisciplinary Seed funding and in part by UT Battelle subaward 4000123266. This material is also based upon work supported by the National Science Foundation under Grant No. 2004541.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Lindquist, N., Luszczek, P., Dongarra, J. (2020). Improving the Performance of the GMRES Method Using Mixed-Precision Techniques. In: Nichols, J., Verastegui, B., Maccabe, A.‘., Hernandez, O., Parete-Koon, S., Ahearn, T. (eds) Driving Scientific and Engineering Discoveries Through the Convergence of HPC, Big Data and AI. SMC 2020. Communications in Computer and Information Science, vol 1315. Springer, Cham. https://doi.org/10.1007/978-3-030-63393-6_4
Download citation
DOI: https://doi.org/10.1007/978-3-030-63393-6_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-63392-9
Online ISBN: 978-3-030-63393-6
eBook Packages: Computer ScienceComputer Science (R0)