×

zbMATH — the first resource for mathematics

An application of the Kato-temple inequality on matrix eigenvalues to the dqds algorithm for singular values. (English) Zbl 1416.65099
The differential quotient difference with shifts (dqds) algorithm can be used to compute the singular values of a matrix with a high relative accuracy (see [K. V. Fernando and B. N. Parlett, Numer. Math. 67, No. 2, 191–229 (1994; Zbl 0814.65036)]). This is important because the sizes of singular values of a matrix may range over many orders and so high absolute accuracy may give poor results for the smaller singular values. The algorithm described in the paper above involves shifts at each stage; the implementation DLASQ of dqds in LAPACK uses what is called the aggressive strategy to choose this shift. In the present paper the authors present an alternative strategy using eigenvalue estimates to choose the shifts to implement the dqds algorithm. They give details of computer experiments for \(n\times n\) matrices with \(n\) ranging from \(10^{4}\) to \(10^{6}\) and show that often, without loss in accuracy, an implementation of their shift strategy is faster than DLASQ with the aggressive strategy.

MSC:
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
15A18 Eigenvalues, singular values, and eigenvectors
65F30 Other matrix algorithms (MSC2010)
Software:
DLASQ; LAPACK
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] K. V. Fernando and B. N. Parlett, Accurate singular values and differential qd algorithms, Numer. Math., 67 (1994), 191-229.
[2] LAPACK, http://www.netlib.org/lapack/.
[3] B. N. Parlett and O. A. Marques, An implementation of the dqds algorithm (positive case), Linear Algebra Appl., 309 (2000), 217-259.
[4] U. von Matt, The orthogonal qd-algorithm, SIAM J. Sci. Comput., 18 (1997), 1163-1186.
[5] K. Kimura, T. Yamashita and Y. Nakamura, 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 (2011), 285207.
[6] T. Yamashita, K. Kimura and Y. Nakamura, Subtraction-free recurrence relations for lower bounds of the minimal singular value of an upper bidiagonal matrix, J. Math-for-Ind., 4 (2012), 55-71.
[7] F. Chatelin; with exercises by M. Ahuès and F. Chatelin, translated with additional material by W. Ledermann, Eigenvalues of Matrices, Wiley & Sons, Chichester, New York, 1993.
[8] B. N. Parlett, The Symmetric Eigenvalue Problem, Englewood Cliffs, Prentice-Hall, NJ, 1980.
[9] K. Kimura et al., Application of the Kato-Temple inequality for eigenvalues of symmetric matrices to numerical algorithms with shift for singular values, in: Proc. of ICKS 2008, S. Kurohashi et al. eds., pp. 113-118, the IEEE Computer Society, CA, 2008.
[10] M. Takata et al., An improved shift strategy for the modified discrete Lotka-Volterra with shift algorithm, in: Proc. of PDPTA 2011, H. R. Arabnia et al. eds., Vol. II, 2011, pp. 720-726. CSREA Press, Las Vegas, 2011.
[11] M. Iwasaki and Y. Nakamura, Accurate computation of singular values in terms of shifted integrable schemes, Jpn J. Indust. Appl. Math., 23 (2006), 239-259.
[12] S. Gerschgorin, Über die Abgrenzung der Eigenwerte einer Matrix, Izv. Akad. Nauk. USSR Otd. Fiz.-Mat. Nauk., 7 (1931), 749-754.
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.