Applications of Mathematics, Vol. 65, No. 5, pp. 677-702, 2020

Convergence acceleration of shifted $LR$ transformations for totally nonnegative Hessenberg matrices

Akiko Fukuda, Yusaku Yamamoto, Masashi Iwasaki, Emiko Ishiwata, Yoshimasa Nakamura

Received December 30, 2019.   Published online September 7, 2020.

Abstract:  We design shifted $LR$ transformations based on the integrable discrete hungry Toda equation to compute eigenvalues of totally nonnegative matrices of the banded Hessenberg form. The shifted $LR$ transformation can be regarded as an extension of the extension employed in the well-known dqds algorithm for the symmetric tridiagonal eigenvalue problem. In this paper, we propose a new and effective shift strategy for the sequence of shifted $LR$ transformations by considering the concept of the Newton shift. We show that the shifted $LR$ transformations with the resulting shift strategy converge with order $2-\epsilon$ for arbitrary $\epsilon>0$.
Keywords:  $LR$ transformation; totally nonnegative matrix; Newton shift; convergence rate
Classification MSC:  34B16, 34C25
DOI:  10.21136/AM.2020.0378-19

PDF available at:  Springer   Institute of Mathematics CAS

[1] F. L. Bauer: qd-method with Newton shift. Technical Report 56. Computer Science Department, Stanford University, Stanford (1967).
[2] K. V. Fernando, B. N. Parlett: Accurate singular values and differential qd algorithms. Numer. Math. 67 (1994), 191-229. DOI 10.1007/s002110050024 | MR 1262781 | Zbl 0814.65036
[3] A. Fukuda, E. Ishiwata, Y. Yamamoto, M. Iwasaki, Y. Nakamura: Integrable discrete hungry systems and their related matrix eigenvalues. Ann. Mat. Pura Appl. 192 (2013), 423-445. DOI 10.1007/s10231-011-0231-0 | MR 3061107 | Zbl 1349.37064
[4] A. Fukuda, Y. Yamamoto, M. Iwasaki, E. Ishiwata, Y. Nakamura: Error analysis for matrix eigenvalue algorithm based on the discrete hungry Toda equation. Numer. Algorithms 61 (2012), 243-260. DOI 10.1007/s11075-012-9606-6 | MR 2969294 | Zbl 1257.65019
[5] A. Fukuda, Y. Yamamoto, M. Iwasaki, E. Ishiwata, Y. Nakamura: On a shifted $LR$ transformation derived from the discrete hungry Toda equation. Monatsh. Math. 170 (2013), 11-26. DOI 10.1007/s00605-012-0404-y | MR 3032671 | Zbl 1311.65036
[6] G. H. Golub, C. F. Van Loan: Matrix Computations. Johns Hopkins Studies in the Mathematical Sciences. The Johns Hopkins University Press, Baltimore (2013). MR 3024913 | Zbl 1268.65037
[7] R. A. Horn, C. R. Johnson: Matrix Analysis. Cambridge University Press, Cambridge (1985). DOI 10.1017/CBO9780511810817 | MR 0832183 | Zbl 0576.15001
[8] LAPACK Team: LAPACK: Linear Algebra PACKage. Available at SW 00503
[9] C.-K. Li, R. Mathias: Interlacing inequalities for totally nonnegative matrices. Linear Algebra Appl. 341 (2002), 35-44. DOI 10.1016/S0024-3795(01)00240-3 | MR 1873607 | Zbl 0997.15014
[10] B. N. Parlett: The new qd algorithms. Acta Numerica 4 (1995), 459-491. DOI 10.1017/S0962492900002580 | MR 1352476 | Zbl 0835.65059
[11] A. Pinkus: Totally Positive Matrices. Cambridge Tracts in Mathematics 181. Cambridge University Press, Cambridge (2009). DOI 10.1017/CBO9780511691713 | MR 2584277 | Zbl 1185.15028
[12] C. Reinsch, F. L. Bauer: Rational QR transformation with Newton shift for symmetric tridiagonal matrices. Numer. Math. 11 (1968), 264-272. DOI 10.1007/BF02161847 | MR 1553960 | Zbl 0164.45201
[13] H. Rutishauser: Lectures on Numerical Mathematics. Birkh√§user, Boston (1990). DOI 10.1007/978-1-4612-3468-5 | MR 1102678 | Zbl 0699.65002
[14] J.-Q. Sun, X.-B. Hu, H.-W. Tam: Short note: An integrable numerical algorithm for computing eigenvalues of a specially structured matrix. Numer. Linear Algebra Appl. 18 (2011), 261-274. DOI 10.1002/nla.754 | MR 2791246 | Zbl 1249.65079
[15] T. Tokihiro, A. Nagai, J. Satsuma: Proof of solitonical nature of box and ball systems by means of inverse ultra-discretization. Inverse Probl. 15 (1999), 1639-1662. DOI 10.1088/0266-5611/15/6/314 | MR 1733220 | Zbl 1138.37341

Affiliations:   Akiko Fukuda, Department of Mathematical Sciences, Shibaura Institute of Technology, 307 Fukasaku, Minuma-ku, Saitama 337-8570, Japan, e-mail:; Yusaku Yamamoto, Department of Communication Engineering and Informatics, The University of Electro-Communications, 1-5-1 Chofugaoka, Chofu, Tokyo 182-8585, Japan, e-mail:; Masashi Iwasaki, Department of Life and Environmental Sciences, Kyoto Prefectural University, 1-5 Shimogamo Nakaragi-cho, Sakyo-ku, Kyoto 606-8522, Japan, e-mail:; Emiko Ishiwata, Department of Applied Mathematics, Tokyo University of Science, 1-3 Kagurazaka, Shinjuku-ku, Tokyo 162-8601, Japan, e-mail:; Yoshimasa Nakamura, Graduate School of Informatics, Kyoto University, 36-1 Yoshida-Honmachi, Sakyo-ku, Kyoto 606-8501, Japan, e-mail:

PDF available at: