Symmetric-diagonal reductions as preprocessing for symmetric positive definite generalized eigenvalue solvers

Document Type : Research Article

Author

Department of Mathematics, Faculty of Science, University of Kurdistan, 66177-15175, Sanandaj, Iran

Abstract

We discuss  some potential advantages of the  orthogonal symmetric-diagonal reduction in  two main versions of the Schur-QR method  for symmetric positive definite  generalized eigenvalue problems. We also advise and use the appropriate reductions  as preprocessing on  the solvers, mainly  the Cholesky-QR method, of the  considered  problems. We discuss numerical stability of the  methods via providing upper bound for backward error of the computed eigenpairs and via investigating two kinds of  scaled residual errors. We also propose  and apply  two kinds of symmetrizing  which  improve  the stability and the performance  of the methods. Numerical experiments show that the  implemented versions of the Schur-QR method and the preprocessed versions of the Cholesky-QR  method are  usually more stable than the Cholesky-QR method. 

Keywords

Main Subjects


[1] M. Ahuesa, A. Largillier, F.D. D´Almeida, P.B. Vasconcelos, Spectral refinement on quasi-diagonal
matrices, Linear Algebra Appl. 401 (2005) 109–117.
[2] Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, H. van der Vorst, Templates for the Solution of Algebraic
Eigenvalue Problems: A Practical Guide, SIAM, Philadelphia, 2000.
[3] S. Chandrasekara, I.C.F. Ipsen, Backward errors for eigenvalue and singular value decompositions,
Numer. Math. 68 (1994) 215–223.
[4] S. Chandrasekara, An efficient and stable algorithm for the symmetric-definite generalized eigen-
value problem, SIAM J. Matrix Anal. Appl. 21 (2000) 1202–1228.
[5] B.N. Datta, Numerical Linear Algebra and Applications, Brooks/Cole, Pacific Grove, CA, 1995.
[6] P.I. Davies, N.J. Higham, F. Tisseur, Analysis of the Cholesky method with iterative refinement for
solving the symmetric definite generalized eigenproblem, SIAM J. Matrix Anal. Appl. 23 (2001)
472–493.
[7] J.J. Dongarra, C.B. Moler, J.H. Wilkinson, Improving the accuracy of computed eigenvalues and
eigenvectors, SIAM J. Numer. Anal. 20 (1983) 23–45.
[8] V. Frayss´e, V. Toumazou, A note on the normwise perturbation theory for the regular generalized
eigenproblem, Numer. Linear Algebra Appl. 5 (1998) 1–10.
[9] G.H. Golub, C.F. Van Loan, Matrix Computations (3rd edition). The Johns Hopkins University
Press, Baltimore, 1996.
[10] D.J. Higham, N.J. Higham, Structured backward error and condition of generalized eigenvalue
problems, SIAM J. Matrix Anal. Appl. 20 (1998) 493–512.
[11] N.J. Higham, Accuracy and Stability of Numerical Algorithms (Second edition). SIAM, Philadel-
phia, 2002.
[12] P. Lancaster, Linearization of regular matrix polynomials, Electron. J. Linear Algebra 17 (2008)
21–27.
[13] S. Miyajima, T. Ogita, S.M. Rump, S. Oishi, Fast verification for all eigenpairs in symmetric posi-
tive definite generalized eigenvalue problems, Reliab. Comput. 14 (2010) 24–45.
[14] C.B. Moler, G.W. Stewart, An algorithm for generalized matrix eigenvalue problems, SIAM J.
Numer. Anal. 10 (1973) 241–256.
[15] T. Ogita, K. Aishima, Iterative refinement for symmetric eigenvalue decomposition, Japan J. Indust.
Appl. Math. 35 (2018) 1007–1035.
[16] T. Ogita, K. Aishima, Iterative refinement for symmetric eigenvalue decomposition II: clustered
eigenvalues, Japan J. Indust. Appl. Math. 36 (2019) 435–459.
[17] G. Peters, J.H. Wilkinson, Ax = λ Bx and the generalized eigenproblem, SIAM J. Numer. Anal. 7
(1970) 479–492.
[18] S.M. Rump, Verification of positive definiteness, BIT 46 (2006) 433–452.
[19] R. Boisvert, R. Pozo, K. Remington, R. Barrett, J. Dongarra, Matrix Market, NIST.
[20] G. W. Stewart, Matrix Algorithms, Volume II: Eigensystems, SIAM, Philadelphia, 2001.
[21] F. Tisseur, Newton’s method in floating point arithmetic and iterative refinement of generalized
eigenvalue problems, SIAM J. Matrix Anal. Appl. 22 (2001) 1038–1057.
[22] F. Tisseur, Tridiagonal-Diagonal reduction of symmetric indefinite pairs, SIAM J. Matrix Anal.
Appl. 26 (2004) 215–232.
[23] J.H. Wilkinson, The Algebraic Eigenvalue Problem, Oxford University Press, Oxford, UK, 1965.