Department of Applied Mathematics & Physics, Kyoto University
Technical Report 2011-017 (December 09, 2011)
Subtraction-free recurrence relations for lower bounds of the minimal singular value of an upper bidiagonal matrix
by Takumi Yamashita, Kinji Kimura and Yoshimasa Nakamura
On an $N \times N$ upper bidiagonal matrix $B$, where all the diagonals and the upper subdiagonals are positive, and its transpose $B^{T}$, it is shown in the recent paper that quantities $J_{M} ( B ) \equiv \textrm{Tr} ( ( ( B^{T} B )^{M} )^{-1} )$ $( M = 1, 2, \dots )$ gives a sequence of lower bounds $\theta _{M} ( B )$ of the minimal singular value of $B$ through $\theta _{M} ( B ) \equiv ( J_{M} ( B ) )^{- 1 / ( 2M )}$. In the recent paper, simple recurrence relations for computing all the diagonals of $( ( B^{T} B )^{M} )^{-1}$ and $( ( B B^{T} )^{M} )^{-1}$ are also presented. The square of $\theta _{M} ( B )$ can be used as a shift of origin in numerical algorithms for computing all the singular values of $B$. In this paper, new recurrence relations which have advantages to the old ones are presented. The new recurrence relations consist of only addition, multiplication and division among positive quantities. Namely, they are subtraction-free. This property excludes any possibility of cancellation error in numerical computation of the traces $J_{M} ( B )$. Computational cost for the trace $J_{M} ( B )$ $( M = 1, 2, \dots )$ and efficient implementations for $J_{2} ( B )$ and $J_{3} ( B )$ are also discussed.