## JMI2012A-8 Subtraction-free recurrence relations for lower bounds of the minimal singular value of an upper bidiagonal matrix (pp.55-71)

Author(s)： Takumi Yamashita, Kinji Kimura and Yoshimasa Nakamura

J. Math-for-Ind. 4A (2012) 55-71.

Abstract
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 [4] that quantities $J_M(B) \equiv \operatorname{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 [4], simple recurrence relations for computing all the diagonals of $((B^T B)^M)^{-1}$ and $((BB^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 over the old ones in [4] 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.

Keyword(s).　 lower bound of the minimal singular value, subtraction-free recurrence relations