An implementation of the dqds algorithm (positive case)

The dqds algorithm was introduced in 1994 to compute singular values of bid iagonal matrices to high relative accuracy but it may also be used to compu te eigenvalues of tridiagonal matrices. This paper discusses in detail the issues that have to be faced when the algorithm is to be realized on a comp uter: criteria for accepting a value, for splitting the matrix, and for cho osing a shift to reduce the number of iterations, as well as the relative a dvantages of using IEEE arithmetic when available. Ways to avoid unnecessar y over/underflows are described. In addition some new formulae are develope d to approximate the smallest eigenvalue from a twisted factorization of a matrix. The results of extensive testing are presented at the end. The list of contents is a valuable guide to the reader interested in specific featu res of the algorithm. (C) 2000 Elsevier Science Inc. All rights reserved.