zbMATH — the first resource for mathematics

A new subtraction-free formula for lower bounds of the minimal singular value of an upper bidiagonal matrix. (English) Zbl 1329.65079
Traces of inverse powers of a matrix \(BB^T\) determine lower bounds of the smallest singular value of an upper bidiagonal matrix \(B\) with positive entries on both diagonals. Several approaches to the computation of these traces have been studied previously, including one subtraction-free formula. This paper derives another subtraction-free formula different from the previous one. An algorithm for its computation is presented. A comparison of computational costs shows that the evaluation of the new formula requires less operations than the previously proposed one. An efficient implementation of the algorithm for the special case of the second power is included. Numerical experiments conclude the paper.

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
15A18 Eigenvalues, singular values, and eigenvectors
15A42 Inequalities involving eigenvalues and eigenvectors
65F50 Computational methods for sparse matrices
Full Text: DOI arXiv
[1] Bai, Z; Fahey, M; Golub, GH, Some large-scale matrix computation problems, J. Comput. Appl. Math., 74, 71-89, (1996) · Zbl 0870.65035
[2] Bailey, DH, High-precision floating-point arithmetic in scientific computation, Comput. Sci. Eng., 7, 54-61, (2005)
[3] Brezinski, C; Fika, P; Mitrouli, M, Estimations of the trace of powers of positive self-adjoint operators by extrapolation of the moments, Electron. Trans. Numer. Anal., 39, 144-155, (2012) · Zbl 1287.65042
[4] Dekker, TJ, A floating-point technique for extending the available precision, Numer. Math., 18, 224-242, (1971) · Zbl 0226.65034
[5] Fernando, KV; Parlett, BN, Accurate singular values and differential qd algorithms, Numer. Math., 67, 191-229, (1994) · Zbl 0814.65036
[6] Golub, G.H., Meurant, M.: Matrices, Moments and Quadrature with Applications. Princeton University Press, Princeton and Oxford (2010) · Zbl 1217.65056
[7] Hong, YP; Pan, C-T, A lower bound for the smallest singular value, Linear Algebra Appl., 172, 27-32, (1992) · Zbl 0768.15012
[8] Iwasaki, M., Nakamura, Y.: Accurate computation of singular values in terms of shifted integrable schemes. Japan J. Indust. Appl. Math. 23, 239-259 (2006) · Zbl 1117.65055
[9] Johnson, C.R.: A Gersgorin-type lower bound for the smallest singular value. Linear Algebra Appl. 112, 1-7 (1989) · Zbl 0723.15013
[10] Johnson, CR; Szulc, T, Further lower bounds for the smallest singular value, Linear Algebra Appl., 272, 169-179, (1998) · Zbl 0891.15013
[11] Kimura, K., Yamashita, T., Nakamura, Y.: Conserved quantities of the discrete finite Toda equation and lower bounds of the minimal singular value of upper bidiagonal matrices. J. Phys. A: Math. Theor. 44(285207), 12 (2011) · Zbl 1223.37068
[12] Knuth, D.E.: The Art of Computer Programming: Seminumerical Algorithms, volume 2, Addison-Wesley, Reading, MA (1969) · Zbl 0191.18001
[13] Li, L, Lower bounds for the smallest singular value, Comput. Math. Appl., 41, 483-487, (2001) · Zbl 0986.15016
[14] Von Matt, U, The orthogonal qd-algorithm, SIAM J. Sci. Comput., 18, 1163-1186, (1997) · Zbl 0895.65014
[15] Nagata, M; Iwasaki, M; Nakamura, Y, Error analysis of the mdlvs algorithm for computing bidiagonal singular values, Numer. Algor., 61, 261-274, (2012) · Zbl 1259.65066
[16] Rojo, O, Further bounds for the smallest singular value and the spectral condition number, Comput. Math. Appl., 38, 215-228, (1999) · Zbl 0947.15012
[17] Wilkinson, J.H.: The Algebraic Eigenvalue Problem. Oxford University Press, Oxford (1965) · Zbl 0258.65037
[18] Yamashita, T; Kimura, K; Nakamura, Y, Subtraction-free recurrence relations for lower bounds of the minimal singular value of an upper bidiagona matrix, J. Math-for-Ind., 4, 55-71, (2012) · Zbl 1302.15012
[19] Yamashita, T., Kimura, K., Takata, M., Nakamura, Y.: An application of the Kato-Temple inequality on matrix eigenvalues to the dqds algorithm for singular values. JSIAM Letters 5, 21-24 (2013) · Zbl 1416.65099
[20] Yu, Y-S; Gu, D-H, A note on a lower bound for the smallest singular value, Linear Algebra Appl., 253, 25-38, (1997) · Zbl 0876.15015
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.