The efficient utilization of mixed-precision numerical linear algebra algorithms can offer attractive acceleration to scientific computing applications. Especially with the hardware integration of low-precision special-function units designed for machine learning applications, the traditional numerical algorithms community urgently needs to reconsider the floating point formats used in the distinct operations to efficiently leverage the available compute power. In this work, we provide a comprehensive survey of mixed-precision numerical linear algebra routines, including the underlying concepts, theoretical background, and experimental results for both dense and sparse linear algebra problems.
AbdelfattahATomovSDongarraJJ (2019) Fast batched matrix multiplication for small sizes using half-precision arithmetic on GPUs. In: 2019 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2019, Rio de Janeiro, Brazil, 20–24 May 2019, pp. 111–122. IEEE.
2.
AbdelfattahATomovSDongarraJ (2020) Investigating the benefit of FP16-enabled mixed-precision solvers for symmetric positive definite matrices using GPUs. In: VVKrzhizhanovskayaGZávodszkyMHLeesJJDongarraPMASlootSBJTeixeira (eds) Computational Science—ICCS 2020, Lecture Notes in Computer Science, Vol. 12138. New York, NY: Springer International Publishing, pp. 237–250. DOI: 10.1007/978-3-030-50417-5_18.
3.
AgulloEDemmelJDongarraJ, et al. (2009) Numerical linear algebra on emerging architectures: the PLASMA and MAGMA projects. Journal of Physics: Conference Series180: 012037.
4.
AlvermannABasermannABungartzHJ, et al. (2019) Benefits from using mixed precision computations in the ELPA-AEO and ESSEX-II eigensolver projects. Japan Journal of Industrial and Applied Mathematics36(2): 699–717.
5.
AndersonEBaiZBischofCH, et al. (1999) LAPACK Users’ Guide. 3rd edn. Philadelphia, PA: Society for Industrial and Applied Mathematics. ISBN 0-89871-447-8. Available at: http://www.netlib.org/lapack/lug/(accessed 2020).
6.
AnztHCojeanTChenYC, et al. (2020) Ginkgo: A high performance numerical linear algebra library. Journal of Open Source Software5(52): 2260. DOI: https://doi.org/10.21105/joss.02260.
7.
AnztHDongarraJFlegarG, et al. (2019a) Adaptive precision in block-jacobi preconditioning for iterative sparse linear system solvers. Concurrency and Computation: Practice and Experience31(6): e4460.
8.
AnztHFlegarGGrützmacherT, et al. (2019b) Toward a modular precision ecosystem for high-performance computing. The International Journal of High Performance Computing Applications33(6): 1069–1078.
9.
AnztHHuckleTKBräckleJ, et al. (2018) Incomplete sparse approximate inverses for parallel preconditioning. Parallel Computing71: 1–22.
10.
ArioliMDuffIS (2009) Using FGMRES to obtain backward stability in mixed precision. Electronic Transactions on Numerical Analysis33: 31–44.
11.
ArioliMDuffISGrattonS, et al. (2007) A note on GMRES preconditioned by a perturbed decomposition with static pivoting. SIAM Journal on Scientific Computing29(5): 2024–2044.
12.
BarlowJL (2019) Block modified Gram–Schmidt algorithms and their analysis. SIAM Journal on Matrix Analysis and Applications40(4): 1257–1290.
13.
BjörckÅ (1967a) Iterative refinement of linear least squares solutions I. BIT Numerical Mathematics7(4): 257–278.
14.
BjörckÅ (1967b) Solving linear least squares problems by Gram-Schmidt orthogonalization. BIT Numerical Mathematics7(1): 1–21.
15.
BjörckÅ (1990) Iterative refinement and reliable computing. In: CoxMGHammarlingSJ (eds) Reliable Numerical Computation. Oxford: Oxford University Press, pp. 249–266.
16.
BjörckÅ (1994) Numerics of Gram-Schmidt orthogonalization. Linear Algebra and its Applications197: 297–316.
17.
BjörckÅPaigeCC (1992) Loss and recapture of orthogonality in the modified Gram-Schmidt algorithm. SIAM Journal on Matrix Analysis and Applications13(1): 176–190.
18.
BlanchardPHighamNJLopezF, et al. (2020) Mixed precision block fused multiply-add: error analysis and application to GPU tensor cores. SIAM Journal on Scientific Computing42(3): C124–C141.
19.
CarsonEHighamNJ (2017) A new analysis of iterative refinement and its application to accurate solution of ill-conditioned sparse linear systems. SIAM Journal on Scientific Computing39(6): A2834–A2856.
20.
CarsonEHighamNJ (2018) Accelerating the solution of linear systems by iterative refinement in three precisions. SIAM Journal on Scientific Computing40(2): A817–A847.
21.
CarsonEHighamNJPraneshS (2020) Three-precision GMRES-based iterative refinement for least squares problems. SIAM Journal on Scientific Computing42(6): A4063–A408.
22.
CarsonEC (2015) Communication-avoiding Krylov subspace methods in theory and practice. PhD Thesis, University of California, Berkeley.
23.
ClarkK (2019) Effective use of mixed precision for hpc. In: Smoky Mountain Conference 2019, Tennessee, 3–6 September 2019.
24.
ClarkMABabichRBarrosK, et al. (2010) Solving lattice QCD systems of equations using mixed precision solvers on GPUs. Computer Physics Communications181(9): 1517–1528.
25.
DaviesPIHighamNJTisseurF (2001) Analysis of the Cholesky method with iterative refinement for solving the symmetric definite generalized eigenproblem. SIAM Journal on Matrix Analysis and Applications23(2): 472–493.
26.
DemmelJWHidaYKahanW, et al. (2006) Error bounds from extra-precise iterative refinement. ACM Transactions on Mathematical Software32(2): 325–351.
27.
DongarraJJ (1982) Algorithm 589 SICEDR: a FORTRAN subroutine for improving the accuracy of computed matrix eigenvalues. ACM Transactions on Mathematical Software8(4): 371–375.
28.
DongarraJJMolerCBWilkinsonJH (1983) Improving the accuracy of computed eigenvalues and eigenvectors. SIAM Journal on Numerical Analysis20(1): 23–45.
29.
ElbleJMSahinidisNV (2012) Scaling linear optimization problems prior to application of the simplex method. Computational Optimization and Applications52(2): 345–371.
30.
EmansMvan der MeerA (2012) Mixed-precision AMG as linear equation solver for definite systems. In: Proceedings of International Conference on Computational Science, ICCS 2010, Vol. 1, The Netherlands 31 May–2 June 2010, pp. 175–183.
31.
FlegarGAnztHCojeanT, et al. (2021) Adaptive precision block-Jacobi for high performance preconditioning in the ginkgo linear algebra software. ACM Transaction on Mathematical Software47(2): e4460.
32.
FoxAKolasinskiA (2019) Error analysis of inline ZFP compression for multigrid methods. In: 2019 Copper Mountain Conference for Multigrid Methods, Copper Mountain, CO, March 25, 2019.
33.
FukayaTKannanRNakatsukasaY, et al. (2020) Shifted CholeskyQR for computing the QR factorization of ill-conditioned matrices. SIAM Journal on Scientific Computing42(1): A477–A503.
34.
GiraudLGrattonSLangouJ (2004) A rank-k update procedure for reorthogonalizing the orthogonal factor from modified Gram–Schmidt. SIAM Journal on Matrix Analysis and Applications25(4): 1163–1177.
35.
GlimbergSLEngsig-KarupAPMadsenMG (2011) A fast GPU-accelerated mixed-precision strategy for fully nonlinearwater wave computations. In: Proceedings of ENUMATH 2011, University of Leicester.
36.
GrattonSSimonETitley-PeloquinDTointP (2019) Exploiting variable precision in GMRES. arXiv preprintarXiv:1907.10550.
37.
GreenbaumA (1989) Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences. Linear Algebra and its Applications113: 7–63.
38.
GreenbaumA (1997) Estimating the attainable accuracy of recursively computed residual methods. SIAM Journal on Matrix Analysis and Applications18(3): 535–551.
39.
GrützmacherTCojeanTFlegarG, et al. (2019) A customized precision format based on mantissa segmentation for accelerating sparse linear algebra. Concurrency and Computation: Practice and Experience32: e5418.
40.
GuptaSAgrawalAGopalakrishnanK, et al. (2015) Deep learning with limited numerical precision. In: Proceedings of the 32nd International Conference on International Conference on Machine Learning, Vol. 37, ICML’15. JMLR.org, pp. 1737–1746. Available at: http://dl.acm.org/citation.cfm?id=3045118.3045303(accessed 2020).
41.
GustafsonJ (2015) The End of Error: Unum Computing. Milton Park: Chapman & Hall/CRC Computational Science. Taylor & Francis. ISBN 9781482239867. Available at: https://books.google.de/books?id=W2ThoAEACAAJ(accessed 2020).
42.
HaidarAAbdelfattahAZounonM, et al. (2018a) The design of fast and energy-efficient linear solvers: on the potential of half-precision arithmetic and iterative refinement techniques. In: YShiHFuYTianVVKrzhizhanovskayaMHLeesJDongarraPMASloot (eds) Computational Science—ICCS 2018. Cham: Springer International Publishing, pp. 586–600. DOI: 10.1007/978-3-319-93698-7_45.
43.
HaidarABayraktarHTomovS, et al. (2020) Mixed-precision solution of linear systems using accelerator-based computing. Mixed-precision iterative refinement using tensor cores on GPUs to accelerate solution of linear systems. Proceedings of the Royal Society A476(2243): 20200110, 2020.
44.
HaidarATomovSDongarraJ, et al. (2018b) Harnessing GPU Tensor Cores for fast FP16 arithmetic to speed up mixed-precision iterative refinement solvers. In: Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis, SC ‘18, Dallas, TX, USA, 11–16 November 2018. Piscataway, NJ, USA: IEEE Press, pp. 47: 1–47:11.
45.
HaidarAWuPTomovS, et al. (2017) Investigating half precision arithmetic to accelerate dense linear system solvers. In: Proceedings of the 8th Workshop on Latest Advances in Scalable Algorithms for Large-Scale Systems, New York, NY, November 2017, pp. 1–8.
46.
HighamNJ (1989) The accuracy of solutions to triangular systems. SIAM Journal on Numerical Analysis26(5): 1252–1265.
47.
HighamNJ (1997) Iterative refinement for linear systems and LAPACK. IMA Journal of Numerical Analysis17(4): 495–509.
48.
HighamNJ (2002) Accuracy and Stability of Numerical Algorithms. 2nd edn. Philadelphia, PA: Society for Industrial and Applied Mathematics. ISBN 0-89871-521-0.
49.
HighamNJ (2019) Error analysis for standard and GMRES-based iterative refinement in two and three-precisions. MIMS EPrint 2019.19, Manchester: Manchester Institute for Mathematical Sciences, The University of Manchester. Available at: http://eprints.maths.manchester.ac.uk/2735/(accessed 2020).
50.
HighamNJMaryT (2019) A new approach to probabilistic rounding error analysis. SIAM Journal on Scientific Computing41(5): A2815–A2835.
51.
HighamNJMaryT (2020) Sharper probabilistic backward error analysis for basic linear algebra kernels with random data. SIAM Journal on Scientific Computing42(5): A3427–A3446.
52.
HighamNJPraneshS (2021) Exploiting lower precision arithmetic in solving symmetric positive definite linear systems and least squares problems. SIAM Journal on Scientific Computing43(1): A258–A277.
HighamNJPraneshSZounonM (2019) Squeezing a matrix into half precision, with an application to solving linear systems. SIAM Journal on Scientific Computing41(4): A2536–A2551.
55.
HoggJDScottJA (2010) A fast and robust mixed-precision solver for the solution of sparse symmetric linear systems. ACM Transactions on Mathematical Software37(2): 17:1–17:24.
56.
IEEE (2019) IEEE Standard for Floating-Point Arithmetic, IEEE Std 754-2019 (Revision of IEEE 754-2008). New York, NY: The Institute of Electrical and Electronics Engineers. ISBN 978-1-5044-5924-2. DOI:10.1109/IEEESTD.2019.8766229.
57.
JoffrainTLowTMQuintana-OrtES, et al. (2006) Accumulating Householder transformations, revisited. ACM Transactions on Mathematical Software (TOMS32(2): 169–179.
58.
KnightPARuizDUçarB (2014) A symmetry preserving algorithm for matrix scaling. SIAM Journal on Matrix Analysis and Applications35(3): 931–955.
59.
LangouJLangouJLuszczekP, et al. (2006) Exploiting the performance of 32 bit floating point arithmetic in obtaining 64 bit accuracy (revisiting iterative refinement for linear systems). In: Proceedings of the 2006 ACM/IEEE Conference on Supercomputing, Tampa, FL, USA, 11–17 November 2006.
60.
LeonSJBjörckÅGanderW (2013) Gram-Schmidt orthogonalization: 100 years and more. Numerical Linear Algebra with Applications20(3): 492–532.
LjungkvistKKronbichlerM (2017) Multigrid for matrix-free finite element computations on graphics processors. Technical report, Department of Information Technology, Uppsala University.
63.
LjungkvistKKronbichlerM (2019) Multigrid for matrix-free high-order finite element computations on graphics processors. ACM Transactions on Parallel Processing6: 3322813.
64.
MalardJPaigeC (1994) Efficiency and scalability of two parallel QR factorization algorithms. In: Proceedings of IEEE Scalable High Performance Computing Conference. New York, NY: IEEE, pp. 615–622.
65.
MeurantGStrakošZ (2006) The Lanczos and conjugate gradient algorithms in finite precision arithmetic. Acta Numerica15: 471–542.
66.
MolerCB (1967) Iterative refinement in floating point. Journal of the ACM (JACM)14(2): 316–321.
OgitaTAishimaK (2018) Iterative refinement for symmetric eigenvalue decomposition. Japan Journal of Industrial and Applied Mathematics35(3): 1007–1035.
69.
OgitaTAishimaK (2019) Iterative refinement for symmetric eigenvalue decomposition II: clustered eigenvalues. Japan Journal of Industrial and Applied Mathematics36: 435–459.
70.
PaigeCC (1980) Accuracy and effectiveness of the Lanczos algorithm for the symmetric eigenproblem. Linear Algebra and its Applications34: 235–258.
71.
PaigeCC (2018) The effects of loss of orthogonality on large scale numerical computations. In: International Conference on Computational Science and Its Applications. Cham: Springer, pp. 429–439.
72.
PaigeCCStrakošZ (2002) Residual and backward error bounds in minimum residual Krylov subspace methods. SIAM Journal on Scientific Computing23(6): 1898–1923.
73.
PaigeCCWüllingW (2014) Properties of a unitary matrix obtained from a sequence of normalized vectors. SIAM Journal on Matrix Analysis and Applications35(2): 526–545.
74.
PaigeCCRozložnkMStrakošZ (2006) Modified gram-schmidt MGS, least squares, and backward stability of MGS-GMRES. SIAM Journal on Matrix Analysis and Application28(1): 264–284.
75.
PetschowMQuintana-OrtEBientinesiP (2014) Improved accuracy and parallelism for MRRR-based eigensolvers—a mixed precision approach. SIAM Journal on Scientific Computing36(2): C240–C263.
76.
PuglisiC (1992) Modification of the Householder method based on the compact WY representation. SIAM Journal on Scientific Computing13(3): 723–726.
77.
RichterCSchopsSClemensM (2014)GPU-accelerated mixed precision algebraic multigrid preconditioners for discrete elliptic field problems. 9th IET International Conference on Computation in Electromagnetics (CEM 2014), London, UK, 2014, pp. 1–2, DOI: 10.1049/cp.2014.0185.
78.
SaadYSchultzMH (1986) GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM Journal on scientific and statistical computing7(3): 856–869.
79.
SayoodK (2012) Introduction to Data Compression, Fourth Edition. 4th edn. San Francisco, CA: Morgan Kaufmann Publishers Inc. ISBN 0124157963.
80.
SimonciniVSzyldDB (2003) Theory of inexact Krylov subspace methods and applications to scientific computing. SIAM Journal on Scientific Computing25(2): 454–477.
81.
SkeelRD (1980) Iterative refinement implies numerical stability for Gaussian elimination. Mathematics of Computation35(151): 817–832.
82.
SleijpenGLvan der VorstHA (1996) Reliable updated residuals in hybrid Bi-CG methods. Computing56(2): 141–163.
83.
SmoktunowiczABarlowJLLangouJ (2006) A note on the error analysis of classical Gram–Schmidt. Numerische Mathematik105(2): 299–313.
84.
StewartGW (1973) Introduction to Matrix Computations. New York, NY: Academic Press. ISBN 0-12-670350-7.
85.
SumiyoshiYFujiiANukadaA, et al. (2014) Mixed-precision amg method for many core accelerators. In: EUROMPI/ASIA 14: Proceedings of the 21st European MPI Users’ Group Meeting. September 2014, pp. 127–132.
86.
SunX (1996) Aggregations of elementary transformations. Technical Report DUKE-TR-1996-03, Durham, NC: Duke University.
87.
ŚwirydowiczKLangouJAnanthanS, et al. (2020) Low synchronization Gram-Schmidt and generalized minimal residual algorithms. Numerical Linear Algebra with Applications28: e2343.
88.
TamstorfRBenzakenJMcCormickS (2020a) Algebraic error analysis for mixed precision multigrid solvers. SIAM Journal on Scientific ComputingSubmitted.
The Trilinos Project Team (2020) The Trilinos Project Website. Available at: https://trilinos.github.io(accessed 2020).
91.
TisseurF (2001) Newton’s method in floating point arithmetic and iterative refinement of generalized eigenvalue problems. SIAM Journal on Matrix Analysis and Applications22(4): 1038–1057.
92.
van den EshofJSleijpenGL (2004) Inexact Krylov subspace methods for linear systems. SIAM Journal on Matrix Analysis and Applications26(1): 125–153.
93.
Van Der VorstHAYeQ (2000) Residual replacement strategies for Krylov subspace iterative methods for the convergence of true residuals. SIAM Journal on Scientific Computing22(3): 835–852.
94.
WalkerHF (1988) Implementation of the GMRES method using Householder transformations. SIAM Journal on Scientific Computing9(1): 152–163.
95.
WilkinsonJH (1963) Rounding Errors in Algebraic Processes. Notes on Applied Science No. 32, Her Majesty’s Stationery Office. ISBN 0-486-67999-3. Also published by Prentice-Hall, Englewood Cliffs, NJ, USA. Reprinted by Dover, New York, 1994.
96.
YamagishiTMatsumuraY (2016) GPU acceleration of a non-hydrostatic ocean model with a multigrid poisson/helmholtz solver. Procedia Computer Science80: 1658–1669.
97.
YamazakiITomovSDongarraJ (2015) Mixed-precision Cholesky QR factorization and its case studies on multicore CPU with multiple GPUs. SIAM Journal on Scientific Computing37(1): C307–C330.
98.
YamazakiITomovSDongarraJ (2016) Stability and performance of various singular value QR implementations on multicore CPU with a GPU. ACM Transactions on Mathematical Software43(2): 10:1–10:18.
