Paper Info
Title
Error analysis for matrix eigenvalue algorithm based on the discrete hungry Toda equation
Abstract
Based on the integrable discrete hungry Toda (dhToda) equation, the authors designed an algorithm for computing eigenvalues of a class of totally nonnegative matrices (Ann Mat Pura Appl, doi: 10.1007/s10231-011-0231-0 ). This is named the dhToda algorithm, and can be regarded as an extension of the well-known qd algorithm. The shifted dhToda algorithm has been also designed by introducing the origin shift in order to accelerate the convergence. In this paper, we first propose the differential form of the shifted dhToda algorithm, by referring to that of the qds (dqds) algorithm. The number of subtractions is then reduced and the effect of cancellation in floating point arithmetic is minimized. Next, from the viewpoint of mixed error analysis, we investigate numerical stability of the proposed algorithm in floating point arithmetic. Based on this result, we give a relative perturbation bound for eigenvalues computed by the new algorithm. Thus it is verified that the eigenvalues computed by the proposed algorithm have high relative accuracy. Numerical examples agree with our error analysis for the algorithm.
Year
DOI
Venue
2012
10.1007/s11075-012-9606-6
Numerical Algorithms
Keywords
Field
DocType
Shifted,LR,transformation,Discrete hungry Toda equation,Mixed stability,Relative perturbation,65F15,65F50,37K10
Convergence (routing),Mathematical optimization,Mathematical analysis,Matrix (mathematics),Floating point,Eigenvalue algorithm,Algorithm,Binary GCD algorithm,Eigenvalues and eigenvectors,Numerical stability,Cornacchia's algorithm,Mathematics
Journal
Volume
Issue
ISSN
61
2
1017-1398
Citations 
PageRank 
References 
1
0.51
1
Authors
5
Name
Order
Citations
PageRank
Fukuda Akiko111.19
Yusaku Yamamoto25220.61
Masashi Iwasaki3279.42
Emiko Ishiwata4349.71
Yoshimasa Nakamura54817.38