×
Aishima, Kensuke; Matsuo, Takayasu; Murota, Kazuo

Rigorous proof of cubic convergence for the dqds algorithm for singular values. (English) Zbl 1153.65041

Japan J. Ind. Appl. Math. 25, No. 1, 65-81 (2008).
The authors present the differential quotient difference with shifts (dqds) algorithm together with a mathematically rigorous proof for its asymptotic cubic convergence in the presence of the shift strategy proposed by K.V. Fernando and B.N. Parlett [Numer. Math. 67, No.2, 191–229 (1994; Zbl 0814.65036)]. They also propose a concrete procedure for the shift.
Reviewer: Constantin Popa (Constanţa)

Cited in 1 Review
Cited in 5 Documents

MSC:

65F25 Orthogonalization in numerical linear algebra

Keywords:

singular value; bidiagonal matrix; dqds algorithm; differential quotient difference with shifts algorithm; asymptotic cubic convergence

Citations:

Zbl 0814.65036

Software:

LAPACK
Cite Review PDF
Full Text: DOI

References:

[1] K. Aishima, T. Matsuo, K. Murota and M. Sugihara, On Convergence of the dqds Algorithm for Singular Value Computation. SIAM Journal on Matrix Analysis and Applications, to appear. · Zbl 1165.65018
[2] K. Aishima, T. Matsuo, K. Murota and M. Sugihara, A Shift Strategy for Superquadratic Convergence in the dqds Algorithm for Singular Values. Mathematical Engineering Technical Reports, METR 2007-12, University of Tokyo, March 2007. · Zbl 1294.65043
[3] E. Anderson, Z. Bai, C. Bischof, S. Blackford, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenny and D. Sorensen, LAPACK Users’ Guide, Third Edition. SIAM, 1999. · Zbl 0934.65030
[4] J. Demmel, Applied Numerical Linear Algebra. SIAM, Philadelphia, 1997.
[5] J. Demmel and W. Kahan, Accurate Singular Values of Bidiagonal Matrices. SIAM Journal on Scientific Computing,11 (1990), 873–912. · Zbl 0705.65027 · doi:10.1137/0911052
[6] I.S. Dhillon, A New O(n2) Algorithm for the Symmetric Tridiagonal Eigenvalue/Eigenvector Problem. Ph.D. Thesis, Computer Science Division, University of California, Berkeley, California, 1997.
[7] I.S. Dhillon and B.N. Parlett, Multiple Representations to Compute Orthogonal Eigenvectors of Symmetric Tridiagonal Matrices. Linear Algebra and Its Applications,387 (2004), 1–28. · Zbl 1055.65048 · doi:10.1016/j.laa.2003.12.028
[8] I.S. Dhillon and B.N. Parlett, Orthogonal Eigenvectors and Relative Gaps. SIAM Journal on Matrix Analysis and Applications,25 (2004), 858–899. · Zbl 1068.65046 · doi:10.1137/S0895479800370111
[9] K.V. Fernando and B.N. Parlett, Accurate Singular Values and Differential qd Algorithms. Numerische Mathematik,67 (1994), 191–229. · Zbl 0814.65036 · doi:10.1007/s002110050024
[10] P. Henrici, Applied and Computational Complex Analysis, Vol. 1. Wiley, New York, 1974. · Zbl 0313.30001
[11] LAPACK, http://www.netlib.org/lapack/. · Zbl 0755.65028
[12] B.N. Parlett, The New qd Algorithm. Acta Numerica, 1995, 459–491. · Zbl 0835.65059
[13] B.N. Parlett, The Symmetric Eigenvalue Problem. Prentice-Hall, Englewood Cliffs, New Jersey, 1980; SIAM, Philadelphia, 1998. · Zbl 0431.65017
[14] B.N. Parlett and O. Marques, An Implementation of the dqds Algorithm (Positive Case). Linear Algebra and Its Applications,309 (2000), 217–259. · Zbl 0952.65031 · doi:10.1016/S0024-3795(00)00010-0
[15] H. Rutishauser, Über eine kubisch konvergente Variante der LR-Transformation. Zeitschrift für Angewandte Mathematik und Mechanik,11 (1960), 49–54. · Zbl 0128.11701
[16] J.H. Wilkinson, The Algebraic Eigenvalue Problem. Clarendon Press, Oxford, 1965. · Zbl 0258.65037
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.