Convergence acceleration of shifted L R transformations for totally nonnegative Hessenberg matrices

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

Applications of Mathematics (2020)

  • Volume: 65, Issue: 5, page 677-702
  • ISSN: 0862-7940

Abstract

top
We design shifted L R transformations based on the integrable discrete hungry Toda equation to compute eigenvalues of totally nonnegative matrices of the banded Hessenberg form. The shifted L R 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 L R transformations by considering the concept of the Newton shift. We show that the shifted L R transformations with the resulting shift strategy converge with order 2 - ϵ for arbitrary ϵ > 0 .

How to cite

top

Fukuda, Akiko, et al. "Convergence acceleration of shifted $LR$ transformations for totally nonnegative Hessenberg matrices." Applications of Mathematics 65.5 (2020): 677-702. <http://eudml.org/doc/296992>.

@article{Fukuda2020,
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$.},
author = {Fukuda, Akiko, Yamamoto, Yusaku, Iwasaki, Masashi, Ishiwata, Emiko, Nakamura, Yoshimasa},
journal = {Applications of Mathematics},
keywords = {$LR$ transformation; totally nonnegative matrix; Newton shift; convergence rate},
language = {eng},
number = {5},
pages = {677-702},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Convergence acceleration of shifted $LR$ transformations for totally nonnegative Hessenberg matrices},
url = {http://eudml.org/doc/296992},
volume = {65},
year = {2020},
}

TY - JOUR
AU - Fukuda, Akiko
AU - Yamamoto, Yusaku
AU - Iwasaki, Masashi
AU - Ishiwata, Emiko
AU - Nakamura, Yoshimasa
TI - Convergence acceleration of shifted $LR$ transformations for totally nonnegative Hessenberg matrices
JO - Applications of Mathematics
PY - 2020
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 65
IS - 5
SP - 677
EP - 702
AB - 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$.
LA - eng
KW - $LR$ transformation; totally nonnegative matrix; Newton shift; convergence rate
UR - http://eudml.org/doc/296992
ER -

References

top
  1. Bauer, F. L., qd-method with Newton shift, Technical Report 56. Computer Science Department, Stanford University, Stanford (1967). (1967) 
  2. Fernando, K. V., Parlett, B. N., 10.1007/s002110050024, Numer. Math. 67 (1994), 191-229. (1994) Zbl0814.65036MR1262781DOI10.1007/s002110050024
  3. Fukuda, A., Ishiwata, E., Yamamoto, Y., Iwasaki, M., Nakamura, Y., 10.1007/s10231-011-0231-0, Ann. Mat. Pura Appl. 192 (2013), 423-445. (2013) Zbl1349.37064MR3061107DOI10.1007/s10231-011-0231-0
  4. Fukuda, A., Yamamoto, Y., Iwasaki, M., Ishiwata, E., Nakamura, Y., 10.1007/s11075-012-9606-6, Numer. Algorithms 61 (2012), 243-260. (2012) Zbl1257.65019MR2969294DOI10.1007/s11075-012-9606-6
  5. Fukuda, A., Yamamoto, Y., Iwasaki, M., Ishiwata, E., Nakamura, Y., 10.1007/s00605-012-0404-y, Monatsh. Math. 170 (2013), 11-26. (2013) Zbl1311.65036MR3032671DOI10.1007/s00605-012-0404-y
  6. Golub, G. H., Loan, C. F. Van, Matrix Computations, Johns Hopkins Studies in the Mathematical Sciences. The Johns Hopkins University Press, Baltimore (2013). (2013) Zbl1268.65037MR3024913
  7. Horn, R. A., Johnson, C. R., 10.1017/CBO9780511810817, Cambridge University Press, Cambridge (1985). (1985) Zbl0576.15001MR0832183DOI10.1017/CBO9780511810817
  8. Team, LAPACK, LAPACK: Linear Algebra PACKage, Available at http://www.netlib.org/lapack/. 
  9. Li, C.-K., Mathias, R., 10.1016/S0024-3795(01)00240-3, Linear Algebra Appl. 341 (2002), 35-44. (2002) Zbl0997.15014MR1873607DOI10.1016/S0024-3795(01)00240-3
  10. Parlett, B. N., 10.1017/S0962492900002580, Acta Numerica 4 (1995), 459-491. (1995) Zbl0835.65059MR1352476DOI10.1017/S0962492900002580
  11. Pinkus, A., 10.1017/CBO9780511691713, Cambridge Tracts in Mathematics 181. Cambridge University Press, Cambridge (2009). (2009) Zbl1185.15028MR2584277DOI10.1017/CBO9780511691713
  12. Reinsch, C., Bauer, F. L., 10.1007/BF02161847, Numer. Math. 11 (1968), 264-272. (1968) Zbl0164.45201MR1553960DOI10.1007/BF02161847
  13. Rutishauser, H., 10.1007/978-1-4612-3468-5, Birkhäuser, Boston (1990). (1990) Zbl0699.65002MR1102678DOI10.1007/978-1-4612-3468-5
  14. Sun, J.-Q., Hu, X.-B., Tam, H.-W., 10.1002/nla.754, Numer. Linear Algebra Appl. 18 (2011), 261-274. (2011) Zbl1249.65079MR2791246DOI10.1002/nla.754
  15. Tokihiro, T., Nagai, A., Satsuma, J., 10.1088/0266-5611/15/6/314, Inverse Probl. 15 (1999), 1639-1662. (1999) Zbl1138.37341MR1733220DOI10.1088/0266-5611/15/6/314

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.