×

Mixed precision bisection. (English) Zbl 1402.65027

Summary: We discuss the implementation of the bisection algorithm for the computation of the eigenvalues of symmetric tridiagonal matrices in a context of mixed precision arithmetic. This approach is motivated by the emergence of processors which carry out floating-point operations much faster in single precision than they do in double precision. Perturbation theory results are used to decide when to switch from single to double precision. Numerical examples are presented.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices

Software:

LAPACK; ScaLAPACK; CholQR
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Anderson, E., et al.: LAPACK Users’ Guide. SIAM, Philadelphia (1999) · Zbl 0755.65028 · doi:10.1137/1.9780898719604
[2] Blackford, L., et al.: ScaLAPACK Users’ Guide. SIAM, Philadelphia (1997) · Zbl 0886.65022 · doi:10.1137/1.9780898719642
[3] Buttari, A; etal., Mixed precision iterative refinement techniques for the solution of dense linear systems, Int. J. High Perform. Comput. Appl., 21, 457-466, (2007) · doi:10.1177/1094342007084026
[4] Buttari, A; etal., Using mixed precision for sparse matrix computations to enhance the performance while achieving 64-bit accuracy, ACM Trans. Math. Softw. TOMS, 34, 17:1-17:22, (2008) · Zbl 1190.65117
[5] Demmel, J.W.: The inherent inaccuracy of implicit tridiagonal QR. LAPACK working note 15 (1992)
[6] Demmel, JW; Li, X, Faster numerical algorithms via exception handling, IEEE Trans. Comput., 43, 983-992, (1992) · Zbl 1073.68502 · doi:10.1109/12.295860
[7] Demmel, JW; Dhillon, I; Ren, H, On the correctness of some bisection-like parallel eigenvalue algorithms in floating point arithmetic, Electr. Trans. Numer. Anal., 3, 116-149, (1995) · Zbl 0860.65026
[8] Demmel, J.W.: Applied Numerical Linear Algebra. SIAM, Philadelphia (1997) · Zbl 0879.65017 · doi:10.1137/1.9781611971446
[9] Giraud, l; Haidar, A; Watson, L, Mixed-precision preconditioners in parallel domain decomposition solvers, Lect. Notes Comput. Sci. Eng, 60, 357-364, (2008) · Zbl 1139.65022 · doi:10.1007/978-3-540-75199-1_44
[10] Golub, G., Van Loan, C.: Matrix Computations, 2nd edn. The Johns Hopkins University Press, Baltimore (1989) · Zbl 0733.65016
[11] Higham, N.: The rise of mixed precision arithmetic. https://nickhigham.wordpress.com/2015/10/20/the-rise-of-mixed-precision-arithmetic/. Accessed Nov 2015
[12] Kurzak, J; Dongarra, J, Implementation of mixed precision in solving systems of linear equations on the CELL processor, Concurr. Comput. Pract. Exp., 19, 1371-1385, (2007) · doi:10.1002/cpe.1164
[13] Langou, J., et al.: Exploiting the performance of 32 bit floating point arithmetic in obtaining 64 bit accuracy (revisiting iterative refinement for linear systems. In: Proceedings of the ACM/IEEE 2006 Conference. IEEE Computer Society Press (2006)
[14] Parlett, B.N.: The Symmetric Eigenvalue Problem. Prentice-Hall, Englewood Cliffs (1998) · Zbl 0885.65039 · doi:10.1137/1.9781611971163
[15] Petschow, M; Quintana-Orti, ES; Bientinesi, P, Improved accuracy and parallelism for MRRR-based eigensolvers—a mixed precision approach, SIAM J. Sci. Comput., 36, c240-c263, (2014) · Zbl 1296.65059 · doi:10.1137/130911561
[16] Ralha, R, Perturbation splitting for more accurate eigenvalues, SIAM J. Matrix Anal. Appl., 31, 75-91, (2009) · Zbl 1188.65044 · doi:10.1137/070687049
[17] Volkov, V., Demmel, J.W.: Using GPUs to accelerate the bisection algorithm for finding eigenvalues of symmetric tridiagonal matrices. LAPACK working note 197 (2008)
[18] Wilkinson, J.H.: The Algebraic Eigenvalue Problem. Oxford University Press, London (1965) · Zbl 0258.65037
[19] Yamazaki, I; Tomov, S; Dongarra, J, Mixed-precision choleski QR factorization and its case studies on multicore CPU with multiple gpus, SIAM J. Sci. Comput., 37, c307-c330, (2015) · Zbl 1320.65046 · doi:10.1137/14M0973773
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.