Search

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 − ε for arbitrary ε > 0. [ABSTRACT FROM AUTHOR]

The construction of totally nonnegative (TN) matrices with prescribed eigenvalues is an important topic in real-valued nonnegative inverse eigenvalue problems. TN matrices are square matrices whose minors are all nonnegative. Our previous paper (Numer. Algor. 70, 469-484, ??2015) presented a finite-step construction of TN matrices limited to upper or lower Hessenberg forms with prescribed eigenvalues, based on the discrete hungry Toda (dhToda) equation which is derived from the study of integrable systems. Building on our previous paper, we produce the construction of banded TN matrices with an arbitrary number of diagonals in both lower and upper triangular parts and prescribed eigenvalues, involving upper Hessenberg, lower Hessenberg, and dense TN matrices with prescribed eigenvalues. We first prepare an infinite sequence associated with distinct eigenvalues $\lambda _{1},\lambda _{2},\dots ,\lambda _{m}$ and two integers M and N which determine the upper and lower bandwidths of m-by- m banded matrices, respectively. Both M and N play a key role for achieving our purpose. The study follows similar lines to our previous paper, but is complicated by the introduction of N. We next consider extended Hankel determinants and extended Hadamard polynomials involving elements of the infinite sequence and then derive their relationships. These relationships help us understand banded TN matrices with eigenvalues $\lambda _{1},\lambda _{2},\dots ,\lambda _{m}$ from the viewpoint of an extension of the dhToda equation. Finally, we propose a finite-step procedure for constructing TN matrices with an arbitrary upper and lower bandwidths and prescribed eigenvalues and also give illustrative examples. [ABSTRACT FROM AUTHOR]

Matrices where all minors are nonnegative are said to be totally nonnegative (TN) matrices. In the case of banded TN matrices, which can be expressed by products of several bidiagonal TN matrices, Fukuda et al. (Annal. Mat. Pura Appl. 192, 423-445, ) discussed the eigenvalue problem from the viewpoint of the discrete hungry Toda (dhToda) equation. The dhToda equation is a discrete integrable system associated with box and ball systems. In this paper, we consider an inverse eigenvalue problem for such banded TN matrices by examining the properties of the dhToda equation. This problem is a real-valued nonnegative inverse eigenvalue problem. First, we show the determinant solution to the dhToda equation with suitable boundary conditions. Next, we clarify the relationship between the characteristic polynomials of the banded TN matrices and the determinant solution. Finally, taking this relationship into account, we design a finite-step procedure for constructing banded TN matrices with specified eigenvalues. We also present an example to demonstrate this procedure. [ABSTRACT FROM AUTHOR]

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:). 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. [ABSTRACT FROM AUTHOR]