×

Iterative refinement for symmetric eigenvalue decomposition. (English) Zbl 1403.65018

Summary: An efficient refinement algorithm is proposed for symmetric eigenvalue problems. The structure of the algorithm is straightforward, primarily comprising matrix multiplications. We show that the proposed algorithm converges quadratically if a modestly accurate initial guess is given, including the case of multiple eigenvalues. Our convergence analysis can be extended to Hermitian matrices. Numerical results demonstrate excellent performance of the proposed algorithm in terms of convergence rate and overall computational cost, and show that the proposed algorithm is considerably faster than a standard approach using multiple-precision arithmetic.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
15A18 Eigenvalues, singular values, and eigenvectors
15A23 Factorization of matrices
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Absil, PA; Mahony, R.; Sepulchre, R.; Dooren, P., A Grassmann-Rayleigh quotient iteration for computing invariant subspaces, SIAM Rev., 44, 57-73, (2006) · Zbl 0995.65037 · doi:10.1137/S0036144500378648
[2] Advanpix: Multiprecision Computing Toolbox for MATLAB, Code and documentation. http://www.advanpix.com/ (2016)
[3] Ahuesa, M.; Largillier, A.; D’Almeida, FD; Vasconcelos, PB, Spectral refinement on quasi-diagonal matrices, Linear Algebra Appl., 401, 109-117, (2005) · Zbl 1075.65050 · doi:10.1016/j.laa.2003.12.004
[4] Anderson, E., Bai, Z., Bischof, C., Blackford, S., Demmel, J., Dongarra, J., Du Croz, J., Greenbaum, A., Hammarling, S., McKenney, A., Sorensen, D.: LAPACK Users’ Guide, 3rd edn. SIAM, Philadelphia (1999) · Zbl 0934.65030 · doi:10.1137/1.9780898719604
[5] Atkinson, K., Han, W.: Theoretical Numerical Analysis, 3rd edn. Springer, New York (2009) · Zbl 1181.47078
[6] Collar, AR, Some notes on Jahn’s method for the improvement of approximate latent roots and vectors of a square matrix, Quart. J. Mech. Appl. Math., 1, 145-148, (1948) · Zbl 0035.20502 · doi:10.1093/qjmam/1.1.145
[7] Davies, PI; Higham, NJ; Tisseur, F., Analysis of the Cholesky method with iterative refinement for solving the symmetric definite generalized eigenproblem, SIAM J. Matrix Anal. Appl., 23, 472-493, (2001) · Zbl 1002.65044 · doi:10.1137/S0895479800373498
[8] Davies, PI; Smith, MI, Updating the singular value decomposition, J. Comput. Appl. Math., 170, 145-167, (2004) · Zbl 1050.65036 · doi:10.1016/j.cam.2003.12.039
[9] Davies, RO; Modi, JJ, A direct method for completing eigenproblem solutions on a parallel computer, Linear Algebra Appl., 77, 61-74, (1986) · Zbl 0587.65026 · doi:10.1016/0024-3795(86)90162-X
[10] Demmel, J.W.: Applied Numerical Linear Algebra. SIAM, Philadelphia (1997) · doi:10.1137/1.9781611971446
[11] Dhillon, IS; Parlett, BN, Multiple representations to compute orthogonal eigenvectors of symmetric tridiagonal matrices, Linear Algebra Appl., 387, 1-28, (2004) · Zbl 1055.65048 · doi:10.1016/j.laa.2003.12.028
[12] Dongarra, JJ; Moler, CB; Wilkinson, JH, Improving the accuracy of computed eigenvalues and eigenvectors, SIAM J. Numer. Anal., 20, 23-45, (1983) · Zbl 0523.65021 · doi:10.1137/0720002
[13] GMP: GNU Multiple Precision Arithmetic Library, Code and documentation. http://gmplib.org/ (2015)
[14] Golub, G.H., Van Loan, C.F.: Matrix Computations, 4th edn. The Johns Hopkins University Press, Baltimore (2013) · Zbl 1268.65037
[15] Gu, M.; Eisenstat, SC, A divide-and-conquer algorithm for the symmetric tridiagonal eigenproblem, SIAM J. Matrix Anal. Appl., 16, 172-191, (1995) · Zbl 0815.65050 · doi:10.1137/S0895479892241287
[16] Hida, Y., Li, X.S., Bailey, D.H.: Algorithms for quad-double precision floating point arithmetic. In: Proceedings of the 15th IEEE Symposium on Computer Arithmetic, pp. 155-162. IEEE Computer Society Press (2001)
[17] Higham, N.J.: Accuracy and Stability of Numerical Algorithms, 2nd edn. SIAM, Philadelphia (2002) · Zbl 1011.65010 · doi:10.1137/1.9780898718027
[18] Higham, N.J.: Functions of Matrices: Theory and Computation. SIAM, Philadelphia (2008) · Zbl 1167.15001 · doi:10.1137/1.9780898717778
[19] Jahn, HA, Improvement of an approximate set of latent roots and modal columns of a matrix by methods akin to those of classical perturbation theory, Quart. J. Mech. Appl. Math., 1, 131-144, (1948) · Zbl 0035.20501 · doi:10.1093/qjmam/1.1.131
[20] Li, XS; Demmel, JW; Bailey, DH; Henry, G.; Hida, Y.; Iskandar, J.; Kahan, W.; Kang, SY; Kapur, A.; Martin, MC; Thompson, BJ; Tung, T.; Yoo, D., Design, implementation and testing of extended and mixed precision BLAS, ACM Trans. Math. Softw., 28, 152-205, (2002) · Zbl 1070.65523 · doi:10.1145/567806.567808
[21] MPFR: The GNU MPFR Library, Code and documentation. http://www.mpfr.org/ (2013)
[22] Ogita, T.; Rump, SM; Oishi, S., Accurate sum and dot product, SIAM J. Sci. Comput., 26, 1955-1988, (2005) · Zbl 1084.65041 · doi:10.1137/030601818
[23] Oishi, S., Fast enclosure of matrix eigenvalues and singular values via rounding mode controlled computation, Linear Algebra Appl., 324, 133-146, (2001) · Zbl 0978.65026 · doi:10.1016/S0024-3795(00)00272-X
[24] Ozaki, K.; Ogita, T.; Oishi, S.; Rump, SM, Error-free transformations of matrix multiplication by using fast routines of matrix multiplication and its applications, Numer. Algorithms, 59, 95-118, (2012) · Zbl 1244.65062 · doi:10.1007/s11075-011-9478-1
[25] Parlett, B.N.: The symmetric eigenvalue problem, vol. 20, 2nd edn. Classics in Applied Mathematics. SIAM, Philadelphia (1998) · Zbl 0885.65039
[26] Priest, D.M.: Algorithms for arbitrary precision floating point arithmetic. In: Proceedings of the 10th Symposium on Computer Arithmetic, pp. 132-145. IEEE Computer Society Press (1991)
[27] Rump, SM; Ogita, T.; Oishi, S., Accurate floating-point summation part I: faithful rounding, SIAM J. Sci. Comput., 31, 189-224, (2008) · Zbl 1185.65082 · doi:10.1137/050645671
[28] Rump, SM; Ogita, T.; Oishi, S., Accurate floating-point summation part II: sign, \(K\)-fold faithful and rounding to nearest, SIAM J. Sci. Comput., 31, 1269-1302, (2008) · Zbl 1190.65074 · doi:10.1137/07068816X
[29] Tisseur, F., Newton’s method in floating point arithmetic and iterative refinement of generalized eigenvalue problems, SIAM J. Matrix Anal. Appl., 22, 1038-1057, (2001) · Zbl 0982.65040 · doi:10.1137/S0895479899359837
[30] Wilkinson, J.H.: The Algebraic Eigenvalue Problem. Clarendon Press, Oxford (1965) · Zbl 0258.65037
[31] Yamamoto, S.; Fujiwara, T.; Hatsugai, Y., Electronic structure of charge and spin stripe order in \(\text{La}_{2-x}\,\text{ Sr }_{x}\,\text{ Ni }\,\text{ O }_{4}\) (\(x =\frac{1}{3}, \frac{1}{2}\)), Phys. Rev. B, 76, 165114, (2007) · doi:10.1103/PhysRevB.76.165114
[32] Yamamoto, S.; Sogabe, T.; Hoshi, T.; Zhang, S-L; Fujiwara, T., Shifted conjugate-orthogonal-conjugate-gradient method and its application to double orbital extended Hubbard model, J. Phys. Soc. Jpn., 77, 114713, (2008) · doi:10.1143/JPSJ.77.114713
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.