Applications of Mathematics, Vol. 62, No. 4, pp. 357-375, 2017

Improving backward stability of Sakurai-Sugiura method with balancing technique in polynomial eigenvalue problem

Hongjia Chen, Akira Imakura, Tetsuya Sakurai

Received January 29, 2017.  First published July 5, 2017.

Abstract:  One of the most efficient methods for solving the polynomial eigenvalue problem (PEP) is the Sakurai-Sugiura method with Rayleigh-Ritz projection (SS-RR), which finds the eigenvalues contained in a certain domain using the contour integral. The SS-RR method converts the original PEP to a small projected PEP using the Rayleigh-Ritz projection. However, the SS-RR method suffers from backward instability when the norms of the coefficient matrices of the projected PEP vary widely. To improve the backward stability of the SS-RR method, we combine it with a balancing technique for solving a small projected PEP. We then analyze the backward stability of the SS-RR method. Several numerical examples demonstrate that the SS-RR method with the balancing technique reduces the backward error of eigenpairs of PEP.
Keywords:  SS-RR method; polynomial eigenvalue problem; balancing technique
Classification MSC:  65F15, 15A18
DOI:  10.21136/AM.2017.0016-17

[1] J. Asakura, T. Sakurai, H. Tadano, T. Ikegami, K. Kimura: A numerical method for nonlinear eigenvalue problems using contour integrals. JSIAM Lett. 1 (2009), 52-55. DOI 10.14495/jsiaml.1.52 | MR 3042556 | Zbl 1278.65072
[2] J. Asakura, T. Sakurai, H. Tadano, T. Ikegami, K. Kimura: A numerical method for polynomial eigenvalue problems using contour integral. Japan J. Ind. Appl. Math. 27 (2010), 73-90. DOI 10.1007/s13160-010-0005-x | MR 2685138 | Zbl 1204.65056
[3] T. Betcke, N. J. Higham, V. Mehrmann, C. Schröder, F. Tisseur: NLEVP: A collection of nonlinear eigenvalue problems. ACM Trans. Math. Softw. 39 (2013), Paper No. 7, 28 pages. DOI 10.1145/2427023.2427024 | MR 3031626 | Zbl 1295.65140
[4] H. Chen, Y. Maeda, A. Imakura, T. Sakurai, F. Tisseur: Improving the numerical stability of the Sakurai-Sugiura method for quadratic eigenvalue problems. JSIAM Lett. 9 (2017), 17-20. DOI 10.14495/jsiaml.9.17
[5] N. J. Higham, R. Li, F. Tisseur: Backward error of polynomial eigenproblems solved by linearization. SIAM J. Matrix Anal. Appl. 29 (2007), 1218-1241. DOI 10.1137/060663738 | MR 2369292 | Zbl 1159.65042
[6] N. J. Higham, D. S. Mackey, F. Tisseur, S. D. Garvey: Scaling, sensitivity and stability in the numerical solution of quadratic eigenvalue problems. Int. J. Numer. Methods Eng. 73 (2008), 344-360. DOI 10.1002/nme.2076 | MR 2382048 | Zbl 1166.74009
[7] T. Ikegami, T. Sakurai: Contour integral eigensolver for non-Hermitian systems: a Rayleigh-Ritz-type approach. Taiwanese J. Math. 14 (2010), 825-837. MR 2667719 | Zbl 1198.65071
[8] T. Ikegami, T. Sakurai, U. Nagashima: A filter diagonalization for generalized eigenvalue problems based on the Sakurai-Sugiura projection method. J. Comput. Appl. Math. 233 (2010), 1927-1936. DOI 10.1016/ | MR 2564028 | Zbl 1185.65061
[9] E. E. Osborne: On preconditioning of matrices. J. Assoc. Comput. Math. 7 (1960), 338-345. DOI 10.1145/321043.321048 | MR 0143333 | Zbl 0106.31604
[10] B. Parlett, C. Reinsch: Balancing a matrix for calculation of eigenvalues and eigenvectors. Numer. Math. 13 (1969), 293-304. DOI 10.1007/BF02165404 | MR 1553969 | Zbl 0184.37703
[11] T. Sakurai, H. Sugiura: A projection method for generalized eigenvalue problems using numerical integration. J. Comput. Appl. Math. 159 (2003), 119-128. DOI 10.1016/S0377-0427(03)00565-X | MR 2022322 | Zbl 1037.65040
[12] F. Tisseur: Backward error and condition of polynomial eigenvalue problems. Linear Algebra Appl. 309 (2000), 339-361. DOI 10.1016/S0024-3795(99)00063-4 | MR 1758374 | Zbl 0955.65027
[13] F. Tisseur, K. Meerbergen: The quadratic eigenvalue problem. SIAM Rev. 43 (2001), 235-286. DOI 10.1137/S0036144500381988 | MR 1861082 | Zbl 0985.65028
[14] S. Yokota, T. Sakurai: A projection method for nonlinear eigenvalue problems using contour integrals. JSIAM Lett. 5 (2013), 41-44. DOI 10.14495/jsiaml.5.41 | MR 3035551

Affiliations:   Hongjia Chen, Akira Imakura, Tetsuya Sakurai, Department of Computer Science, University of Tsukuba, 1-1-1 Tennodai, Tsukuba, Ibaraki 305-8573, Japan, e-mail:

PDF available at: