Department of Applied Mathematics & Physics, Kyoto University
Technical Report 2008-010 (September 15, 2008)
On $O(N)$ formula for the diagonal elements of inverse powers of symmetric positive definite tridiagonal matrices
by Kinji Kimura, Takumi Yamashita and Yoshimasa Nakamura
On $N \times N~(N \geq 2)$ non-singular upper bidiagonal matrix $\bm{B}$ and its transpose $\bm{B}^{T}$,
matrix products $(\bm{B}^{T} \bm{B})$ and $(\bm{BB}^{T})$ are symmetric positive definite tridiagonal matrices.
Let $M$ denote an arbitrary positive integer.
We present a formula to compute diagonals of inverse powers of these matrix products such that $( (\bm{B}^{T} \bm{B})^{M} ) ^{-1}$ and $( (\bm{BB}^{T})^{M} ) ^{-1}$
in the form of recurrence relations and their initial values.
All diagonals of the inverse of $(\bm{B}^{T} \bm{B})^{M}$ or $(\bm{BB}^{T})^{M}$ are computed within $O(N)$ flops according to the presented formula.
Traces of the inverses of $(\bm{B}^{T} \bm{B})^{M}$ and $(\bm{BB}^{T})^{M}$ can be used to compute lower bounds of the minimal singular value of $\bm{B}$.